Как лучше решать задачу о пяти батарейках?

[Ktina]

Есть пять батареек, из которых три заряжены, а две разряжены. Фотоаппарат работает от двух заряженных батареек. Покажите, как за четыре попытки можно гарантированно включить фотоаппарат.

Я предлагаю попарно проверить первые три батарейки (первую со второй, затем первую с третьей и, наконец, вторую с третьей).
Если среди этих трёх есть две заряженные, фотик заработает при одной из первых трёх попыток. Если нет, значит, 4-ая и 5-ая заряжены, поскольку всего заряженных - три. И тогда четвёртая попытка обязана оказаться удачной.

А вот авторское решение:

Цитата:

Вставим первую и вторую батарейки. Если фотоаппарат не работает, то либо одна из них разряжена, либо обе. Вставим теперь третью и четвёртую батарейки. Если фотоаппарат не работает, то:
1) одна из них разряжена,
2) из первых двух разряжена одна,
3) пятая батарейка точно работает.
Осталось проверить пятую батарейку в паре с каждой из первых двух.

Ваше мнение, у кого длиннее лучше?

[Dmitriy40]

Авторский вариант лучше: для проверки всех 10 возможных ситуаций он требует в сумме 23 попыток против 25 Ваших. Т.е. на большой серии испытаний в среднем должно требоваться меньше проверок. Но ИМХО это уже поиск блох, оба варианта достаточно хороши.
Как мне представляется, недостаток Вашего варианта в том, что обнаружив неисправную (-ые) батарейку в первой попытке Вы продолжаете её (их) проверять второй и третьей попыткой.
Похоже авторский вариант вообще оптимальный, меньше 23 попыток и не получится.

[ET]

Имхо авторский и ваш вариант одинаковые
Только авторсикй с вашим задом наперед
Модифицируйте ваш следующим образом и получите авторский:
сначала проверьте 4ю и 5ю батарейку
А потом первые 3 по кругу
и это по сути авторский и есть (с небольшим отличием, тт проверяем последнюю с 3й и 4й, а не с одной из первых двух, что то же самое)

[Dmitriy40]

Это и будет авторский (с перестановкой номеров, от чего ничего не зависит). А не модифицированный Ktina. Они отличаются фактом повторной проверки на втором-третьем шаге уже обнаруженных неисправных батареек.
И одинаковыми они быть не могут т.к. требуют разного количества проверок для всей совокупности исходных вариантов. А одинаковые алгоритмы должны требовать одинаковое количество проверок.

[wrest]

Ktina
Так шагов-то одинаково, на четвертом гарантированно включается.
Вопрос тогда какой способ в среднем быстрее.

Всего 10 вариантов размещений батареек.
На первом шаге у вас и у автора включаются 3 из 10 вариантов. Если фотоаппарат не включился, то на втором шаге у вас включаются 2 варианта, у автора 3 варианта. Если опять не включился, то на третьем шаге у вас включаются 2 варианта, у автора - тоже 2 варианта. И наконец на последнем шаге у вас включаются 3 варианта, у автора 2 варианта.

Легко видеть, что авторский вариант в среднем быстрее вашего, а ваш соответственно длиннее медленнее.

[Евгений Машеров]

"Авторское" мне представляется лучше, как дающее в среднем меньшее число проверок. Дело в том, что для Вашей схемы после первой неудачной проверки мы уже знаем, что среди первых двух по крайней мере одна разряжена, и вторая и третья попытки - хотя бы одна заведомо будет неудачна, а другая будет иметь меньшую вероятность успеха по сравнению с первой проверкой. При "авторской" же первая проверка даст ту же вероятность успеха, что и у Вас (3/10 - первая батарейка годна с вероятностью 3/5, а вторая, если годна первая, 2/4) , но вторая при неуспехе первой проверки - выше, чем у Вас (заведомый успех, если сели первые две проверенные, и 1/3, если села одна из проверенных уже: 2/3 вероятность годной третьей, и 1/2 вероятность годной четвёртой, если годна третья)

[Shadow]

И автор, и Ktina разбивают батареек на две группы - пара и тройка. Автор вначале проверяет пару, Ktina - тройку.

Вероятность, что в паре ровно 0 фалшивых $p_0=\dfrac{3}{10}$

$p_1=\dfrac{6}{10},\;p_2=\dfrac{1}{10}$

Математическое ожидание числа проверок тройки, где ровно одна фальшивая $m=\dfrac{1}{3}(1+2+3)=2$

Математическое ожидание у автора
$E_A=p_0\cdot 1+p_1(1+2)+p_2(1+1)=2,3$

У Ktina
$E_K=p_0\cdot 4+p_1\cdot 2+p_2\cdot 1=2,5$

Dmitriy40 в сообщении #1263827 писал(а):

он требует в сумме 23 попыток против 25 Ваших