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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обложка:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Обложка:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Вам может быть интересно
Задача про таблетки и злого гения

Как логика и ограничения помогают найти банку с отравленными таблетками.

medium
Что такое искусственный интеллект

В этой статье ни одной шутки про «Скайнет».

medium
Функции. Зачем они нужны и как их писать, чтобы вас уважали программисты

Сложная важная статья для тех, кто хочет стать крутым программистом.

medium
Задачка: как подбросить гнутую монетку

Что делать, если вероятность выпадения не 50 на 50?

medium
Простая задачка про секретных агентов, в которой легко ошибиться

Мы ошиблись с первого раза, а вы?

easy
Задача про секс и математику

Могут ли логика, математика и статистика привести к созданию новой крепкой семьи?

medium
Задача про квадраты, которую никто не может решить

Но вы сможете

Самая сложная задача для школьников, которую никто не смог решить

Теперь попробуйте вы

hard
Задача про номер дома

Диалог программистов с зубодробительной логикой

medium
easy
[anycomment]
Exit mobile version