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

Предыдущий
вопрос Следующий
вопрос

Для начала заметим, что количество вершин в n-мерном кубе равно 2^n. Поскольку более половины вершин покрашены, то количество покрашенных вершин хотя бы 2^{n-1} + 1.

Теперь рассмотрим одно из рёбер куба. Так как каждая вершина подсоединена к ровно n рёбрам, то количество покрашенных рёбер, выходящих из одной покрашенной вершины, равно n.

Таким образом, общее число рёбер, ведущих из всех покрашенных вершин, не меньше, чем количество покрашенных вершин, умноженное на n, то есть n(2^{n-1} + 1) = n2^{n-1} + n. Так как 2^{n-1} > n (для всех n>1), то n*2^{n-1} + n > n, то есть количество покрашенных рёбер не меньше n.