Мистер Фокс и Мистер Форд играют в следующую игру. Сначала Мистер Фокс выбирает натуральное число К большее 600 , но меньшее 700 . Затем Мистер Фокс выписывает на доску какой-то делитель числа К , после чего Мистер Форд выписывает на доску еще один делитель числа К , и так далее. Выписанные на доске числа не могут повторяться, проигрывает тот, кто не может выписать очередное число. Какое наибольшее число К может выписать Мистер Фокс, чтобы обязательно выиграть в эту игру.
More Questions From This User See All
Answers & Comments
Verified answer
Т.к. первый ход у Фокса, а числа на доске не могут повторяться, то Фокс победит, если число делителей числа нечетно.
Лемма: натуральное число имеет нечетное число делителей тогда и только тогда, когда это число полный квадрат.
Док-во: =>) Пусть а не является полным квадратом. Пусть b - делитель a => существует единственное c такое, что a=bc. При этом с≠b (иначе a - полный квадрат). А значит для любого делителя числа a найдется парный ему делитель => число делителей числа a четно.
<=) Если a - полный квадрат, то существует единственное c такое, что a=c*с. Для любого же другого делителя b числа a найдется парный ему и не равный делитель (иначе получим a=c*c=b*b=>a=b - противоречие). А значит число делителей нечетно.
Доказано.
Значит задача сводится к нахождению максимального полного квадрата на промежутке (600; 700).
700<729=27*27
Значит имеет смысл проверить 26: 26*26=676 - подходит.
Ответ: 676