Задачи для развития ума от 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. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа?
На хабре сегодня промелькнули задачи, который собрал 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. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа?
MIT Mind Tasks
On a habr today flashed the tasks that Petar Maymounkov collected, he graduated from Harvard and defended himself at the Massachusetts Institute of Technology. Many of these tasks were often met at interviews, so it’s very cool to solve and understand for yourself, it can come in handy.
Task 1 *
12 identical-looking balls were issued, of which, as you were told, only one is different in weight. Your task is to determine which one is easier and harder. The only tool at your disposal is a two-cup scale. Only balls can be placed on cups. Scales can be used no more than three times.
Task 2 *
You have two crystal balls. It is necessary to find out the fall from which of the 100 floors of your building the ball can withstand without breaking. Moreover, you need to find a strategy that requires a minimum number of attempts, assuming the results of the attempts are not as supportive of the chosen technique as possible and evaluate this number. You can break both balls in a fruitful search.
Formulated by Mark Gorton.
Task 3 *
Suppose a guy has 1000 bottles of wine. It turns out that one of them is poisoned. Fortunately, he still has 10 mice that he is willing to sacrifice for experiments. The experiments take a day, that is, the mouse slurped poisonous wine dies only after 24 hours. Our hero is planning a big party for tomorrow. How many of 1000 bottles can be checked on mice and served to the table were a guy of seven spans in his forehead? For example, he can give each mouse a taste from one of the bottles, and thus be sure of at least ten bottles if no animals are bullied. With a fatal outcome, the guy receives 999 reliable bottles, but as already indicated, the tasks assume a script that is unfriendly to the chosen test method. All mice should be bottled immediately because only 24 hours are left before the party.
Threw Sanjay Menon.
Task 4 *
Four beer mugs are placed on the edges of the square table, some upside down. A robot crawls across the table executing three commands: (a) “flip the corner circle” (b) “flip two diagonal circles” (c) “flip two adjacent circles”. However, after each team it is unpredictable in which corner, on which diagonal or on the side of the table the circles will attract the robot more. Come up with a series of commands forcing the robot to bring the circles to at least uniformity.
Shared by Benjamin Rossman.
Task 5 ***
Issued: 8x8 chessboard and a set of dominoes of 31 dice (do not ask where to buy one) such that the bone covers exactly two adjacent cells on the board. Two diametrically and diagonally opposite cells are cut out (62 cells remain on the board in this way). Your task is to decompose the bones on the board properly, that is, cover all the cells and not go beyond the edges.
Submitted by Tasho Statev Kaletha.
Task 6 **
In your hands is a computer with an n-bit machine word that supports standard operation bits: AND, OR, NOT, XOR, LEFT SHIFT, RIGHT SHIFT. How many bit operations will you need to determine the number of bits set per unit in the machine word w? Any desired number of registers and free COPY operation can be considered available. The result should be obtained in the form of an integer represented by a machine word.
Task David Karger.
Problem 7
Estimate how much √1 + √2 + · · + √50 orally (either on a piece of paper, or on two pieces of paper) is as accurate as you can.
Authorship not established.
Task 8 **
The prisoner is limited to a square platform. There are 4 dogs at your disposal that can patrol the perimeter of the fence. Dogs are one and a half times faster than the convict but weaker. An escape is considered successful if at least two dogs do not interfere with the perimeter crossing. The challenge here is to show the condemned his place at the beginning and put the dogs in the head how they should behave. You are free to provide each dog with separate instructions.
Shared Sam Yagan via Chris Coyne.
Task 9 **
(The notorious problem of two envelopes) You are in the game. Here are two sealed envelopes. In each envelope, the positive number and the numbers in the envelopes are different. You are free to select and print one envelope. After reviewing the contents, you have the right to end the game. Your catch is the number inside the envelope. Or it's your choice to prefer an unknown number inside another, unopened envelope. And now the question is: What strategy will provide a probability of more than 1/2 to get a larger number? You have absolutely no reason to speculate about the contents of the envelopes.
The task was first sent by Chris Coyne many years ago. A wonderful solution was introduced by Krzysztof Onak.
Task 10 ***
Show that a unit cube cannot be split into a finite number of smaller cubes with pairwise unequal edge lengths. It should be noted, not so with the square.
Submitted by Benjamin Rossman.
Task 11 **
Let Col be a three-color graph at the vertices 1 ... 2006. Show that there exist x, y such that COL (x) = COL (y) and | x - y | is a square.
Presented on
On a habr today flashed the tasks that Petar Maymounkov collected, he graduated from Harvard and defended himself at the Massachusetts Institute of Technology. Many of these tasks were often met at interviews, so it’s very cool to solve and understand for yourself, it can come in handy.
Task 1 *
12 identical-looking balls were issued, of which, as you were told, only one is different in weight. Your task is to determine which one is easier and harder. The only tool at your disposal is a two-cup scale. Only balls can be placed on cups. Scales can be used no more than three times.
Task 2 *
You have two crystal balls. It is necessary to find out the fall from which of the 100 floors of your building the ball can withstand without breaking. Moreover, you need to find a strategy that requires a minimum number of attempts, assuming the results of the attempts are not as supportive of the chosen technique as possible and evaluate this number. You can break both balls in a fruitful search.
Formulated by Mark Gorton.
Task 3 *
Suppose a guy has 1000 bottles of wine. It turns out that one of them is poisoned. Fortunately, he still has 10 mice that he is willing to sacrifice for experiments. The experiments take a day, that is, the mouse slurped poisonous wine dies only after 24 hours. Our hero is planning a big party for tomorrow. How many of 1000 bottles can be checked on mice and served to the table were a guy of seven spans in his forehead? For example, he can give each mouse a taste from one of the bottles, and thus be sure of at least ten bottles if no animals are bullied. With a fatal outcome, the guy receives 999 reliable bottles, but as already indicated, the tasks assume a script that is unfriendly to the chosen test method. All mice should be bottled immediately because only 24 hours are left before the party.
Threw Sanjay Menon.
Task 4 *
Four beer mugs are placed on the edges of the square table, some upside down. A robot crawls across the table executing three commands: (a) “flip the corner circle” (b) “flip two diagonal circles” (c) “flip two adjacent circles”. However, after each team it is unpredictable in which corner, on which diagonal or on the side of the table the circles will attract the robot more. Come up with a series of commands forcing the robot to bring the circles to at least uniformity.
Shared by Benjamin Rossman.
Task 5 ***
Issued: 8x8 chessboard and a set of dominoes of 31 dice (do not ask where to buy one) such that the bone covers exactly two adjacent cells on the board. Two diametrically and diagonally opposite cells are cut out (62 cells remain on the board in this way). Your task is to decompose the bones on the board properly, that is, cover all the cells and not go beyond the edges.
Submitted by Tasho Statev Kaletha.
Task 6 **
In your hands is a computer with an n-bit machine word that supports standard operation bits: AND, OR, NOT, XOR, LEFT SHIFT, RIGHT SHIFT. How many bit operations will you need to determine the number of bits set per unit in the machine word w? Any desired number of registers and free COPY operation can be considered available. The result should be obtained in the form of an integer represented by a machine word.
Task David Karger.
Problem 7
Estimate how much √1 + √2 + · · + √50 orally (either on a piece of paper, or on two pieces of paper) is as accurate as you can.
Authorship not established.
Task 8 **
The prisoner is limited to a square platform. There are 4 dogs at your disposal that can patrol the perimeter of the fence. Dogs are one and a half times faster than the convict but weaker. An escape is considered successful if at least two dogs do not interfere with the perimeter crossing. The challenge here is to show the condemned his place at the beginning and put the dogs in the head how they should behave. You are free to provide each dog with separate instructions.
Shared Sam Yagan via Chris Coyne.
Task 9 **
(The notorious problem of two envelopes) You are in the game. Here are two sealed envelopes. In each envelope, the positive number and the numbers in the envelopes are different. You are free to select and print one envelope. After reviewing the contents, you have the right to end the game. Your catch is the number inside the envelope. Or it's your choice to prefer an unknown number inside another, unopened envelope. And now the question is: What strategy will provide a probability of more than 1/2 to get a larger number? You have absolutely no reason to speculate about the contents of the envelopes.
The task was first sent by Chris Coyne many years ago. A wonderful solution was introduced by Krzysztof Onak.
Task 10 ***
Show that a unit cube cannot be split into a finite number of smaller cubes with pairwise unequal edge lengths. It should be noted, not so with the square.
Submitted by Benjamin Rossman.
Task 11 **
Let Col be a three-color graph at the vertices 1 ... 2006. Show that there exist x, y such that COL (x) = COL (y) and | x - y | is a square.
Presented on
У записи 1 лайков,
1 репостов.
1 репостов.
Эту запись оставил(а) на своей стене Евгения Зевахина
![Марина Любас [ и ]](https://pp.userapi.com/c639423/v639423727/57895/LsxBaxDf8vs.jpg "Марина Любас [ и ]")
