Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела комбинаторика
Разделы подтемы Игры
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#110627

На доске нарисована окружность и на ней отмечены 2n  точек, делящие ее на 2n  равных дуг. Петя и Вася играют в следующую игру. Петя выбирает натуральное число d≤n  и объявляет это число Васе. После этого для победы Васе нужно покрасить все отмеченные точки в n  цветов, в каждый цвет — ровно две точки, так, чтобы для каждой пары одноцветных точек на одной из дуг между ними было ровно (d− 1)  отмеченная точка. Найдите все n,  для которых Петя сможет помешать Васе выиграть.

Подсказки к задаче

Подсказка 1

Точки удобно нумеровать остатками от деления на 2n. Попробуем показать, что в случае, когда n — степень двойки, Вася сможет победить. Может ли Вася хорошим образом разбить остатки на пары?

Подсказка 2

Рассмотрим произвольное d. Пусть Вася будет по кругу создавать пары (0, d), (2d, 3d) и так далее, пока среди остатков вида 2kd впервые не произойдет повторение. Каким может быть это повторение?

Подсказка 3

Верно! Это повторение — остаток 0. Учитывая, что 2n — степень двойки, легко показать, что цикл будет четной длины, и остатки удастся разбить. Пусть n не является степенью двойки. Какое число следует назвать?

Подсказка 4

Верно! Если m — степень вхождения двойки в n, то следует назвать в качестве числа d (m+1)-ю степень двойки. Повернем окружность так, чтобы у нас была пара (0,d). Можно ли тогда восстановить остальные пары?

Показать ответ и решение

Пронумеруем отмеченные точки подряд остатками при делении на 2n  (0,1,2,...,2n − 1),  начиная с некоторой точки.

1)  Покажем, что для     m
n= 2  при любом d ≤n  Вася сможет победить, разбив нужным образом остатки на (одноцветные) пары.

Пусть для данного d  он пойдет по кругу и будет создавать пары

(0,d),(2d,3d),(4d,5d)

и т.д., пока в ряду 0,d,2d,...  впервые не возникло повторение остатка. Пусть первое повторение — это sd.  Повторение sd≡ td (mod 2n),  где t> 0,  невозможно, так как иначе

(s− 1)d ≡(t− 1)d  (mod 2n)

и повторение уже случилось шагом ранее. Тогда sd≡ 0 (mod 2n),  т.е. sd:2m+1.  Минимальное натуральное s  с таким свойством — это ----2m+1---
 НОД(d,2m+1) — степень двойки, большая 20 =1.  Значит, s  четно. Поэтому образуется цикл (четной длины) (0,d,2d,...,(s− 1)d),  в котором все остатки разбиты нужным образом на пары.

Так, все остатки разобьем на такие непересекающиеся циклы длины s  (совмещаемые поворотами окружности), а в каждом цикле разобьем нужным образом остатки на пары.

2)  Пусть     m
n= 2 ⋅t,  где t≥3  — нечетное число. Покажем, что Вася проиграет, если названо число     m+1
d= 2  (оно, очевидно, меньше n).  Предположим, Вася все же сделал требуемое разбиение на пары. Не умаляя общности, считаем, что одна из его пар это (0,d)  (к этому случаю можно прийти, повернув нужным образом окружность). Заметим, что остаток 2d  может быть соединен только с 3d,  так как d= 2d− d  уже занят. Рассуждая так далее, однозначно восстанавливаем пары

(0,d),(2d,3d),(4d,5d),...,((t− 1)d,td)

Но td= 2m+1⋅t≡ 0 (mod 2n)  уже занят. Противоречие.

Ответ:

Все n,  не равные степени двойки

Ошибка.
Попробуйте повторить позже

Задача 2#125070

В каждой клетке доски 2 ×200  лежит по рублёвой монете. Даша и Соня играют, делая ходы по очереди, начинает Даша. За один ход можно выбрать любую монету и передвинуть её: Даша двигает монету на соседнюю по диагонали клетку, Соня — на соседнюю по стороне. Если две монеты оказываются в одной клетке, одна из них тут же снимается с доски и достаётся Соне. Соня может остановить игру в любой момент и забрать все полученные деньги. Какой наибольший выигрыш она может получить, как бы ни играла Даша?

Источники: Всеросс, РЭ, 2025, 9.4 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Чтобы придумать стратегию за Соню, попробуйте разбить доску на какие-нибудь маленькие части, в рамках которых она сможет легко получать монеты.

Подсказка 2:

Разбейте на квадраты 2 на 2. Давайте заметим, что если в таком квадрате есть хотя бы 2 монеты, то Соня легко сможет получить одну из них (почему?). Исходя из этого, можно понять, каким будет ответ.

Подсказка 3:

Итак, скорее всего вы поняли, что ответ будет 300. Осталось придумать стратегию за Дашу, с помощью которой она всегда сможет сохранить 100 монет на доске. Попробуйте выбрать 100 монет, находящихся в каких-то определённых столбцах.

Подсказка 4:

Будет здорово, если эти столбцы не будут рядом. Тогда Соне будет сложнее забрать какую-то из выбранных монет. Значит, можно взять, например, нечётные столбцы и придумать стратегию, при которой после каждого хода Даши выбранные монеты находятся в этих столбцах.

