НеГрустин
НеГрустин личный блог
20 октября 2014, 07:13

Can you solve this puzzle? (Задача)

 

Source link: http://www.optiver.com/amsterdam/careers/job-vacancies/details/5341/Junior-Researcher


You have to walk from point A to point B 10 times, blindfolded. Every time before you start walking, a fair coin is tossed, and if it comes out heads, a wall in the middle is present (situation 2 in the picture), while if it comes out tails it is not (situation 1 in the picture). As you are blindfolded, you do not know if the wall is present or not.
Even though you are blindfolded, you can move in perfectly straight lines towards any point you choose. Can you give a prescription how to walk from A to B so that the total distance you cover is as small as possible? What distance do you expect to cover in those 10 walks?

Can you solve this puzzle? (Задача)






Fair Play — in play! Search in Web — is not a solve! ;)
Know this already — don't put an answer.
Solution paths describe — Your bonus points!



Special thanks to Тот самый Артур 





Далее — решите задачку, и только потом — сравнивайте!







Мои рассуждения:
 
Так как задачка для программеров, то решение в виде алгоритма:


1) шагаем от А до центра;
2) чекаем, презент ли уолл;
— иф презент,
3а) муваем ап то 1метр,
4а) зэн муваем стрэйт в точку В
— иф уолл нот презент,
3б) муваем сразу стрэйт в точку В
Усё! ;)
Correct Me if I wrong))))

 


 
Теперь дистанс'ы.

При идеальном раскладе — 10 из 10 — путь равен 20 метрам.
При очень плохом раскладе — 0 из 10 — максимальный путь по алгоритму = 1+1+1.41 = 3.41 х 10 = 34.14 м.

При средней «везучести» — 4 из 10 — путь = (4 х 2м) + (6 х (1+1+1.41м)) = 8 + 20,48 = 28,48 м.
Итого: средняя везучесть «выгрызает» неплохо — восемь с половиной метров из четырнадцати!


Можно было, конечно, ломиться сразу напрямик к верхней (или нижней) точке стены, а затем как в 4а),  но тогда полный путь будет = 2 х 1.414 х 10 = 28.28 м.
Таким образом, обыгрываем dumb_throught даже при трёх «не_стенах.» Алгоритм признаём живучим.))

Ответ на второй вопрос: «No greater than 31 meters.»





Интересно — меня бы взяли?))))


9 Комментариев
    • AlexeyTikhonov
      20 октября 2014, 08:31
      НеГрустин, Что-то у меня с английским таким худо,
      можешь написать по русски что надо-то (условие).
      Решу, или аналитически или Монте-Карло.
    • The Archie Slap
      20 октября 2014, 18:44
      НеГрустин, Супер, все верно!

      Только с fair coin всегда подразумеваем 50% 'везучести' на дистанции, я думаю столько и надо брать, не смотря на то, что всего 10 раз подкидываем.

      1. (4*5) + (2*5) = 30 — двигаясь линейнo
      2. (1.414*2*10) = 28.28 — двигаясь по диагоналям сразу
      3. (3.414*5) + (2*5) = 17.07 — прямо-вверх-диагональ

      Wall/NoWall = 6:4 >>> (3.414*6) + (2*4) = 28.484 — не выгодно методом 3, лучше по диагонали.

      Ответ:

      В долгосроке, либо с вероятностью в нашу сторону — используем метод 3.
      При вероятности против нас — используем метод 2.

      П.С. Помимо умения решать задачки, там много других критерий и тестов на скорость, внимательность и навыков в целом :))
  • VadimChes
    20 февраля 2015, 01:18
    У меня получилось в среднем 26.2 метра при десяти проходках. Т.е. вероятность встретить стену равна 0.5. Пишем уравнение зависимости средней длины проходки от отклонения по горизонтали, считаем его минимум… Итого это отклонение равно корень из 0.125.
    Может, я в чем-то и ошибаюсь.
  • VadimChes
    20 февраля 2015, 08:59
    В задаче нам не дали оснований полагать, что одна сторона монетки выпадает чаще другой. Да и странная это была бы монета. В среднем двигаясь так будет кратчайший путь. Хотя конечно каждый отдельный результат будет больше или меньше

Активные форумы
Что сейчас обсуждают

Старый дизайн
Старый
дизайн