ВсОШ 2021, 9 класс, задача 8
Сотне мудрецов предложили следующее испытание. Их по очереди (в заранее известном порядке) приводят в зал. В зале смотритель предлагает мудрецу на выбор каких-то два различных числа из набора . Мудрец выбирает ровно одно из них, сообщает выбранное число смотрителю и уходит из зала. При этом до своего выбора мудрец имеет право узнать у смотрителя, какое из чисел выбрал каждый из двух предыдущих мудрецов (второй мудрец имеет право узнать про первого). Во время испытания любое общение между мудрецами запрещено. Если в конце сумма всех чисел, выбранных мудрецами, окажется равной , то мудрецы провалили испытание; иначе они его выдержали. Докажите, что мудрецы могут заранее договориться о своих действиях так, чтобы гарантированно выдержать испытание.
(С. Берлов)
Ответ
Решение.
Приведем одну из возможных договоренностей. Каждый мудрец будет пользоваться одной из двух стратегий: либо выбирать из двух предложенных чисел нечетное (стратегия Н), либо выбирать из двух чисел большее (стратегия Б). Выбирать их они будут так:
(1) Первый мудрец действует по стратегии Б. Второй мудрец действует по стратегии Н, если первый выбрал тройку, иначе он использует стратегию Б.
(*) -й мудрец, при , действует по стратегии Н, если -й мудрец выбрал тройку, а -й - не тройку; иначе он использует стратегию Б.
(100) Сотый мудрец действует по стратегии Б, если -й выбрал тройку, а иначе - по стратегии Н. Проанализируем, что произойдет к моменту захода сотого мудреца. Выпишем в ряд выбранных к этому моменту чисел в порядке их выбора; пусть - их сумма. Если в ряду записана единица, то она была выписана по стратегии Н, поэтому прямо перед нее записана тройка, а прямо перед этой тройкой не может стоять другой тройки. Выделим в выписанном ряду эти тройку и единицу. Выделенные пары не пересекаются, сумма в каждой из них равна 4. Все остальные числа в ряду - либо двойки, либо тройки. Далее, если среди невыделенных чисел есть тройка, рассмотрим первую такую тройку. Либо она стоит в конце ряда (то есть ее выбрал -й мудрец), либо после нее не может стоять ни единица (иначе она выделена), ни двойка (по алгоритму (∗)). Поэтому после нашей тройки может стоять лишь тройка, и она тоже не выделена. Итак, либо все невыделенные числа - двойки (и ), либо среди них ровно одна тройка - последняя (и ), либо невыделенных троек хотя бы две (и ). В последнем
случае мудрецы уже выдержали испытание, ибо после хода последнего мудреца сумма превысит . Иначе мы получаем, что , если -й мудрец не назвал , и , если назвал. Согласно , в первом случае сумма выбранных чисел будет нечетной, а во втором она будет больше 200. Значит, и в этих случаях испытание пройдено.