Показать ответ и решение

Сначала приведём стратегию за Соню. Пока она не получила больше 299 монет, перед её ходом на доске остаётся хотя бы 101 монета. Разобьем доску на 100 квадратов 2×2.  Получается, что какие-то две монеты лежат в одном и том же квадрате 2× 2.  Если эти две монеты соседние по стороне, то Соня надвигает одну на другую, и получает ещё одну монету. Если они стоят по диагонали, то Соня сдвигает одну из них в столбец к другой (здесь и далее столбец имеет длину 2, строка — длину 200). Теперь, какой бы ход ни сделала Даша, эти две монетки всё ещё будут соседними по стороне (либо одна будет снята и уйдёт в доход Сони), значит, своим следующим ходом Соня сможет получить ещё одну монетку. Таким образом, Соня всегда сможет увеличивать свой выигрыш, пока он меньше 300.

Теперь покажем, как играть за Дашу, чтобы Соня не получила больше 300 монет. Пронумеруем столбцы числами от 1 до 200 по порядку, выберем в каждом нечётном столбце по одной монетке и мысленно покрасим их в красный цвет. Даше достаточно обеспечить, чтобы красные монетки всегда оставались на доске. Для этого, в свою очередь, достаточно, чтобы две красные монеты никогда не попадали в одну клетку, потому что когда в клетку попадают красная и не красная монеты, можно считать, что с доски снимается не красная.

Назовём расположение монет на доске стабильным, если по одной красной монете лежит в столбцах 1,3,5,...,197,  а ещё одна располагается в одном из двух последних столбцов 199, 200. Легко видеть, что после любого хода из стабильной позиции две красные монеты не окажутся в одной клетке. Даша будет играть так, чтобы после каждого её хода получалась стабильная позиция. Если после хода Сони позиция осталась стабильной, то Даша двигает сотую красную фишку между двумя последними столбцами, так же Даша поступит и своим первым ходом. Если же после хода Сони позиция перестала быть стабильной, то Соня подвинула одну из красных монет из некоторого столбца x  в соседний столбец. Тогда Даша своим ходом вернёт её в столбец x.  Таким образом, на доске всегда останется хотя бы 100 монет, и Соня заработает не более трёхсот рублей.

Ответ:

300

Ошибка.
Попробуйте повторить позже

Задача 3#127159

Петя и Вася играют в игру на изначально пустой клетчатой таблице 100× 100,  делая ходы по очереди. Начинает Петя. За свой ход игрок вписывает в некоторую пустую клетку любую заглавную букву русского алфавита (в каждую клетку можно вписать ровно одну букву). Когда все клетки будут заполнены, Петя объявляется победителем, если найдутся четыре подряд идущие клетки по горизонтали, в которых слева направо написано слово «ПЕТЯ», или найдутся четыре подряд идущие клетки по вертикали, в которых сверху вниз написано слово «ПЕТЯ». Сможет ли Петя выиграть независимо от действий Васи?

Источники: ВСОШ, ЗЭ, 2025, 10.1 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте придумать выигрышную стратегию для Васи.

Подсказка 2:

Хорошей идеей будет выбрать некоторую букву, которой нет в слове ПЕТЯ, и некоторым образом с её помощью блокировать появление данного слова. Как это сделать?

Подсказка 3:

Попробуйте придумать такой алгоритм выставления буквы, при котором будет блокироваться появление сочетания букв ПЕ по горизонтали и ТЯ по вертикали. Как нужно отвечать на ходы Пети, чтобы добиться этого?

Показать ответ и решение

Опишем выигрышную стратегию Васи. Пусть Вася все время пишет букву «Ю» в клетку согласно следующим ниже условиям; а если указанная клетка не существует или уже занята, а также если Петя ставит любую букву отличную от «П», «Е», «Т», «Я», то пусть Вася ставит «Ю» в любую свободную клетку.

Если Петя в некоторой клетке пишет букву «П», то Вася пишет «Ю» в клетке, соседней с ней справа; если Петя пишет букву «Е», то Вася пишет «Ю» в клетке, соседней с ней слева; если Петя пишет букву «Т», то Вася пишет «Ю» в клетке, соседней с ней снизу; если Петя пишет букву «Я», то Вася пишет «Ю» в клетке, соседней с ней сверху.

Из первых двух условий следует, что в двух соседних по горизонтали клетках не могло появиться «ПЕ», читаемое слева направо. В самом деле, предположим, что горизонтальное «ПЕ» появилось; тогда после появления первой из этих двух букв Вася, согласно описанной стратегии, сразу займёт место второй из этих букв — противоречие. Аналогично, в двух соседних по вертикали клетках не могло появиться «ТЯ», читаемое сверху вниз.

Ответ:

не сможет

Ошибка.
Попробуйте повторить позже

Задача 4#128201

В строку выписаны числа 1, 2, 3, …, 60 (ровно в таком порядке). Игорь и Руслан по очереди ставят знаки +,− и × между ними, начинает Игорь; за ход каждый ставит один знак. Когда между каждыми двумя соседними числами поставлен знак, вычисляется значение полученного выражения. Если оно делится на 3, то победа присуждается Игорю, иначе Руслану. Кто из игроков может выиграть, независимо от действий соперника?

