17-я Международная Жаутыковская олимпиада по математике, 2021 год

Сауық кешке 99 қонақ келді. Кешті ойын түрде Анна және Боб тамадалары жүргізеді (тамадалар қонақтардың құрамына кірмейді). Шеңбер бойымен 99 орындық қойылған; бастапқыда барлық қонақтар орындықтардың айналасында жүреді. Тамадалар кезектесіп жүреді.
    Тамада өзінің жүрісінде тұрып тұрған қонақты таңдайды да, оған бос тұрған $c$ орындықты көрсетеді, сол кезде қонақ сол орындыққа отыруы керек; ал егер $c$ орындығына көрші екі орындықтардың кемінде біреуі бос емес болса, онда сол тамада $c$-ға көрші бос емес орындықта отырған қонақтың орындықтан тұрып кетуіне бұйрық береді (егер екі орындық та бол болмаса, онда тамада екі орындықтың біреуін таңдайды). Сол кезде бұйрықтар мезетте орындалады.
    Жүрісті Анна бастайды; оның мақсаты — оның қандай да бір жүрісінен кейін кемінде $k$ орындық бос болмауы керек. $k$-ның қандай ең үлкен мәнінде, Боб қалай ойнамаса да, Анна өз мақсатына жете алады? ( И. Богданов )

Комментарий/решение

Ия Анна өз мақсатына жете алады.

Егер Анна бір адамды отырғызып содан кейін Боб келіп соның алдына отырғызуы мүмкін,сол кезде Аннаның отырғызған адамы орнынан тұрады ал отырған адам саны 1 болып қала береді.Сосын Анна мақсатына жетуі үшін Бобтың отырғызған адамының жанына емес басқа жерге отырғызады .Сосын Боб келіп өз адамын, екі адамның біреуін таңдап тұрғызып соның алдына отырғызады.Сонда адам саны 2 болады .Осылай жалғаса береді.Және Анна әр адамның арасынан 1 орындық тастап кетеді сонда барлық адам саны 65ке жетеді. Себебі әр адам тақ орындықтарға отырған жағдайда 1,3,5,7,9.........97. 99ыншы орындыққа адам отыра алмайды егер отыратын болса 1нші орындықтағы адам тұрады қалай алған жағдайда да максималды адам саны 65.

демек k=65.

№90 ДБАММГ

Решение с книги:

Ответ: $34$

Будем называть расположение гостей стабильным , если у каждого свободного стула хотя бы один сосед занят. Очевидно, что в стабильном расположении хотя бы $33$ стула занято, поскольку нет подряд идущих $3$ незанятых. Заметим, что кол-во занятых стульев не уменьшается.

Заметим, что если после хода игрока В расположение стало стабильным, то на любой ход игрока А у игрока В есть контр-ход, который возвращает то же самое расположение. Так что для игрока А важно, чтобы после хода В расположение не было стабильным.

Стратегия для игрока А для $k <= 34:$

Если расположение не стабильное, то игрок А всегда может увеличивать кол-во гостей в круге (ведь есть три подряд идущих свободных стульев). Из всех таких возможностей, игрок А будет выбирать тот, после хода которого как бы ни ходил игрок В, расположение не станет стабильным, за исключением случая, если после хода В будет хотя бы 34 гостя (если так нельзя ходить, то просто любым ходом, увеличивая кол-во гостей).

Рассмотрим теперь момент игры где:

1) Походил А и стало $+1 --> 32$ (после хода А увеличивается, поскольку расположение у нас пока что нестабильное), и после хода В оно увеличилось до $33$. Если расположение нестабильное, то увеличиваем до $34$ и гг. Если стабильное, то оно обязательно вида, где расстояние между соседними гостями равно $3$ для каждой пары соседних. Разобьем круг на $33$ групп по $3$ числа, тогда БОО гости в середине каждой группы. Значит игрок А походил в центр какой-то группы, и после него В поступил так же. Но игрок А должен был не выбирать центр группы, а соседнюю с центром, ведь тогда можно было избежать стабильной конфигурации после хода В.

2) Походил А и стало $+1 --> 33$, Если после В стало 34, то гг, поэтому после В осталось 33 и расположение стало стабильным (от противного). Тогда В походил в центр какой-то группы и расположение стало стабильным, причем 1 гость встал. Если до этого хода В игрок А посадил ставшего гостя, то он поступил неправильно, поскольку ему следовало выбрать центр группы, тогда на любой ход игрока В в какой-то группе можно было поставить $2$ гостя. Если до этого хода В игрок А посадил кого-то в центр группы, то ему следовало выбрать стул, который находится в группе, где встанет гость после хода В, симметричный относительно центра этой группы. В этом случае даже если после хода В будет стабильное расположение, будет $34$ гостя.

Теперь покажем, что В может сделать так, чтобы было не более $35$ гостей.

Будем рассматривать все те же группы. Если игрок А выбрал не центр, то В выбирает центр и убирает гостя А, если А выбрал центр, то В даьлше выбирает центр и тп. Рассмотрим моменты когда:

1) Если после хода В осталась лишь 0 нетронутых групп, тогда у нас 33 гостя и стабильное положение.

2) Если после хода В осталась лишь $1$ нетронутая группа, значит на доске сейчас $32$ гостя, причем каждый в центре. Если игрок А выбирает не по в оставшейся группе, то В выбирает по центру и у нас опять случай 1)

Если игрок А все таки выбрал центр, то В выбирает в рандомной группе число (оно не в центре, ведь все центры заняты). На любой ход (кроме одного) у В есть reverse-ход, поэтому игрок А увеличивает количество гостей до $34$, затем В наконец-то закрывает центр последней группы, оставляя кол-во гостей, равным $34$. Поскольку у нас стабильное расположение, то игрок В сможет не увеличивать кол-во гостей, гг