Сто игроков играют вместе против казино.
Процесс игры происходит следующим образом: игроки пронумерованы от 1 до 100. Каждому игроку соответствует жетон с таким же номером. Жетоны уносятся в отдельную комнату, где случайным образом раскладываются по 100 коробочкам (распределение равномерное). Для удобства, коробки также пронумерованы от 1 до 100. Игроки по очереди заходят в комнату с коробками и пытаются отыскать жетон со своим номером. Найденный жетон остается в коробке. Каждый игрок имеет право открыть не более 50 коробочек. После того как игрок закончил свою попытку, он удаляется в комнату ожидания, к своим друзьям, уже завершившим свои попытки, а испытательная комната и коробки приводятся к исходному виду.
Таким образом, какая-либо передача информации между теми, кто свою попытку сделал и ожидающими своей очереди, совершенно исключена. Задача без подвохов.
Если все игроки успешно отыскали свои номера, казино выплачивает каждому по сто долларов.
Если хотя бы один из игроков свой номер не нашел, каждый игрок выплачивает казино один доллар.
Как должны действовать игроки, чтобы математическое ожидание их выигрыша было положительным? (Это возможно).
Решение на следующей неделе, комментарии скрыты.
https://www.youtube.com/watch?v=eivGlBKlK6M
Segodnya mne bez golovolomok:(
ps. Spasibo za vse ostolnoe!
Решение.
Были установлены следующие факты:
- а) Изменить индивидуальную вероятность нахождения номерка человеком (== 0.5) мы не можем. Значит надо добиваться большей "одновременности" успехов\неудач всех игроков.
- б) Это значит, что мы должны составить такой алгоритм действий всех игроков, что они или одновременно "угадывали" или одновременно же "не угадывали".
- в) Алгоритм поиска не учитывающий значения билетиков в открытых ящиках нам не поможет (вообще-то это были довольно нестрогиме рассуждения + оценка сверху).
II. НОВАЯ (БОЛЕЕ УЗКАЯ) ФОРМУЛИРОВКА
Переформулируем (на самом деле это более строгое условие но на практике вероятности близки до неразличимых значений) нашу задачу следующим образом:
Найти такую пару (C, A): [C]aracteristic и [A]lgorithm, что:
- для любой [S]equence (случайно перетасованных числел 1-100) обладающей свойством С существует алгоритм A(n), находящий номерок (n) не более, чем за 50 просмотров.
- вероятность того, что Sequence будет обладать заданным Characteristic не менее 1\100.
III. РЕШЕНИЕ:
Characteristic:
Для любого номера "n" за 50 прыжков("прыжком" назовём переход к ящику с номером == номеру билетика в только что открытом) от "ящика с номером n" можно добраться до "ящика содержащего билетик с номером n"
Algorithm:
1. Начинаем с ящика с номером n (искомое число).
2. Номер следующего ящика вычисляем по формуле: box[i-1], т.е. просто открываем ящик с тем номером, который лежал в предыдущем.
IV. ПОЧЕМУ ЭТО РАБОТАЕТ:
1. Давайте представим наши "ящики и номерки" в виде графа (возможно нагляднее в виде двудольного?):
-а- вершины (будем считать их ящиками) пронумеруем от 1 до 100.
-б- рёбра: если ящик №n содержит бумажку с №m, то проведём направленное ребро (n,m).
2. Посмотрим какими свойствами обладает наш граф:
-а- в каждую вершину входит и выходит ровно по одному ребру (исходящее ребро -- бумажка, лежащая в ящике, входящее -- одна бумажка имеет № == №ящика).
-б- наш граф представляет собой объединение направленных простых циклов. Простой цикл, это не содержащая других рёбер цепочка a1 -> a2 ->...an -> a1 (для конечного графа со свойством 2.а -- очевидно док-ся).
-в- надо отметить, что ничего о "длине" цепочек мы не сказали. Т.е. граф может представлять собой как одну цепочку из 100 элементов, так и 100 цепочек по 1у элементу.
3. Посмотрим, что представляет собой наш алгоритм, напомню, что мы ищем "бумажку №n", и начинаем поиск, с "ящика №n":
-а- существует дуга входящая в n (m->n) <=> в "ящике №m" лежит "бумажка с номером n".
-б- двигаясь по дугам мы найдём нужный нам "ящик №m" только пройдя все элементы цикла начиная с m.
V. НЕКОТОРЫЕ ИНТЕРЕСНОСТИ:
Описанным выше способом ломались LM-hash (хэширование паролей для Win-XP) правда не всегда. Это когда мы "похитили хэш", а нам надо узнать пароль.
http://en.wikipedia.org/wiki/LM_hash
Грубо говоря способ такой (пусть у пользователя был пароль passw, а мы похитили его хэш):
hash( passw) -> hash( hash( passw)) -> hash^3(passw) ->... -> hash^k(passw) == new_pass.
hash(passw) == hash(new_pass) (при этом сами строки passw, new_pass скорее всего не равны).
Тут всплывает сразу масса проблем:
a) ОДЗ(lm_hash) == 2^256 (2 слова по 8 байт, но второе лишнее) -- ОЧЕНЬ много значений, почему цепочки такие короткие, что ответ находится за разумное время
б) граф (построенный тем же способом) наз ОДЗ lm_hash вообще-то не совокупность простых циклов, т.к. пароль предварительно "приводится" к upper_case.
в) Область определения lm_hash -- 14 "символов" = 67^14, область допустимых значений 8 байт = 256^8.
И они скорее всего не совпадают(скорее всего существуют строки, которые не будут являться lm-хэшем другой строки).
Собственно у меня есть резонный вопрос (на который нет ответа): почему этот способ вообще даёт результат хоть в каком-то % случаев.
Edited at 2014-12-22 01:03 pm (UTC)