Калужский Александр: Пришлите ссылку на задачу...
25-04-2024
Читать статью
didnt respond: Почему на РешуЕгэ условие стратегии побе..
///: Спасибо Вам большое! Всё очень понятно!!..
22-04-2024
Продолжаем решать задачи на теорию игр. Сегодня у нас разбор 20 задания из ЕГЭ по информатике 2021.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче было S камней 1 ≤ S ≤ 64.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
S0 - первоначальное количество камней в куче.
Т.к. Петя не может выиграть на своём своём первом ходе, то найдём значения S0, при которых это возможно.
Распишем все варианты для Петиного первого хода.
Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 33.
Рассмотрим все два случая:
1. S0+1 (Петя сделал +1 к кучке)
Ваня ни при каких обстоятельствах не должен выиграть на своём первом ходе. Найдём при каких значениях S0 это будет выполняться для этой ветки.
Для случая, когда Петя сделал +1 к кучке на первом своём ходу получается ограничение:
Рассмотрим, при каких значениях S0 Петя на втором своём ходе может выиграть в данной ситуации.
С учётом всех ограничений получили значение S0 = 31, при котором Петя может выиграть на втором своём ходе.
Проанализируем два варианта a) и б) и понимаем, что в ответ пойдёт S0 = 31. При таком начальном количестве камней у Вани не будет возможности "испортить игру" и в случае а), и в случае б).
2. 2*S0 (Петя удвоил количество камней в куче.)
Найдём ограничения, при которых Ваня не выиграет при любых условиях на своём первом ходе.
Значит, при этом первом ходе Пети, S0 должно быть меньше 17.
Узнаем, при каких значениях S0 Петя на втором своём ходе может выиграть в данной ситуации.
С учётом ограничения S0 < 17 получаем значение S0 = 16.
Объединив a) и б) для второго случая (когда первый ход Пети был 2*S0), получаем значение S0 = 16. Мы проверяли пункт б), чтобы проверить, нет ли возможности у Вани "испортить" игру.
В задаче просили найти 2 значения для переменной S, при которых будут выполняться условия задачи. Мы нашли два значения. На этом можно завершить решение и записать ответ.
Решим задачу из Демонстрационного варианта ЕГЭ по информатике 2021.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Обозначим первую кучу за a, вторую кучу за b.
S0 - первоначальное количество камней во второй куче.
a=7, b=S0.
Петя может сделать всего 4 действия. Распишем сумму двух кучек для 4-х случаев. Эти суммы должны быть меньше 77.
Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 35.
Рассмотрим случай, когда Петя оставил следующие кучки:
1. a=8, b=S0 (Петя сделал +1 к первой кучке)
Получается, что для случая, когда Петя сделал +1 к первой кучке, нам подходят значения для S0 < 35. В этом случае есть возможность Ване НЕ выиграть на своём ходе. Это ограничение совпадает с главным ограничением, которое мы получили на первом ходе Пети.
С учётом всех ограничений получили значение S0 = 34, при котором Петя будет выигрывать на втором своём ходе. Это значение наибольшее в допустимом диапазоне. Меньше значение теперь мы получить не можем (при данном первом ходе Пети), потому что у Вани есть возможность всегда "свернуть" в пункт а), и здесь значения меньшие, чем 34 не проходят.
Рассмотрим остальные ходы Вани. Если у него будет возможность пойти так, что Петя на втором ходе не сможет выиграть, значит, он так всегда сможет ходить, и наш ответ S0 = 34 нельзя будет засчитать.
В пункте б) есть решение.
В пункте в) есть решения.
Пункт г) тоже имеет решение. Как только нашли за Петю решение, можно прекратить рассматривать оставшиеся ходы у Пети на втором ходе, потому что мы нашли уже максимальное значение S0 = 34 из диапазона S0 < 35, и в пунктах б), в), г) нам важно убедиться, что решения просто есть.
Мы должны выбрать из всех четырёх пунктов (а), б), в), г)) самое больше число. Это будет S0 = 34. Именно это значение удовлетворяет всем четырём пунктам одновременно. Тогда у Вани не будет возможности сходить так, что Петя на своём втором ходе не сможет выиграть.
Получается, что значение S0 = 34 пойдёт в ответ.
2. a=7, b=S0+1 (Петя сделал +1 ко второй кучке)
Значит, при этом первом ходе Пети, S0 должно быть меньше 34.
Видим, что у Вани есть возможность "свернуть" на путь a=8 (7+1), b=S0+1, и тем самым, не оставить шансов Пети выиграть. (Ни одно неравенство не пройдёт ограничение S0 < 34).
Значит, вариант a=7, b=S0+1 на первом Петином ходу не принёс результатов.
3. a=14, b=S0 (Петя увеличил первую кучку в 2 раза.)
Значит, при этом первом ходе Пети, S0 должно быть меньше 32.
С учётом ограничения S0 < 32 получаем значение S0 = 31. Получили наибольшее значение в допустимом диапазоне. Значит, меньше чем 31, в данной ветке значение быть не может.
Убедимся, что при остальных ходах Вани, Петя сможет выиграть на своём втором ходе.
Пункт б) имеет решение.
Пункт в) имеет решения.
В пункте г) есть решение.
Таким образом, мы нашли наибольшее решение S0 = 31 при ограничении S0 < 32. Оно подходит для всех четырёх пунктов а), б) в), г).
Посмотрим ещё одну задачу 20 Задания из примерных вариантов ЕГЭ по информатике 2021.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 18). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 74. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 74 или больше камней.
В начальный момент в первой куче было 12 камней, во второй куче — S камней, 1 ≤ S ≤ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, т. е не гарантирующие выигрыш независимо от игры противника.
a=12, b=S0.
Петя может сделать всего 4 действия. Распишем сумму двух кучек для 4-х случаев. Эти суммы должны быть меньше 74.
Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 31.
1. a=13, b=S0 (Петя сделал +1 к первой кучке)
Получается, что для случая, когда Петя сделал +1 к первой кучке, нам подходят значения для S0 < 31. В этом случае есть возможность Ване НЕ выиграть на первом своём ходе. Это ограничение совпадает с главным ограничением, которое мы получили на первом ходе Пети.
С учётом всех ограничений получили значение S0 = 30, при котором Петя будет выигрывать на втором своём ходе. Это максимальное значение, для данного ограничения S0 < 32. Даже, если мы найдём меньшее число при других ходах Вани в этой ветке, всё равно мы выберем значение 32. Но всё же нужно проверить остальные ходы Вани, вдруг у него будет возможность выводить нас на такую ситуацию, когда Петя не сможет выиграть на своём втором ходе.
Пункт б) имеет решения.
Пункт г) имеет решение.
Таким образом, значение S0 = 30 удовлетворяет всем четырём пунктам, и у Вани нет возможности "испортить праздник" Пети.
Один ответ есть.
2. a=12, b=S0+1 (Петя сделал +1 ко второй кучке)
Значит, при этом первом ходе Пети, S0 должно быть меньше 30.
Видим, что у Вани есть возможность "свернуть" на путь a=13 (12+1), b=S0+1, и тем самым, не оставить шансов Пети выиграть. (Ни одно неравенство не пройдёт ограничение S0 < 30).
Значит, вариант a=12, b=S0+1 на первом Петином ходу не принёс результатов.
3. a=24, b=S0 (Петя увеличил первую кучку в 2 раза.)
Значит, при этом первом ходе Пети, S0 должно быть меньше 25.
С учётом ограничения S0 < 25 получаем значение S0 = 24. Максимальное значение при допустимом диапазоне. Значит, меньше чем 24, значение при данном первом ходе Пети быть не может, иначе оно не будет проходить в пункте а).
Проверим остальные ходы Вани.
Пункт г) имеет решения.
Ваня не сможет сделать такой ход, при котором Петя не сможет выиграть на втором ходе.
Выбираем такое значение S0 = 24, которое подходит под все пункты а), б), в), г).
Пишем ответ из двух значений 24 и 30.
На этом всё. Удачи на экзамене по информатике 2021!
