Математикадан Эйлер олимпиадасы, 2009-2010 оқу жылы, Дистанциялық кезеңнің 1-ші туры

Әрқайсысы 2 тастан тұратын 2009 үйме берілген. Құрамындағы тастар саны жұп болатын үйменің (ондай үймелер бірнеше болса кез келгенін) жартысын басқа кез келген үймеге салуға болады. Осындай операциялар арқылы бір үймеде көп дегенде қанша тас алуға болады?

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

Комментарии от администратора Комментарии от администратора №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)$.