Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) 1 камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней, такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (10, 6), (20, 10) и (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 223. В начальный момент в первой куче было 17 камней, во второй куче – S камней, 1 ≤ S ≤ 205.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. При каком минимальном значении S такое возможно?

Задание 20.

Известно, что Петя имеет выигрышную стратегию. Укажите два значения при которых:

·        Петя не может победить первым ходом

·        при любом ходе Вани Петя побеждает своим вторым ходом

Задание 21.

Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.

Код программы для решения задачи 19 представлен ниже, чтобы скачать коды на задания 20 и 21, оплатите товар. 

def f(x,p,q): #x-неизвестная куча камней, ее мы ниже подбираем в цикле for; p-вторая куча; q- уровень дерева
    if (x+p)>=223 and q==3:# выигрышная ((x+p)>=223 ) и уровень дерева =3, т.е. для В1
        return True
    if (x+p)>=223 and q!=3:# выигрышная ((x+p)>=223 ), но не для В1
        return False
    if (x+p)<223 and q==2:# не выигрышная ((x+p)>=223 ) и П1 ход (не должен выиграть), поэтому or. q=предыдущие перед выигрышными
        return f(x+1,p,q+1) or f(x*2,p,q+1) or f(x,p+1,q+1) or f(x,p*2,q+1)
    if (x+p)<223 and q==1:# не выигрышная ((x+p)>=223 ) и П1 ход (не должен выиграть). Иначе q=те, которые не выше
        return f(x+1,p,q+1) or f(x*2,p,q+1) or f(x,p+1,q+1) or f(x,p*2,q+1)# or если неудачный ход, and если при любом ходе
for s in range(1,206):#подбираю неизвестную кучу
    if f(s,17,1):# 17 - вторая известная куча, 1-исходное состояние(уровень дерева)
        print(s)
        break