головоломка про 8 шприков бильярдных

Ну что, пятниццо наступило... Понеслось дальше? ;)


Начальник полиции пришел к королю с докладом.
- Из надежных источников мне стало известно, Ваше величество, что вчера ваш младший брат пригласил к себе всех ваших министров и предложил им по миллиону золотых, если они согласятся устроить дворцовый переворот и свергнуть Вас с престола. К счастью, большинство министров выступило против этой идеи. Но теперь Ваш брат точно знает, какие министры Вам верны и будет пытаться избавиться от них.
- Но какие именно министры мне верны, а какие нет?!!! - вскричал король.
- Это мне неизвестно, - отвечал начальник полиции.
- Ну так узнайте это срочно! Даю вам месяц на расследование. Если через 30 дней вы мне не представите точной информации про каждого министра, я отдам вас своему палачу! Уж он то не предатель!

Даже начальнику полиции тяжело добиться встречи с министром. По закону в течение одного дня он может встретиться лишь с одним министром и задать ему лишь один вопрос. При этом вопрос должен быть таким, на который министр может ответить "да" или "нет". Вопрос должен допускать однозначный ответ (да или нет). Начальник полиции знает, что честные министры будут отвечать на вопросы правдиво, тогда как продажные могут либо говорить правду, либо лгать, чтобы запутать следствие.

Всего у короля 21 министр. Известно, что более половины министров честны. Нужно про каждого министра узнать, честен он или продажен, потратив на расследование не более 30 дней. Как быть?

P.S. Министрам известно о честности/продажности других министров.

Решил для 3-х министров Принцип ясен, для составления прогрессии не хватает времени и мозгоFF

Цитата:

от: Митрич16
Решил для 3-х министров... Принцип ясен, для составления прогрессии не хватает времени и мозгоFF...

А мне вот не хватило исключительно второго :D :D :D Соотвественно, решение не мое, так что ежели что не так - чур сильно не бить:

Для 2N+1 министров существует алгоритм опроса, требующий не более 3N вопросов. Соответственно, для 3 министров - 3 вопроса, для 5 - 6, для 7 - 9, для 9 - 12.

Алгоритм проще проиллюстрировать на конкретных примерах.

(1) 3 министра (M1,M2,M3)
Шаг 1
Спрашиваем M2 о честности M1. Если ответ "да", то значит М1 честен, если "нет", то M3 честен.
Шаг 2
Задаем честному министру 2 вопроса о честности всех остальных

(2) 5 министров (M1,M2,M3,М4,М5)
Шаг 1
Спрашиваем M2 о честности M1. Если ответ "да", то переходим к шагу 2. Если ответ "нет", то значит среди M1 и М2 один точно продажен, а значит среди (M3,М4,М5) не более чем 1 продажный министр. Задача сводится к задаче (1) для трех министров (M3,М4,М5). Решаем ее, а затем задаем честному министру 2 вопроса о честности M1 и M2.
Шаг 2
Спрашиваем M3 о честности M1. Если ответ "да", то М1 честен. В этом случае переходим к шагу 3. Если ответ "нет", то среди (M2,М3) один точно продажен, причем когда мы определим, честен ли на самом деле М1, мы узнаем, кто из (M2,M3) соврал. Задача сводится к задаче (1) для (M1,M4,M5). Решаем ее, а затем задаем честному министру 1 вопрос о честности M2 или M3.
Шаг 3
Задаем честному министру M1 4 вопроса о честности всех остальных

(3) 7 министров
Шаг 1
Спрашиваем M2 о честности M1. Если ответ "да", то переходим к шагу 2. Если ответ "нет", то задача сводится к задаче (2) для (M3,М4,М5,M6,M7). Решаем ее, а затем задаем честному министру 2 вопроса о честности M1 и M2
Шаг 2
Спрашиваем M3 о честности M1. Если ответ "да", переходим к шагу 3. Если ответ "нет", то задача сводится к задаче (2) для (M1,М4,М5,M6,M7). Решаем ее, а затем задаем честному министру 1 вопрос о честности M2 или M3
Шаг 3
Спрашиваем M4 о честности M1. Если ответ "да" (то есть M1 - честный), переходим к шагу 4. Если ответ "нет", то задача сводится к задаче (2) на Шаге 2 для (M1,М2,М5,M6,M7). Решаем ее, а затем задаем честному министру 1 вопрос о честности M3 или M4
Шаг 4
Задаем честному министру M1 6 вопросов о честности всех остальных

Теперь уже несложно написать общее решение.

