Задача на сообразительность.

[Cash]

ole-ole-ole в сообщении #1036325 писал(а):

Да, это ситуация простая. А как все-таки следует делать изначально? Группу из 4 проверить, а потом оставшиеся?

Ну нельзя же быть таким рохлей. Самому никак не проверить? Где попытки решения?

[ole-ole-ole]

grizzly в сообщении #1036324 писал(а):

Я бы для уровня ТС за основополагающее равенство предлагал $7=2+2+2+1$. Проверять 3 пары, потом действовать по обстоятельствам. Тогда бы количество различных вариантов допустить ошибку уменьшилось бы в несколько раз.

ок, берем 3 пары из всех.

Возможные варианты

фнн
нфн
ннф
ффн
нфф

Берем первый вариант. Если фнн, то один или два шара фонят в первой паре. Берем последний (внепарный шар) и проверяем его. Если не фонит, то первая пара будет фонящих. Если фонит, то придется еще одну проверку одного из шаров первой пары произвести. В худшем случае, в первом варианте будет 5 проверок.
Второй и третий рассматривается аналогично, все там симметрично.
Четвертый вариант. Сразу понятно что по одному фонящему шару в первой и второй паре. Фозможные варианты:
фннф (а)
нффн (б)
фнфн (в)
нфнф (г)
Берем первый шар первой пары. Проверяем. Берем первый шар второй пары -- проверяем. Полученный результат можно быстро понять, выбрав из (а),...,(г).
Верно?

[iancaple]

Хочу подчеркнуть в принципе, что число вариантов полезно считать на каждом шаге, а не только для оценки снизу.Сравним три способа первой проверки.
1. Проверяется группа из 1 шара, если "да"(фонят), то 6 вариантов, если "нет" то $C^2_6=15$
2. Проверяется группа из 2 шаров, если "да" то 11 вариантов, если "нет" то $C^2_5=10$
3. Проверяется группа из 3 шаров, если "да",то 15 вариантов, если "нет" то $C^2_4=6$
За 4 проверки распознать 15 вариантов (когда max 16) -я не завидую тем участникам, которые предлагали начать с 1 или 3-х шаров.
Grizzly предложил начать с двух, потом еще два, тут я согласен лишь наполовину. Начинаем с двух, но при ответе "да" следующая проверка обязательно одного из шаров этой пары. Если "нет", то с парой все ясно, если "да", то другой шар может быть любым, остается за 3 проверки найти один шар из 6-ти, это возможно...

[ole-ole-ole]

Cash в сообщении #1036334 писал(а):

ole-ole-ole в сообщении #1036325 писал(а):

Да, это ситуация простая. А как все-таки следует делать изначально? Группу из 4 проверить, а потом оставшиеся?

Ну нельзя же быть таким рохлей. Самому никак не проверить? Где попытки решения?

Вот, это было на предыдущей странице!!!

ole-ole-ole в сообщении #1036308 писал(а):

Можно пойти по-другому.
Взять просто группу из четырех и группу из трех. Каждую из этих групп сразу проверяем прибором.
1.Если фонит только группа из четырех, то то там еще за 3 испытания найдем нужные шары (всего 5 испытаний).
2.Если фонит только группа из трех, то за два испытания определим их (всего 4 испытания).
3.Если фонит и та, и та группа. То по одному фонящему шару в каждой.
В четверке можно фонящий шар за три испытания найти. Во тройке за два. Итого 7 испытаний. Что-то много.

[Cash]

Вам же сказали, что 5. Ну ищите за 5.
Или мозги одноразовые - на один выстрел хватает?

[Nemiroff]

ole-ole-ole в сообщении #1036335 писал(а):

Верно?

Ну короче: три проверки на три пары. Нашли либо две пары, либо одну пару. Если две пары, то ещё две проверки на один шарик из каждой пары. Если нашли одну пару, то одна проверка на один шарик из пары, вторая на седьмой, непарный.

У вас вроде то же самое написано, только слов дофига.

[ole-ole-ole]

Спасибо, действительно. Но как доказать, что меньше 5 нельзя сделать, пока что это не ясно.

[Nemiroff]

Ну вы же пополам каждый раз делите число вариантов. А вариантов 21.

[ole-ole-ole]

Nemiroff в сообщении #1036369 писал(а):

Ну вы же пополам каждый раз делите число вариантов. А вариантов 21.

А не 22 ли варианта? В смысле на два каждый раз делю?
1100000 (1)
0110000 (2)
0011000 (3)
0001100 (4)
0000110 (5)
0000011 (6)
1000001 (7)
1000010 (8)
1000100 (9)
1001000 (10)
1001000 (11)
1010000 (12)
0100001 (13)
0100010 (14)
0100100 (15)
0101000 (16)
0010001 (17)
0010010 (18)
0010100 (19)
0001001 (20)
0001010 (21)
0000101 (22)

[Nemiroff]

Нет, не 22.
В прямом. Ну представьте дерево ваших проверок. Если у него пять слоев, то внизу у него 32 вершинки. И на эти 32 вершинки есть 21 вариант, так что иногда будут повторения, на разные проверки получаются одни и те же номера шариков. Это не страшно. А если четыре слоя, то ответов 16 — в принципе может быть при процедуре не более 16 различных ответов. А вам нужно как минимум 21.

[ole-ole-ole]

Хорошо, спасибо! А почему, все-таки 21?))

[Nemiroff]

Потому что $\frac{n(n-1)}{2}$. Какой из ваших вариантов лишний, искать не буду.

[amon]

Nemiroff в сообщении #1036298 писал(а):

Но подход у levtsn ошибочный. Потому что по такой логике для распознавания 2 из 6 должно хватать четырёх проверок. А не хватит.

В защиту levtsn'a.

ole-ole-ole в сообщении #1036236 писал(а):

Но как доказать, что число 5 нельзя уменьшить?

levtsn в сообщении #1036238 писал(а):

Всего возможно 21 исход. Это более 4 бит информации. Следовательно 4 проверками узнать исход невозможно.

К стати, а как доказать, что для распознавания 2 из 6 четырёх проверок не хватит? (Это чистый вопрос, без подковырок. Я чего-то туплю здесь)

[Nemiroff]

amon в сообщении #1036421 писал(а):

К стати, а как доказать, что для распознавания 2 из 6 четырёх проверок не хватит? (Это чистый вопрос, без подковырок. Я чего-то туплю здесь)

Ну да, так наивно не пройдёт, потому что там 15 вариантов.
Вы когда первый раз проверяете, вы берёте кучку из $1$, $2$, $3$ или $4$ шариков. Вот если не щёлкнуло, то у вас осталось соответственно $5$, $4$, $3$ и $2$ шарика с двумя плохими, а значит осталось $10$, $6$, $3$ и $1$ вариант. А если щёлкнуло, то остались все остальные $15-n$ вариантов, то бишь $5$, $9$, $12$, $14$ вариантов. А значит, какую бы вы кучку изначально не взяли, у вас после первой проверки останется пара вариантов щёлкнуло — не щёлкнуло, где одно число из пары больше $8$. А значит за оставшиеся три проверки определить не удастся.

[amon]

(Оффтоп)

Nemiroff в сообщении #1036430 писал(а):

Ну да, так наивно не пройдёт, потому что там 15 вариантов.

Спасибо! Пошел думать, как это связано с парадоксом Гиббса, и связано ли вообще.