Задачи для развития ума от MIT

На хабре сегодня промелькнули задачи, который собрал Petar Maymounkov, он окончил Гарвард и защитился в Массачусетском технологическом институт. Многие из этих задач часто встречали на собеседованиях, так что для себя очень круто прорешать и разобрать, может пригодится. Если что-то решили - пишите в комментарии.

Задача 1*
Выдано 12 одинаковых на вид шаров из которых, как вам сказали, только один отличается по весу. Ваша задача заключается в том, чтобы определить какой именно и легче он или тяжелее. Единственный инструмент в вашем распоряжении это весы с двумя чашками. На чашки можно класть только шары. Весы можно использовать не более трех раз.
Авторство не установлено.



Задача 2*
У вас есть два хрустальных шара. Необходимо выяснить, падение с какого из 100 этажей вашего здания шар еще выдерживает не разбиваясь. Более того, нужно найти стратегию требующую минимальное количество попыток полагая результаты попыток максимально не благосклонными выбранной методике и оценить это количество. Можно разбить оба шара в плодотворных поисках.
Сформулировано Mark Gorton.

Задача 3*
Положим у парня есть 1000 бутылок вина. Выясняется, что одна из них отравлена. На счастье у него еще есть 10 мышей, которыми он готов пожертвовать для экспериментов. Опыты занимают сутки, то есть мышь хлебнувшая ядовитого вина подыхает только через 24 часа. Наш герой как раз планирует масштабную вечеринку на завтра. Сколько из 1000 бутылок может быть проверено на мышах и подано к столу окажись парень семи пядей во лбу? К примеру он может дать каждой мыши отведать из одной из бутылок и таким образом быть уверенным по меньшей мере в десяти бутылках, если ни одно животное не окочурится. При летальном исходе парень получает 999 надежных бутылок, но как уже указывалось, в задачах предпологается сценарий недружелюбный выбранной методике испытаний. Все мыши должны быть распределены по бутылкам немедленно потому что до вечеринки остается всего 24 часа.
Подкинул Sanjay Menon.

Задача 4*
Четыре пивные кружки расставлены по краям квадратного стола, некоторые вверх ногами. По столу ползает робот исполняющий три команды (а) «перевернуть угловую кружку» (б) «перевернуть две диагональных кружки» (с) «перевернуть две соседние кружки». Однако после каждой команды непредсказуемо в каком углу, на какой диагонали или стороне стола кружки приглянутся роботу больше. Придумайте серию команд понуждающую робота привести кружки хотя бы к единообразию.
Поделился Benjamin Rossman.

Задача 5***
Выдано: шахматная доска 8х8 и набор домино из 31 кости (не спрашивайте где такой купить) таких, что кость покрывает в точности две соседние клетки на доске. Две диаметрально и диагонально противоположные клетки выпилены (на доске остается 62 клетки таким образом). Ваша задача разложить кости на доске надлежащим образом, то есть накрыть все клетки и не выйти за края.
Прислал Tasho Statev Kaletha.

Задача 6**
В ваших руках компьютер с n-битным машинным словом, поддерживающий стандартные бит операции: AND, OR, NOT, XOR, LEFT SHIFT, RIGHT SHIFT. Сколько битовых операций вам понадобится для определения числа установленных в единицу бит в машинном слове w? Можно считать доступным любое нужное количество регистров и бесплатной операцию COPY. Результат должен быть получен в форме целого числа представленного машинным словом.
Задача David Karger.

Проблема 7
Прикиньте сколько будет √1 + √2 + · · · + √50 устно (или на листочке бумаги, или на двух листочках) настолько точно, насколько вам под силу.
Авторство не установлено.

Задача 8**
Заключенный ограничен квадратной площадкой. В вашем распоряжении 4 собаки, которые могут патрулировать периметр ограждения. Собаки в полтора раза быстрее осужденного но слабее. Побег считается удавшимся если пересечению периметра не препятствуют по меньшей мере два пса. Вызов здесь в том, чтобы указать осужденному его место вначале и втемяшить в голову собакам, как им следует себя вести. Вы вольны снабдить каждого пса отдельными инструкциями.
Поделился Sam Yagan через посредство Chris Coyne.

Задача 9**
(Пресловутая проблема двух конвертов) Вы в игре. Перед вами два запечатанных конверта. В каждом конверте положительное число и числа в конвертах рознятся. Вы вольны выбрать и распечатать один конверт. Ознакомившись с содержимым вы вправе закончить игру. Ваш улов число внутри конверта. Или за вами выбор предпочесть неизвестное вам число внутри другого, нераспечатанного конверта. А теперь вопрос: Какая стратегия обеспечит вероятность более 1/2 заполучить большее число? У вас нет ровно никаких оснований строить предположения о содержимом конвертов.
Задачку впервые подослал Chris Coyne много лет назад. Замечательное решение представил Krzysztof Onak.

