Задача:
В элитном 16–этажном доме всего 4 подъезда. На каждом этаже расположена только одна квартира. За какое наименьшее число вопросов можно узнать у жильца этого дома номер его квартиры, если неразговорчивый жилец отвечает на все вопросы только «да» и «нет»?
Решение:
Нетрудно посчитать, что всего в доме 4 * 16 = 64 квартиры. Изначально у нас нет никакой информации о номере квартиры, а значит нам надо будет, задавая вопросы, выбирать из 64 возможных вариантов. Поскольку на каждый наш вопрос жилец может ответить только «да» или «нет», то сокращать количество вариантов каждым вопросом мы сможем не более чем вдвое.
Чтобы задавать вопросы, которые сокращают количество вариантов вдвое, будем пользоваться методом половинного деления: возьмем множество всех квартир и разделим на 2 множества одинакового размера. Например, квартиры с 1 по 32 и квартиры с 33 по 64. А теперь зададим такой вопрос: «Вы живете в квартире с номером с 1 по 32?» Вне зависимости от ответа на этот вопрос, у нас останется 32 варианта: если ответ был да, то это квартиры с 1 по 32, а если нет, то с 33 по 64.
И так далее, всегда будем делить количество вариантов на 2 множества одинакового размера. И с помощью вопроса будем определять в каком множестве находится искомая квартира.
Вот что у нас получится:
- В начале: 64 варианта.
- После 1 вопроса: 32 варианта.
- После 2 вопросов: 16 вариантов.
- После 3 вопросов: 8 вариантов.
- После 4 вопросов: 4 варианта.
- После 5 вопросов: 2 варианта.
- После 6 вопросов: 1 вариант.
Но один вариант как раз и означает, что мы можем наверняка сказать номер искомой квартиры.
Заметим, что то же самое можно было понять проще: 64 — это 2 в шестой степени.
Ответ: 6 вопросов.
Нашли ошибку? Знаете как решить лучше? Пишите в комментариях!
Подписывайтесь на наш канал, ставьте лайки, чтобы не пропустить новые задачи!