Источники: ВСОШ, ЗЭ, 2025, 9.7 (см. olympiads.mccme.ru)

Показать ответ и решение

Заменим все числа в строке на их остатки от деления на 3, от этого результат игры не изменится. Получим строку 1,  2,  0,  …, 1,  2,  0.  Промежутки между числами пронумеруем слева направо от 1 до 59. Первым ходом Игорь ставит знак минус в 30-й промежуток, а все остальные промежутки он разбивает на пары вида (i,30+ i).  Если Руслан ставит в какой-то промежуток знак плюс или минус, то Игорь в парный промежуток ставит минус или плюс соответственно. А если Руслан ставит знак умножить, то Игорь ставит в парный промежуток также знак умножить. Когда все знаки расставлены, полученное выражение разбивается на несколько слагаемых. При этом в левой и правой половинах выражения набор слагаемых одинаковый, но берутся они с противоположными знаками. Следовательно, его значение будет давать остаток 0 при делении на 3.

Ответ:

Игорь

Ошибка.
Попробуйте повторить позже

Задача 5#128217

По кругу выписаны 100 единиц. Петя и Вася играют в игру, каждый делает по 1010  ходов. Петя каждым своим ходом выбирает 9 стоящих подряд чисел и уменьшает каждое из них на 2. Вася каждый своим ходом выбирает 10 стоящих подряд чисел и увеличивает каждое из них на 1. Ребята ходят по очереди, начинает Петя. Докажите, что Вася сможет действовать так, чтобы после каждого его хода среди 100 выписанных чисел было не менее пяти положительных, как бы ни играл Петя.

Источники: ВСОШ, ЗЭ, 2025, 11.6 (см. olympiads.mccme.ru)

Показать доказательство

Обозначим записанные по кругу числа a,
 1  a ,
 2  …, a  .
 100  Вася будет следить лишь за десятью числами, которые он разобьёт на пары: (a9,a18),  (a27,a36),  …, (a90,a99).  За один ход Петя может уменьшить не более, чем одно из этих 10 чисел. Если Петя уменьшил одно из чисел пары (ai,ai+9),  Вася в ответ добавит 1 к числам ai,  ai+1,  …, ai+9.  Если же Петя не уменьшил ни одно из этих 10 чисел, Вася сделает любой разрешённый ход. Таким образом, после пары ходов Пети и Васи сумма чисел в каждой из пяти Васиных пар не уменьшится. Поскольку изначально пять сумм в парах положительны, то после каждого Васиного хода сумма в каждой из этих пяти пар будет положительной, поэтому в каждой из пар будет хотя бы одно положительное число. Таким образом, после любого Васиного хода будет хотя бы 5 положительных чисел, что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 6#34920

Петя и Вася играют в следующую игру. На доске написаны числа от 1  до 2014.  За ход разрешается вычеркнуть любое число вместе со всеми его делителями. Ходят по очереди, начинает Петя. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?

Подсказки к задаче

Подсказка 1

Давайте подумаем над тем, кто в принципе может иметь здесь выигрышную стратегию. Если она есть у первого игрока, то всё и так понятно. А что если она есть у второго? Как тогда может сходить первый игрок?

Показать ответ и решение

По правилам игры ничьих не бывает, поэтому либо первый игрок, либо второй имеет выигрышную стратегию. Первый игрок может “передать ход” второму, вычеркнув первым ходом 1.  Действительно, пусть второй вычёркивает число x  и все его делители. После этого хода вычеркнуты те числа, какие были бы вычеркнуты, если бы первый игрок первым своим ходом вычеркнул x  (и все его делители). Поэтому у второго игрока не может быть выигрышной стратегии: первый игрок, “передав ход”, может играть, следуя любой стратегии второго игрока. Значит, выигрышная стратегия есть у первого игрока.

Ответ: Первый

Ошибка.
Попробуйте повторить позже

Задача 7#34926

Даны две кучки спичек. В одной 2021,  в другой 2022  спичек. Двое играют в следующую игру: при своем ходе каждый выбрасывает одну из двух кучек, а другую делит на две не обязательно равные кучки. Проигравшим считается тот, кто не может разделить кучку на две части. Кто может выиграть при правильной игре?

Показать ответ и решение

Игра конечна, следовательно, у одного из игроков есть выигрышная стратегия. Докажем, что у второго не может быть выигрышной стратегии. Предположим, что она у него есть, и будем играть за первого. Первым ходом выбросим кучку 2021,  а вторую разделим на   2021  и 1.  Второй игрок обязательно выбросит кучку 1  и разделит как-то кучку 2021.  С этого момента у второго игрока есть ответные ходы на каждый наш ход, соответствующие выигрышной стратегии. Тогда можем начать игру по-другому: первым ходом выбросим кучку 2022  и разделим кучку 2021  так же, как и второй игрок разделил бы ее в соответствии со своей выигрышной стратегией. Теперь будем отвечать на ходы второго по его же стратегии и победим. Значит, у первого тоже есть выигрышная стратегия. Противоречие.

Доказали, что первый игрок имеет выигрышную стратегию.

