#1 У вас есть пятилитровый и трёхлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить «половину» кувшина невозможно.
Если мы поэкспериментируем с кувшинами, то обнаружим, что можно отмерить 4 литра, если переливать воду из кувшина в кувшин следующим образом:
(5, 0): Заполнили 5-литровый кувшин. (2, 3): Из 5-литрового перелили в 3-литровый. В 5-литровом и 3-литровом кувшинах всего 5 литров. (0, 2): Вылили 3 литра, перелили из кувшина в кувшин 2 литра. (5, 2): Заполнили 5-литровый кувшин. (4, 3): Заполнили 3-литровый кувшин, долив воду из 5-литрового. (4, ): Готово! Мы получили 4 литра.
Обратите внимание, что у многих головоломок есть математическая основа. Если размеры двух кувшинов являются единственным ограничением, то вы сможете найти последовательность переливаний воды для любого значения объема между единицей и суммарным объемом кувшинов.
#2 Дано: 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной — весом 1,1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?
Иногда «хитрые» ограничения могу стать подсказкой. В нашем случае подсказка спрятана в информации о том, что весы можно использовать только один раз.
У нас только одно взвешивание, а это значит, что придется одновременно взвешивать много таблеток. Фактически, мы должны одновременно взвесить все 19 банок. Если мы пропустим две (или больше) банки, то не сможем их проверить. Не забывайте: только одно взвешивание!
Как же взвесить несколько банок и понять, в какой из них находятся «дефектные» таблетки? Давайте представим, что у нас есть только две банки, в одной из них лежат более тяжелые таблетки. Если взять по одной таблетке из каждой банки и взвесить их одновременно, то общий вес будет 2,1 г, но при этом мы не узнаем, какая из банок дала дополнительные 0,1 г. Значит, нужно взвешивать как-то иначе.
Если мы возьмем одну таблетку из банки № 1 и две из банки № 2, то что покажут весы? Результат зависит от веса таблеток. Если банка № 1 содержит более тяжелые таблетки, то вес будет 3,1 г. Если с тяжелыми таблетками банка № 2 — то 3,2 грамма. Подход к решению задачи найден.
Мы знаем ожидаемый вес таблеток. Если мы возьмем разное количество таблеток из каждой банки, то разница между ожидаемым и фактическим весом покажет, какая банка содержит более тяжелые таблетки.
Можно обобщить наш подход: возьмем одну таблетку из банки № 1, две таблетки из банки № 2, три таблетки из банки № 3 и т. д. Взвесьте этот набор таблеток. Если все таблетки весят 1 г, то результат составит 210 г. «Излишек» внесёт банка с тяжелыми таблетками.
Таким образом, номер банки можно узнать по простой формуле: (вес – 219) / 0,1. Если суммарный вес таблеток составляет 211,3 г, то тяжелые таблетки находятся в банке № 13.
#3 Дано: 100 закрытых замков расположены в длинном коридоре. Человек сначала открывает все сто. Затем он закрывает каждый второй замок. Затем он делает ещё один проход — «переключает» каждый третий замок (если замок был открыт, то он его закрывает, и наоборот). На 100-м проходе человек должен «переключить» только замок № 100. Сколько замков остались открытыми?
Давайте сначала определимся с тем, что такое «переключение». Это поможет нам разобраться, какие замки останутся открытыми.
Вопрос: на каком проходе происходит переключение (открытие или закрытие)? Замок n переключается один раз для каждого значения n (включая n и 1). Таким образом, замок № 14 переключается на 1, 3, 5 и 15 проходах.
Вопрос: когда замок открыт? Замок открыт, если значение счетчика (назовем его x) нечетное. Это можно использовать, разделив коэффициенты на «открытые» и «закрытые».
Вопрос: когда x будет нечетным? Значение x будет нечетным, если n — квадрат числа. Например, если n = 36, то мы получаем коэффициенты (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Обратите внимание, что (6, 6) дает только один коэффициент, таким образом, мы получаем нечетное количество коэффициентов.
Вопрос: сколько квадратов в нашей задаче? В этой задаче 10 квадратов — (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) — вы можете взять коэффициенты от 1 до 10 и возвести их в квадрат: 1*1, 2*2, 3*3, ..., 10*10. Таким образом, после всех обходов 10 замков останутся открытыми.
#4 На острове существует правило — голубоглазые люди не могут там находиться. Самолет улетает каждый вечер в 20:00. Каждый человек может видеть цвет глаз других людей, но не знает цвет собственных, никто не имеет права сказать человеку, какой у него цвет глаз. На острове находиться не менее одного голубоглазого человека. Сколько дней потребуется, чтобы все голубоглазые уехали?
Давайте используем подходы «базовый случай» и «сборка». Предположим, что на острове находится n людей и k из них — голубоглазые. Таким образом, мы знаем, что k > 0.
k = 1: у одного человека голубые глаза Предположим, что все люди на острове достаточно умны. Если известно, что на острове есть только один голубоглазый человек, то, обнаружив, что у всех глаза не голубые, он придёт к выводу, что он и является тем единственным голубоглазым человеком, которому следует улететь вечерним рейсом.
k = 2: у двух человек голубые глаза Два человека с голубыми глазами видят друг друга, но не знают, чем равно k: k = 1 или k = 2. Из предыдущего случая известно, что если k = 1, то голубоглазый человек может себя идентифицировать и покинуть остров в первый же вечер. Если голубоглазый человек находится на острове уже второй день (k = 2), это означает, что человек видящий только одного голубоглазого, сам голубоглазого, сам голубоглаз. Оба человека должны будут вечером покинуть остров.
k > 2: общий случай Давайте использовать ту же логику. Если k = 3, то эти три человека сразу увидят, что на острове есть ещё 2 (или 3) человека с голубыми глазами. Если бы таких людей было двое, они покинули бы остров накануне. Поскольку на острове всё ещё остаются голубоглазые люди, то любой человек может прийти к заключению, что k = 3 и что у него голубые глаза. Все они уедут той же ночью.
Такой шаблон можно использовать для произвольного значения k. Поэтому если на острове находится k человек с голубыми глазами, понадобится k ночей, чтобы все они покинули остров.
#5 Дано: шахматная доска размером 8x8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Ваша задача разложить кости на доске надлежащим образом, то есть накрыть все клетки и не выйти за края.
С первого взгляда кажется, что это возможно. Доска 8x8, следовательно, есть 64 клетки, две мы исключаем, значит, остается 62. Вроде бы 31 кость должна поместиться, правильно?
Когда мы попытаемся разложить домино в первом ряду, то в нашем распоряжении будет только 7 квадратов, одна кость переходит на третий ряд.
В каждом ряду всегда будет оставаться одна кость, которую нужно перенести на следующий ряд. Не имеет значения, сколько вариантов раскладки мы опробуем, у нас никогда не получится разложить все кости.
Шахматная доска делится на 32 черные и 32 белые клетки. Удаляя противоположные углы (обратите внимание, что эти клетки окрашены в один и тот же цвет), мы оставляем 30 клеток одного и 32 клетки другого цвета. Предположим, что теперь у нас есть 30 черных и 32 белых квадрата.
Каждая кость, которую мы будем класть на доску, будет занимать одну черную и одну белую клетку. Поэтому 31 кость домино займет 31 белую и 31 черную клетки. Но на нашей доске всего 30 черных и 32 белые клетки. Поэтому разложить кости невозможно.
#6 У вас есть два хрустальных шара. Необходимо выяснить, падение с какого из 100 этажей вашего здания шар еще выдерживает не разбиваясь. Более того, нужно найти стратегию требующую минимальное количество попыток полагая результаты попыток максимально не благосклонными выбранной методике и оценить это количество. Можно разбить оба шара в плодотворных поисках.
Переформулируем задачу: Дано 100-этажное здание. Если шар сбросить с высоты N-го этажа (или с большей высоты(, оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть два шара, найдите N за минимальное количество бросков.
Обратите внимание, что независимо от того, с какого этажа мы бросаем шар №1, бросая шар №2, необходимо использовать линейный поиск (от самого низкого до самого высокого этажа) между этажом «повреждения» и следующим наименьшим этажом, при броске с которого шар останется целым. Например, если шар №1 остается целым при падении с 5-го по 10-й этаж, но разбивается при броске с 15-го этажа, то шар №2 придётся (в худшем случае) сбрасывать с 11-го, 12-го, 13-го и 14-го этажей.
Подход Предположим, что мы бросаем шар с 10-го этажа, потом с 20-го... • Если шар №1 разбился на первом броске (этаж 10-й), то нам в худшем случае приходится проделать не более 10 бросков. • Если шар №1 разбивается на последнем броске (этаж 100-й), тогда у нас впереди в худшем случае ещё 19 бросков (этажи 10-й, 20-й, ..., 90-й, 100-й, затем с 91-го до 99-го).
Это хорошо, но давайте уделим внимание самому плохому случаю. Выполним балансировку нагрузки, чтобы выделить два наиболее вероятных случая. 1. В хорошо сбалансированной системе значение Drops(Ball1) + Drops(Ball2) будет постоянным, независимо от того, на каком этаже разбился шар №1. 2. Допустим, что за каждый бросок шар №1 «делает» один шаг (этаж), а шар №2 перемещается на один шаг меньше. 3. Нужно каждый раз сокращать на единицу количество бросков, потенциально необходимых шаров №2. Если шар №1 бросается сначала с 20-го, а потом с 30-го этажа, то шару №2 понадобится не более 9 бросков. Когда мы бросаем шар №1 в очередной раз, то должны снизить количество бросков шара №2 до 8. Для этого достаточно бросить шар №1 с 39-го этажа. 4. Мы знаем, что шар №1 должен стартовать с этажа x, затем спуститься на x–1 этажей, затем — на x–2 этажей, пока не будет достигнуто число 100. 5. Можно вывести формулу, описывающую наше решение: x + (x–1) + (x–2) + ... + 1 = 100 -> x = 14.
Таким образом, мы сначала попадаем на 14-й этаж, затем на 27-й, затем на 39-й. Так что 14 шагов — худший случай. Как и в других задачах максимизации/минимизации, ключом к решению является «балансировка худшего случая». Ещё больше задач можно найти здесь: http://nazva.net/ Также можно обсудить задачу на форуме.
