В одном криминальном царстве, слаборазвитом государстве жил-был король. Однажды он решил провести борьбу с коррупцией и в качестве показательной меры уволить одного из своих 199 министров. Всех этих министров пригласили во дворец короля и рассадили за большим круглым столом. Сперва хотели уволить министра, имеющего самый большой банковский счет. Однако заняло бы это достаточно много времени, поскольку для проверки банковского счета одного человека требуется 20 минут. Король же повелел выявить главного коррупционера в течение 4 часов, пока он принимает различные лечебные процедуры в сауне. По мнению главного советника короля, уволить можно любого министра, лишь бы для этого нашлось достаточное юридическое обоснование. Главный юрист королевства предложил считать главным коррупционером любого из министров, сидящим за круглым столом, у которого банковский счет больше, чем у обоих его соседей (слева и справа).
Доказать, что за 4 часа наверняка можно найти министра, удовлетворяющего этому условию. (Банковские счета министров проверяются последовательно, т.е. в отведенное время можно проверить не более 12 банковских счетов. Предполагается также, что все банковские счета различны.)

Решения задачи я не знаю. Дихотомия тут не проходит.

Ээээ... Навскидку даже скажу, что доказательство не существует, ибо задача не решается ГАРАНТИРОВАННО, а только вариантно:
Предполагается также, что все банковские счета различны - предположим, что счета идут от 1 енота до 199 енотов, министры совершенно случайно сели последовательно - т.е. по кругу от 1 до 199. В таком случае задача не имеет решение вообще - то есть нет министра у которого счёт больше, чем у соседей. Ибо даже последний будет
199 = 198 + 1. Т.е. не больше, а равно.

(2) вово

(2)Окружность и кольцо - это разные вещи. Имеющий 199 будет богаче обоих своих соседей. Или же если вы имеете ввиду что он должен быть богаче их в сумме, то я уверен, что подразумевается богаче каждого по отдельности.

(2) Видимо больше чем у соседа слева и больше чем у соседа справа

Короче тут сортировка нужна продвинутая, я кроме пузырька ни одной не помню ))

не, тут надо отбрасывать тех, у кого слева или справа меньше.
Но шаг 1 по любому такой - взять и взвесить любого чувака (кольцо-то).
Ну для определенности с номером 1.

далее остается еще 11 из 198 вариантов

(8) Тут хитрее, ищем-то не самого богатого, а того, кто богаче любого из соседей, тогда решаемо, если покумекать...

(9) Жаль, что пересаживать нельзя, задача решалась бы за час.

(9) Не любого, а обоих

А может часть министров выгнать из-за стола? И из оставшихся выбрать по параметрам юриста.

(12) логично... оставляем трех... три взвешивания - и вуаля

если мы померили чувака, это нам ни очем не говорит, т.к. у его соседа слева и справа счет может быть больше, чем у него.

если мы померили двух соседей, это тоже ничего не говорит, т.к. у соседа максимального из них двоих счет может быть больше, единственно, что в результате измерения двоих соседей мы можем отшить минимального...

(12) Можно и не выгонять, просто видимо задача решается в цепочке из 12 чисел, пусть и разорванной

+(15) Не, ни фига, простейший ряд от 1 до 12 и нет решения

+(9) Брр.. Не любого а каждого из соседей. Таким образом если они по весу подряд сидят от 1 до 199 надо искать у кого 199, за 12 итераций. Все та же продвинутая сортировка, которых не помню...

(0) Уточни, министр должен быть богаче ОБОИХ в сумме, или богаче каждого по отдельности?

(18)Обоих в сумме - легко доказать, что решения нет, см. (2)

(18) Дык что так что этак, если обоих в сумме, посади подряд и задача не решаема. Если каждого в отдельности, посади подряд и нужно найти максимум из 199 за 12 итераций, тоже чет сомнительно..

(0) А может быть ты ошибся, и там было 19 министров?..

Делить на три части окружность, один будет самым богатым, отсекаем треть 1/3*1/3*1/3... 199/3*6 сработает...

Ну как-то так, круг-то рассекаем, с крайними надо думать, но неохота. Засада если у них бабок одинаково...