Задача 10***
Покажите, что единичный куб не может быть разбит на конечное число меньших кубов с попарно неравной длиной ребра. Следует заметить, не так с квадратом.
Прислал Benjamin Rossman.

Задача 11**
Пусть Col трехцветный граф на вершинах 1…2006. Покажите, что существуют x,y такие, что COL(x) = COL(y) и |x − y| является квадратом.
Представлено на Мэрилендской Математической Олимпиаде 2006. Позаимствовано из блога Luca Trevisan.

Задача 12**
Лист бумаги разбит регулярной решеткой правильных шестиугольников (соты), некоторые шестиугольники по краям листа будем полагать неправильными, но по меньшей мере один влазит целиком. Вообразите теперь, что шестиугольники беспорядочно раскрашены в черный и белый цвета. Докажите что существует черная тропинка сверху вниз листа, либо белая слева направо. Для образования тропинки два шестиугольника считаются соседствующими, когда они имеют общее ребро. К шестиугольникам на левом краю листа можно отнести те, что имеют общее ребро с этим, левым краем листа. То же для верхнего, нижнего и правого края.
Поделился Benjamin Rossman.

Задача 13*
(Загадка суммы и произведения) Пусть x и y два целых числа 1 \< x \< y притом x + y \<= 100. Салли сказали только сумму x + y, а вот Полю произведение xy. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа?
Позаимствовано в блоге Lance Fortnow.


Теги:
promo levashove march 20, 2018 17:56 15
Buy for 50 tokens
Привет. Меня зовут Евгений Левашов, я живу в Калининграде и работаю техническим писателем и техническим копирайтером. Проще говоря, я пишу инструкции и статьи на ИТ-тематику. Инструкции, документации, статьи на Хабрахабр и т.д.. Это блог с некоторых пор является зеркалом моего сайта.…
Третья задача дошла)
Из тысячи бутылок можно сделать куб с гранью в десять бутылок.
Выберем одну из вершин за точку отсчета с тремя примыкающими гранями.
Десять мышек выстроятся на грани и отопьют каждая из своей плоскости - по 100 бутылок за подход.
Потом еще по подходу с двух других граней.
Так мы вычислим координаты ядовитой бутылки))
А мышки оближут всего по 298 бутылок)

Это гуманней чем решение с двоичной системой из комментов на хабре))
Загадка №1
Загадка очень простая, для первоклашек... 1 раз весы используем) Разделить 12 шаров на 6 групп по 2 шара...
Берем 2 шара (1я группа) и кладем на разные чаши... (1 вариант)
Чаши на равновесии т.е. шары одинаковые: продолжаем подкладывать группы шаров пока не сдвинется равновесие...
Когда сдвинулось запомнили какая по счету группа из 2 шаров повлияла...
2 раз используем весы) берем ту группу которую запомнили, и контрольный шар шар из любой другой группы, т.к. группа из 2 шаров в котором другой по весу шар уже найдена... и перевзвешиваем с контрольным шаром один из двух шаров, если равнозначны, значит тот шар что остался и есть лишний, если не равнозначен вес, значит на весы положили с контрольным шаром другой по весу шар...

7ая задача
для любого первого курса, ну или что-то типа того.
Это обычный ряд, а значит просто интегрируем и получается (2/3)*(n)^3/2=125*2*2*sqrt(2)/3=235,7, конечно в вольфраме 239 получилось, но это мелочи, прост что-то забыл учесть.
7-я
7-я позволила почувствовать себя умным.

1. Конечно, интеграл x^1/2 на интервале от 0 до 50. Плохо. Вылазят иррациональные числа. Помню только 2 значащие цифры. Либо применять численный метод поиска корня. Формула Ньютона? Тоже не помню.

2. Перепишем как интеграл x^1/2 на интервале от 0 до 49 плюс 50^1/2. Такой интеграл ищется гораздо легче. У меня получилось 228,7 + 50^1/2.

3. Исследуем расхождение кривой y=x^1/2 и искомой фигуры, состоящей их столбиков шириной 1 и высотой, как указано в задании: 1^1/2, 2^1/2... Как видно, фигура и кривая совпадают при каждом целочисленном х, но в промежутках искомая фигура везде выше. Прикинем величину расхождения площадей на каждом единичном отрезке.

4. На промежутке от 0 до 1 можно грубо сказать, что расхождение площади равно половине квадрата 1х1. Но можно и точно, т.к. интеграл y=x^1/2 на интервале от 0 до 1 равен 2/3. Соответственно, разность площадей 1*1 - 2/3 = 1/3

