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 ДБАММГ