Олимпиада Туймаада по математике. Младшая лига. 2021 год


Есть куча из $2021^{2021}$ камней. За один ход можно разбить любую кучу на две части, количества камней в которых отличаются на степень двойки с целым неотрицательным показателем. После нескольких ходов оказалось, что количество камней в каждой кучке — степень двойки с целым неотрицательным показателем. Докажите, что было сделано четное число ходов. ( М. Антипов )
посмотреть в олимпиаде

Комментарий/решение:

  0
2022-10-01 20:31:44.0 #

Будем называть кучку красной, если кол-во камней в этой кучке дает остаток 0 при делении на 3; синей если дает остаток 1; зеленой если дает остаток 2

Понятно что красная кучка будет разделятся синюю и зеленую; синяя кучка будет разделятся на зеленую и красную; зеленая кучка будет разделятся на красную и синюю т.к. $2^k\equiv 1,2 (mod 3)$.

Заметим, что каждый раз количество красных кучек меняется на 1. В начале их было 0, а также в конце их кол-во 0. Значит было сделано четное кол-во ходов