(22) не понял(((

(18, 21). Богаче соседа слева и богаче соседа справа. Конечно, не в сумме. Министров точно 199. Задача, как мне сказали, была на 3-й Соросовской Олимпиаде для школьников (!) в 199х году.

(22,23)По условию не может быть одинаково, но также в условии нет возрастания. Министры не по возрастанию дохода расположены, а случайным образом. Склоняюсь к (21)

(23). Бабок одинаково быть не может по условию. Смотри уточнение в скобках в (0).

(27) да увидел уже... даже уже решил в уме... договорю по трубе - напишу...

Делаем на круге 4 замера и определяем самого богатого из троих соседних, оставляем половину, которая рядом с ним - 67 в худшем раскладе - ЧЕТЫРЕ замера
мин1-макс-мин2, никто не будет спорить, что среди этих 67ми найдется один, который богаче соседей?
67 делим на 4 части, центр и крайние известны - ДВА замера. там найдется МахХ и рядом МинY и МинZ, никто не будет спорить? остается 34 в плохом раскладе
34 делим на 4 части ДВУМЯ замерами 17
17 дробим = 9 ДВА замера
9 дробим = 5 ДВА замера
в пяти уже просто определим недостающих...
итого ДВЕНАДЦАТЬ ЗАМЕРОВ

(+29) ну рассекаем симметрично конечно всегда.... а когда нечет, то чуть в сторону...

(29)Я буду спорить. Вполне может быть, что нет никого богаче. Закономерности в рассадке нет.
Полагаю, что задача нерешаема. Возьмем для простоты не 199, а 13 министров, сделаем замеры по 12 из них. Берем худший вариант - лесенку. По имеющимся данным мы не можем сказать, будет ли оставшийся министр богаче остальных или беднее - то есть ответа мы не получили. При 199 задача еще усложняется, то есть общего решения иметь не будет.

(29)"Делаем на круге 4 замера и определяем самого богатого из троих соседних, оставляем ПОЛОВИНУ, которая рядом с ним"
что подразумевается по словом половина(это где-то 100)? ИЛИ четвертина(делили то на 4) это 50?  67 получиться если делать 3 замера а не 4...

(29)и  какую часть министров сидящих слева от самого богатого или справа?

(32, 33) Да, пивка выпил уже изрядно, делю на 6 вместо четырёх, счас пересчитаем...

Совсем легкая задача.
Вспоминаем золотое сечение, и смотрим что 1.6^12 почти триста.
А дальше дело техники...

Сначала смотрим 0-го и 100-го, потом в соотношении золотого сечения (ближе к наиболее богатому) делим отрезок от наиболее богатого к наиболее удаленному от него.

(35,36)В третий раз спрашиваю - разве они упорядочены?

Так, ошибся. Берем нулевого и 123-го.

(37) Среди тех кого мы уже проверили мы можем определить самого богатого?

(37) Для примера - для восьмерых министров решаем за пять телодвижений.
Смотрим нулевого и пятого. Если пятый больше то смотрим третьего, если нулевой больше, то смотрим второго. На бумаге легко проверить...

(40)
Ну смотрим. А там лесенка от нуля до пяти. Не догоняю.

За шесть телодвидений решаем тринадцать...
3 - 3
4 - 5
5 - 8
6 - 13
7 - 21
8 - 34
9 - 55
10 - 89
11 - 144
12 - 233... А у нас всего 199 :)

Смотри нулевого и пятого - пятый больше.
Смотрим третьего - пятый больше.
Смотрим шестого - шестой больше.
Смотрим седьмого... Их всего восемь - от нуля до 7.

NS, объясни как это может сработать на неупорядоченном кольце? по моему в каких пропорциях не бери - не сойдется..

Я алгоритм сказал (на восьми) предлагай раскладку на восьми чтоб алгоритм не выдал правильного...
Возьми восемь бумажек, размести на них числа от 0 до 7.
Размести их по кругу, проверяешь нулевого и пятого (первого и шестого), и далее по моему алгоритму - от наибольшего среди открытых в сторону более дальнего, в золотой пропорции, ближе к наиьбольшему...

(43)Спасибо, дошло, хоть и не сразу

Что-то я тоже недогнал:
Есть следующий порядок

1 2 3 4 5 6 7 8        министры
---------------
2 4 8 7 5 3 1 7        счета

Как считаем?

Смотрим первого и шестого
1 2 3 4 5 6 7 8
2 ? ? ? ? 3 ? ?
Больший шестой, смотрим в сторону наиболее удаленного среди открытых (1) в соотношении золотой пропорции, ближе к наибольшему. Это четвертый.
1 2 3 4 5 6 7 8
2 ? ? 7 ? 3 ? ?
Больший (4), смотрим в сторону наиболее удаленного среди открытых (1) в соотношении золотой пропорции, ближе к наибольшему. Это третий.
1 2 3 4 5 6 7 8
2 ? 8 7 ? 3 ? ?
Больший (3), смотрим в сторону наиболее удаленного среди открытых (1) в соотношении золотой пропорции, ближе к наибольшему. Это (2).
1 2 3 4 5 6 7 8
2 4 8 7 ? 3 ? ?
Третьего нах. За пять проверок с восьмью министарми разделались.

(42) ты традиционно гениален :)
ну надо же, ряд Фибоначчи, все же так просто... главное так близко был... эх...

С золотого сечения пришел к нему...
Изначально пришел к золотому.

(50) интересно, что натолкнуло?

Решал сверху. Рассматривал ситуацию когда в ряд три числа
(1)....(2)...(3)
И (2) из них большее.
Если расстояния (1)-(2) и (2)-(3) одинаковы,
то поделив оба отрезка пополам, за две попытки сокращем расстояние вдвое.
То есть получаем (1)-(1')-(2)-(2')-(3)
максимальным может быть только (1'),(2),(2') и соответственно приходим к структуре
(1)-(1')-(2), (1')-(2)-(2') или (2)-(2')-(3)

 Тут я сообразил что при золотом сечении за одну попытку сокращаем расстояние примерно в 1.6 раза (даже чуть больше), а 1.6^2 всяко больше двух.
(1)-------(2)----(3)
(1)----(1')--(2)----(3)
большее (1') либо (2)
Приходим к (1)----(1')--(2) либо (2')--(2)----(3)

Поняв как двигаться сверху, начал рассматривать задачу снизу - от минимального числа министров.

NS, объясни как это может сработать на неупорядоченном кольце? по моему в каких пропорциях не бери - не сойдется..

чето я не понял, если честно....
Мегамонстры!

(53) я тоже не догоняю

В (45) есть совет.
Их (52) можно понять почему в тройке подряд идущих чисел большее всегда будет в центре.
А вообще есть аналогичный метод поиска экстремума функции одной переменной -
http://www.opu.odessa.ua/konsp/MMXTP/RAZDEL5/glava573.htm

(56) Почему это в тройке подряд идущих чисел большее в центре?

1 2 3 - двойка не большее...

Не догоняю я ваш метод... Или мозгов не хватат или или... ;-)

Ха.... НС ты не прав...
Ты найдешь максимального из 12 чуваков, НО....
Если у его соседей будет хотя бы у одного больше бабок, его не уволят...
так что это не поиск экстремума... Незачет.

(58)
У меня есть подозрение что ты не прочитал условие задачи...
Нужно найти такого у которых всего два соседа беднее.

(57) Из трех чисел на окружности всегда можно поместить наибольшее в центре.
И тогда в тройке (1)-(2)-(3) наибольшее будет в центре.
А дальше в алгоритме после каждого шага расстояние сокращается более чем в 1.6 раз. И после каждого шага мы получаем тройку где наибольшее в центре.

(59) Два БЛИЖАЙШИХ соседа, по левую и правую руку, батенька!

(59) иначе можно было сделать только три измерения, ыггыгы...

(56) гениально!!!!
а я то , по тупости своей , пытался самого толстого из них найти(((

(60) Я могу представить что можно не понять решение без теста, я могу понять что не хватает воображения провести тест в уме. Но чтоб не понять что всё работает попробовав на восьми бумажках...
Смени ник, позоришь славное имя 1Сника :-))

Ближайших. Не переживай :)

Гений, глянь на пост (48) - всё подробно описано. Пошагово.
А в посте (42) написано максимальное число министров которое можно разрешить за разное число проверок.

(60,61) берём бумажку, ручку и проверяем

Смотрим первого и шестого
1234 5678
1234 5678

Больший шестой, смотрим в сторону наиболее удаленного среди открытых (1) в соотношении золотой пропорции, ближе к наибольшему. Это четвертый.
1234 5678
1??4 ?6??

Больший (6), смотрим в сторону наиболее удаленного среди открытых (1) в соотношении золотой пропорции, ближе к наибольшему. Это седьмой.
1234 5678
1??4 ?67?
Больший (7), смотрим в сторону наиболее удаленного среди открытых (1) в соотношении золотой пропорции, ближе к наибольшему. Это (8).
1234 5678
1??4 ?678

Гы…

И все равно не догоняю, как это работает.

Пять проверок нужно чтобы разобраться в 8-ю министрами, с чего ты взял, что за 12 проверок разберешься со 199? всего на три проверки больше и 199? Чето не веридцо...

(63) Давай тест на 199, с учетом (67). Не торопись с выводами. Гыгыгы..

5 из 8 не впечатляет...

(67) пардон, больше всего не 7 проверок...

Вот тебе контраргумент - для того, чтобы доказать вину министра, нужно ОБЯЗАТЕЛЬНО знать значение ДВУХ его соседей.
Учитывая полную неопределенность счетов министров, какие бы измерения мы не производили, всегда возможен вариант, когда в результате измерений мы будем попадать на министров, находящихся упорядоченно, я считаю, что задача не имеет решения.

проще всего это представить так.
НС называет мне номер министра, а я называю ему сумму счета, которая мне подходит. С таким раскладом НС никогда у меня не выиграет... за 12 ходов из 199.

т.е. если он мне называет министра без соседей, я ему говорю любую сумму.
Если он мне называет министра, у которого есть один сосед я называю ему сумму меньше, чем у соседа.
Если у министра есть два соседа, я называю ему сумму среднюю между этими двумя соседями...

Вот и все правила игры... Фиг выиграешь!

Хотя не, правила нужно уточнить, но суть от этого не меняется...

(73) Еще раз - смени ник :)
Перед сменой попробуй 13 министров за 6 попыток.

Гы, не НС видимо по ходу прав... задачка действительно решается методом половинного деления. Ладно, убедил.

(75) Не завидуй! ;-)