5. На интервале от 1 до 4 (3 единичных интервала) кривая y=x^1/2 на каждом из единичных интервалов уже хорошо аппроксимируется прямой. Если построить прямоугольники с вершинами (1;1)(2;2^1/2), (2;2^1/2)(3;3^1/2) и (3;3^1/2)(4;4^1/2), то видно, что суммарная их площадь равна 1, каждый поделен аппроксимирующим отрезком по диагонали. Соответственно, можно приблизительно принять, что расхождение площади искомой фигуры и "корневой" кривой на интервале от 1 до 4 равно 0,5.

6. То же справедливо для интервалов от 4 до 9, от 9 до 16, от 16 до 25, от 25 до 36, от 36 до 49. Всего найденных "расхождений" площади: 1/3 + 0,5*6 = 3,33

7. Осталось найти корень из 50-ти. Это 7 с чем-то. Построим аппроксимирующий отрезок от точки (49;7) до (64;8). Понятно, что это очень грубое приближение "коренной" кривой для 15-ти единичных отрезков. Но замечательно, что на первом единичном отрезке от 49 до 50 приближение оказывается на удивление хорошим (дальше все расходится, но оно нам и не надо). Получается, что 50^1/2 примерно равно 7 + 1/15 или 7,07.

8 Складываем все: 228,7 + 3,33 + 7,07 = 239,1

Калькулятор выдает 239,03. Расхождение 0,07%

Edited at 2013-11-21 16:25 (UTC)
С 12-ю шарами, вроде, решил:
1 действие берем произвольно 6 шаров и раскладываем по 3 на весы.
Если чаши уравновесились, то откладываем эти 6 шаров и используем другие 6 для сл. действия поделив их по 3 на каждую чашу. Одна из этих пар по 3 шара или легче или тяжелей

2 действие: на одной из чаш меняем 3 шара используя шары из 6-ти которые мы отложили, которые имеют одинаковый вес.
если весы не поменяли своего положения, то искомый шар находится среди тех 3ех шаров, которые мы оставили на весах и не поменяли - он или легче или тяжелей, в зависимости от нового положения весов. Если же весы поменяли свое положение, то нужный нам шар находится среди 3ех, которые мы заменили шарами с одинаковым весом и он так же - легче или тяжелей, в зависимости от нового положения весов.

Благодоря прошлому действию мы получили 3 шара и уже точно знаем - он тяжелей или легче.

3-е действие:
Осталось взвесить эти два из этих трех. Если вес одинаков - искомый шар - оставшийся. Если нет - искомый тот который легче или тяжелей, в зависимости из действия номер 2
#1
Первую можно решить за 2 действия вместо 3. Используем только одну чашу весов, на которой закрепляем 12 шаров по периметру. Соответственно первым действием определяем 2 противоположных шара, один из которых фальшив, а один нет (остальные тоже нет). Вторым действием кладем на разные чаши один из этих шаров и любой другой из оставшихся 10-ти. Если они имеют один вес, то оставшийся шар фальшив. А если они не имеют одинаковый вес, то понятно - тяжелее фальшивый шар или легче
2-я,
1-й шар кидать с этажа кратным 3 начиная с 3-го когда шар разобьется, берем второй шар и кидаем с этажа где разбился 3-й минус 2, если 2-й шар не разобьется кидаем его на этаж выше.
причем есть в (33 и 3 в периоде)% второй шар останется целым.
Задача 1 :решение 1 (если это честно конечно) начинаем класть по 6 шаров на каждую чашу , по одному шару, так как это весы мы либо сразу определяем сколько весит 1й шар, либо начинаем класть второй и определяем вес, либо продолжаем класть шары пока не поймем что положили шар легче или тяжелее. решение 2: действие 1) кладем на каждую чашу по 6 шаров потом выбираем , ту в которой лежит отличный от других шар ,действие 2) раскладываем по 3 шара на чашу, опять определяем которая отличается. действие 3) Кладем на одну чашу один шар, а на другую 2 шара , если по весу определяем что шар который лежит один отличается то мы выигрываем , если же другая чаша, то мы поднимаем один шар , и в случае ели весы уравновешиваются нужный шар у нас в руках, а если нет то он на чаше опять же мы определили что вот он...
#1 Решается за 3 действия методом исключения.

1. На обоих чашах по 6 шаров (одна из двух групп будет легче)
2. 6 шаров, один из которых легче, взвешиваем опять, по 3 шара на чашу.
3. У нас осталось 3 шара, один из которых легкий. Взвешиваем два – если одинаковы, то тот, что не взвесили – легкий.
Боже мой, вы вообще читаете условие???? торопыги такие. Ты не знаешь легче искомый шар или тяжелее. Если взять две группы по 6 шаров, ты и так будешь знать что они отличаются по весу, взвешивать их по шесть крайне не логично!!