Задача про сторожа и фонарик
vk f t

Задача про сторожа и фонарик

Ваша любимая задача на перебор и логику.

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

Сторож проверял инвентарь и заметил, что у него не работает фонарик. Он пошарил в тумбочке и вытащил 8 батареек. Насколько он помнил, половина из них — свежие, потому что он совсем недавно покупал в магазине батарейки по акции. А вот ещё четыре точно разряжены: сторож планировал их утилизировать, но оказалось, что сделать это в России не так просто. В общем, теперь дворнику нужно вставить батарейки в фонарик, чтобы проверить, какие из них заряжены.

Чтобы фонарик заработал, в него должны быть вставлены две заряженные батарейки. Сколько максимально пар батареек нужно перебрать сторожу, чтобы фонарик точно заработал?

Решение

Назовём каждую батарейку отдельной буквой — А Б В Г Д Е Ж З. Это позволит нам не перепутать батарейки, когда мы будем менять их местами друг с другом.

Теперь разобьём батарейки на пары и проверим в фонарике каждую из них:

(А Б) (В Г) (Д Е) (Ж З) — это четыре первые пары.

Если фонарик заработал на какой-то из них — отлично, мы нашли нужную пару.

Если лампочка так и не загорелась, значит, в каждой паре у нас оказалась одна хорошая батарейка, и одна плохая. Давайте подумаем, почему:

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

Следовательно, раз ни одна из пар не включила фонарь, в любой из них есть одна рабочая и одна нерабочая батарейка.

Теперь возьмём любые две пары — например, (А Б) и (В Г) — и поменяем в них первые батарейки местами. Получим:

(В Б) и (А Г) — в этот момент мы проверили уже шесть пар.

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

берём пару (В Б), достаём оттуда вторую батарейку Б и ставим её на первое место в паре (А Г), получаем: (Б Г) — это седьмая пара.

Если фонарик загорелся, значит, второй мы поставили хорошую батарейку. Если фонарик всё ещё не светит, получается, в этой паре у нас две плохих батарейки, а две хороших остались в другой — (В А). Ставим их в фонарик, и готово!

Получается, что нам понадобится проверить максимум 7 пар.

Ещё по теме