Эйлер атындағы олимпиада, 2020-2021 оқу жылы, аймақтық кезеңнің 1 туры

Петя мен Вася келесі ойын ойнауда. Вася бір қатарға 150 тиынды тізіп шығады: олардың кейбіреулерін «бүк»-пен жоғары қаратып, кейбіреулерін «шік»-пен жоғары қаратып қояды. Петя өз жүрісінде кез келген қатар орналасқан үш тиынды көрсете алады, содан кейін Вася өз қалауынша осы үш тиынның екеуін аударуы керек. Петя тиындардың мүмкін болғанша көбірегі «шік»-пен жоғары қарап жатқанын қалайды, ал Вася оған кедергі жасағысы келеді. $k$ санының қандай ең үлкен мәнінде, Петя Васяның жүрісіне қарамастан, кемінде $k$ тиын «шік»-пен жоғары қарайтындай етіп жасай алады? ( С. Берлов, Н. Власова )

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

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 74.
Решение. Покажем, как Петя может обеспечить 74 «решки». Разобьем все монеты на пары идущих подряд. На $k$-ом шаге $(1 \le k \le 74)$ Петя смотрит на монеты в паре $(2k-1, 2k).$ Если среди них есть хотя бы одна решка, то переходит к следующему шагу. Если среди них нет решки, то Петя указывает на тройку $(2k-1, 2k, 2k+1),$ после чего в этой паре появляется хотя бы одна решка. Таким образом, через 74 шага в каждой паре монет, кроме последней, будет хотя бы одна решка, то есть решек будет не менее 74.
   Покажем, как Вася может помешать положить больше 74 «решек». Вначале он кладет орлом вверх все монеты с нечетными номерами, а также монету 150, а все остальные монеты — решкой. Далее он разбивает монеты с номерами 2-149 на пары подряд идущих. Среди любых трех монет, на которые может указать Петя, две монеты обязательно будут из одной пары. Именно их Вася и переворачивает. При такой игре Васи монеты 1 и 150 всегда будут лежать орлом вверх, а в каждой его паре будет ровно один орел и одна решка.