|
|
 |
Условие
С цепочкой камней домино, сложенной по обычным правилам, разрешается проделывать такую операцию: выбирается кусок из нескольких подряд доминошек с одинаковыми очками на концах куска, переворачивается целиком и вставляется на то же место. Докажите, что если у двух цепочек, сложенных из двух одинаковых комплектов домино, значения очков на концах совпадают, то разрешёнными операциями можно сделать порядок следования доминошек во второй цепочке таким же, как в первой.
Решение
Пусть обе цепочки лежат на столе горизонтально. Будем обозначать доминошку парой цифр (a, b), где a и b – количества очков на половинках.
Если из цепочки A можно получить цепочку B, то и из цепочки B можно получить цепочку A. Поэтому достаточно доказать, что, применяя разрешённые операции к обеим цепочкам, можно получить из них две одинаковые цепочки.
Пусть в начале первой цепочки стоит доминошка (a, x), а в начале второй – (a, y). Докажем, что разрешёнными операциями можно из этих цепочек получить цепочки с одинаковой первой доминошкой.
Первый способ. Если x = y, то это уже сделано. Нетрудно это сделать также, если цепочки содержат доминошку (a, a) – она переносится в начало. Пусть это не так. Рассмотрим все доминошки, на которых есть a (а-доминошки), и назовём такую доминошку плохой, если она лежит цифрой a к началу, и хорошей в противном случае.
Пусть в первой цепочке m хороших доминошек. Так как внутри цепочки после каждой хорошей доминошки лежит плохая, то всего в ней 2m + 1 или 2m а-доминошек (последнее происходит, когда последняя в цепочке доминошка хорошая). Поскольку концы цепочек совпадают, то вторая цепочка содержит столько же плохих и и столько же хороших доминошек, сколько и первая. Если среди 2m хороших доминошек обеих цепочек есть одинаковые, то переворачивая куски от начала до этих доминошек, мы помещаем их в начало.
Если же все хорошие доминошки различны, то среди них есть все, кроме, может быть, одного, типы a-доминошек. Значит, среди них есть либо (x, a) (во второй цепочке), либо (y, a) – в первой. В первом случае, переставляем (x, a) в начало второй цепочки, после чего её начало совпадёт с началом первой. Аналогично поступим во втором случае.
Второй способ. Пусть первая цепочка имеет вид (a, x) A (a, y) B, вторая – вид (a, y) C (a, x) D (буквы A, ..., D обозначают куски цепочек, a, x, y – разные цифры).
Если нам удастся перевернуть доминошку (a, y) в первой цепочке, то потом мы сможем её поместить в начало.
Предположим, что её перевернуть нельзя. Тогда участки A-a и y-B не содержат одинаковых цифр (наличие таких цифр означает существование куска с одинаковыми цифрами на концах, содержащего доминошку (a, y)).
Первая доминошка участка C содержит y. Кусок A не содержит этой цифры, поэтому "копия" этой доминошки входит в B. По той же причине в B входит и "копия" второй доминошки из С. Так последовательно мы дойдём до последней доминошки из C и придём к противоречию: она содержит цифру a, а B такой цифры не содержит.
Теперь можно применить аналогичные рассуждения к кускам цепочек, начинающимся со второй доминошки. И т.д.
Замечания
8 баллов
