Задача из журнала «Квант» (1997, №4)
Условие
Имеются N карточек, на которых написаны различные(неизвестные) числа. Они расположены на столе по кругу числами вниз. Надо найти три какие-нибудь лежащие рядом карточки такие, что число, написанное на средней карточке, больше, чем на каждой из двух соседних. При этом разрешается перевернуть последовательно не более k карточек. Докажите, что это возможно, если:
а) N=5,k=4; б)N=76,k=10; в)N=199,k=12;
Решение
а) «Откроем» среди 5 чисел, расположенных по окружности, два числа a<b, стоящих на расстоянии 2 друг от друга, и еще одно, соседнее с большим из них — c. Из соображений симметрии, можно считать, что [latex]c 79, f_{12}=223 > 199,[/latex] это даст решения задач б) и в). Для этого докажем сначала индукцией по k, что в рядуa,…,b,…,c
из fk+fk−1+1=fk+1+1 чисел, где известны a,b,c, причем d— наибольшее и находится от a и c на расстоянии fk−1 и fk−2, можно найти нужную тройку за k−1 попытку. Для k=2(для ряда из четырех чисел a,b,.,c) это очевидно. Пусть вплоть до некоторого значения k−1 то доказано. Рассмотрим данный ряд и «откроем» число d, находящееся на расстояниях fk−1 от a и fk−2 от b:
a,…,d,…,b,…,c
Если d>b, то мы можем применить предположение индукции к fk+1 числам a,…,d,…,b,а если d<b — то к числам d,…,b,…,c: за k−2 попытки среди них найдется нужная тройка.
Теперь среди fk=fk−1+fk−2=2fk−2+fk−3 чисел по окружности достаточно «открыть» два числа a<b на расстоянии fk−2 и число c, находящееся на расстоянии fk−2 от a и fk−3 от b. По соображениям симметрии, можно считать, что b>c. По доказанному выше, среди идущих подряд fk−2+fk−3+1=fk−1+1 чисел a,…,b,…,c за k−3 попытки можно найти нужную тройку.
В. Протасов, А. Заславский
— Не придумали название для задачи
— Не подключили публикацию на страницу задач http://ib.mazurok.com/kbaht/
— Нет SVG