Очевидное свойство n-мерного куба

[grizzly]

Пусть $Q^n$ -- $n$-мерный куб с $2^n$ вершинами и $n2^{n-1}$ рёбрами. Пусть $M$ -- подмножество вершин этого куба и $|M|=2^k, 1\le k<n$. Интересует вопрос о максимально возможном количестве рёбер оригинального куба, соединяющих вершины множества $M$. Доказать, что этот максимум достигается в тех и только в тех случаях, когда $M$ является $k$-мерной гипергранью куба.

Утверждение выглядит настолько очевидным, что хочется верить в существование несложного доказательства.
Задача навеяна этой темой. В частном случае ($k=n-1$) результат данной задачи тривиальным образом влечёт необходимое в той.

[grizzly]

Не особо продвинувшись в решении и этой задачи, я предпринял попытки поиска известных решений (оказалось, правда, что часть пути я и сам прошёл в нужном направлении). Найти было несложно, сложнее догадаться, как искать. Поэтому поделюсь здесь этим опытом -- может, кому-то из начинающих будет полезно.

Я взял для наглядности 3d-проекцию 4d-куба и, добавляя в неё мысленно вершины, нашёл (эмпирически) максимальное количество рёбер для каждого набора. Получилась такая последовательность:
0, 1, 2, 4, 5, 7, 9, 12, 13, 15, ...
Нашёл её у Слоана -- A000788; оттуда по спискам литературы и далее -- приходим к каким-то первым работам, в которых, как правило, рассматриваются ещё приземлённые вопросы, а не фрактально-мерные обобщения.

Пару слов о работах и результатах. Всё это, конечно, не какие-то архисложные вещи (кстати, интересные), но у меня совсем не сложилось впечатления, что их должно быть легко переформулировать в терминах комбинаторики, понятной продвинутому школьнику.

В следующем сообщении приведу здесь своё простое рассуждение, решающее ту задачу из ПРР, с которой началась эта тема -- чтобы подтвердить прямую связь между этими вопросами.

[grizzly]

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

Теперь вот что получается. Если задача из ПРР действительно имеет простое комбинаторное решение типа развешивания различающихся флажков по мачтам (тема параграфа в книге Виленкина), то оно может быть вполне доступно продвинутому школьнику, имеющему опыт решения подобных задач (но я сам ещё не решил). Не будут ли тогда относительно просто решаться и задачи с рёбрами на пространственных решётках, раз они до эквивалентности похожи? Например, есть ещё подобная задача (см. A007818), которая пока не решена.