(76) Не половинного деления. А деления в соотношении золотой пропорции.

(78) Какая разница в этом случае?

(79) Огромная. Методом половинного деления за 12 попыток не найти.

(80) Да ладно... На своем примере из 8 ты юзаешь метод половинного деления...

то бишь когда ищещь следующую точку между а и б, делишь отрезок пополам, и если он поровну не делится, идешь в сторону наибольшего.

(81) Метод половинного деления дает решение на восьми министрах за ШЕСТЬ попыток.
(82) Чувствуются серьезные пробелы в математике. Метод золотого сечения это уже оказывается метод половинного деления с округлением если не делится? :)
восемь это тоже округленное 13 пополам? а 5 я так понимаю это округленное 8/2. А 34 это округленное 55/2?
 А скорость сходимости (1+SQRT(5))/2 ~ 1.618... Это наверняка округленная двойка :)))

(83)"Ты знал, ты знал!!!!"

По аське отправил знакомой девушке текст задачи...
Через несколько минут получил ответ

"Надя (12:20:26 24/10/2007)
ну проверить за 4 часа 12 министров и потом пересадить их так, чтоб получилось нужное условие"

А вы тут про математику говорите...

(85)собственно, в этом случае задачка решается за час))))

(84) О методе золотого сечения для поиска экстремумов я знал, но уже успел его забыть. Когда решал задачу просто решал уравнение чтоб соотношение длинного/короткого ребра при делении отрезка сохранялось (как в (52)). Вышел на квадратное уравнение, решил, и понял что открыл велосипед :)

