Пара задачек с YAC 2012

    Привет!

    Сегодня на YAC были интересные задачки на анализ данных.

    Приведу парочку из них для желающих поразмять мозг. Если вы были на конференции(а хаброидов было не мало) и в курсе решения, то будет разумно не вываливать все, что вы и так уже знаете.

    Задачки привожу по памяти.

    1. Из тюрьмы сбежал преступник. Выбежав на парковку, он сел в автомобиль и скрылся по дороге в одном из направлений. От тюрьмы уходят два бесконечных непересекающихся направления.

    Затем из тюрьмы выбегает коп, преследующий преступника и садится в свою машину. Машина копа более быстрая, чем у сбежавшего чела, но коп об этом не знает. Так же коп не знает в какую сторону уехал зек. Сможет ли коп догнать преступника? Докажите.

    2. Имеется пространство в форме квадрата с равными сторонами. В центре квадрата тусуется волк. По углам сидят собаки. Волк может перемещаться по квадрату как ему угодно. Собаки же только по периметру. Скорость собаки превышает скорость волка в 1.5 раза. При столкновении волка с собакой, волк побеждает(бой происходит мгновенно). Но две собаки смогут победить волка. Вопрос. Сможет ли волк сбежать из вышеуказанно пространства живым?

    пы.сы. Топик опубликовал скучая на вокзале. Ноут сядет через часок. Если пропаду, то объявлюсь с комментариями утром.

    пы.пы.сы. Ноутбук умирает. Удачных рассуждений. Завтра присоединюсь. И добавлю еще одну задачку.

    upd: Еще одна задача
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 72

      0
      1) похоже что параллельные направления от тюрмы могут идти только в 1 направлении. и тогда коп догонит сбежавшего.
      2) да, сможет, если сразу пойдёт в угол. тогда волк встретиться только с 1 собакой (он преодолеет половину диагонали квадрата чуть быстрее, чем собака целую сторону, так что встретиться только с 1 собакой).
        0
        1. направления расходятся в разные стороны
        2. учитывайте, что скорость собаки выше чем у волка в 1.5 раза
          +1
          тьфу ты, я тут что-то перепутал, что на 1.42 умножать ;) Получается, что через угол он так сходу не уйдёт. Сейчас подумаю ещё немного.
            0
            2. а что если волку посидеть у середины ребра, дождавшись пока все собаки окажутся в одной точке и затем рвануть назад, к противоположному?
              0
              Да, хороший вариант. Но давайте предположим, что собаки имеют чуточку больше мозгов и не будут толкаться тупо в одной точке.
                –1
                Волк подходит к одному углу, ждет, когда все собаки там соберутся, и ломится в противоположный угол.
                  0
                  Ну, или даже так: волк направляется к середине стороны квадрата А. Две собаки вынуждены туда бежать из ближайших углов. Две остальные остаются в углах.
                  После чего волк по диагонали бежит в середину одной из прилегающих сторон Б, куда успевает лишь одна собака, поскольку волку потребуется пробежать примерно в 1,4 раза меньшее расстояние, чем второй собаке из А в Б.
                    0
                    вы допускаете, что собака глупа. попробуйте решить задачу «наизнанку»: представьте, что вы играете за собак. Вы можете сформулировать беспроигрышную стратегию для собаки?
                      0
                      Но скорость собаки в 1.5 раза больше. Следовательно вторая собака его догоняет.
                0
                в первом вопросе мне не очень понятна формулировка. Если тюрма — здание и оба направления уходят от дверей тюрмы, и при этом не пересекаются, то они параллельны и представляют собой лучи. Так что коп обязан догнать приступника (он не может ошибиться с направлением). Если же направления коллинеарны и не однонаправлены, то с вероятностью в 50% догонит ;)
                  0
                  уточню про дорогу. это одна дорога. по ней можно поехать бесконечно на юг, или бесконечно на восток. разъехавшись в разные стороны они не пересекутся. так лучше?

                  вариант с 50% крайне очевиден и подойдет как решение классе в пятом. 50/50 = либо/либо.
                    0
                    не юг, а запад имел в виду. но суть в принципе не меняется.
                      0
                      А принимается во внимание факт того, что земля круглая?)
                        0
                        нет
                          0
                          Сначала коп должен бесконечное время ехать в одну сторону, а затем, убедившись, что там преступника нет, ехать бесконечное время в противоположную сторону.
                            0
                            Он не может убедиться в отсутствии преступника в одной стороне, так как длина дороги бесконечна.
                              0
                              Еще он не может убедиться в этом, т.к. не знает, что его машина быстрее, и что гипотетически он может его догнать.
              0
              1. Если коп знает через сколько времени с начала побега он начал погоню и он не дурак, то догонит.
                0
                Обоснуйте
                  0
                  Ну если коп начал погоню то как минимум он уже предполагает что его машина может быть быстрее. Допустим он предположил что его скорость на 1 км/ч больше чем у преступника, тогда он зная время побега может вычислить через сколько времени он сможет его догнать поехав по одной из дорог. Он начинает погоню по любой дороге, если он не догнал за это время, то разворачивается и едет по другой. В этом случае он так же исходя из предположения о скорости может вычислить за через сколько он гипотетически может его догнать.
                    0
                    Попробуйте вычислить.
                      0
                      Так как я предложил решение через предположение о разнице скорости в 1 км/ч, то задача решается элементарно. Мы просто имеем что скорость приближения равна 1 км/ч.
                      Соответственно если погоня началась через час после побега, а скорость копа 100 км/ч, то в одну сторону копу потребуется 99 часов, во вторую — 9900 ч (100 часов * гипотетическая скорость преступника 99 км/ч).

                      Практически уверен что у этой задачи есть более элегантное и более математическое решение без предположений о разнице скоростей в 1ч.
                        0
                        При скорости копа выше на бесконечно малую величину получаем вариант с бесконечностями.
                        0
                        тут много писать.
                        Пусть побег совершён в момент Т
                        коп начинает дорого в момент времени Т+Тd
                        скорость преступника V
                        копа — V+Vd (Vd может быть любым).
                        соотношение скоростей копа и преступника K=(V+Vd)/V

                        время встречи в одном из направлений Tx1=Td/(K-1) секунд (размерность вроде сошлась)
                        время встречи в другом направлении Tx2=Tx1/(K-1).

                        То есть сделав все предположения мы получаем, что коп сможет догнать преступника за Tx1+Tx2, но не сделает этого, если ошибётся с предположением о разности скоростей.
                        С какой вероятностью оценка разности скоростей полицеского окажется верной?)
                          0
                          в случае, когда Vd=0, то решение вырождается во вариант «коп никогда не догонит никогО» ;) Что в целом, вроде бы, соответствует действительности.
                        0
                        Машина копа более быстрая, чем у сбежавшего чела, но коп об этом не знает.

                        На самом деле, я тоже думал над подобным решением, но условие задачи это решение перечеркивает.

                        В целом, я думаю, что оригинальное решение как раз основывается на подобном логическом заключении. С одной оговоркой. Разница в скорости может быть любой (в том числе и меньше 1км/ч).
                        И беря за основу, что разница в скорости 1км/ч — мы просто увеличиваем шансы того, что догонит.
                        Чем меньше мы будем предполагать разницу в скорости — тем больше вероятность того, что догонит. Но, 100% утверждения в этой задаче сделать нельзя.
                          +1
                          На самом деле, конечно, коп подозревает, что его машина быстрее. Просто он не знает насколько. А в рассуждении выше фигурирует конкретное число Vd.

                          Можно выкрутиться так и будем считать, что Td известно (то есть, коп может оценить верхнюю границу, ну, пусть, один час).

                          Предположим, что Vd = 1км/ч. Проедемся, как написано выше в обе стороны. Не догнали? Ну, наверно Vd меньше. Может 0.5км/ч? Проедемся обять в обе стороны с новым Vd и соответственно пересчитанным Td.

                          Кажется — доказать не пытался — что для любого ненулевого Vd в итоге коп догонит, когда-нибудь.
                      0
                      По условию коп не знает, что скорость его машины выше. Таким образом он может ехать в неправильную сторону бесконечно долго.
                        +1
                        Если коп не дурак, то он должен предположить, что его машина быстрее, иначе догнать беглеца он не сможет в любом случае.
                          0
                          В условии не сказано, что коп — дурак или умный ;)
                          0
                          Он не знает но может это предположить, иначе ему вообще бессмысленно начинать погоню.
                        0
                        2. Дойдем до центра и выберем любого волка. Если волк сейчас в вершине, то выберем любую сторону около противоположной вершины. А если на какой-то стороне, то выбираем противоположную ей сторону. Заметим, что до выбранной стороны нам бежать по перпендикуляру a/2(a — сторона квадрата), а волку не менее a. Мы затратим 0.5a / V, волк 2/3 / V. Мы выиграли?
                          0
                          > и выберем любого волка
                          Любого волка из одного присутствующего в задаче?
                            0
                            Ну ок, одну из собак.
                          0
                          с собаками я поторопился. «играя» за собак можно предложить стратегию такую, что волк не сможет выбраться.
                          Строится она на том, что от волка строится перпендикуляр к каждой из сторон, а так же «наклонные» под 45 градусов к той же стороне. Получается своеобразный «прицел». Собаки могут успевать находиться в точках пересечения наклонной и стороны квадрата. Таким образом, волк не может встретиться только с 1 собакой и, насколько я понимаю конструкцию, не может «запутать» собак так, чтобы обогнать хотя бы 1 из пары.
                            +2
                            Правильно, cобаки выигрывают.

                            Чтобы не запутаться в построениях, можно обратить внимание, что проeкции положения собак на диагонали квадрата совпадают с проeкцией волка, а потом доказать что а) собаки могут сохранять эту ситуацию за счет 1.5 > sqrt(2), б) когда волк доползeт до границы, его встретят 2, а в углу все 3 собаки.
                              –1
                              если в начале задачи волк сидит в центре, то когда он дойдет до одного из углов он встретит только одну собаку, две другие [из соседних углов туда еще не успеют]
                                0
                                Успеют.
                                  0
                                  точно, успевают
                                  значит, волк проиграл, ведь даже чтобы пробежать из одного угла в другой по диагонали ему надо sqrt(a)/x, а собакам 2*а/1,5*x
                            0
                            Волком по расширяющейся спирали надо двигаться, и при малейшей возможности уходить.
                              +2
                              Решение первой задачи от havoc_a (read-only)
                              решение задачи 1:
                              пусть зэк стартует в момент времени t=0 и его движение задаётся кривой y=t (т.е. возьмём скорость равной 1)
                              коп стартует в момент времени t=E (естественно, предполага, что его машина быстрее, иначе какой смысл пробовать доганать?)
                              коп быстренько прикидывает, что ему нужно двигаться по кривой Y=(vt-E)sin(vt-E), где v — максимальная скорость его машины.
                              за точку 0 по оси s (пройденное расстояние) возьмём тюрму
                              По условию v>1 (скорость зэка мы приняли за 1), таким образом коп догонит зека, не зная точно, в какую сторону он поехал.
                                0
                                ого! прикрутить сюда колебания я как-то не додумался. Хотя лежит на поверхности.
                                  0
                                  (ab)' = a'b + b'a, так что по кривой вида vt*sin(vt) он поехать не сможет.

                                  Но сама идея с тем чтобы кататься туда-сюда должна быть правильной, только линейное увеличение колебаний явно будет недостаточно.
                                  +1
                                  Решение первой задачи, опираясь на то, что скорость мента Vm равна скорости зэка Vz + константана Vc, где Vc > ε.

                                  В обе стороны отправляем по виртуальной машине со скоростью Vv = (Vm + Vz) / 2. Т.к. мент не знает скорости зэка, лучше возьмем Vv = Vm — ε.
                                  Мент ждет 1 секунду, потом едет за первом виртуальной машиной, и когда-то ее догонит т.к. скорость его больше этой виртуальной машины. Потом разворачивается и едет за другой. И ее догонит, по тем-же причинам. Потом снова едет за первой, потом снова за второй и так до бесконечности. Учитывая, что скорость виртуальной машины больше скорости зэка, одна из виртуальных машин когда-то его догонит, и мент когда-то догонит ту виртуальную машину, которая уже догнала / обогнала зэка. В общем, мент обязательно догонит.

                                  P. S. Следуя этому алгоритму, мент будет на столько зол, что зэк скорей всего не выживет.
                                    +1
                                    Еще проще — 1 км влево, 10^100 вправо, 10^200 влево, 10^300 вправо…
                                      0
                                      Вот только экспоненты тут не хватит, т.к. доля потраченного «зря» времени всегда будет не меньше некоторой константы. И если доля отличия нашей скорости от скорости преступника меньше этой константы, то мы его не догоним.
                                      Так что едем 1! влево, 2! вправо, 3! влево и т.д.
                                        +1
                                        Если ε известен, а он известен (из условия, в режиме адекватности) — достаточно экспоненты.
                                          0
                                          Думаю, лучше интерпретировать «коп не знает, что его машина быстрее» как «коп не знает, насколько его машина быстрее».
                                            0
                                            Даже если не знает, он будет рассчитывать, что его машина быстрее, иначе все зря. Так что все нормально.
                                              0
                                              Ну да, мы знаем, что мы быстрее, но не знаем насколько.
                                      +1
                                      хорошо, но
                                      1. ε неизвестна, может быть сколь угодно малой.
                                      2. нет смысла гоняться за одной и той же виртуальной машиной много раз.

                                      я делаю другое допущение, что коп примерно знает когда выбежал преступник. Ну, на уровне «не раньше, чем час назад» или «не раньше, чем год назад».

                                      Тогда запускаем виртуальные машины стартовавшие в это время (час назад или год назад) с разными скоростями в обе стороны. Со скоростями, например, V1=Vm — ε (для какой-то фиксированной ε), V2=Vm — ε/2, V3=Vm — ε/3, и так далее. Ну и мент догоняет вначале V1 справа, потом V1 слева, потом V2 справа, и так далее. То есть на каждом втором шаге он предполагает что преступник ехал чуть быстрее, раз он его пока еще не догнал. Рано или поздно догонит…
                                        0
                                        Ну, в таких терминах всё еще проще.
                                        Предполагаем, что он выехал влево со скоростью в 1+x раз меньше нашей, и это было за x минут до начала погони. Пытаемся догнать. Если не получилось — предполагаем, что он выехал вправо со скоростью в 1+x/2 раз меньше нашей за 2x минут до начала погони. И т.д. Рано или поздно наше предположение окажется соответствующим действительности, и мы его догоним.
                                          0
                                          1. Может, поэтому гонятся он будет очень долго, если не повезет сразу догнать. Но вопрос был о теоретической возможности, которую я и доказал.
                                          2. Грубо говоря, а данном контексте, ε это такая величина, что ε = ε / 2; ε != 0; То бишь, сколь угодно малая величина, нет смысла ее делить. Ваше решение годно для нормальной константы, для ε так делать не нужно.
                                            0
                                            Маленькая проблема: такого ε среди вещественных чисел не существует. А скорость автомобиля всё же должна быть вещественным числом:)
                                              0
                                              Странно, что для вас это проблема). Для меня нет). Это я грубо говоря, говорил. Ну просто константа, которая достаточно мала, чтобы гарантировано быть меньше разности скоростей. Не того уровня задача, чтобы протестовать против такого утверждения.
                                                0
                                                ИМХО, в этом один из основных пунктов этой, действительно несложной, задачи. Такой константы, по условию, нет.
                                                  0
                                                  И для меня всегда проблема, когда люди начинают использовать исчисление бесконечно малых нестрого. Очень уж легко получить таким образом неверные утверждения.
                                                  Хотите использовать бесконечно малые в точности как обычные числа — к вашим услугам нестандартный анализ, в котором, правда, есть свои заморочки. Иначе нужно учитывать аксиому Архимеда и аккуратно переходить к пределам.
                                                    +1
                                                    Хорошо, тогда берем за финальное решение то, что предложил petropavel.
                                        0
                                        Ради всего святого, дайте еще задачек!!! И, по возможности, посоветуйте сборник таких вот задачек.
                                          0
                                          Сам бы рад такой сборник заиметь. Доберусь до компа, сделаю еще 1 пост с задачкой.
                                            0
                                            в детстве занимались по сборнику «Математическая смекалка» Кордемского
                                            0
                                              +2
                                              TheHorse просит задачек, DudeOnTheHorse скидывает TheHorse задачки)
                                                0
                                                Вторая шутка про нас :)
                                              +1
                                              «Как сдвинуть гору Фудзи» Уильям Паундстоун
                                              0
                                              По второй задаче, нужно выбрать внутренний квадрат (круг), перемещение по которому будет происходить быстрее чем собаки будут адаптироваться под положение волка. Перемещаясь по такому квадрату (кругу) волк вероятно сможет привести собак в положение, когда он сможет выйти убив одну из собак или никого не убивая.
                                                0
                                                Нужен точный, а не вероятный ответ.
                                                –2
                                                1-я задачка не очень корректно сформулирована, но решается:
                                                Коп должен ехать Х часов в одну сторону. потом развернуться, вернуться до тюрьмы и ехать в другую сторону. В каждой итерации нужно заезжать в N раз дальше чем в предыдущей итерации. Например — ехать 1 час на юг, вернуться, ехать 10 часов на север, вернуться, ехать 100 часов на юг, вернуться, и т.д. Чем больше N тем раньше догонит.

                                                2-я задачка вообще примитив — у волка нет шансов. Проведем через волка две прямые, параллельные диагоналям (!!!) квадрата. Собаки должны в точках пересечения этих прямых со стенками квадрата. волку капец.
                                                Формулки можете самостоятельно на досуге написать…
                                                  0
                                                  Легко доказать, что так коп преступника не догонит. Пусть у копа скорость V, а у преступника — U. Коп проезжает вначале V километров на юг за час, потом VN километров на север за N+2 часа, потом VN2 километров на юг за N2+2N+2 часов, и так далее. В общем, на каждом шаге он проезжает в какую-то сторону VNk километров за
                                                  image
                                                  часов, в течение которых преступник едет в одну сторону с постоянной скоростью U. Чтобы коп догнал преступника, необходимо чтобы
                                                  image
                                                  или
                                                  image

                                                  Поскольку коп не знает, насколько его машина быстрее, то N выбирается не зная V/U. И какое бы N коп не выбрал, всегда может оказаться, что V/U достаточно мало, чтобы нарушить это неравенство при любом k. И тогда коп никогда не догонит преступника.

                                                  На самом деле, конечно, догонит, доказательств достаточно выше в обсуждении. Но ему нужно будет ехать не «в N раз дальше чем в предыдущей итерации». Расстояние должно возрастать быстрее, чем по экспоненте. Об этом тоже, впрочем, выше уже упоминалось, но без формул.

                                                  0
                                                  Исходя из условия, у меня получилось, что у волка нет шансов.

                                                  Если бы собаки могли перемещаться только до соседнего угла, тогда можно было бы обмануть.

                                                  А так получается:
                                                  можно принять, что охранять его будут две собаки, к которым он начал движение из центра, а две остальные на подстраховке. Чем ближе он к «охранникам-собакам» тем, они ближе друг к другу при смещении в любую сторону по часовой или против собаки смещаются в этом же направлении, сохраняя необходимые расстояния.

                                                  или нужно математически описать?

                                                    0
                                                    А я тоже долго думал над задачей, там и не смог найти решения. Я все-таки соберусь, и распишу свою логику, в целом думаю будет интересно.

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