Question

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

Answer 1

Ответ:

Предположим, что в n-мерном кубе покрашено более половины вершин. Нам нужно доказать, что покрашено не менее n рёбер.

В n-мерном кубе есть 2^n вершин, так как каждая вершина имеет n координат, и каждая координата может быть 0 или 1. Если более половины вершин покрашено, то как минимум 2^n / 2 = 2^(n-1) вершин покрашено.

Рассмотрим n-мерное ребро куба. Оно соединяет две вершины, и для каждой вершины существует n-1 другая вершина, соединенная с ней этим ребром. Поскольку более половины вершин покрашены, то среди этих вершин есть хотя бы 2^(n-1) покрашенных. Это означает, что как минимум 2^(n-1) вершин имеют общее ребро с рассматриваемым ребром.

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

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

Таким образом, доказано, что в n-мерном кубе, где покрашено более половины вершин, покрашено не менее n рёбер.

Пошаговое объяснение:

Сделайте ответ лучше?

Answer 2

Давайте рассмотрим n-мерный куб и предположим, что более половины его вершин окрашены. Пусть количество вершин в кубе равно 2^n (поскольку каждая вершина имеет две возможные состояния - покрашена или нет), и более половины из них окрашены. То есть, если мы обозначим количество окрашенных вершин как k, то k > 2^n / 2 = 2^(n-1).

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

Для каждой вершины есть 2^n-1 других вершин, с которыми она образует рёбра. Поскольку k > 2^(n-1), то существует более 2^(n-1) окрашенных вершин. Значит, каждая из них соединена рёбрами с более, чем половиной вершин, иначе бы не соблюдалось условие k > 2^(n-1).

Таким образом, если мы рассмотрим все эти вершины и подсчитаем рёбра, исходящие из них, то каждая из них будет вносить в этот подсчёт более половины рёбер. И поскольку у нас есть более 2^(n-1) таких вершин, то общее количество окрашенных рёбер будет не менее:

2^(n-1) * (половина рёбер) = 2^(n-1) * (2^n) = 2^(n-1 + n) = 2^(2n-1)

Таким образом, мы доказали, что в n-мерном кубе, в котором покрашено более половины вершин, окрашено не менее n рёбер.