Задачи для развития ума от 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.