Пара старых задачек по-массачусетски

Для некоторых мне известны возможные решения. Некоторые изредка встречаются на собеседованиях, реже чем об обедающих философах. Интересно было ознакомиться, как развлекаются в МассТехе.

Задача 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.

Примечания переводчика.

Оригинал.
Автор не удосужился разъяснить *астериски, оставлено как есть.

Задача 9 встречалась мне в формулировке с твердым предположением, что содержимое конвертов рознится вдвое. Однако оставлен оригинальный, авторский вариант.
Задача 13 переведена корректно и имеет строгое, известное мне решение. Ответ 4 13.

Составитель подборки, Petar Maymounkov окончил Гарвард, защетился в MIT, работал на Tumblr. Автор алгоритма Kademlia и референсной реализации. Сейчас заправляет проектом распределенных вычислений реализуемом на языке программирования Go, что и привлекло внимание вашего покорного слуги.

От себя бы добавил:
Задача невесты
У нас невеста на выданье. Женихи приезжают на смотрины с завидной регулярностью. Женихи на смотринах представляют полный и добросовестный отчет по всем поставленным вопросам любого рода. Результатом смотрин может быть только женитьба или бесповоротный отказ. Отставленные женихи немедленно и насовсем уезжают. Время играет против невесты. Необходимо предложить для невесты осмысленную стратегию.
Постановку задачи приписывают Б.А.Березовскому.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 86

    +3
    Просто список задачек как таковой мало интересен. А вот описание различных вариантов решения было бы интересно почитать.

    p.s.
    ≥ больше либо равно
    ≤ меньше либо равно
    ≠ не равно
      0
      Это перевод, как есть. Я знаю не все решения. Я полагаю, что не все решены. Могу выложить известные мне решения отдельным материалом.
        0
        Выложи отдельный пост и предложи решение задачки с невестой. На мой взгляд, невесте стоит составить ограниченный список вопросов по приоритетам, затем собрать воедино женихов и одновременно задавать вопросы по порядку сразу всем, если ответ не устраивает — прогонять.
          0
          Сразу всем нельзя — ограничения задачи, только по очереди.
          Решение Березовского
          Провести вменяемое количество опытов, скажем 1000. Далее если кандидат превосходит весь пройденный материал хотя бы по одному параметру, например самый лысый, то считать годным. Потом подругам хвастаться, мой по крайней мере самый лысый
            +2
            Задача про собеседование, аналогичная задаче невесте, приводится с решением в книге «с ослом» (Кормен, Лейзерсон, Ривест. Алгоритмы. Построение и анализ).
            Если заранее известно число кандидатов (N), то нужно пропустить первых k = N/e независимо от их качеств (пусть качества каждого кандидата оцениваются одним числом), после чего либо следует выбрать первого кандидата, оказавшегося лучше первых k, либо последнего.
              +5
              Как написано у Гарднера, «Если первый же, кто делает ей предложение, очень близок к ее идеалу, то, как написал нам один из читателей, «она будет просто дурой, если не примет предложения». ». Решение с N/e предполагает, что нам вообще неизвестна функция распределения женихов по «качеству», а есть только функция сравнения (как в типичной задаче сортировки).
          +1
          По человечески, я Бауманку заканчивал, приятно было ощутить соосность. Что в курилках MIT о том же трепятся
          0
          Задача 1 — встречал такую, только не с 12 шарами, а с 13
            0
            Да там суть решения не изменится, все равно первое взвешивание по 4 шара на каждую сторону, и дальше от этого плясать.
              0
              там всегда надо по 4 взвешивать. Просто правильный порядок взвешивания выбрать.
              как-то так
              пусть a — первая чашка легче, b — равно, c — вторая легче. Имеем 27 вариантов от aaa до ссс. откидываем bbb. Остается 26. А затем учитываем, что мы не знаем, легче шар или тяжелее, aba == cbc, например. отбираем разные варианты и подбираем номера шаров, которые дадут 12 (13) разных исходов
                0
                а в 3 попытки уложитесь?
                  0
                  Вполне
                  Мы получаем 13 пар ((aaa,ccc),(aab,ccb),(aac,cсa)...). «ааа» = все три раза левая чаша легче, «ссс» = все три раза правая чаша легче. так как мы не знаем, легче или тяжелее неизвестный шар, для нас исходы ааа и ссс — равнозначны.
                  Из полученных 13 пар выбираем 12 вариантов таким образом, чтоб буквы а, b и c находились на первой, второй и третьей позиции по 4 раза. Я подобрал, например, так:
                  Combination Number Combination
                  ccb 1 aab
                  aac 2 cca
                  aba 3 cbc
                  cbb 4 abb
                  cba 5 abc
                  aca 6 cac
                  cab 7 acb
                  acc 8 caa
                  bcc 9 baa
                  bab 10 bcb
                  bac 11 bca
                  bba 12 bbc

                  Слева и справа у нас «эквивалентные» комбинации.
                  Присвавиваем полученным комбинациям номера от 1 до 12.
                  далее логика такая: Число 1, комбинация ccb. Значит, шар №1 в первом взвешивании лежит на правой чаше, во втором — тоже на правой, а в третьем взвешивании не участвует. и т.д.
                  Для такого выбора получаем взвешивания:
                  1. №№ 2,3,6,8 и 1,4,5,7
                  2. №№ 2,7,10,11 и 1,6,8,9
                  3. №№ 3,5,6,12 и 2,8,9,11

                  Проверка: пусть у нас более тяжелый шар №8. Видим, что исход будет такой: caa. По табличке — это соответствует номеру 8.
                    0
                    А, ну и 13 шар определяется исходом bbb — то есть как шар, который ни разу не взвешивали, а все три взвешивания показали равенство.
                    0
                    Здесь задача с подвохом — вам не известно легче или тяжелее шар. «Ваша задача заключается в том, чтобы определить какой именно и легче он или тяжелее»
                      0
                      ну и я про тоже: первое что приходит на ум — взвесить 6-ки шаров — и определить в какой из них отклонение, но мы не знаем легче или тяжелее — поэтому не сможем определить, в какой кучке нормальные шары, в какой затесался «проблемный шар.
                    +1
                    Если при первом взвешивании положить на каждую чашу по три шара мы будем знать в любом результате по меньшей мере шестерку не бракованных шаров.
                  +10
                  О, а 3я задача красивая.
                  Плод моего воображения
                  Закодируем номер каждой бутылки в двоичной системе счисления, пронумеруем мышек от 1 до 10, и каждую бутылку дадим попробовать тем мышкам, у которых номера совпадают с единицами в двоичной записи номера бутылки. Например, из бутылки с номером 1100110001 отведают вина мышки с номерами 1, 2, 5, 6, 10. Таким образом из каждой бутылки выпьет хотя бы одна мышка. Номер каждой бутылки — число от 1 до 1000, а десятью двоичными цифрами можно закодировать любое число от 1 до 1024 (вообще-то от 0 до 1023, но здесь не важно). По истечении суток смотрим, какие мышки сдохли, декодируем число и однозначно восстанавливаем номер бутылки. PROFIT, ибо на вечеринку отправятся 999 бутылок.
                  Недостаток решения: каждой мышке придётся выпить примерно из 500 бутылок. Реалистичный прогноз: все они загнутся раньше 24 часов от передозировки алкоголя или гипергидратации.
                    –1
                    Можно проще — распределить бутылки на 10 мышей, итого получим 100 рядов по 10 бутылок. Каждая мышь выпивает в ряду из своей и соседней. например, первая выпивает из бутылки 1 и 2 и переходит к бутылке 11 и 12, затем 21 и 22 и т.д. Вторая мышь выпивает из 2 и 3, 12 и 13 и т.д. Десятая мышь пьет 10 и 1, 20 и 11 и т.д. Далее смотрим какие мыши траванулись — если 2 и 3, то яд в 3й бутылке (т.е. на персечении множеств), если отравились 1 и 2, то яд во второй бутылке. Суть решения такое же, просто подход обозначение несколько иное.
                      +1
                      Не понял.
                      Пусть отравились 1 и 2 мыши. Первая пила из бутылок с номерами 1, 2, 11, 12, ..., 991, 992. Вторая — из 2, 3, 12, 13, ..., 992, 993. Пересечение — 2, 12, ..., 992.
                        +1
                        Согласен, ошибочка вышла
                        +2
                        В вашем варианты если отравились мыши 2 и 3, то нужно выкинуть бутылки (3,13,23,33...)

                        Предложенный выше вариант предполагает, что 999 бутылок попадут на вечеринку.
                          0
                          Да, есть ошибка, надо иначе комбинировать, собственно что и сделано выше в двоичной системе.
                        +6
                        Элегантно. Апплодисменты.
                        +4
                        Третья задача часто встречается в варианте «240 бочек, 48 часов до момента Х, 5 тестеров, смерть наступает не позднее, чем через 24 часа (т.е. может и раньше) ». И главные действущие лица: патриций и рабы, никакой жестокости в обращении с животными
                        • UFO just landed and posted this here
                            0
                            Здорово. Если так пойдет отдельный пост с ответами потеряет смысл.
                              +3
                              Что бы не перекапывать комментарии в поисках ответов, нужно их собрать в один пост.
                            0
                            Задача 9.
                            Мы конечно не знаем закон, по которому распределены случайные числа в конвертах, но предположим, что это равномерное распределение на (0; +inf).
                            Тогда F(x)=0 для любого x, где F(x) — вероятность того, что случайное число X < x.
                            Открываем один из конвертов, случайное число в нём принимает конкретное значение x.
                            Вероятность того, что число в другом конверте меьше, равна нулю, соответстенно нужно открыть второй конверт и мы со 100% вероятностью получим большее число.
                            P.S. Вас не должно смущать что конкретное меньшее число в конверте появиться может, но вероятность этого равна нулю. Такова уж теория вероятностей.
                              0
                              Тут я недостаточно подкован, теряю нить.
                              Как уже указывалось, мне задачка встречалась в формулировке, где содержимое конвертов можно полагать рознящимся вдвое. Обнаруживаем в конверте 100 и ожидаем в другом 50 или 200 с равными вероятностями, то есть (1/2)*50 + (1/2)*200 = 125. Уверенно выбираем оставшийся нераспечатанным.
                                +1
                                Если представить себе, что на втором конверте сидит второй игрок, он тем же образом получит выигрушность обмена конвертами и для себя тоже, а оба игрока выигрывать не могут.
                                  0
                                  Ошибка в подсчете вероятности, там вовсе не 50/50 )

                                  Самая простая стратегия — вибираем любое число X, и если в открытом конверте значение меньше X — производим обмен. Этот прием увеличивает вероятность выбора с исходных 50% на чуть большую величину (на сколько именно — зависит от того, какова плотность значений в районе X).

                                  Для ещё большего гарантированного увеличения уже потребуется дополнительная информация о распределении значений, например, для игры, где значения отличаются в два раза — разбиваем все на непересекающиеся промежутки [a/2, 2a), [b/2, 2b),… и в зависимости от того в какой промежуток попали — сравниваем с a или с b и т.д.
                                  0
                                  А если представить себе, что на другом конверте сидит другой игрок? Воспользовавшись тем же алгоритмом, он придет к такому же выводу и согласится поменяться, но обмен, очевидно, не может быть выигрышным для обоих игроков, и ни один игрок не может выигрывать чаще — они же в одинаковых условиях. Получаем равновероятность. По идее, ваша логика должна работать, если число появляется в момент вскрытия конверта, но не в случае, когда число на момент начала игры уже зафиксировано.
                                    +1
                                    Если бы было сказано «положительные целые числа», то можно было бы легко выкрутится правилом «если увидели в первом конверте число 1 — выбираем второй». И того на множестве пар любых положительных целых чисел мы в среднем будем выбирать большее число в > 50% случаев. Но сказано просто «положительные», так что тут фиг его знает.
                                      0
                                      Если натуральные — то все, похоже, зависит от способа рандомизации. По идее, если сначала сгенерировать два случайных, а потом случайно одно из них дать в конверте игроку — то будет, очевидно, 50% (если у игрока не 1; собственно, в задаче с конкретной, поставленной здесь целью это будет верно не только для натуральных, а для любых чисел). Если сначала сгенерировать одно, дать игроку выбрать, а при вскрытии конверта сгенерировать второе (неважно, получит его игрок или нет) — то с вероятностью 100% второе будет больше, так как меньших чисел всего-навсего конечно. Вообще эта задача сильно отличается от классической проблемы двух конвертов — там нас просят максимизировать выигрыш, а тут надо всего-навсего с максимальной вероятностью получить большее число, неважно, насколько именно оно будет больше.
                                      +1
                                      Мы конечно не знаем закон, по которому распределены случайные числа в конвертах, но предположим, что это равномерное распределение на (0; +inf).
                                      Собственно закон распределения тут играет решающую роль при выборе стратегии. Что такое «равномерное распределение на (0:+inf)» науке не известно, посему и все остальные рассуждения смысле не имеют.
                                        0
                                        Закон распределения не имеет никакого значения. Даже если каждый раз в конвертах будет одна и та же пара чисел, стратегия будет работать. Надо только выбирать не только случайную степень двойки (опять, с любой функцией распределения — лишь бы вероятность каждой степени было ненулевой), но и брать строго случайный конверт из двух предложенных.
                                          0
                                          Вы о какой стратегии говорите? Я отвечал на пост Andrew1000000. Там ни о каких степенях двойки речи не было.
                                          ,
                                        0
                                        Согласен, что условие задачи некорректное.
                                        Нужно либо указать закон распределения, либо сделать уточнение, как в топике, что числа отличаются в два раза.
                                        А всё-таки интересно, можно ли определить равномерное распределение на бесконечности, например так:
                                        F(x)=0 для любого x.
                                        Тогда f(x)=F'(x)=0 тоже для любого x.
                                        Вот здесь тоже задавались этим вопросом.
                                          +1
                                          Почему же некорректное? Распределение неизвестно, отношение сумм неизвестно, выигрывает игрок, если выберет конверт с большей суммой… решение существует. Только если отношение сумм в конвертах неизвестно, придётся выбирать случайное число с распределением, плотным на всей прямой. Например, с плотностью 1/(pi*(1+x^2)). Всё равно шанс, что оно окажется между суммами в конвертах, ненулевой (как бы ни играло казино) — и в этом случае мы выиграем. А в остальных случаях шанс на выигрыш будет ровно 50%.
                                          Равномерного распределения на всей прямой, к сожалению, не существует.

                                            0
                                            Про равномерное распределение на всей прямой:
                                            Существенным условием является интеграл от плотности — он должен быть равен 1. Для константных функций из R в R такое невозможно.
                                            Если расширить действительные числа бесконечно малыми величинами, то построить константную функцию можно, но при таком расширении нарушаются многие другие аксиоматические требования и нужно заново выстраивать всю теорию вероятностей. Может быть кто-то и пытался этим заниматься, но если результат и был, то большого распространения он не получил.
                                        0
                                        Задача 6 представляется в совсем ином свете, если доступны арифметические операции ADD и SUB )
                                        В частности, классический вариант — быстро посчитать кол-во единичных бит в 32-х битном слове на стандартной x86 архитектуре )
                                          0
                                          В задаче 6 не сказано, есть ли загрузка константы. Думаю, что сдвиг всегда на 1 бит. Если загрузки константы нет (то есть, мы даже младший бит выделить не можем быстрее, чем за n-2 операции (хотя нет, можем за 3)), то дело становится интересным. Похоже, что ответ порядка n*log(n), но надо считать точнее.
                                          Я как-то программировал игру «жизнь» с использованием битовых масок для представления поля — так там была похожая задачка: по 8 маскам построить две — в одной будут те разряды, в которых единички есть ровно в 2 масках из 8, в другой — в которых единички ровно в 3 масках.
                                          Делал через сложение с помощью and,or,xor.
                                            0
                                            Да, тоже баловался таким (про «жизнь»). ;) Где-то порядка сотни-полторы (давно было, точно не помню) асмовых инструкций надо было в среднем выполнить для обработки 32-х клеток (т.е. 3-5 инструкций на клетку — сильно быстрее прямого расчета).
                                              0
                                              Я её писал на DCPU-16 — получилось, по-моему, инструкций 70 на 16 клеток. Уже не помню, как — то ли через двухбитную сумму трёх битов, то ли суммированием в «1-ричной системе» (учитывая, что суммы больше 4 нам не интересны).
                                          +1
                                          В задачке 7 первая реакция — посчитаем интеграл, получим 100/3 * sqrt(50), то есть примерно 236. А дальше зависит от того, сколько есть времени — можно посчитать сумму нескольких первых, а остальное добить интегралом. Или посчитать все корни до 3 знаков… 2 листочков должно хватить.
                                          Задачки 8,10,11,13 пока не встречались (про 10 что-то слышал). Надо их подумать.
                                            0
                                            Задачи 2, 3, 4 мне давали на различных собеседованиях
                                              0
                                              задача 10 с тремя звездами

                                              куб не разбиваем, в отличие от квадрата.

                                              доказательство тут ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B0#.D0.9A.D1.83.D0.B1.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BA.D1.83.D0.B1.D0.B0

                                              это скорее на знания и общую эрудицию задачи.
                                                0
                                                такое мнение что задачи со звездой, часто встречаются на собеседованиях и мелькают в инете регулярно,
                                                задача 13 например, сильно напоминает задачу о мудрецах habrahabr.ru/post/72824/
                                                задачи с двумя звездами достаточно сложны, в разных вариациях встречаются и разрешимы.
                                                а три звезды — это заведомые нерешайки…
                                                  0
                                                  задача 9 по смыслу похожа на задачу профессора из фильма «21», только чуть чуть надо прописать стратегию…
                                                    –1
                                                    ну и напоследок: 7я задача без звездочек. — это школьная программма — сумма геометрической прогрессии
                                                    • UFO just landed and posted this here
                                                        0
                                                        1^(`1/2) + 2^(1/2) +…
                                                          +2
                                                          Если вкратце, то это — не прогрессия.
                                                          Геометрическая прогрессия — это показательный ряд (не уверен в точности термина; скажем, ряд, соответствующий показательной функции) an
                                                          В данном случае — степенной ряд na.
                                                          Это все-таки очень разные вещи.
                                                            0
                                                            согласна.

                                                            это сумма ряда. не прогрессия. и уж тем более не геометрическая.
                                                            ошиблась.
                                                            и сумма степенного ряда тоже считается. но, действительно уже не в школьной программе.
                                                            виноватая.
                                                              +2
                                                              Можно написать
                                                              sqrt(n-1)=sqrt(n)*(1-1/2n-1/8n^2-1/16n^3-...)
                                                              (это бином Ньютона),
                                                              задать функцию S(n)=sqrt(n)*(2/3*n+a+b/n+c/n^2+...)
                                                              и потребовать условие S(n)-S(n-1)=sqrt(n).
                                                              Методом неопределённых коэффициентов находим a=1/2, b=1/24, c не находится — ну и не надо.
                                                              Теперь сумму sqrt(a+1)+sqrt(a+2)+...+sqrt(b) можно оценить как S(b)-S(a).
                                                              Находим S(50)=sqrt(50)*(100/3+1/2+1/1200)=239.2
                                                              S(5)-sqrt(5)=sqrt(5)*(7/3+1/2+1/120)=6.35
                                                              sqrt(1)+...+sqrt(50)=S(50)-(S(5)-sqrt(5))+1+sqrt(2)+sqrt(3)+2=239.0. Пишем это в качестве ответа. Всё решение — поллисточка.
                                                              Если бы мы посчитали S(50) с большим числом знаков, получили бы
                                                              S(50)-(S(5)-sqrt(5))+1+sqrt(2)+sqrt(3)+2=239.0357914
                                                              Правильный ответ — 239.0358004, то есть ошибка была бы 10^(-5) (а у нас получилась 0.035 — меньше надо было с sqrt(50) лениться, ведь ясно, что это примерно 7.071068 — строится из 8 знаков sqrt(2)).
                                                                0
                                                                да верю я,
                                                                написала же, что ошиблась, сказав, что это геометрическая прогрессия…
                                                                меня интересовала больше сложность задач, и то что,
                                                                часть из задач заведомо не решаемы,
                                                                а часть имеют решения но сложные,
                                                                а часть стандартные…
                                                                ну почему вы не читаете коменты с нчала?

                                                                вот кстате ответ экселя на туже сумму. можете сопоставить неточность. 239,0358006

                                                                  0
                                                                  Сумма квадратных корней равна S(n)+C1

                                                                  C1=-1/(Pi)*(1+1/2V2+1/3V3+1/4V4+...), примерно 0,21
                                                                    0
                                                                    C С1 ошибся надо еще посмотреть.
                                                                      0
                                                                      Один из последних результатов
                                                                      Сумма квадратных корней = ((4n + 3)sqrt(n)/6 — exp(-Pi / 2))

                                                                      Ряд C1=-1/(4*Pi)*(1+1/2V2+1/3V3+1/4V4+...), страшно медленно сходится.
                                                    0
                                                    Задача 7.
                                                    1+√2+√3+2+√5+√2*√3+√7+2*√2+3+√2*√5+√11+2*√3+√13+√2*√7+√3*√5+4+√17+3*√2+√19+2*√5+√3*√7+√2*√11+√23+2*√2*√3+5=15+√2(1+√3+2+√5+√7+3+√11+2*√3)+√3*(1+2+√5+√7)+√5(1+2)+√7+√11+√13+√17+√19+√23=15+√2*(6+3*√3+√5+√7+√11)+√3*(3+√5+√7)+3*√5=15+27,4+13,7+6,7=62,8
                                                    Это для первых 25 чисел, дальше лень считать.
                                                    Нет, в лоб тут не посчитаешь, нужно найти какую-то закономерность, но пока ничего в голову не приходит.
                                                      +2
                                                      Задача 5 — нет решения: каждое домино покрывает одну чёрную и одну белую клетку. Но на доске из условия клеток одного цвета на 2 больше клеток другого цвета.
                                                        0
                                                        Задачка 11.
                                                        Предположим, что числа удалось раскрасить в 3 цвета так, что для чисел, разность которых — полный квадрат, цвета разные.
                                                        Пусть COL(1)=A, COL(26)=C.
                                                        Тогда COL(10)=COL(17)=B (поскольку 10-1=26-17=3^2, 17-1=26-10=4^2).
                                                        Получается, что клетки, расстояние между которыми равно 7, должны быть одинакового цвета (если их номера лежат между 10 и 1997), а значит, клетка 59 имеет тот же цвет, что и клетка 10. Но 59-10=7^2 — противоречие.

                                                        На самом деле, получается, что 10, 51 и 52 одного цвета, но 52-51=1^2, и для этого хватает графа из 61 вершины. Какова минимальная длина отрезка, который можно раскрасить в 3 цвета, пока не знаю.
                                                          0
                                                          Боюсь запутать вас переводом. Хорошо, если под теорией узлов и хроматическим числом графа мы подразумеваем одно и то же. Еще вернее вам будет глянуть в оригинал статьи,
                                                            0
                                                            Заглянул. Там написано «пусть COL — раскраска множества 1..2006 в три цвета». Впрочем, так я и думал. Графы там подразумеваются, но явно не упоминаются.
                                                              0
                                                              Собственно термин 3-coloring, вольно переведенный мной как трехцветный широко употребляется в англоязычных статьях, как хроматическое число графа или узла,
                                                                0
                                                                Если верить Вики, то graph coloring — это правильная раскраска графа, а chromatic number — минимальное количество цветов в правильной раскраске. Если coloring где-то действительно употребляется в смысле «число», то это как-то странно. Впрочем, восток — дело тонкое…
                                                                  0
                                                                  A coloring using at most k colors is called a (proper) k-coloring. The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G)
                                                                  0
                                                                  Может вы правы и здесь никаких графов в помине нет, а просто множество. Но вроде множества не красят.
                                                                    0
                                                                    На математических олимпиадах это делают очень часто. «Раскрасить числа или точки в несколько цветов» — обычное дело.
                                                                  0
                                                                  Исправлено. Это был overengineering с моей стороны. Спасибо.
                                                                0
                                                                Программа сказала, что самый длинный отрезок, который можно покрасить в 3 цвета — 28 чисел.
                                                                0
                                                                Задачка 8.
                                                                Проведём через заключенного прямые, параллельные диагоналям квадрата, и научим собак находиться в точках пересечения этих прямых с периметром. Очевидно, что как бы заключенный не двигался, собакам не придётся бежать быстрее, чем в sqrt(2) раза больше его скорости — значит, выполнить задание они смогут. Когда заключённый подойдёт к стороне, его всегда встретят две собаки. А если он догадается подойти к углу — то сразу три.
                                                                  0
                                                                  Это решение неправильное (или неполное) — в условии не сказано, что мы можем выбирать место начального расположения собак! И если все собаки вначале сидят в одном месте — в середине одной из сторон, то я не вижу, как мы можем помешать заключённому, если он побежит прямо к противоположной стороне.
                                                                    +2
                                                                    На мой взгляд правомерно считать начальное положение псов частью их инструкций.
                                                                  0
                                                                  Задача 6
                                                                  Если константы есть, то для регистра длиной 2^N можно справиться за 2^N+N*(N-1)*3/2+1 операций (пример для N=5):

                                                                  b=a&0x55555555;
                                                                  a=(a>>1)&0x55555555;
                                                                  a=((a&b)<<1) | (a^b);
                                                                  
                                                                  b=a&0x33333333;
                                                                  a=(a>>2)&0x33333333;
                                                                  c=(a&b)<<1;
                                                                  a^=b^c;
                                                                  
                                                                  b=a&0x0f0f0f0f;
                                                                  a=(a>>4)&0x0f0f0f0f;
                                                                  c=(a&b)<<1;
                                                                  a^=b;
                                                                  b=(a&c)<<1;
                                                                  a^=b^c;
                                                                  
                                                                  b=a&0x00ff00ff;
                                                                  a=(a>>8)&0x00ff00ff;
                                                                  c=(a&b)<<1;
                                                                  a^=b;
                                                                  b=(a&c)<<1;
                                                                  a^=c;
                                                                  c=(a&b)<<1;
                                                                  a^=b^c;
                                                                  
                                                                  b=a&0x0000ffff;
                                                                  a>>=16;   
                                                                  c=(a&b)<<1;
                                                                  a^=b;    
                                                                  b=(a&c)<<1;
                                                                  a^=c;    
                                                                  c=(a&b)<<1;
                                                                  a^=b;    
                                                                  b=(a&c)<<1;
                                                                  a^=b^c;  
                                                                  


                                                                  Если сдвиги на любое число разрядов считаются за 1 такт, то остаётся (3*N^2-N)/2+2 операции.
                                                                  Без констант сложнее — придётся затратить 3*2^N операций, только чтобы получить отдельные биты.



                                                                    0
                                                                    Ай, ну зачем решение 13й задачи прямо в тексте топика давать? Предупреждать же надо.
                                                                      0
                                                                      В тексте только ответ, чтобы свериться. Известное мне решение довольно громоздкое и в топик бы не влезло,
                                                                      0
                                                                      Видел в точности этот список задач на своём любимом форуме с головоломками, года два назад. Задачки, безусловно, хороши, но с бородой.
                                                                        0
                                                                        Бородатость нынче входит в моду. Поделитесь ссылкой на форум.
                                                                      0
                                                                      А что насчет 4й задачи?
                                                                      По-моему там два варианта:
                                                                      1. мы можем использовать условия в программе (например, остановиться когда все кружки в одинаковой позиции) и тогда задача не имеет смысла, т.к. можно просто переворачивать одну кружку пока не получим нужный результат.

                                                                      2. мы должны составить последовательность команд из которой мы не можем выйти до полного завершения, и в процессе мы не можем ставить условия или получать состояние кружек. И тогда эту задачу невозможно решить.

                                                                      Или я не прав и во втором случае есть решение?
                                                                        0
                                                                        Там, скорее, первый вариант. Но «переворачивать одну кружку» — не работает, поскольку вредный робот может всегда переворачивать неправильную кружку. Непредсказуемо оно для нас, но не для робота.
                                                                        Похожая, но более интересная задача была в книжке «Математический цветник». Там можно было выбрать две кружки, на ощупь определить их ориентацию, и в зависимости от результата перевернуть сколько-то из них (0, 1 или 2).
                                                                          0
                                                                          «вредный робот может всегда переворачивать неправильную кружку», все равно, это практически не усложняет задачу.
                                                                            0
                                                                            И сколько ходов достаточно для гарантированного выигрыша?
                                                                              +1
                                                                              Т.к. нам не важно как именно поставить кружки, все вверх или все вниз дном, и не важно на каком угле, грани или диагонали стоит «неправильная кружка» — считаем что такие состояния эквивалентны:
                                                                              ++     -+     --  
                                                                              +-     ++     -+ и т.д.
                                                                              

                                                                              Тогда имеем 4 возможных начальных состояния:
                                                                              0     1     2     3
                                                                              ++    +-    --    +-
                                                                              ++    ++    ++    -+
                                                                              

                                                                              С вот такой таблицей переходов:
                                                                              (а) «перевернуть угловую кружку»
                                                                              (б) «перевернуть две диагональных кружки»
                                                                              (с) «перевернуть две соседние кружки».
                                                                                     |   а   |   б   |   с   |
                                                                              -------------------------------      
                                                                              0 | ++ |   1   |   3   |   2   |
                                                                                | ++ |       |       |       |
                                                                              -------------------------------
                                                                              1 | -+ | 0,2,3 |   1   |   1   |
                                                                                | ++ |       |       |       |
                                                                              -------------------------------
                                                                              2 | -- |   1   |   2   |  0,3  |
                                                                                | ++ |       |       |       |
                                                                              -------------------------------
                                                                              3 | +- |   1   |   0   |   2   |
                                                                                | -+ |       |       |       |
                                                                              


                                                                              Собственно получаем:
                                                                              while(state != 0) {
                                                                                  switch(state) {
                                                                                      case 1:
                                                                                          а();
                                                                                          break;
                                                                              
                                                                                      case 2:
                                                                                          с();
                                                                                          break;
                                                                              
                                                                                      case 3:
                                                                                          б();
                                                                                          break;
                                                                                  }
                                                                              
                                                                                 state = getState();
                                                                              }
                                                                              


                                                                              Кол-во шагов для выхода из состояния:
                                                                              0 = 0
                                                                              1 = 1-3
                                                                              2 = 1-2
                                                                              3 = 1

                                                                      Only users with full accounts can post comments. Log in, please.