Загадка суммы и произведения
Обновлено: 22.11.2024
Головоломка « Сумма и произведение» , также известная как « Невозможная головоломка», потому что в ней не хватает информации для решения, это логическая головоломка . Впервые она была опубликована в 1969 году Гансом Фройденталем , а название « Невозможная головоломка» было придумано Мартином Гарднером . Загадка разрешима, хотя и нелегко. Подобных вариантов головоломок существует множество.
Другие решения
Проблема может быть обобщена. Оценка X + Y ≤ 100 выбрана довольно сознательно. Если предел X + Y изменить, количество решений может измениться. Для X + Y <62 решения нет. Поначалу это может показаться нелогичным, поскольку решение X = 4, Y = 13 укладывается в границы. Но за счет исключения продуктов с коэффициентами, которые суммируются с числами между этими границами, больше не существует нескольких способов факторизации всех нерешений, что приводит к тому, что информация не дает никакого решения проблемы. Например, если X = 2, Y = 62, X + Y = 64, X · Y = 124 не рассматривается, то остается только одно произведение из 124, а именно. 4 · 31, что дает сумму 35. Затем 35 исключается, когда S заявляет, что P не может знать коэффициенты продукта, чего не было бы, если бы сумма 64 была разрешена.
С другой стороны, когда предел составляет X + Y ≤ 1685 или выше, появляется второе решение X = 4, Y = 61. Таким образом, с этого момента проблема не является разрешимой в том смысле, что больше не существует уникальное решение. Аналогично, если X + Y ≤ 1970 или выше, появляется третье решение ( X = 16, Y = 73). Все эти три решения содержат одно простое число. Первое решение без простого числа - четвертое, которое появляется при X + Y ≤ 2522 или выше со значениями X = 16 = 2 · 2 · 2 · 2 и Y = 111 = 3 · 37.
Если условие Y > X > 1 изменяется на Y > X > 2, существует единственное решение для пороговых значений X + Y ≤ t для 124 < t <5045, после чего есть несколько решений. На уровне 124 и ниже решений нет. Неудивительно, что порог решения поднялся. Интуитивно, проблема пространство не получило « когда» разреженный простое число-больше не доступно как фактор X , создавая меньше возможные продукты Х · Y от заданной суммы A . Когда существует много решений, то есть для больших t , некоторые решения совпадают с решениями для исходной задачи с Y > X > 1, например X = 16, Y = 163.
Если вместо этого условие X + Y ≤ t для некоторого порога t заменить на X · Y ≤ u , проблема изменится. Становится проще решить с меньшими затратами на вычисления. Разумным значением для u могло бы быть u = t · t / 4 для соответствующего t на основе наибольшего произведения двух факторов, сумма которых t равна ( t / 2) · ( t / 2). Теперь у проблемы есть уникальное решение в диапазонах 47 < t <60, 71 < t <80, 107 < t <128 и 131 < t <144 и нет решения ниже этого порога. Результаты альтернативной формулировки не совпадают с результатами исходной формулировки ни по количеству решений, ни по содержанию.
Головоломка
X и Y две разные целые числа больше 1. Их сумма не превышает 100, а Y больше , чем X . S и P - два математика (и, следовательно, совершенные логики); S знает сумму Х + Y и Р знает продукт Х × Y . И S, и P знают всю информацию в этом абзаце.
Происходит следующий разговор (оба участника говорят правду):
- S говорит: «P не знает X и Y ».
- P говорит: «Теперь я знаю X и Y ».
- S говорит: «Теперь я также знаю X и Y ».
Что такое X и Y ?
Следующая загадка
Думаю многим будет интересно порешать эти задачи, которые собрал 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.
Объяснение
Проблема довольно легко решается, если прояснить концепции и перспективы. В этом участвуют три стороны: S, P и O. S знает сумму X + Y , P знает произведение X · Y , а наблюдатель O не знает ничего, кроме исходной постановки задачи. Все три стороны хранят одну и ту же информацию, но интерпретируют ее по-разному. Тогда это превращается в информационную игру.
Назовем разбиение числа A на два члена A = B + C 2-разбиением. Нет необходимости в каких-либо продвинутых знаниях, таких как гипотеза Гольдбаха или тот факт, что произведение B · C такого разбиения на 2 должно быть уникальным (т.е. нет двух других чисел, которые также при умножении дают тот же результат). Но с помощью гипотезы Гольдбаха, а также того факта, что P немедленно узнал бы X и Y, если бы их произведение было полупервичным , можно вывести, что сумма x + y не может быть четной, поскольку каждое четное число может быть записано как сумма двух простые числа. Тогда произведение этих двух чисел будет полупростым числом.
Шаг 1. S (Sue), P (Pete) и O (Otto) составляют таблицы всех продуктов, которые могут быть сформированы из двух частей сумм в диапазоне, то есть от 5 до 100 ( X > 1 и Y> X требует, чтобы мы начали с 5). Например, 11 можно разделить на 2 + 9, 3 + 8, 4 + 7 и 5 + 6. Соответствующие продукты - 18, 24, 28 и 30, и игроки ставят галочки напротив каждого из этих продуктов в своих таблицах (Таблица 1). Когда они закончены, на некоторых числах нет отметок, на некоторых - одна, а на некоторых - больше одной.
Шаг 2. Теперь Сью смотрит на свою сумму и все ее деления на 2. Она видит, что все 2-разбиения имеют продукты, которые не являются уникальными, т.е. существует другая факторизация, которая представляет собой 2-разбиение некоторой другой возможной суммы. Она видит это в таблице на шаге 1, где все ее продукты отмечены более чем одной галочкой. Она понимает, что из-за этого Пит не сможет однозначно определить факторы X и Y , глядя на продукт (для этого потребовалось бы, чтобы хотя бы один из продуктов-кандидатов имел только одну отметку). Таким образом, она восклицает: «P не может знать X и Y ». Когда Пит и Отто слышат это, они получают информацию о том, что ни один из продуктов, связанных с суммой Сью, не является уникальным. Перебирая возможные суммы одну за другой, Сью, Пит и Отто теперь могут, каждый по отдельности, составить список всех подходящих сумм (Таблица 2). Таблица содержит те суммы, у которых все 2-разбиения имеют продукты, которые не являются уникальными, т. Е. Имеют более одной отметки в таблице 1. Сью, Пит и Отто создали таблицу сумм кандидатов (Сью, конечно, уже знает ее сумма, но необходимо проследить мышление Пита).
Шаг 3. Учитывая новую информацию в Таблице 2, Пит еще раз смотрит на свой продукт. Суммы всех возможных 2-разбиений его продукта, кроме одного, исчезли из таблицы 2 по сравнению со всеми числами от 5 до 100, которые с самого начала считались суммами. Единственное, что осталось, должно быть суммой двух скрытых чисел X и Y , произведение X · Y которых он знает. По сумме и произведению легко узнать отдельные числа, и поэтому он говорит Сью: «Теперь я знаю X и Y ». Пит закончил и выходит из игры.
Шаг 4. Сью и Отто пересчитывают Таблицу 1, на этот раз подсчитывая только произведения 2-разбиений из сумм, которые находятся в Таблице 2, а не из всех чисел в диапазоне от 5 до 100, как в исходной Таблице 1. Эта обновленная таблица называется Таблицей. 1B. Сью просматривает все произведения 2-разбиений своей суммы и обнаруживает, что только одно из них встречается в таблице 1B ровно один раз . Тогда это должно быть произведение Пита, и она может вывести два числа из их суммы и произведения так же легко, как и Пит. Таким образом, она говорит Отто (Пита уже нет), что «теперь я также знаю X и Y ». Сью тоже закончила и выходит из игры, остается только Отто.
Шаг 5. Исходя из информации, представленной на шаге 4, Отто просматривает все суммы в таблице 2 в поисках одной из которых только для одного разбиения на 2 имеется одна отметка в таблице 1B. Нужный один может иметь только одну галочку, или Сью не был бы в состоянии знать X и Y с уверенностью. Наконец, Отто приходит к желаемой сумме, которая также оказывается единственной, обладающей этими свойствами, что делает исходную проблему разрешимой с помощью единственного решения. Задача Отто теперь тоже выполнена.
Следующая загадка
Выдано 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.
Примечания переводчика.
Оригинал.
Автор не удосужился разъяснить *астериски, оставлено как есть.
Задача 9 встречалась мне в формулировке с твердым предположением, что содержимое конвертов рознится вдвое. Однако оставлен оригинальный, авторский вариант.
Задача 13 переведена корректно и имеет строгое, известное мне решение. Ответ 4 13.
Составитель подборки, Petar Maymounkov окончил Гарвард, защетился в MIT, работал на Tumblr. Автор алгоритма Kademlia и референсной реализации. Сейчас заправляет проектом распределенных вычислений реализуемом на языке программирования Go, что и привлекло внимание вашего покорного слуги.
СОДЕРЖАНИЕ
Решение
В решении X и Y равны 4 и 13, причем P изначально знает, что произведение равно 52, а S знает, что сумма равна 17.
Первоначально P не знает решения, так как
52 = 4 × 13 = 2 × 26
и S знает, что P не знает решения, поскольку все возможные суммы до 17 в пределах ограничений дают аналогично неоднозначные продукты. Однако каждый может выработать решение, исключив другие возможности, следующие за утверждениями другого, и этого достаточно, чтобы читатель нашел решение с учетом ограничений.
Следующая загадка
Выдано 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.
Примечания переводчика.
Оригинал.
Автор не удосужился разъяснить *астериски, оставлено как есть.
Задача 9 встречалась мне в формулировке с твердым предположением, что содержимое конвертов рознится вдвое. Однако оставлен оригинальный, авторский вариант.
Задача 13 переведена корректно и имеет строгое, известное мне решение. Ответ 4 13.
Составитель подборки, Petar Maymounkov окончил Гарвард, защетился в MIT, работал на Tumblr. Автор алгоритма Kademlia и референсной реализации. Сейчас заправляет проектом распределенных вычислений реализуемом на языке программирования Go, что и привлекло внимание вашего покорного слуги.
Читайте также: