|
1. Абрикосы и хурма В трёх ящиках находятся абрикосы и хурма. Каждый ящик имеет наклейку, на которой написано что содержится внутри. В одном ящике - две хурмы (хх), во втором - два абрикоса (аа), а в третьем - одна хурма и один абрикос (ха). Только кто-то перепутал все наклейки, и теперь трудно сказать, что и где лежит. Если вы, не заглядывая внутрь, вынете из ящиков по одному абрикосу или хурме, то сколько штук абрикосов или хурмы вам придётся достать, чтобы определить содержимое каждого контейнера? 
Решение: Чтобы определить содержимое всех ящиков, достаточно достать один фрукт из ящика с наклейкой ха. Например, если вы достанете хурму, то в нём осталась ещё одна хурма: ведь вам известно, что все наклейки не соответствуют содержанию ящиков. Следовательно, в ящике хх лежат абрикосы, а в ящике аа - абрикос и хурма. 2. Контролёр ОТК положил 90 стандартных деталей в 9 коробок поровну, а 10 бракованных деталей в отдельную коробку. Он не может вспомнить в какой коробке лежат бракованные детали. Но знает, что каждая стандартная деталь весит 20 грамм, а бракованная – 21 грамм. Как он может узнать в какой коробке лежат бракованные детали с помощью одного взвешивания? Решение: Занумеруем коробки. Возьмём из коробки №1 одну деталь, из коробки №2 две детали, из коробки №3 три детали и т. д., из коробки №10 десять деталей. Тогда всего взятых деталей будет 1 + 2 + 3 + … + 9 + 10 = (1+10) • 5 = 55. Взвесим все 55 деталей вместе. Если бы они были стандартными, то весы показали бы 55 • 20 = 1100 г. Но так как есть бракованные детали, то вес будет больше. Например, 1107 г - эти лишние 7 г образовались за счёт 7 бракованных деталей из коробки №7. Номер бракованной коробки N = Р – 1100, где Р – общий вес деталей в граммах. 3. Я живу в пятиэтажном доме с 4 подъездами и с 4 квартирами на каждой лестничной площадке. За какое наименьшее число вопросов можно определить, в какой квартире я живу, если на все вопросы я буду отвечать правдиво, но только да или нет? Решение: Нужно задавать вопросы, связанные с номером квартиры. В доме 5 • 4 • 4 = 80 квартир. Приведу один из вариантов перечня вопросов, если задана квартира 22. 1. Номер вашей квартиры больше 40? (Нет) 2. Номер вашей квартиры больше 20? (Да) 3. Номер вашей квартиры больше 25? (Нет) 4. Номер вашей квартиры больше 23? (Нет) 5. Номер вашей квартиры равен 21? (Нет) 6. Номер вашей квартиры равен 22? (Да). Этот метод называется методом половинного деления. Он же используется в игре "Угадай Число" О таких играх некто Билл Гейтс говаривал что-то вроде: "Я люблю эти маленькие игры. В них можно начать играть в любой момент, и в любой момент отложить в сторону".
Здесь Вам нужно угадать число в выбранном диапазоне за указанное число попыток. Игра Двадцать вопросов. Я вспомнил одну старую игру, в которую часто играл еще в юности. Кто-нибудь загадывает что-нибудь определенное, например Большей Бен, молоток на парадной двери, бой часов в соседней комнате, верхнюю пуговицу на пиджаке приятеля или трубку мистера Болдуина. Вы должны установить, что было загано, задав не больше 20 вопросов, на которые можно отвечать «да» или «нет». Задавать вопросы следует осмотрительно, так как, сп росив, например: «Это животное, растение или минерал?», вы можете получить неудовлетворительный ответ «да» и тем самым затратите один вопрос впустую. Опытный игрок в «20 вопросов» ошибается редко; мне известны чрезвычайно трудные случаи, когда решение все же удавалось найти именно при таком условии. Недавно мне предложили один новый вариант этой игры, в котором требуется некоторая изобретательность, причем разные люди могут подойти к решению по-разному. Состоит игра в следующем. Я задумываю шестизначное число. Можно ли угадать его, задав лишь 20 вопросов, на которые я отвечу только «да» или «нет»? После двадцатого вопроса вы должны назвать это число. Пусть искомое число принадлежит множеству, состоящему из элементов и 2 k – 1 ≤ n < 2 k , k Î N , где k это наименьшая степень двойки, для которой справедливо это неравенство. Значит, наименьшее число вопросов, необходимых для нахождения элемента множества равно k . 4. Некто загадал число в диапазоне от 1 до 32. За какое наименьшее число вопросов можно угадать это число, если задавать вопросы, на которые можно ответить да или нет? Решение: Загаданное число больше 16? (нет) Загаданное число больше 8? (нет) Загаданное число больше 4? (да) Загаданное число больше 6? (да) Вы загадали число 7. Наименьшее число вопросов равно 4.
|
