Олимпиадная задача о перестановках цепочки домино — теория алгоритмов, 8–10 класс

  Пусть обе цепочки лежат на столе горизонтально. Будем обозначать доминошку парой цифр  (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 такой цифры не содержит.   Теперь можно применить аналогичные рассуждения к кускам цепочек, начинающимся со второй доминошки. И т.д.

Ответ задачи отсутствует