Question

5. В n-мерном кубе покрашено более половины вершин. Ре- бро называется покрашенным, если покрашены обе ограни- чивающие его вершины. Докажите, что покрашено не менее n рёбер.

Answer 1

В n-мерном кубе имеется 2^n вершин. Если более половины вершин покрашены, то покрашено более 2^(n-1) вершин. Каждая вершина соединена с n другими вершинами ребрами. Следовательно, каждая покрашенная вершина соединена с n другими вершинами ребрами. Таким образом, общее количество ребер, соединенных с покрашенными вершинами, равно n * 2^(n-1). Однако каждое ребро соединяет две вершины, поэтому каждое ребро учитывается дважды. Следовательно, общее количество покрашенных ребер равно (n * 2^(n-1)) / 2 = n * 2^(n-2), что больше или равно n для любого n >= 1. Таким образом, если в n-мерном кубе покрашено более половины вершин, то покрашено не менее n ребер.