Нижняя оценка числа способов

[2old]

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

Для начала сделаем все числа в состоящие из цифр $1,0$, так как-то привычнее. Расположим все цифры в ряд так, что любые два соседние числа отличаются на один символ. Произвольным образом разметим каждое число, к какому ящику оно относится.

Количество способов выбрать число из первого ящика $2^{n-1}$. Теперь смотрим, где оно стояло в ряду - на месте $i$, возможны три варианта:
1. числа на местах $i-1,i+1$ из второго ящика, тогда для этого числа как минимум два способа исправив один символ сделать его как число из второго ящика
2. одно из чисел на местах $i-1,i+1$ из второго ящика, тогда для этого числа есть как минимум один способ
3. Оба числа $i-1,i+1$ из первого ящика

На третьем случае я застрял...

[grizzly]

2old в сообщении #1029552 писал(а):

На третьем случае я застрял...

Соседей у Вас маловато. Обычно в таких случаях раскрашивают вершины $n$-мерного куба, каждое ребро которого соединяет вершины, отличающиеся на одну координату. Но это просто другой способ сформулировать задачу, а не решение.

-- 22.06.2015, 12:07 --

PS. Я видел эту задачу на форуме, но до полноценного решения там дело не дошло.

[grizzly]

2old
Вы собираетесь решать задачу? :)

В терминах раскраски гиперкуба она звучит даже интереснее. Примерно так: если вершины гиперкуба раскрашены поровну в два цвета, то найдётся гипергрань с равным количеством вершин каждого цвета.

UPD 26.07. Формулировка не только не равносильна, но и ошибочна (при $n=3$ можно покрасить контрпример).

Этого утверждения достаточно для применения индукции. Как по мне, такая формулировка красивее (даже если эта задача сложнее, в чём я сомневаюсь).

[TOTAL]

do i=1,n-1
Если два числа с (i-1)-ой звездочкой, различающиеся только i-ой цифрой, находятся в одном и том же ящике,
то одно число выкинем, а у оставшегося заменим i-ю цифру звездочкой.
enddo

Очевидно, числа с одинаковым количеством звездочек имеют соседей в другом ящике (во позиции сразу за звездочкой).

Ошибка. Не учтено, что может не найтись двух чисел с (i-1)-ой звездочкой, различающиеся только i-ой цифрой

[2old]

grizzly
Собираюсь, но я ничего не понимаю :(

[grizzly]

TOTAL
Я бы просил Вас прокомментировать на примере.
$n=3$. Ящик 1:
(0,0,0)
(1,0,0)
(0,1,0)
(0,0,1)
После работы цикла остаётся следующее:
(*,0,0)
(0,1,0)
(0,0,1)
Какой Вы делаете из этого вывод? Для последних двух троек мне понятно, почему в другом ящике есть сопряжённый. Из двух чисел, закодированных под звёздочкой в Ящике 2 сопряжённый, очевидно, имеется только для одного -- зато для него их (сопряжённых) там аж два. Ваше рассуждение об этом ничего не упоминает, а без этого вряд ли.

[TOTAL]

grizzly в сообщении #1030103 писал(а):

TOTAL
Я бы просил Вас прокомментировать на примере.

Комментирую: в том якобы решении была ошибка.

[grizzly]

Я выложил задачу на MSE и обсудил дополнительно с ТС (в ЛС). Задача, оказывается, была дана в книге Виленкина с соавторами "Комбинаторика" (задача 24 в главе 3, тема -- раскладка по ящикам с учётом порядка, я смотрел в издании 2006 г.).
На MSE пока было предложено решение из теории графов (я, увы, далёк от этого, но попытаюсь разбираться хотя бы на уровне проверки решения).

[grizzly]

В гиперкубических терминах задача звучит так: вершины $n$-мерного куба раскрашены в 2 цвета; доказать, что как минимум $2^{n-1}$ ребро соединяет вершины разных цветов.

С учётом результата этой задачи для $k=2^{n-1}$ решение получается совсем простым: максимальное число рёбер, соединяющих красные вершины, может быть $(n-1)2^{n-2}$; столько же для синих; следовательно, остальных будет не меньше чем $n2^{n-1}-2(n-1)2^{n-2}=2^{n-1}$. Ввиду тривиальности рассуждений, различающих эти задачи, их можно считать равносильными.

[2old]

Комбинаторно мне решить так и не удалось, но как мне кажется, решение из области теории графов есть проще. По индукции легко показать, что в $n$-мерном кубе есть гамильтонов цикл. Это же доказательство доставляет обход, в котором каждая вершина отличается на один бит. Ну и вроде все, просто красим вершины в два цвета поочередно.

-- 03.07.2015, 16:19 --

grizzly
Четность степень всех вершин это для эйлерова, для гамильтонова не нужно (и мы даже не обязаны по всем ребрам в нем пройти).

Для обычного куба последовательность в цикле такая:
$000 \to 010 \to 011 \to 001 \to 101 \to 111 \to 110 \to 100 \to 000$

Если кратко, то индукционный переход такой: построили гамильтонов путь в $n-1$ кубе, поднялись "на верх", там просто копия нижнего, но начнем теперь путь с конца, поэтому закончим над началом "нижнего" куба и спустим обратно.

Ну и теперь в нашем цикле красим вершины почерти в два цвета, т.е. кладем в два ящика. Достав любую вершину теперь точно знаем, что есть две отличающихся от нее на $1$ бит в другом ящике: шаг вперед и шаг назад по циклу.

Когда я отвечал сообщение еще было

[grizzly]

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

Вашу идею я не понял. Ведь вопрос в терминах графов стоит не в том, как раскрасить вершины гиперкуба, чтобы соседние были разных цветов, а наоборот -- все вершины уже раскрашены и нужно найти достаточно много разноцветных соседей.

-- 03.07.2015, 15:25 --

2old в сообщении #1033171 писал(а):

Когда я отвечал сообщение еще было

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

-- 03.07.2015, 15:27 --

2old в сообщении #1033171 писал(а):

Достав любую вершину теперь точно знаем, что есть две отличающихся от нее на $1$ бит в другом ящике

Выше в теме есть мой пример, когда в Ящике 1 есть вершина, у которой вообще нет соседей в другом ящике.

[2old]

grizzly
Да, я так долго думал, что забыл условие немного)))

[fractalon]

Цитата:

У меня появились сомнения насчёт существования сколько-то простого комбинаторного решения.

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

[grizzly]

fractalon в сообщении #1033432 писал(а):

А почему нельзя переформулировать гиперкубическое решение комбинаторно?

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

fractalon в сообщении #1033432 писал(а):

Но это, конечно, только переформулирование уже данного решения.

О каком решении Вы говорите? Если о том, что основано на результате другой задачи (которую я поместил в олимпиадный раздел), так ведь и решение той задачи пока не такое уж простое. Единственное известное мне решение -- в статье, на которую я сослался. Там была решена оригинальная задача -- в статье даже списка литературы (почти) нет. То решение я тоже не взялся бы оформить комбинаторно

[sup]

У задачи с карточками есть очень простое комбинаторное решение. Как это часто бывает, надо немного усилить утверждение, после чего оно доказывается по индукции.
Давайте введем некие обозначения. Вместо цифр 1,2 будем использовать стандартную двоичную систему.
Пусть $I_n$ - множество $n$-битных двоичных чисел. Пусть $U \subset I_n$ - некое подмножество. Как обычно $|U|$ - его мощность. Для двух множеств $U,V$ через $U \# V$ обозначим количество пар $(u,v)$, таких, что $u \in U, v \in V$ и битовые записи $u,v$ отличаются лишь в одном разряде. Отметим, что эта операция симметрична $U \# V = V\# U$. Тогда имеет место следующее неравенство

$$ U \# (I_n \setminus U) \geqslant \min ( |U|, |I_n \setminus U|) $$

В частном случае, когда $|U| = 2^{n-1}$, получаем исходное утверждение относительно карточек.
Доказывать будем индукцией по $n$. Для $n = 1,2$ проверка элементарна.
Рассмотрим общий случай.
Во всех элементах множества $U$ выделим последний разряд. Он равен либо 0 либо 1. А предыдущие $(n-1)$ разрядов образуют некий элемент множества $I_{n-1}$. Так вот. Легко видеть, что множество $I_{n-1}$ можно представить в виде объединения попарно не пересекающихся множеств $A,B, X, Y$

$$I_{n-1} = A \bigcup B \bigcup X \bigcup Y$$

таким образом, что
1. если $a \in A$ то $(a,0) \in U$ и $(a,1) \not \in U$
2. если $b \in B$ то $(b,1) \in U$ и $(b,0) \not \in U$
3. если $x \in X$ то $(x,0) \in U$ и $(x,1) \in U$
4. если $y \in Y$ то $(y,0) \not \in U$ и $(y,1) \not \in U$
Ну а теперь элементарно проверяется, что

$$ U \# (I_n \setminus U) = |A| + |B| + 2A \# B + A\#Y + B\#Y + A\#X + B\#X + 2X\#Y$$

Отсюда следует, что если в множестве $U$ элементы вида $(b,1)$ заменить на $(b,0)$, то величина $ U \# (I_n \setminus U)$ может лишь уменьшиться. Важно отметить, что такая замена возможна, поскольку это всего лишь обмен элементами из множеств $U$ и $ I_n \setminus U$. В связи с этим считаем, что $B = \varnothing$.
Но тогда

$$ U \# (I_n \setminus U) = |A| + X \# (A \bigcup Y) + Y\#(A \bigcup X)$$

Без потери общности можем считать, что $|U| \leqslant 2^{n-1}$, а значит $|X| \leqslant |Y|$. По построению $I_{n-1} = A \bigcup X \bigcup Y$. По индуктивному предположению получаем

$$ U \# (I_n \setminus U) \geqslant |A| + |X| + \min (|Y| , |A \bigcup X|) \geqslant |A| + 2|X| = |U|$$