Ответ:

Первый

Ошибка.
Попробуйте повторить позже

Задача 8#34928

На доске написано число 2.  За ход разрешается прибавить к числу на доске любой из его делителей, меньший самого числа. Выигрывает тот, кто первым получит число больше 1000000.  Кто может выиграть при правильной игре?

Подсказки к задаче

Подсказка 1

Заметим сразу, что у нас просто спрашивают, кто может выиграть при правильной игре. То есть стратегию не обязательно приводить. Какие тогда есть идеи, варианты, чтобы выяснить это? Попробуем немного пофантазировать и начнём выписывать какие-то числа.

Показать ответ и решение

Первый игрок напишет число 3,  второй число 4.  Далее первый может написать число 6,  а может написать число 5,  и тогда второй напишет число 6.  После написания числа 6  выигрышная стратегия есть либо у ходящего, либо у его противника. Так как первый игрок после написания числа 6  может по своему желанию оказаться и ходящим, и противником ходящего, он может воспользоваться выигрышной стратегией. Таким образом мы доказали, что у первого есть выигрышная стратегия.

Ответ:

Первый

Ошибка.
Попробуйте повторить позже

Задача 9#78961

На столе лежат N  кучек по одному ореху в каждой (N > 2).  Двое ходят по очереди. За ход нужно выбрать две кучки, где числа орехов взаимно просты, и объединить эти кучки в одну. Выиграет тот, кто сделает последний ход. Для каждого N  выясните, кто из играющих может всегда выигрывать, как бы ни играл его противник.

Показать ответ и решение

Для выигрыша ему достаточно до самого конца объединять имеющиеся кучки так, чтобы была одна большая кучка и несколько кучек по одному ореху. При такой стратегии сохраняется инвариант — нечетность максимальной кучки после хода второго. В случае нечётного  N  второй придерживается такой стратегии до конца, а в случае чётного — до позиции из четырёх кучек N − 3,1,1  и 1,  после чего на любой ход первого: N − 2,1,1  или N − 3,2,1  — отвечает ходом N − 2,2.

Ответ:

Всегда выигрывает второй

Ошибка.
Попробуйте повторить позже

Задача 10#85492

Имеется кучка из 100 камней. Двое играют в следующую игру. Первый игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый может забрать 1,2 или 3 камня, затем второй 1,2,3  или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?

Источники: ММО - 2024, первый день, 11.3 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Давайте внимательно посмотрим на то, какое количество камней всегда может набрать первый игрок, после хода второго. Что можно заметить?

Подсказка 2

Первым ходом первый игрок всегда забирает ровно один камень, поэтому тут не очень интересно. А вот дальше второй игрок забирает один или два камня, а первый от 1 до 3 камней. Какое число камней можно набрать после хода второго и первого вместе?

Подсказка 3

Ровно 3 камня, на следующем ходе 5 камней, дальше 7 и так далее. То есть после хода первого получаются последовательные нечётные числа. А разность чего равняется последовательным нечётным числам?

Подсказка 4

Разность квадратов — это нечётное число. Поэтому, так как первым ходом первый игрок забирает 1 камень, то есть квадрат. А это значит, что после каждого его хода забирается такое количество камней, которое равно квадрату натурального числа!

Показать ответ и решение

Докажем, что для любого натурального n≥ 10  первый игрок на своём n  -ом ходе может добиться, чтобы количество забранных из кучки камней равнялось  2
n  , и второй игрок не сможет ему помешать. Доказательство проведём индуктивно.

В свой первый ход первый игрок забирает один камень, т. е. число забранных камней равно  2
1  . Пусть в свой n  -й ход первому игроку удалось сделать так, чтобы количество забранных камней равнялось  2
n  . В свой n  -й ход второй игрок может взять от 1  до 2n  камней. Поскольку      2   2
(n +1) − n =2n +1,  после его хода общее количество забранных камней будет больше  2
n  и меньше      2
(n+ 1)  . Первый игрок в свой следующий ход может взять от 1  до 2n+ 1  камня и точно сможет получить      2
(n+ 1)  забранных камней независимо от предыдущего хода второго игрока.

Таким образом, поскольку       2
100= 10  , побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём 10  ходе он возьмёт последний камень.

Ответ: первый

Ошибка.
Попробуйте повторить позже

Задача 11#85561

Аня и Боря играют в игру. Они по очереди (начинает Аня) выписывают по одной цифре, пока не получится шестизначное число. При этом первая выписанная цифра ненулевая и все выписанные цифры различны. Аня выигрывает, если полученное шестизначное число делится хотя бы на одно из чисел: 2,3 или 5. Если этого не случается, то выигрывает Боря. Кто выигрывает при правильной игре?

Источники: Курчатов - 2024, 11.3 (см. olimpiadakurchatov.ru)

Подсказки к задаче

Подсказка 1

Подумаем, какие цифры и на какой позиции могли бы принести Боре победу? Что нужно сделать Ане, чтобы предотвратить это?

Подсказка 2

Если на третий ход Бори оставить ему числа 0, 2, 4, 5, 6, 8, то он проиграет. Значит, если Боря хочет победить, то в свой последний ход он подставит одно из числе 1, 3, 7, 9. Какие еще вынужденные ходы можно приписать Боре?

