М1605 О поиске нужной тройки

Задача из журнала «Квант» (1997, №4)

Условие

Имеются N карточек, на которых написаны различные(неизвестные) числа. Они расположены на столе по кругу числами вниз. Надо найти три какие-нибудь лежащие рядом карточки такие, что число, написанное на средней карточке, больше, чем на каждой из двух соседних. При этом разрешается перевернуть последовательно не более k карточек. Докажите, что это возможно, если:

а) N=5, k=4; б)N=76, k=10; в)N=199, k=12 ;

Решение

а) «Откроем» среди 5 чисел, расположенных по окружности, два числа a < b, стоящих на расстоянии 2 друг от друга, и еще одно, соседнее с большим из них — c. Из соображений симметрии, можно считать, что c <b> 79, f_{12}=223 > 199, это даст решения задач б) и в). Для этого докажем сначала индукцией по k, что в рядуa, ... ,b, ... ,c

из f_k + f_{k-1}+1= f_{k+1} + 1 чисел, где известны a, b, c, причем d - наибольшее и находится от a и c на расстоянии f_{k-1} и f_{k-2}, можно найти нужную тройку за k-1 попытку. Для k = 2(для ряда из четырех чисел a, b, ., c) это очевидно. Пусть вплоть до некоторого значения k-1 то доказано. Рассмотрим данный ряд и «откроем» число d, находящееся на расстояниях f_{k-1} от a и f_{k-2} от b:

a, ... , d, ..., b, ... , c

Если d > b, то мы можем применить предположение индукции к f_k + 1 числам a, ... , d , ... , b, а если d < b — то к числам d, ... , b, ... , c : за k-2 попытки среди них найдется нужная тройка.

Теперь среди f_k = f_{k-1} + f_{k-2} = 2f_{k-2} + f_{k-3} чисел по окружности достаточно «открыть» два числа a < b на расстоянии f_{k-2} и число c, находящееся на расстоянии f_{k-2} от a и f_{k-3} от b. По соображениям симметрии, можно считать, что b > c. По доказанному выше, среди идущих подряд f_{k-2} + f_{k-3} + 1 = f_{k-1} + 1 чисел a, ... , b, ... , c за k-3 попытки можно найти нужную тройку.

В. Протасов, А. Заславский

qunt
 

М1605 О поиске нужной тройки: 1 комментарий

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *