Теория игр. Задачи с одной кучей | ЕГЭ по информатике

[DNS.shop.]

1a)Петя выиграет первым ходом, это значит, что любая из комманд выше(+1;*3) в любом случае приведет Петю к выигрышу, т.е наберет минимум 34 камня, самое максимальное количество камней для выигрыша - 33, т.к 33 + 1 = 34, осталось найти минимальное число, при котором первым ходом получится выиграть Пете, к примеру: 16 * 3 = 48, берем меньше, 15 * 3 = 45, еще меньше, до того момента, пока у Пети не получится выиграть первым ходом:13*3 = 39, еще получается, 12*3= 36, все еще получается, 11 * 3 = 33 - а вот тут уже не получается, =>берем минимальное и максимальное значения, при которых Петя выиграет первым ходом [12;33].
1Б)Ваня выиграет первым ходом.Ванин первый ход - это ход после Пети, т.е второй по счету.
Петя не выигрывает первым ходом, а следовательно это возможность передается Ване.
Пете нужно набрать до 34 камней, не включая 34, чтобы Ваня смог победить своим первым ходом в любом случае.При 12 Петя может выиграть первым ходом, => возьмем число меньше - 11, возьмем два хода Пети:
11 + 1 = 12, 11 * 3 = 33, как мы видим Петя не выигрывает, а Ване достается возможность выиграть при любом ходе 12 * 3 = 36 и 33 + 1 = 34.На всякий случай возьмем числа меньше для проверки: возьмем число 10, Петя ходит: 10 + 1 = 11 или 10 * 3 = 30, как мы видим Ваня своим первым ходом выигрывает только при одно условии, что Петя первым ходом приумножил кучу камней в 3 раза, но нам нужно, чтобы Ваня выиграл при любом первом ходе, => числа меньше 11 не до конца достоверный, берем в ответ только число 11.
2 Петя может выиграть своим вторым ходом. Петин второй ход является третьим в игре, решить этот пункт можно опираясь на пукнт 1Б). Ваня выиграет своим первым ходом, по счету вторым, если Петя сходит из 11-ти любой из перечисленных двух комбинаций, но нам нужно, чтобы в этот раз победил Петя выиграл хотя бы одним ходом, => отойдем назад на 1 : 11-1 = 10, Петя ходит из 10 либо в 11, либо в 30, далее ходит Ваня, который побеждает при одном условии, если Петя первым ходом ходит в 30, но если он ходит от 11-ти, тогда не выигрывает, тогда у него получаетя сходить в 12 или в 33, => следующий Петин ход в любом случае выигрышный, проверим с 9 -кой : Петя пойдет в 10 или в 27, но если Ваня сходит после 10 в 11 у Пети не получится выиграть с ходом + 1, т.к 9 -(П) 10 -(В) 11 - (П)33 или (П)12, =>в ответ берем 10.
3 Ваня выиграет своим перым или вторым ходом, опираясь на предыдущие пункты, а именно на пункт 1б), становится понятно, что Ваня победит в первом ходу, при условии, что Петя придет из 11-ти либо в 12, либо в 33, а следом Ваня выиграет при любом условии, из пункта 2 становится понятно, что Петя выигрывает своим вторым, если пойдет из 10-ти, => исходя из двух вышеперечисленных условий можно сделать вывод, что если Петя пойдет из 9-ти, то Ваня выиграет при втором ходе, но также может выиграть, если Петя приумножит кучу в 3 раза - 27 - (В)либо 28, либо же 54, что больше 34, => в ответ берем 9

[jonspeen]

Может быть я не так правильно понял условие, но все же, хочется задать вопрос..
Пункт 2
Так если S=10, Петя может сделать *3 и сделать 30, в этом случае выиграет Ваня, а нам этого не нужно. Не поняль ;;;)
Можете пожалуйста объяснить.
А а, все понял, лайк поставил ;)

[sincere_proger]

Мы должны решать задачу, беря в расчёт лучшие ходы противника?