Подсказка 3

Заметим, что чисел 1, 3, 7, 9 не так уж и много, значит Боря не должен их «закончить» раньше своего третьего хода. Тогда какие цифры он должен ставить в своих ходы?

Подсказка 4

Выходит, что Боря в свои первый и второй ходы должен ставить цифры из {0, 2, 4, 5, 6, 8}. Тогда какие цифры должна поставить Аня, чтобы Боря не смог победить в конце?

Подсказка 5

Аня своим первым и вторым ходом поставит 3 и 9. Осталось лишь разобрать случаи того, какие именно ходы сделает Боря! Подумайте, а как должна поступить Аня вторым ходом, чтобы застать Борю врасплох?

Подсказка 6

Обратите внимание на остатки чисел при делении на 3!

Показать ответ и решение

Пусть a-ba-b-ab-
 1 12 23 3  - итоговое шестизначное число. Пусть также A = {0,2,4,5,6,8} и B = {1,3,7,9} . Заметим, что если Боря своим третьим ходом поставит цифру из множества A  , Аня выиграет, поскольку полученное число будет делиться на 2 . Значит, b3 ∈ B  .

Пусть Аня первым ходом выберет цифру a1 = 3  , а вторым ходом - цифру a2 =  9. Если Боря на первом или втором ходу выберет цифру из множества B  , то своим третьим ходом Аня заберет последнюю оставшуюся цифру из множества B  , и Боря вынужден будет взять свою цифру b3  из A  , что приведет к его проигрышу. Значит, Боря вынужден взять первые две свои цифры b1  и b2  взяты из множества A  . Заметим, что Боря вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Ане достаточно подобрать цифру a3  так, чтобы сумма цифр a1+b1+ a2+ b2+ a3  давала бы остаток 2 при делении на 3 . Поскольку a1 = 3  и a2 = 9  не влияют на остаток этой суммы, все зависит от остатка суммы b1+b2  . Покажем, как действовать Ане в каждом из случаев.

Если b1 +b2  делится на 3 , то Аня выберет цифру a3  из набора {2,5,8} : поскольку до этого момента эти цифры мог выбирать только Боря, как минимум одна из этих трех цифр останется не выбранной.

Если b1 +b2  дает остаток 1 при делении на 3 , Аня выберет цифру a3 = 1  . Как мы помним, Боря не мог ее выбрать на первых двух ходах.

Наконец, если b1+ b2  дает остаток 2 при делении на 3 , Аня выберет цифру a3  из набора {0,6} . Боря не мог выбрать обе эти цифры, поскольку тогда b1+b2 = 6  , а мы предположили, что b1+b2  дает остаток 2 при делении на 3 .

Таким образом, Аня выиграет.

Ответ:

Аня

Ошибка.
Попробуйте повторить позже

Задача 12#88667

Вначале на доске написано число 1010.  Петя за ход должен уменьшить его, разделив нацело на чётное число от 2  до 100,  Вася — на нечётное от 2  до 100.  Проигрывает тот, кто не сможет ходить, начинает Петя. Кто из игроков имеет выигрышную стратегию?

Подсказки к задаче

Подсказка 1

Посмотрите на разложение числа 10^10 на множители. На какие именно числа от 2 до 100 могут делить Петя и Вася?

Подсказка 2

Вася может делить только на 5 или 25. А Петя на четные числа от 2 до 100 вида 2^a, 2^a * 5, 2^a * 25. Кто из игроков своими ходами может помешать другому?

Подсказка 3

Петя может мешать Васе, потому что может "забирать" пятерки из разложения на множители числа на доске, а вот Вася двойки не заберет. Как теперь придумать стратегию за Петю?

Показать ответ и решение

Заметим, что 1010 = 210⋅510,  то есть Вася может делить только на 5  или 25  , а Петя —– только на четные числа (вида  a a
2 ,2 ⋅5  или  a
2 ⋅25  , где a∈ ℕ.  ) То есть Вася проигрывает, когда заканчиваются все 10  пятерок, а Петя —– когда заканчиваются все 10  двоек. Причем Вася может забирать только свои пятерки, а Петя может забирать как двойки, так и пятерки.

Значит, Петя может быстрее приблизить Васю к проигрышу, когда будет забирать его пятерки. Действительно, Петя может первым ходом поделить число на 50,  а затем каждым ходом будет делить число на доске на 2.  Не позднее, чем после 8  ходов Васи пятерок не останется (но двоек будет хотя бы 2  , так как забирает их только Петя), значит, Вася не сможет сходить, а Петя выиграет.

Ответ:

Петя

Ошибка.
Попробуйте повторить позже

Задача 13#88769

В крайней левой клетки полоски 1× 100  стоит фишка. Петя и Вася играют в игру, начинает Петя. За ход разрешается сдвинуть эту фишку на одну или две клетки вправо. Выигрывает тот, кто поставит фишку в самую правую клетку. Кто из игроков может победить, как бы ни играл соперник?

Показать ответ и решение

Покажем стратегию игры за Васю. Каждым ходом будем двигать фишку на 1 клетку, если Петя своим предыдущим ходом подвинул ее на 2 клетки, и на 2 в противном случае.

