Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, I тур регионального этапа

Петя и Вася играют в игру. Вася кладёт в ряд 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 всегда будут лежать орлом вверх, а в каждой его паре будет ровно один орел и одна решка.