Решайте задания по одному, проверяйте себя сразу и открывайте подсказки там, где нужно.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Верный ответ: 30
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 30, 33. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 30
• Петя: +1 к первой куче → (8, 30). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (16, 30) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 31). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (14, 31) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 30). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (14, 31) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (7, 60). Ваня выигрывает сразу: ×2 вторую кучу → (7, 120).
S = 33
• Петя: +1 к первой куче → (8, 33). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (8, 34) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 34). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (8, 34) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 33). Ваня выигрывает сразу: ×2 вторую кучу → (14, 66).
• Петя: ×2 вторую кучу → (7, 66). Ваня выигрывает сразу: ×2 первую кучу → (14, 66).
Проверка и доказательство.
При S = 30 Петя может перейти в (8, 30), (7, 31), (14, 30) или (7, 60).
Из (7, 60) Ваня выигрывает сразу удвоением второй кучи. В первых трёх случаях Ваня использует стратегию второго хода: переводит игру в позицию, из которой любой ответ Пети позволяет немедленно достичь суммы 77.
Например, после (7, 31) Ваня действует как в задании 20 для S = 31. Однако из (8, 30) Ваня не может закончить игру одним ходом, поэтому гарантии победы первым ходом нет.
При S = 29 у Пети есть ход, нарушающий требование победы Вани не позднее второго хода. Следовательно, минимальное значение равно 30.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19214.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 93. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, а во второй — S камней; 1 ≤ S ≤ 85.
Верный ответ: 38
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 38, 41. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 38
• Петя: +1 к первой куче → (8, 38). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (16, 38) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 39). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (14, 39) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 38). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (14, 39) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (7, 76). Ваня выигрывает сразу: ×2 вторую кучу → (7, 152).
S = 41
• Петя: +1 к первой куче → (8, 41). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (8, 42) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 42). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (8, 42) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 41). Ваня выигрывает сразу: ×2 вторую кучу → (14, 82).
• Петя: ×2 вторую кучу → (7, 82). Ваня выигрывает сразу: ×2 первую кучу → (14, 82).
Проверка и доказательство.
В этой игре порог равен 93. При S = 38 первый ход Пети ведёт в (8, 38), (7, 39), (14, 38) или (7, 76).
Из (7, 76) Ваня выигрывает сразу удвоением второй кучи. Остальные позиции относятся к выигрышным для Вани за два хода: он переводит игру в опорные позиции со значениями 39 или 42, после чего любой ответ Пети оставляет немедленную победу.
После хода Пети в (8, 38) Ваня не может сразу получить сумму 93, поэтому стратегии гарантированной победы первым ходом нет.
Значение 37 ещё не обеспечивает Ване выигрыш при любом продолжении Пети, поэтому минимальным является 38.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19187.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в любую кучу один камень;
б) увеличить количество камней в любой куче в четыре раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 95. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой суммарное количество камней не менее 95. В начальный момент в первой куче было 5 камней, а во второй — S камней, 1 ≤ S ≤ 89.
Верный ответ: 21
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 21. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 21
• Петя: +1 к первой куче → (6, 21). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (6, 22) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (5, 22). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (6, 22) и гарантирует победу своим следующим ходом.
• Петя: ×4 первую кучу → (20, 21). Ваня выигрывает сразу: ×4 первую кучу → (80, 21).
• Петя: ×4 вторую кучу → (5, 84). Ваня выигрывает сразу: ×4 первую кучу → (20, 84).
Проверка и доказательство.
За один ход выбранная куча увеличивается в 4 раза или на один камень. Из начальной позиции (5, 21) Петя может получить (6, 21), (5, 22), (20, 21) или (5, 84).
Последние две позиции позволяют Ване выиграть сразу: из (20, 21) он увеличивает первую кучу в 4 раза, а из (5, 84) добавляет камень. Из (6, 21) и (5, 22) Ваня не выигрывает немедленно, но переводит игру в позицию, где любой ответ Пети открывает достижение порога 95.
Следовательно, Ваня всегда выигрывает не позже второго своего хода, но первый ход гарантировать не может. Обратный анализ даёт единственное значение S = 21.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19160.
Для ответа на задание изучите предложенный ниже текст.
Петя и Ваня играют в игру "Камни". Первый ход всегда делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 73 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче – S камней; 1 ≤ S ≤ 65.
Верный ответ: 28
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 28, 31. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 28
• Петя: +1 к первой куче → (8, 28). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (16, 28) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 29). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (14, 29) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 28). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (14, 29) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (7, 56). Ваня выигрывает сразу: ×2 вторую кучу → (7, 112).
S = 31
• Петя: +1 к первой куче → (8, 31). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (8, 32) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 32). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (8, 32) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 31). Ваня выигрывает сразу: ×2 вторую кучу → (14, 62).
• Петя: ×2 вторую кучу → (7, 62). Ваня выигрывает сразу: ×2 первую кучу → (14, 62).
Проверка и доказательство.
При S = 28 Петя может получить позиции (8, 28), (7, 29), (14, 28) и (7, 56).
Из (7, 56) Ваня выигрывает сразу удвоением второй кучи. В трёх остальных случаях он переводит игру в одну из позиций задания 20 — например, из (7, 29) использует выигрышную стратегию, связанную со значением 29. После этого любой ответ Пети оставляет Ване победу следующим ходом.
Ваня не способен гарантировать победу первым ходом: после перехода Пети в (8, 28) максимальная сумма за один ход Вани ещё меньше 73.
При S = 27 у Пети существует продолжение, не позволяющее Ване гарантировать победу за два хода, поэтому минимальным является 28.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19133.
Для ответа на задание изучите предложенный ниже текст.
Петя и Вася играют в игру «Камни». Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 85. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой будет 85 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче — S камней; 1 ≤ S ≤ 77.
Верный ответ: 34
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 34, 37. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 34
• Петя: +1 к первой куче → (8, 34). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (16, 34) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 35). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (14, 35) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 34). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (14, 35) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (7, 68). Ваня выигрывает сразу: ×2 вторую кучу → (7, 136).
S = 37
• Петя: +1 к первой куче → (8, 37). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (8, 38) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 38). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (8, 38) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 37). Ваня выигрывает сразу: ×2 вторую кучу → (14, 74).
• Петя: ×2 вторую кучу → (7, 74). Ваня выигрывает сразу: ×2 первую кучу → (14, 74).
Проверка и доказательство.
При S = 34 первый ход Пети приводит к одной из позиций: (8, 34), (7, 35), (14, 34) или (7, 68).
Из (7, 68) Вася выигрывает сразу удвоением второй кучи. В трёх остальных случаях Вася использует стратегию второго хода: переводит игру в позицию, где любой последующий ход Пети позволяет немедленно набрать не меньше 85 камней.
Гарантировать победу первым ходом Вася не может: например, после позиции (8, 34) ни один его ход ещё не завершает игру. Значение 34 — минимальное; значение 33 не относится к проигрышным позициям второго уровня.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19106.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 55. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 55 или больше камней. В начальный момент в первой куче было пять камней, во второй куче – S камней; 1 ≤ S ≤ 49. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Верный ответ: 21
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 21, 23. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 21
• Петя: +1 к первой куче → (6, 21). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (12, 21) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (5, 22). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (10, 22) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (10, 21). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (10, 22) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (5, 42). Ваня выигрывает сразу: ×2 вторую кучу → (5, 84).
S = 23
• Петя: +1 к первой куче → (6, 23). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (6, 24) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (5, 24). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (6, 24) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (10, 23). Ваня выигрывает сразу: ×2 вторую кучу → (10, 46).
• Петя: ×2 вторую кучу → (5, 46). Ваня выигрывает сразу: ×2 первую кучу → (10, 46).
Проверка и доказательство.
Из позиции (5, 21) Петя может перейти в (6, 21), (5, 22), (10, 21) или (5, 42).
Из (5, 42) Ваня выигрывает сразу удвоением второй кучи. Первые три позиции являются выигрышными для Вани за два хода: он переводит игру в позицию задания 20, после чего любой ответ Пети оставляет немедленную победу.
При этом после хода Пети в (6, 21) Ваня не может сразу получить сумму 55, поэтому стратегии гарантированной победы первым ходом нет.
S = 20 не подходит: Петя может удвоить первую кучу и получить (10, 20), после чего Ваня не имеет гарантированной победы не позднее своего второго хода. Следовательно, минимальное значение равно 21.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19079.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня, добавить 3 камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда в куче становится не менее 45 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней; 1 ≤ S ≤ 44.
Верный ответ: 16 17
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 16, 17. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 16
• Петя: +2 → 18. Ваня не выигрывает сразу, но ходом +3 переводит игру в опорную позицию 21 и гарантирует победу своим следующим ходом.
• Петя: +3 → 19. Ваня не выигрывает сразу, но ходом +2 переводит игру в опорную позицию 21 и гарантирует победу своим следующим ходом.
• Петя: ×2 → 32. Ваня выигрывает сразу: ×2 → 64.
S = 17
• Петя: +2 → 19. Ваня не выигрывает сразу, но ходом +2 переводит игру в опорную позицию 21 и гарантирует победу своим следующим ходом.
• Петя: +3 → 20. Ваня не выигрывает сразу, но ходом +2 переводит игру в опорную позицию 22 и гарантирует победу своим следующим ходом.
• Петя: ×2 → 34. Ваня выигрывает сразу: ×2 → 68.
Проверка и доказательство.
Для новой игры с порогом 45 подходят две позиции.
S = 16: Петя получает 18, 19 или 32. Из 32 Ваня выигрывает сразу удвоением; из 18 и 19 он использует выигрышную стратегию второго хода через позиции 21 или 22.
S = 17: после ходов Пети получаются 19, 20 или 34. Из 34 Ваня выигрывает сразу, а из 19 и 20 переводит игру в 21 или 22 и затем выигрывает независимо от ответа Пети.
Победа первым ходом не гарантирована: после переходов в 18, 19 или 20 Ваня ещё не достигает 45 одним действием. Других позиций этого уровня нет, поэтому два наибольших значения — 16 и 17.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19052.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 81. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, а во второй — S камней; 1 ≤ S ≤ 74.
Верный ответ: 33
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 33. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 33
• Петя: +1 к первой куче → (7, 33). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (14, 33) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (6, 34). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (12, 34) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (12, 33). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (12, 34) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (6, 66). Ваня выигрывает сразу: ×2 вторую кучу → (6, 132).
Проверка и доказательство.
Начальная позиция равна (6, 33). После ходов Пети возникают (7, 33), (6, 34), (12, 33) или (6, 66).
Из (6, 66) Ваня выигрывает сразу удвоением второй кучи. Три остальные позиции относятся к выигрышным для Вани за два хода: он переводит игру в одну из позиций, из которых любой ответ Пети открывает достижение порога 81.
Ваня не может гарантировать победу первым ходом, поскольку, например, из (7, 33) максимальная сумма после одного хода Вани ещё меньше 81.
Полный обратный анализ даёт одно значение второго проигрышного уровня — S = 33.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19025.
Для ответа на задание изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в два раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Если при этом в куче оказалось не более 45 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 27 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 29.
Верный ответ: 26
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 26. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 26
• Петя: +1 → 27. Ваня не выигрывает сразу, но ходом +1 переводит игру в опорную позицию 28 и гарантирует победу своим следующим ходом.
• Петя: ×2 → 52. Петя немедленно проигрывает из-за перебора.
Проверка и доказательство.
Из 26 Петя может сделать два хода.
Если Петя прибавит единицу, получится 27. Ваня переводит игру в 28 ходом +1. Из 28 любой ход Пети проигрывает: 28 → 29 позволяет Ване получить 30, а 28 → 56 означает немедленное поражение Пети из-за превышения 45.
Если Петя удвоит 26 и получит 52, он сам сразу проигрывает, потому что результат больше 45. Следовательно, Ваня выигрывает при любом ходе Пети не позже своего второго хода.
Гарантии победы первым ходом нет: после хода 26 → 27 Ваня не может сразу попасть в диапазон 30–45. Значение 26 является единственной позицией с такими свойствами.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18998.
Для ответа на задание изучите предложенный ниже текст.
За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 61. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 61 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче – S камней; 1 ≤ S ≤ 53.
Верный ответ: 2
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 22, 25. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 22
• Петя: +1 к первой куче → (8, 22). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (16, 22) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 23). Ваня не выигрывает сразу, но ходом ×2 первую кучу переводит игру в опорную позицию (14, 23) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 22). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (14, 23) и гарантирует победу своим следующим ходом.
• Петя: ×2 вторую кучу → (7, 44). Ваня выигрывает сразу: ×2 вторую кучу → (7, 88).
S = 25
• Петя: +1 к первой куче → (8, 25). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (8, 26) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (7, 26). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (8, 26) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (14, 25). Ваня выигрывает сразу: ×2 вторую кучу → (14, 50).
• Петя: ×2 вторую кучу → (7, 50). Ваня выигрывает сразу: ×2 первую кучу → (14, 50).
Проверка и доказательство.
Подходят S = 22 и S = 25.
При S = 22 ходы Пети ведут в (8, 22), (7, 23), (14, 22) или (7, 44). Последняя позиция даёт Ване немедленную победу, а первые три относятся к позициям, из которых Ваня выигрывает своим вторым ходом.
При S = 25 получаются (8, 25), (7, 26), (14, 25) и (7, 50). Две последние позиции позволяют выиграть сразу, а две первые — не позднее второго хода.
В обоих случаях существует ход Пети, после которого Ваня не может победить немедленно, поэтому гарантии первого хода нет. Обратный анализ всех S даёт ровно два значения.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18971.