Докажем, что данная стратегия является выигрышной. После каждой пары ходов Пети и Васи фишка будет передвинута на 3 клетки, следовательно, после k  хода Васи фишка будет передвинута на 3k  клеток. Наконец, после 33 хода фишка будет передвинута на 99 клеток и окажется в последней.

Ответ: Вася

Ошибка.
Попробуйте повторить позже

Задача 14#90011

Петя и Вася разыгрывают призовой фонд, содержащий перед началом игры натуральное число M  фунтиков. (Мы не знаем, что такое фунтики, но фунтики бесконечно делимы, например можно «отмерить»  √ -
1∕ 2  фунтиков). Петя знает секретное (целое) число фунтиков N  (из диапазона 0≤ N ≤ M),  которое ему нужно для поездки в Иннополис, а Вася должен угадать это число N.

Игра состоит из раундов «Васина догадка - Петин ответ», которые продолжаются, пока Вася не назовет число N  или пока не опустеет призовой фонд. В каждом раунде Вася называет целое число k  (из диапазона 0≤ k≤ M )  и

- если k <N,  то Петя говорит об этом Васе, после чего игроки просто переходят к следующему раунду;

- если k >N,  то Петя говорит об этом Васе, забирает из фонда M ∕3  фунтиков, и если в фонде еще остались фунтики, то игроки переходят к следующему раунду;

- если k =N,  то Петя говорит об этом Васе, затем Вася получает из фонда (x− n)  фунтиков, где x  — количество фунтиков в фонде на данный момент, а n  — количество сыгранных раундов. Если x ≤n,  то Вася получит 0 фунтиков.

Какое наибольшее число фунтиков может гарантировать себе Вася?

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Давайте подумаем, какому условию должна удовлетворять стратегия Васи, иначе говоря, когда он ну точно не получит наибольшее вероятное количество фунтиков?

Подсказка 2

Если он 3 раза назовет число, большее N, то весь фонд уйдёт Пете. Можем сначала подобрать стратегию для Васи, а потом попробовать доказать, что она гарантирует наибольшее возможное количество фунтиков. Давайте рассматривать стратегии Васи с определёнными количествами "провалов" (когда Вася называет число k > N).

Подсказка 3

Давайте рассмотрим наименьшее число n, при котором n(n + 1)/2 ≥ M, и подумаем, какие шаги оптимально делать Васе до первого "провала".

Подсказка 4

Пусть Вася будет называть числа k₁ = n, k₂ = n + (n - 1), ... , kₘ₊₁ = n + (n - 1) + ... + (n - m), пока не угадает число N или не превзойдет его. Попробуйте придумать стратегию, при которой Вася будет совершать не более одного "провала".

Подсказка 5

Если Вася попадает в число N, то игра заканчивается. Иначе после провала он перейдет к угадыванию. Вася будет называть последовательные числа от kₘ₊₁ до N (в случае провала, N будет меньше kₘ₊₁). Сколько тогда фунтиков обеспечит себе Вася?

Подсказка 6

До kₘ₊₁ - (m + 1) раунд, до угадывания — не более (m +1) раунда, тогда Вася сыграет (m + 1) + (n - (m + 1)) раундов и получит (2M/3 - n) фунтиков. Надо теперь доказать, что эта стратегия оптимальна. Предположите для начала, что существует стратегия, при которой Вася может получить больше фунтиков.

Подсказка 7

Эта стратегия будет предписывать возрастающую последовательность чисел k₁ < k₂ < ... < kₜ, где t < n. Какое еще условие на k можно наложить через n? Попробуйте доказать через определение n, что такая стратегия не даст нам гарантированно больше фунтиков.

Показать ответ и решение

Очевидно, что Васе нужна стратегия, в которой он не более двух раз “проваливается”, то есть называет число, большее задуманного Петей N  (так как после третьего "провала"весь фонд уходит Пете). Сначала предложим стратегию, позволяющую Васе гарантированно получить указанное количество фунтиков, а потом докажем, что это максимальное количество, которое он может гарантировать.

Стратегия Васи с одним “провалом”: пусть      y(y+1)
n= {y| 2   ≥M } (т.е. наименьшее натуральное n  , при котором n(n+1)
  2  ≥ M  ). Шаги до “провала”: Вася называет числа k1 =n,k2 = n+ (n − 1),k3 =n +(n− 1)+(n− 2),...,  пока Петя не скажет, что для очередного km+1 =n +(n− 1)+...+(n− m)> N  (первый "провал") или что угадано число N.  Сумма арифметической прогрессии n(n+1)
--2-- ≥M  ≥N,  а значит, такой момент обязательно наступит. Если это в момент первого “провала”, то в этот момент Петя получает из фонда M
-3  фунтиков, в фонде остаётся 2M
3--  фунтиков, а Вася приступает к выполнению шагов до "угадал".

Шаги до “угадал”: Вася называет (не более чем (m + 1))  последовательные числа от (km+1)  до N  (которое меньше km+1  ) до тех пор, пока Петя не скажет, что задуманное число угадано, а Вася, сыграв n= (m + 1)+ (n− (m + 1))  раундов, получает из фонда (2M3-− n)  фунтиков.

