Математика замены батареек

физическое решение: матвей соединяет все батарейки проводниками и получает мегабатарейку.

математическое:

вряд ли можно начать с чего-то умнее, чем взять и проверить случайно 4 пары. Если ни одна не сработала, то берем любые две пары и девятую. Назовем их 5-6, 7-8 и 9. Среди этих пяти батареек две или три хорошие, не более одной в паре и возможно девятая. Берем пятую и проверяем ее с 7,8,9. Если ни одна не сработала, то пятая точно плохая. Потом так еще пару раз и получается за одиннадцать измерений. Даже не просите доказать, что за десять нельзя

Считается ли попыткой та про которую мы уже точно знаем что подойдет еще до вставки в фонарик?

Предлагаю решение за 8 попыток: Берем три батарейки (пусть 1,2,3) пробуем 1-2 и 1-3 и 3-2. Потом берем другие три (пусть 4,5,6) и пробуем 4-5, 4-6 и 5-6. В каждой из этих троек будет миним две плохих, иначе мышка заработает. Значит, получаем три батарейки (7,8,9), из которых максимум одна плохая. Дальше 7-8 и 7-9 не дают результата. Пара 8-9 тогда - хорошие батарейки гарантированно. Итого 3+3+2 = 8 попыток.

Осталось доказать, что за 7 никак.....

Доказательство того, что за 7 никак:

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

Тогда доказываем, что за 8 никак:

• Заметим, что выигрышная стратегия - это серия попыток, каждая следующая не зависит от результата предыдущей - если результат вдруг положительный, то значит задача решена и серия закончена. Поэтому стратегия определяется заранее - если пронумеровать батарейки 1....9, то стратегия - от некий минимальный набор пар батареек с конкретными номерами, (например 1-2, 3-4 ..... ) такой, чтобы при любом раскладе N-я попытка (или раньше) включила мышку.

Из этого следует, что тестировать пары из этого выигрышного набора пар можно в любом порядке, на результат это не повлияет. (1)

Давайте считать, что хорошая батарейка - 1, а плохая - 0.

• Разобъем батарейки на тройки 1,2,3 4,5,6 7,8,9.

• Если мы не трогаем одну из троек (например 7,8,9), то ничего не выйдет, так как может быть, что 7,8,9 = 1-1-1, и никакими действия с оставшимися шестью (среди них только одна рабочая) мы мышку не запустим. Более того, так как мы никаким способом не можем определить единственную рабочую батарейку из любого набора, то если мы будем составлять пары, беря одну батарейку из 1,2,3,4,5,6 и одну любую из 7,8,9 = 1-1-1, например 7, то потребуется шесть попыток 1-7, 2-7, ...., 6-7. Если же при этом окажется, что 7,8,9 = 0-1-1, то потребуется уже десять попыток.

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

Исходя из (1), сделаем эти три операции первыми, например 1-2, 4-5, 7-8.

Предположим, что расклад оказался 1,2,3 = {0,0,1}, 4,5,6 = {0,0,1} и 7,8,9 = {0,1,1} (порядок внутри троек неизвестен), и нам каким то образом об этом узнали. Если мы попытаемся создать пару из единственной рабочей из 1,2,3 и какой-то рабочей из 7,8,9, то видно, что для гарантированного результата понадобится 6 попыток. Значит, нужно составлять пару из двух рабочих из тройки 7,8,9, то есть следующую операцию совершать внутри этой тройки, например 7-9.

Но может оказаться, что при раскладе по прежнему {0,0,1} {0,0,1} {0,1,1} , но при этом неизвестно, в какой из троек находится {0,1,1}. В этом случае нам придется симметрично совершить операцию внутри каждой из троек.

Таким образом, мы пришли к тому, если мы хотим уложится в восемь или меньше попыток, мы обязаны проверить еще одну пару из каждой такой тройки (3). Итого шесть попыток, осталось 2.

Итого, пусть у нас получились такие шесть операций: 1-2, 1-3, 4-5, 4-6, 7-8, 7-9

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

Возвращаясь к условиям задачи, чтобы гарантированно определить пару рабочих батареек (не обязательно из вставлять) потребуется минимум 8 попыток.