|
|
 |
Условие
На столе лежит куча из более чем n² камней. Петя и Вася по очереди берут камни из кучи, первым берёт Петя. За один ход можно брать любое простое число камней, меньшее n, либо любое кратное n число камней, либо один камень. Докажите, что Петя может действовать так, чтобы взять последний камень независимо от действий Васи.
Решение
Предположим противное: у Васи есть стратегия, поволяющая ему гарантированно взять последний камень. Пусть d – изначальное количество камней, а r – остаток от деления d на n. (r ≠ 0, иначе Петя может сразу взять все камни).
Петя после первого своего хода может, взяв кратное n количество камней, оставить любое количество вида ak = r + nk, где 0 ≤ k ≤ n – 1 (все эти количества меньше n²). Пусть ck – ответный ход в Васиной стратегии при ak камнях в куче. Тогда ck не делится на n, иначе после его хода остаётся камней, и Петя может выиграть, действуя по Васиной стратегии для этого числа. Значит, все числа ck меньше n, а тогда два из этих чисел совпадают. Пусть ck = cl (0 ≤ k < l ≤ n – 1).
Напомним, что у Васи есть стратегия выигрыша в ситуации, когда в куче ak – ck камней и ход Пети.
Пусть теперь Петя первым ходом оставит al камней; Вася в ответ возьмёт cl камней. Теперь Петя может взять n(l – k) камней, оставляя ak – ck, и дальше действовать по вышеупомянутой Васиной стратегии. Таким образом, он выиграет. Противоречие.
