Комбинаторика на Всесибе: игры, графы, конструктивы

Для каждой кучки назовём её показателем максимальную степень двойки, на которую делится число содержащихся в ней камней, она может быть равна . Рассмотрим поведение показателей кучек, участвующих в перекладывании. После перекладывания камней из кучки с камнями в кучку с камнями в первой остаётся камней, а во второй становится камней. Если , то

поэтому оба показателя возрастут. Если , то

где . При этом минимальный в данной паре кучек показатель сохраняется, а второй гарантированно становится больше минимального. Заметим, что количество кучек с минимальным среди всех показателем при произвольном перекладывании либо уменьшается на 2, либо не меняется.

Рассмотрим произвольную раскладку камней по более, чем одной кучке. В ней число кучек с минимальным показателем будет чётным. Действительно, общее число камней и сумма количеств камней в не минимальных кучках делятся на поэтому сумма количеств камней в минимальных кучках тоже делится на , значит, их количество делится на 2. Если в раскладке есть хотя бы две кучки, разбиваем все кучки с минимальным показателем на пары, выполняем в каждой перекладывание из большей в меньшую и получаем раскладку с большим минимальным показателем, чем рассматриваемая. Проделав эту процедуру не более, чем раз, получим раскладку с минимальным показателем , то есть с единственной кучкой из камней.

Пусть теперь не является степенью двойки. Рассмотрим любой процесс сборки некоторой раскладки N камней по кучкам в одну и произведём его в обратном порядке, посредством процедур перекладывания, обратных к исходным, когда половина одной из кучек перекладывается в другую. При этом в обратном процессе количество камней в первой кучке (она же последняя в исходном процессе сборки) и всех получающихся на каждом шаге будет делиться на нечётное число . Следовательно, любая раскладка, в которой есть кучка из числа камней, не делящегося на , не может быть собрана в одной кучке. В частности, не может быть собрана в одну раскладка по двум кучкам.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. В случае можно предложить другое решение того, что раскладка по двум кучкам не может быть собрана в одну. Этого достаточно для доказательства необходимости в условии задачи, то есть того, что любая начальная раскладка N камней по кучкам может быть собрана в одной куче только тогда, когда N является степенью двойки.

Докажем по индукции, что после перекладываний количества камней в кучках имеют вид

для некоторого целого числа .

База индукции при очевидна:

то есть .

Шаг индукции: либо мы перекладываем камни из правой кучки в левую, тогда в левой станет , а в правой останется камней, при этом , либо мы перекладываем камни из левой кучки в правую, тогда в левой останется , а в правой станет камней, при этом .

Если после некоторого -ого перекладывания раскладки останется всего одна кучка, то число камней в другой станет равным 0 , следовательно, выполнится равенство одно из равенств или . В обоих случаях N будет делителем числа , то есть тоже степенью двойки противоречие с тем, что в рассматриваемом случае . Следовательно, при любом N , отличном от степени двойки, раскладка не может быть собрана в одну кучку.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Объединяя оба случая и , получаем доказательство более общего утверждения: раскладка N камней может быть собрана в одной кучке тогда и только тогда, когда количество камней в каждой её кучке делится на набольший нечётный делитель N .