На доске написаны числа от 1 до 30. Вася и Джон ходят по очереди, начинает Вася. За один ход нужно заменить два числа на их произведение. Если одно из двух оставшихся на доске чисел делится на другое, то выигрывает Джон, иначе — Вася. Кто из них может выиграть?

Ответ:

Спочатку розглянемо випадок, коли Вася починає гру. Він може замінити на першому ході будь-які два числа, скажімо 1 та 2, і отримати на їх місці число 2. Наступний гравець (Джон) може замінити будь-які два числа, але не може замінити 2, оскільки 2 є простим числом і не міститься у таблиці множення.

Тому, якщо Джон замінює будь-які два числа, то Вася може замінити інші два числа так, щоб одне з них містило 2, а інше - ні. Наприклад, якщо Джон замінює 3 та 4 на 12, то Вася може замінити 2 та 5 на 10, і тоді залишається числа 6, 8, 10, 12, 15, 20 і 30. Жодне з цих чисел не містить 2 як множник, тому Вася перемагає.

Тепер розглянемо випадок, коли Джон починає гру. Якщо Джон замінює будь-які два числа, то Вася може замінити інші два числа так, щоб одне з них було дільником іншого. Наприклад, якщо Джон замінює 1 та 2 на 2, то Вася може замінити 3 та 5 на 15, і тоді залишається числа 4, 6, 8, 10, 12, 20 і 30. Число 4 є дільником 8, тому Вася програє.

Отже, якщо Вася починає гру, він перемагає, а якщо Джон починає гру, він перемагає.