Борьба с коррупцией

[fortpost]

В одном криминальном царстве, слаборазвитом государстве король решил начать борьбу с коррупцией и для примера наказать одного из своих министров. Министров (всего их было 55 человек) рассадили за круглым столом. Сначала хотели найти того из них, у кого больше всего денег на банковском счету, и объявить его главным коррупционером. Однако оказалось, что конституция страны разрешала открыть банковские счета для выявления количества денег не более чем у десяти министров. По мнению Главного юриста, можно объявить коррупционером любого министра, у которого на банковском счету больше денег, чем у каждого из его двух соседей (по одному слева и справа). Каким образом можно наверняка найти соответствующего этим условиям министра, не нарушая при этом основной закон страны? (Можно считать, что суммы на счетах у министров различны.)

[fortpost]

Что, никак не решается? Ответ уже давать?

[Валерий]

Что, никак не решается? Ответ уже давать?

А я и не видел задачу. С ответом лучше подождать

[Sirion]

Я с этой новой работой всё никак не найду времени дорешать... Погоди с ответом, сегодня вечером займусь.

[снн]

Если попорядку открыть первые 10 счетов - выявится только 1 с наибольшей ( т.к. по условию суммы не повторяются), даже, если это крайний порядковый номер без соседа ( по условию задачи "можно", а не  "нужно").  Выявив большую сумму, министра - оставить за столом, 9терых выгнать,а счета закрыть. Затем по кругу попорядку открыть опять 10 счетов - выявить одного, выгнать 9 и закрыть. И так из 10-ок выявятся 5 министров и 5 непроверенных. Открыть счета этих оставшихся и сравнить их.

[BIVES]

Попробую описать решение.
Занумируем министров номерами 1-55.
1,2 Смотрим счет министра с номером 55 и 28. Допустим у министра с номером 55 счет больше (если меньше, то все будет аналогично).
3 Открываем счет министра под номером 10.
Если его счет окажется больше чем счет 55, то мы будем искать корупционера среди
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27, а если у 55 счет больше чем у 10, то мы будем искать корупционера среди
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 1 2 3 4 5 6 7 8 9.
Так как во втором случае кандидатов в корупционеры больше будем считать, что нам не повезло и счет у 55 больше чем у 10 (иначе задача решается проще).
4 Открываем счет у 45. Если его счет окажется больше чем счет 55, то мы будем искать корупционера среди
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54, а если у 55 счет больше чем у 45, то мы будем искать корупционера среди 46 47 48 49 50 51 52 53 54 55 1 2 3 4 5 6 7 8 9.
Будем считать, что нам не повезло и счет у 45 больше чем у 55.
5 Открываем счет у 38. Если его счет окажется больше чем счет 45, то мы будем искать корупционера среди
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44, а если у 45 счет больше чем у 38, то мы будем искать корупционера среди 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54. Так как эти задачи равносильные будем для определенности считать, что у 45 оказалось денег больше.
6 Открываем счет у 49. Если его счет окажется больше чем счет 45, то мы будем искать корупционера среди
46 47 48 49 50 51 52 53 54, а если у 45 счет больше чем у 49, то мы будем искать корупционера среди
39 40 41 42 43 44 45 46 47 48.  Будем считать, что нам не повезло и счет у 45 больше чем у 49.
7 Открываем счет у 42. Если его счет окажется больше чем счет 45, то мы будем искать корупционера среди
39 40 41 42 43 44, а если у 45 счет больше чем у 42, то мы будем искать корупционера среди
43 44 45 46 47 48. Так как эти задачи равносильные будем для определенности считать, что у 45 оказалось денег больше.
8 Открываем счет у 44. Если его счет окажется больше чем счет 45, то открываем счет у 43 и задача решена (так как он будет либо больше чем счет у 44, а значит, больше чем и 42, либо меньше чем счет у 44 и тогда у 44 денег больше чем у 43 и у 45).  Если у 45 счет больше чем у 44, то мы будем искать корупционера среди 45 46 47 48.
9 Открываем счет у 47. Если его счет окажется больше чем счет 45, то открываем счет у 48 и задача решена. Если у 45 счет больше чем у 47, то открываем счет у 46 и задача решена.

[fortpost]

А это авторское решение.
Показать скрытый текст

Заметим, что 55 —как раз 11-й член последовательности Фибоначчи. Пусть каждому министру соответствует точка на окружности. Будем называть длиной дуги, соединяющей две отмеченные точки окружности, число маленьких дуг, не содержащих отмеченных точек на этой дуге. А за расстояние между двумя отмеченными точками возьмем длину наименьшей дуги, их соединяющей. Выберем сначала две точки А и В на расстоянии 21. Вся окружность оказалась разделенной на две дуги длиной 21 и 34. Если банковский счет у В больше, чем у А, то на большей дуге, соединяющей А и В (ее длина 34), берем точку С на расстоянии 13 от В. Если теперь самый большой банковский счет у С, то следующим мы рассматриваем счет министра, расположенного на дуге СА на расстоянии 8 от СВ другом случае рассматриваем министра на дуге ВА на расстоянии также 8. Продолжая таким образом нашу процедуру в соответствии с последовательностью Фибоначчи, мы сможем выявить «коррупционера», оставаясь в рамках конституции. В общем случае, когда число министров равно (n + 1)-му члену последовательности Фибоначчи, нам потребуется n операций.

[BIVES]

fortpost  крутое у вас решение.
Тут, конечно, по-видимому может быть несколько решений, но ваше самое красивое.
Где вы вообще берете такие задачи ?

[fortpost]

fortpost  крутое у вас решение.
Тут, конечно, по-видимому может быть несколько решений, но ваше самое красивое.
Где вы вообще берете такие задачи ?

Ну, решение-то не мое. Стырил из книжки.
Из разных источников. Что-то из литературы, что-то в инете откапываю.