(N) 2N+1 министров
Шаг 1
Спрашиваем M2 о честности M1. Если ответ "да", то переходим к шагу 2. Если ответ "нет", то задача сводится к задаче (N-1) для (M3,...,M_{2N+1}). Решаем ее, а затем задаем честному министру 2 вопроса о честности M1 и M2
Шаг 2
Спрашиваем M3 о честности M1. Если ответ "да", переходим к шагу 3. Если ответ "нет", то задача сводится к задаче (N-1) на Шаге 1 для (M1,М4,M5,...,M_{2N+1}). Решаем ее, а затем задаем честному министру 1 вопрос о честности M2 или M3
Шаг 3
Спрашиваем M4 о честности M1. Если ответ "да", переходим к шагу 4. Если ответ "нет", то задача сводится к задаче (N-1) на Шаге 2 для (M1,М2,М5,M6,...,M_{2N+1}). Решаем ее, а затем задаем честному министру 1 вопрос о честности M3 или M4
......
Шаг K
Спрашиваем M_{K+1} о честности M1. Если ответ "да", переходим к шагу K+1. Если ответ "нет", то задача сводится к задаче (N-1) на Шаге K-1 для (M1,М2,..., M_{K-2},M_{K-1},M_{K+2},M_{K+3},...,M_{2N+1}). Решаем ее, а затем задаем честному министру 1 вопрос о честности M_K или M_{K+1}
......
Шаг N+1
Задаем честному министру M1 2N вопросов о честности всех остальных

А что еще про роботов не было ответа? Тогда вот:
Изначально им показали 16 синих и 8 красных.
Разберем логику роботов с синими лампочками - они видят 6 синих и 5 красных лампочек.
Их правильный ответ в четвертый раз (собственно "не дожидаясь четвёртого вопроса - все равно не делает ответ третьим :) ") базировался на том, что если бы некий робот (на самом деле каждый с синей лампочкой) видел бы 6 краных лампочек, то он ответил (у него было бы достаточно информации ответить) бы в 3-ий раз.
Когда это может произойти? Представим робота видящего 5 синих и 6 красных, ясно бы что его ответ в третий раз базировался бы на том, что если бы на нем была красная лампочка, то с его точки зрения некий робот (каждый из 5 с синей лампочкой) ответили про свой цвет со второго раза. Когда это может случиться? Да когда некий робот видит уже 4 синих и 7 красных и знает что с первого раза никто не ответил - А ответить с первого раза могли только те роботы, которые сразу видели ВСЕ показанные первоначально красные лампочки (т.е. те самые 8 штук).

для 3-х достаточно 2-х вопросов ;)

оживим. для кого-то, скорее всего фигня, но для меня стало полной неожиданностью. вполне реальная быль.
Дано: фонтан в виде гранитного шара весом под тонну. Вопрос: какой мощности должен быть водяной насос, чтобы заставить этот шар вращаться в воде. Подшипники пр. приблуда не применяется.

в смысле - напор воды должен держать шар "навесу"?

Цитата:

от: no ifs no buts
в смысле - напор воды должен держать шар "навесу"?

да, в комплексе с самой "подставкой", но держится на воде.

Цитата:

от: stoler
да, в комплексе с самой "подставкой", но держится на воде.

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

шар диаметром прим. 70-80см. Правильно, вся фишка в "чаше", но размеры небольшие.

А КПД насоса какой?

Цитата:

от: Годзи
А КПД насоса какой?

обл... откуда я знаю? какой-то серийный.

Цитата:

от: stoler
обл... откуда я знаю? какой-то серийный.

А как тогда мощность посчитать, если мы можем прикинуть необходимое ПД, а К мы не знаем?

Цитата:

от: Годзи
А как тогда мощность посчитать, если мы можем прикинуть необходимое ПД, а К мы не знаем?

ну дай с разбросом в три версты. пусть даже кпд 100. в принципе, какой кпд у насоса Ручеек? такой и посчитай.

Цитата:

от: Годзи
А как тогда мощность посчитать, если мы можем прикинуть необходимое ПД, а К мы не знаем?

а зачем нам знать кпд? достаточно - эффективную мощность. а сколько солярки сгорит - вопрос другой

зы. примерно сейчас сказали- около 40см посадочное "очко".

Цитата:

от: no ifs no buts
а зачем нам знать кпд? достаточно - эффективную мощность. а сколько солярки сгорит - вопрос другой

А на насосах разве эффективную пишут? А не пожираемую?

Цитата:

от: Годзи
А на насосах разве эффективную пишут? А не пожираемую?

не, ну что-то про выходные параметры должны писать.

Цитата:

от: Годзи
А на насосах разве эффективную пишут? А не пожираемую?

Вообще-то нужно получить литры в секунду - вне зависимости от диаметра шара и чаши.
У меня очень грубые умозрительные оценки дают результат около 30000 литров воды в секунду...
Это, конечно, ошибка, где-то я лопухнулся...

Цитата:

от: stoler
зы. примерно сейчас сказали- около 40см посадочное "очко".

ну, примерно так можно рассуждать (очень грубо) - давление к краям будет падать, причем, довольно быстро, если не подгонять идеально форму чаши к форме шара. ну, скажем, сантиметров 10 на 10 эффективных будет. от есть, плошадь 0.01 м2. давление, что держало тонну 1000кг/0.01м2 - примерно атмосфера. как это связано с мощностью насоса - не знаю, у него, небось какие-то характеристики этого плана должны быть.