Комбинаторная задачка

[arseniiv]

Whitaker в сообщении #492573 писал(а):

А как же число AO, BO, A1 и B1.

Для индукции не нужно их рассматривать, т. к. числа такого вида войдут в рассматриваемые, можно сказать, автоматически.

Whitaker в сообщении #492573 писал(а):

P.S. И как с помощью него задача решается?

Выберите какую-нибудь вершину из примера с квадратом; перейдите по любому ребру в другую. Одна цифра изменилась, другая (при бо́льших $n$ другие) осталась как была! А про гиперграни я наплёл зря, наверно.

[Whitaker]

Почему автоматически?

[arseniiv]

Если мы добавляем новые цифры слева, то самые правые были учтены на первом шаге.

[Whitaker]

Мне здесь рассказали идею задачи.
Нужно представить себе $n$-мерный куб и раскрасить одну половину в красный цвет, а другую в синий цвет. И задача будет эквивалентно такой доказать, что число ребер соединяющих вершины разных цветов не менее $2^{n-1}$.

[ИСН]

Ровно это мы все и твердим уже вторую страницу.

[Whitaker]

Извините ИСН не догадался

[PAV]

Я все-таки что-то не могу сообразить, как решить задачу. Мне кажется, что индукция здесь не подходит. Ведь если мы разобьем все вершины куба на две группы вида $0\ldots$ и $1\ldots$, то в этих группах вершины могут уже быть раскрашены не поровну, как во всем кубе, поэтому непонятно, как к ним применить утверждение индукции.

Мне кажется, что должно быть какое-то несложное комбинаторное рассуждение, но я что-то не могу сообразить.

[Whitaker]

Я тоже думаю, что наверняка есть какое-то комбинаторное решение.