Программисты обожают подобные задачи, потому что решение таких штук (вроде бы оторванных от реальности) мощно прокачивает алгоритмическое мышление и понимание абстрактного мира машин. Попробуйте сначала решить задачу самостоятельно, а если упрётесь — смотрите ответ.
Сторож проверял инвентарь и заметил, что у него не работает фонарик. Он пошарил в тумбочке и вытащил 8 батареек. Насколько он помнил, половина из них — свежие, потому что он совсем недавно покупал в магазине батарейки по акции. А вот ещё четыре точно разряжены: сторож планировал их утилизировать, но оказалось, что сделать это в России не так просто. В общем, теперь сторожу нужно вставить батарейки в фонарик, чтобы проверить, какие из них заряжены.
Чтобы фонарик заработал, в него должны быть вставлены две заряженные батарейки. Сколько максимально пар батареек нужно перебрать сторожу, чтобы фонарик точно заработал?
Назовём каждую батарейку отдельной буквой — А Б В Г Д Е Ж З. Это позволит нам не перепутать батарейки, когда мы будем менять их местами друг с другом.
Теперь разобьём батарейки на пары и проверим в фонарике каждую из них:
(А Б) (В Г) (Д Е) (Ж З) — это четыре первые пары.
Если фонарик заработал на какой-то из них — отлично, мы нашли нужную пару.
Если лампочка так и не загорелась, значит, в каждой паре у нас оказалась одна хорошая батарейка, и одна плохая. Давайте подумаем, почему:
Если бы в одной паре было две нерабочие батарейки, то на остальные три пары приходилось бы две нерабочие и четыре рабочие батарейки. Неизбежно одна из пар подобралась бы с двумя рабочими батарейками.
Следовательно, раз ни одна из пар не включила фонарь, в любой из них есть одна рабочая и одна нерабочая батарейка.
Теперь возьмём любые две пары — например, (А Б) и (В Г) — и поменяем в них первые батарейки местами. Получим:
(В Б) и (А Г) — в этот момент мы проверили уже шесть пар.
Если фонарик не заработал и после этой перестановки, значит, мы поменяли местами одинаковые батарейки: хорошую заменили на хорошую, или плохую — на плохую. Выходит, нужно взять вторую батарейку из первой пары и поменять её с первой батарейкой из второй пары:
берём пару (В Б), достаём оттуда вторую батарейку Б и ставим её на первое место в паре (А Г), получаем: (Б Г) — это седьмая пара.
Если фонарик загорелся, значит, второй мы поставили хорошую батарейку. Если фонарик всё ещё не светит, получается, в этой паре у нас две плохих батарейки, а две хороших остались в другой — (В А). Ставим их в фонарик, и готово!
Получается, что нам понадобится проверить максимум 7 пар.