NS, объясни как это может сработать на неупорядоченном кольце? по моему в каких пропорциях не бери - не сойдется..

Раз задачка давалась на олимпиаде, то это именно золотое сечение.
Причём налицо поиск локального экстремума.

(88) Ошибка - коммуникатор проглючило.

(0)
енто уж как повезет
всех нах уволить :)

Дык это ж математика, а там есть метод от противного.
Существует ли такое расположение министров (с их счетами) при котором решения не будет?
К примеру если у всех счета одинаковы?
Или министры сидят в порядке возрастания их счетов 1 2 3 ... 198 199 (и снова 1). Тогда 199 это нужный министр, но мы же не знаем о сортировке.

Короче решение такое. Все министры выходят из-за стола и начинаю тянуть жребий на очередность. За стол садятся всегда 3 министра. Вытянувший жребий садится за стол, а первый выходит из-за стола. После каждого изменения проверяем на условие (нужна только проверка счета новых министров).

(93)
см. (92)

блин ну вы ващеее
4 министра любых берем - проверяем и как нужно переставляем, при условии разных счетов - решение = 100 % =))))

+(95)
1ч20м - Кто быстрее уволит министра :)))

+(95)
ан нет гоню.
тут еще уровень важен

+(97)
колличество бабла на счете :
Например 1000000001 1000000002 1000000003 1000000004 1000000005 и т.д тогда решения вообще нет т.к. министров должно быть за 1000000000 :) Тоесть возможны какие то частные случаи, короче опять см. (92)

(0) в задаче не сказано что министры могут или должны пересаживатся

здесь именно докозательство товочто возможно за 12 проверок найти такого министра у которого счет больше чем у левого и больше чем у правого соседа при условии что все счета различны

(97) Проще так - убиваем любого, а 12 скидываются всеми имеющимися деньгами в пользу покойного, становятся по обе стороны от гроба, и самый богатый оказываетсяв середине, при чем уже мертвый. Очень удобно.

(99) Ещё как вариант - самый богатый двухсотый, ибо он - Президент.

Или Премьер...