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

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

Условие

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

а) [latex]N=5, k=4[/latex]; б)[latex]N=76, k=10[/latex]; в)[latex]N=199, k=12 [/latex];

Решение

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

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

[latex]a, … , d, …, b, … , c[/latex]

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

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

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

qunt
 

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

Добавить комментарий для Igor Mazurok Отменить ответ

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