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

[Whitaker]

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

С уважением, Whitaker.

[ИСН]

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

[Whitaker]

А есть ли менее простой способ?

[VAL]

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

А есть ли менее простой способ?

А зачем Вам менее простой, если не секрет?!

[Whitaker]

Наверняка есть другой способ решения данной задачи.
Вряд ли смогу представить себе n-мерный куб.

[arseniiv]

Может помочь, что его гиперграни — $(n-1)$-мерные кубы.

[Whitaker]

Ну вот допустим, что у нас есть $n$-мерный куб. И какая связь есть с нашим кубом и задачкей?
Честно говоря, даже не догадываюсь как ее решать с помощью куба.

[arseniiv]

Вот $n=2$:

\definecolor{qqzzqq}{rgb}{0,0.6,0} \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(3.63,5.56) rectangle (6.9,8.79); \draw (4,8)-- (4,6); \draw (4,6)-- (6,6); \draw (6,6)-- (6,8); \draw (6,8)-- (4,8); \fill [color=qqzzqq] (4,8) circle (1.5pt); \draw[color=qqzzqq] (4.25,8.2) node {21}; \fill [color=qqzzqq] (4,6) circle (1.5pt); \draw[color=qqzzqq] (4.25,6.2) node {11}; \fill [color=qqzzqq] (6,6) circle (1.5pt); \draw[color=qqzzqq] (6.25,6.2) node {12}; \fill [color=qqzzqq] (6,8) circle (1.5pt); \draw[color=qqzzqq] (6.25,8.2) node {22}; \end{tikzpicture}

[Whitaker]

А числа можно ставить в любом порядке?

[MrDindows]

Если сторона куба равняется еденице, то числа - координаты вершин)

[arseniiv]

Лучше по координатам. Т. е. представьте, что эти $n$-мерные кубы имеют одну вершину $(1, \ldots, 1)$, другую $(2, \ldots, 2)$, а остальные расположены вполне естественным образом. Тогда каждая грань соединяет вершины, которые… И тогда каждая гипергрань, т. е. грань размерности на одну меньшей, чем куб, соединяет вершины, которые…

MrDindows уже опередил.

[Shadow]

Можно по индукции, но мало що там связано с комбинаторикой.
Для $n=1$ твердение безусловно верно.
Достаточно доказать, что при увеличении разряда, любое отображение дублируется. Пусть к-разрядное число A отображется в B. При увеличение разрядя имеем 4 числа 0A,0B,1A,1B. И при любой расстановке в 2 группы получатся хотя бы 2 отображения. Даже если 3 из них в одной группе:
0A 0B
1A
1B

В данном случае
0A-0B и 1B-0B

[Whitaker]

Если честно я не так уж "знаком" c n-мерными кубами
Можно об этом где нибудь подробнее почитать?
P.S. И как с помощью него задача решается?

-- Пт окт 14, 2011 20:24:22 --

Shadow в сообщении #492572 писал(а):

Можно по индукции, но мало що там связано с комбинаторикой.
Для $n=1$ твердение безусловно верно.
Достаточно доказать, что при увеличении разряда, любое отображение дублируется. Пусть к-разрядное число A отображется в B. При увеличение разрядя имеем 4 числа 0A,0B,1A,1B. И при любой расстановке в 2 группы получатся хотя бы 2 отображения. Даже если 3 из них в одной группе:
0A 0B
1A
1B

В данном случае
0A-0B и 1B-0B

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

-- Пт окт 14, 2011 20:26:12 --

Shadow
Что вы имеет в виду под "отображением"?

[Shadow]

Цитата:

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

Там 4 числа. В смысле, все в одной группе или как

[Whitaker]

Вы пишите следующее: "Пусть $k$-разрядное число $A$ отображается в $B$"
число $B$ - $(k+1)$-разрядное?
ведь тогда $B =\{OA, A0, 1A, A1\}$