ВсОШ 2023, 11 класс, задача 4
( баллов) На доску записывают пары чисел. Сначала на доску записали пару чисел . Если на доске написана пара чисел , то на доску можно дописать пару , а также пару . Кроме того, если на доске написаны пары чисел и , то на доску можно дописать пару . Могла ли через некоторое время на доске оказаться пара ? Порядок чисел в паре существенен, например, пары чисел и считаются различными.
(И. Почепцов)
Ответ
Ответ. Не могла.
Первое решение. Докажем, что для любой пары , записанной на доске, число делится на .
Действительно, для пары число делится на .
Пусть для пары число делится на . Тогда для пары число делится на , и для пары число делится на .
Пусть для пар , числа , делятся на . Тогда для пары число делится на .
Так как для пары число не делится на , эта пара на доске появиться не может.
Второе решение. Будем к каждой паре на доске дописывать третье число . Тогда сумма чисел в каждой тройке будет равна нулю, а правила дописывания новых пар будут такими: если на доске записана тройка , то можно дописать тройки и , а если записаны тройки и , то можно дописать тройку — назовём эту тройку суммой троек и . Также для тройки и целого числа обозначим через тройку .
Докажем, что все тройки, появляющиеся на доске, имеют вид
с целыми , и . В начальный момент времени это верно: . Теперь достаточно показать, что из троек, имеющих вид , также получаются лишь такие тройки. Для операции взятия суммы троек это очевидно. Для остальных операций это тоже несложно проверить: если имеет вид , то
Утверждение доказано.
Предположим теперь, что на доске появилась тройка , то есть она имеет вид . Тогда имеем
Выражая из первого равенства и подставляя во второе, получаем , то есть . Однако это невозможно, поскольку не делится на .
Замечание. Можно показать, что указанными операциями получаются все тройки, имеющие вид . Также можно заметить, что , так что в формуле можно обойтись без третьего слагаемого.
Аналогичное решение можно получить и без дописывания третьего числа к паре (однако оно будет выглядеть менее естественно). Именно, можно доказать, что все пары, появляющиеся на доске в исходном процессе, имеют вид
с целыми и . Заметим здесь, что если пара имеет вид , то
Верный ответ без обоснования.
Сформулировано утверждение о том, что все получающиеся пары имеют вид .
Это утверждение доказано.
Участник перешёл от пар чисел к тройкам (как во втором решении).
После этого замечено, что все тройки представляются в виде .
После перехода от пар к тройкам утверждение о представимости в виде принимается без доказательства.