Олимпиада имени Леонарда Эйлера2009-2010 учебный год, I тур дистанционного этапа

Имеется 2009 кучек, по 2 камня в каждой. Разрешается взять самую большую кучку из тех, в которых количество камней чётно (если таких несколько, то любую из них), и ровно половину камней из неё переложить в любую другую кучку. Какое наибольшее число камней в одной кучке можно получить такими операциями?

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. 2010.
Решение. Описанные в условии операции не уменьшают числа кучек, поэтому в каждой из них в каждый момент есть хотя бы один камень. Следовательно, накопить в одной кучке более, чем $2009 \cdot 2 - 2008 = 2010$ камней, невозможно.
Покажем, как получить кучку из 2010 камней. Возьмём пять кучек из двух камней и проведём такие преобразования: $(2,2,2,2,2) \to (3,1,2,2,2) \to (3,1,3,1,2) \to (3,1,4,1,1) \to (5,1,2,1,1)$. Три кучки по одному камню отложим, заменим их тремя кучками по два камня и проделаем такие преобразования: $(5,2,2,2,2) \to (5,1,3,2,2) \to (5,1,4,1,2) \to (7,1,2,1,2)$. Теперь отложим две кучи по одному камню, заменим их двумя кучами по два камня и аналогично получим $(9,1,2,1,2)$. Когда в большой куче накопится 2007 камней, останется ещё три кучи по 2 камня и 2005 куч по одному камню. Дальше действуем так: $(2007,2,2,2) \to (2007,1,3,2) \to (2007,1,4,1) \to (2009,1,2,1) \to (2010,1,1,1)$.