Докажем, что такая стратегия оптимальна. Пусть существует стратегия для Васи, позволяющая гарантированно получить больше фунтиков. Эта стратегия предписывает возрастающую последовательность чисел k1 <k2 < ...<kt,  где t<n  и ki+1 < ki+(n− i)  для любого 1≤ i< t.  Но так как n= min{y|y(y2+1) ≥M },  то kt < M,  а значит, остались непроверенные числа от (kt+1)  до M,  и такая стратегия не может гарантированно улучшить результат.

Ответ:

 2M-− min{y|y(y+1)≥ M }
 3          2

Ошибка.
Попробуйте повторить позже

Задача 15#90274

Катя и Юра играют в следующую игру. Имеется пустая таблица из одной строки, состоящая из k= 20232  пустых ячеек: ( a ,...,a
 1    k  ), которые игроки заполняют числами от 0 до 2022. Первым ходит Юра, который выбирает число t  такое, что 1≤t≤ k− 1  и заполняет    t  ячеек. Второй ходит Катя, которая заполняет оставшиеся ячейки. Победитель определяется по следующему правилу: если в результате получается «счастливая» комбинация чисел - полностью заполненная таблица, в которой числа можно разбить на две непересекающиеся группы, суммы чисел в которых одинаковы, то выигрывает Катя, в противном случае выигрывает Юра. Например, комбинация ( 7,5,3,4,6  ) не является «счастливой», так как в ней присутствует нечетное число нечетных чисел. С другой стороны, комбинация (4,5,1,6,8)  является «счастливой», так как 4 +8= 5+ 1+ 6  . У кого из игроков имеется выигрышная стратегия? Ответ обосновать.

Источники: Верченко - 2024, 11.1 (см. ikb.mtuci.ru)

Подсказки к задаче

Подсказка 1.

Сразу поймём, что нет никакого смысла рассматривать случаи, когда первый игрок заполняет ячеек меньше, чем k-1. Ведь Юра может оставить Кате всего лишь одну ячейку. Так что будем считать, что если он заполнил меньше k-1 ячейки, то Катя заполняет оставшиеся ячейки, кроме последней, нулями.

Подсказка 2.

Теперь если мы докажем, что числа на k-1 ячейках можно разбить на такие 2 группы, что суммы чисел в них будут отличаться не менее чем на 2022, то Катя сможет победить, поставив в последнюю ячейку число, уравнивающее суммы этих групп. Сейчас работать с числами не очень удобно. Попробуйте упорядочить их и разбить на подходящие группы.

Подсказка 3.

Если мы упорядочим числа и распределим в группы через один, то сумма в группах будет отличаться не более чем на 2022. Победа!

Показать ответ и решение

Очевидно, что достаточно рассмотреть случай, когда игрок, делающий первый ход, заполняет максимально возможное число ячеек, равное k− 1  . Расположим эти k− 1  число в порядке не убывания: ai1 ≤ai2 ≤ ⋅⋅⋅≤ aik−1  . Здесь в индексах указаны номера позиций, на которых стоят эти числа в таблице. Образуем два множества позиций, которые заполнены: {i1,i3,...} и {i2,i4,...} , беря указанные числа через одно. Тогда суммы чисел на этих позициях могут отличаться друг от друга не более, чем на 2022. Поэтому оставшуюся незаполненной позицию можно заполнить числом от 0 до 2022 так, чтобы получилась «счастливая» комбинация.

Ответ: Катя

Ошибка.
Попробуйте повторить позже

Задача 16#99952

Даны 11  куч, по 10  камней в каждой куче. Петя и Вася по очереди делают ходы, начинает Петя. Петя в свой ход берет из какой-нибудь кучи 1,2  или 3  камня. А Вася в свой ход берет по 1  камню из одной, двух или трех куч. Тот, кто не может сделать ход, проиграл. Кто выигрывает при правильной игре?

Подсказки к задаче

Подсказка 1

Попробуем свести задачу к симметричной стратегии. Для этого надо как-то удобно расположить камни. Как это можно сделать?

Подсказка 2

Попробуем расположить камни в клетках таблицы 11 × 11 с пустой главной диагональю. Как интерпретировать при этом кучи?

Подсказка 3

Верно! Кучами будут столбцы! У какого игрока тогда есть симметричная стратегия?

Показать ответ и решение

Расположим камни в клетки таблицы 11  на 11  так, что главная диагональ была пустой (столбцы будут кучами). Петя должен брать несколько камней из одного столбца, а Вася — из разных. Тогда заметим, что если Вася будет делать ходы симметричные Петиным относительно пустой главной диагонали, то условие будет выполняться. Поэтому у Васи всегда есть ход. Так как игра конечна, то когда-то Петя проиграет.

Ответ:

Вася

Ошибка.
Попробуйте повторить позже

Задача 17#101554

Игорь и Сережа по очереди красят клетки белой доски 7× 7  в черный цвет. Начинает Игорь. За один ход можно покрасить в черный цвет любую белую клетку, не находящуюся в одной строке или в одном столбце с покрашенной на предыдущем шаге клеткой. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?

Подсказки к задаче

Подсказка 1

