Олимпиадная задача о натуральных числах 25 и 36 — теория алгоритмов
На доске написаны числа 25 и 36. За ход разрешается дописать еще одно натуральное число - разность любых двух имеющихся на доске чисел, если она еще не встречалась. Проигрывает тот, кто не может сделать ход.
Разобрать решение
В процессе игры (сравните с алгоритмом Евклида) обязательно будет выписан наибольший общий делитель исходных чисел. Следовательно, будут выписаны и все числа, кратные ему, не превосходящие большего из исходных чисел. В нашем случае НОД равен 1. Поэтому будут выписаны все числа от 1 до 36. Таким образом игра будет продолжаться 34 хода (два числа были написаны сначала), и выигрывает второй игрок.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.