Решение задачи 371

Условие:

На каждой половинке кости домино указано число очков – от 0 до некоторого N, большего 1. Все возможные пары чисел встречаются по одному разу (включая «дубли» – пары одинаковых чисел). Все кости домино выложены в цепочку, причем на прилегающих половинках соседних костей стоят одинаковые числа. Могут ли на концах цепочки стоять различные числа?

Решение:

Предположим, что такое возможно. Доминошки выложены горизонтально -- слева направо в одну цепочку. Без ограничения общности будем считать, что левое число на самой левой доминошке это 0, а правое число на самой правой доминошке -- 1. Заметим, что все числа от 2 до N встречаются на всех доминошках четное число раз, поскольку произвольное число a граничит с таким же числом a на соседней доминошке. Также понятно, что если не учитывать крайнее левое и крайнее правое число, то 0 и 1 встретятся тоже четное число раз по той же причине.

Таким образом 0 и 1 встретятся нечётное число раз, а все остальные числа -- четное. Такого не может быть, потому что любые два числа встречаются одинаковое число раз, а именно -- (N+2).

Ответ: нет.