Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  11
2 года 4 месяца назад #

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

Понятно что красная кучка будет разделятся синюю и зеленую; синяя кучка будет разделятся на зеленую и красную; зеленая кучка будет разделятся на красную и синюю т.к. 2k1,2(mod3).

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