Попробуйте придумать алгоритм, при котором один игрок всегда сможет ответить на ход другого в определённую клетку ходом в другую определённую клетку.

Подсказка 2

Попробуйте разбить клетки на пары так, что один игрок всегда смог ответить второму в парную клетку. Одна клетка точно будет без пары, подумайте, как это обыграть.

Показать ответ и решение

Давайте разобьём клетки на пары следующим образом. Каждой клетке не из главной диагонали поместим в пару клетку, симметричную ей относительно главной диагонали. Клетке на главной диагонали, отличной от центральной, поставим в соответствие клетку из главной диагонали, симметричную ей относительно центральной. Центральная клетка останется без пары.

Теперь приведём стратегию за Игоря. Пусть первым ходом он покрасит центральную, а дальше на каждый ход второго будет отвечать ходом в парную клетку. Нетрудно заметить, что клетки в парах находятся в разных столбцах и строках, а значит, Игорь всегда сможет сделать ход.

Ответ:

Игорь

Ошибка.
Попробуйте повторить позже

Задача 18#101566

Маша и Паша по очереди проводят диагонали в правильном 98  -угольнике, начинает Маша. Разрешено проводить диагональ, если она не перпендикулярна ни одной из ранее проведенных диагоналей, а также пересекает хотя бы половину ранее проведенных диагоналей. Проигрывает тот, кто не может сделать ход. Кто из игроков может обеспечить себе победу независимо от действий соперника?

Подсказки к задаче

Подсказка 1

Требования по проведению диагоналей довольно сложные. Попробуйте придумать такую стратегию, при которой соблюдение всех правил перекладывается на того, кто проиграет. То есть если он до этого смог сходить, то и выигравший тоже сможет.

Подсказка 2

Попробуйте придумать стратегию, опирающуюся на симметрию относительно определённой диагонали.

Показать ответ и решение

Докажем, что Маша может выиграть независимо от действий Паши. Пусть она своим первым ходом соединит отрезком любые две противоположные вершины 98  -угольника, проведя диагональ d0.  Заметим, что теперь ни один из игроков не может проводить диагонали, симметричные сами себе относительно этого отрезка (такая диагональ перпендикулярна первой проведенной). Пусть далее Маша будет делать ходы, симметричные ходам Паши относительно первой проведенной диагонали. Докажем, что такой ход возможен.

Рассмотрим произвольный момент, когда Паша будет делать очередной ход, проведя диагональ d.  До этого момента была проведена 2k+ 1  диагональ для некоторого целого k.  Тогда очередная Пашина диагональ должна пересечь хотя бы k+ 1  ранее проведенную. Следовательно, Машина симметричная диагональ  ′
d также пересечет хотя бы k+ 1  ранее проведенную диагональ. При этом диагональ  ′
d может быть перпендикулярна только диагонали d,  проведенной Пашей ходом ранее. Значит, у нас образовались две перпендикулярные диагонали, симметричные относительно диагонали d0.  Тогда длины этих диагоналей равны. То есть они отличаются друг от друга поворотом на угол ℓ⋅360
-98--= 90  для некоторого целого ℓ,  откуда 98∕ℓ= 4,  что невозможно, так как 98  не делится на 4.

Ответ:

Маша

Ошибка.
Попробуйте повторить позже

Задача 19#104665

На столе лежат

(a) две кучи по 20  камней;

(b) одна куча из 20  камней, другая куча из 30  камней.

Двое игроков играют в следующую игру, делая ходы по очереди. За один ход можно взять любое количество камней, но только из одной кучи. Выигрывает игрок, взявший последний камень. Кто из игроков может выигрывать при правильной игре: начинающий или его соперник?

Показать ответ и решение

Используем симметричную стратегию: будем поддерживать в кучках равное количество камней. Пусть в первой кучке x  камней, а во второй — y,  причём x > y.  Тогда возьмём из первой x− y.  Теперь в кучках поровну камней. Соперник обязан взять хотя бы один, что нарушит равенство количеств. Ясно, что после хода соперника в обеих кучках не может остаться по 0  камней. Значит, если изначально в кучках поровну камней, то победит второй, иначе — первый.

Ответ:

 a)  Соперник b)  Начинающий.

Ошибка.
Попробуйте повторить позже

Задача 20#104666

На столе лежит

(a) 100  спичек;

(b) 101  спичка.

Петя и Вася играют в следующую игру, делая ходы по очереди. Начинает Петя. За один ход можно взять 1,2,3  или 4  спички со стола. Выигрывает игрок, взявший последнюю спичку. Кто из игроков может выиграть, как бы ни играл соперник?

Показать ответ и решение

Используем стратегию дополнения: после каждого нашего хода будем пытаться оставить число спичек, кратное 5.  Действительно, если в данный момент число спичек делится на 5,  то соперник никак не сможет оставить количество, кратное 5.  Если же спичек не кратно   5,  то мы можем взять остаток от деления на 5.  Ясно, что после хода соперника 0  спичек остаться не может. Значит, если спичек изначально кратно 5,  то победит Вася, а иначе — Петя.

Ответ:

 a)  Вася b)  Петя

Рулетка
Вы можете получить скидку в рулетке!