Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, II тур регионального этапа

Үстел үстінде 100 және 101 тасы бар екі үйінді жатыр. Екі ойыншы кезектесіп жүре отырып, ойын ойнайды. Әр жүрісте бір үйіндіні таңдап алып, одан бірнеше (кем дегенде бір) тасты алып тастап, сол үйіндідегі қалған тастарды екі (бос емес) үйіндіге бөлуге рұқсат. Келесі жүрісті жасай алмайтын ойыншы жеңіледі. Дұрыс ойында кім жеңеді: жүрісті бірінші бастаған ойыншы ма, әлде оның қарсыласы ма? ( М. Туревский )

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

Ответ: Первый

Игрок А (тоесть игрок, который первый ходит) забирает один камень из 101 камней и разбивает его на кучки 99, 1

Оставшиеся кучки это 100, 99, 1. Заметим, что кучки над которыми можно делать операции только 99 и 100.

Рассмотрим случай, когда игрок В (игрок, который ходит второй) забирает камень из кучи 99. Тогда он заберет из кучки n камней и разделит оставшееся на кучки b и с. Игрок А заберет n+1 камней и так же разделит оставшееся на b и с. Таким образом, у игрока А всегда будет ход.

Рассмотрим случай, когда игрок В берет камень из кучи 100 хотябы два камня.

Тогда он поделит оставшиеся на b и с, а игрок А заберет n-1 камней и также поделит их на b и с.

Рассмотрим случай, коода игрок В берет 1 камень из кучки 100. Тогда он оставит кучки b+c=2k-1, и пусть у нас тут b - четное.

Тогда игрок А берет 1 камень и разбивает кучку на кучки b-1 и с. Получаем одинаковые кучки с;с и получаем такую же пару b-1;b которую мы только что разобрали, тоесть у игрока А всегда найдется ход.

Доказано