24 июл. 2011 г.

Кто пылесосит по ночам?

Представьте, что каждую ночь вы слышите не стук перфоратора, не уроки игры на пианино, не весёлую пьянку (потому что живёте в хорошем доме, жильцы которого отличаются повышенной вменяемостью), а... работающий пылесос. Вроде бы никто новый в дом не вселился, но почему-то один из соседей внезапно начал пылесосить каждую ночь примерно с 2:00 до 2:30. Нельзя сказать, что это нестерпимо громко, так как спать особо не мешает. Но интригу-то создаёт! Как тут спокойно уснёшь, если шесть месяцев каждую ночь повторяется одна и та же загадка — что они делают пылесосом по ночам? А через полгода всё прекратилось, как будто и не было ничего. И даже не понятно, кого спросить о причине странных ночных звуков.

В комментариях я буду отвечать, совпадают ли ваши версии с ответом, который я имею основания считать правильным.

Ну а если вы любите ясные формулировки, не подразумевающие нескольких толкований, то следующая математическая часть заметки для вас. Вернёмся к последней задачке об общей цели группы людей. Напомню, что вопрос был в том, с какой вероятностью группа из 2N человек побеждает в игре, если все люди умные и умеют договариваться. Другими словами, надо предъявить функцию P(N), которая описывает вероятность победы группы, а также доказать, что группа не может действовать лучше.

В самой заметке мы доказали, что P(1) = 1/2. Более того, для N>1 очевидно, что P(N) <= 1/2 (так как первый игрок не может обеспечить вероятность выше, чем 1/2, а остальные игроки выше 100% тоже не прыгнут.

Легко понять, что P(N) >= 1/2^(2N), так как каждый игрок, если будет действовать случайным образом, вытянет свой номер с вероятностью 1/2, а всего участников 2N. Так мы сделали оценку снизу.

Далее в комментариях к заметке было предложено несколько подходов для игроков:
- сначала открывать коробочку со своим номером на борту, а дальше (пока не нашёл табличку со своим номером) открывать коробочку с тем номером, который был на табличке из прошлой коробочки. Это интересный способ, но как было показано в комментариях ниже, если в нашей перестановке есть циклы, то игроку придётся открывать одни и те же коробочки несколько раз, что, очевидно, неэффективно.
- ещё можно игрокам с чётными номерами открывать только чётные коробочки, а игрокам с нечётными номерами — только нечётные коробочки.
- очень похожий подход: чётные игроки открывают коробочки с 1 по N, а нечётные — с N+1 до 2N.

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

Определим функцию вероятности победы P(N, S), где S — стратегия группы из 2N игроков:
P(N, S) = W(N, S) / C(N).
В этой формуле W(N, S) — это количество побед для группы из 2N человек, пользующихся стратегией S, на всех возможных входных данных (наборах табличек в коробочках). А C(N) — это количество всех возможных входных данных (т.е. количество способов поместить 2N разных табличек в 2N разных коробочек). Здесь мы исходим из того, что размещение табличек по коробочкам является полностью случайным (т.е. мы можем считать, что все эти элементарные события равновероятны).

Как определиться C(N)? Очень легко — C(N) = (2N)! (т.е. 2N(2N-1)(2N-2)(2N-3)...3*2*1). Это одна из первых формул, которую доказывают студенты, начинающие заниматься комбинаторикой.

А как определить W(N, S)? Простейший способ — честно посчитать. Надо всего лишь проверить для всех перестановок, позволяет ли стратегия S выиграть всей группе (за каждый случай победы надо увеличивать W на единицу).

Давайте, например, разберёмся с этой задачкой для N=2 (раз уж с N=1 мы всё поняли в прошлой заметке):
C(2) = 4! = 24. Действительно, у нас есть следующие 24 перестановки табличек в коробочках:
1234,
1243,
1324,
1342,
1423,
1432,
...
...
4312,
4321.

Теперь для каждой стратегии S, которую мы хотим проверить, надо попробовать её применить на всех 24 возможных входных данных. Соответственно, вероятность P(2, S) = W(2, S) / 24.

Зачем все эти сложности? Во-первых, далеко не все задачи получается решить сразу в общем виде. Часто бывает эффективно поиграть с частными случаями, чтобы лучше понять суть. Во-вторых, в теории вероятностей есть масса тонкостей, поэтому очень легко допустить ошибку в рассуждениях (особенно, если не иметь регулярной практики решения вероятностных задач). А предложенный подход хоть и требует аккуратности при переборе случаев, но позволяет избавиться от ошибок в рассуждениях о вероятностях, что на начальном этапе очень нужно.

Далее, имея в руках какие-то надёжно насчитанные равенства и неравенства, можно будет увереннее продвигаться в решении этой задачки. Предлагаю в комментариях к этой заметке добить случай N=2, чтобы в скором времени попробовать ответить на вопрос: если N стремится к бесконечности, то P(N) стремится к нулю? И если не к нулю, то к чему?

Пользуясь случаем, удивлюсь малому количеству ответов к задачке о выворачивании кубика. Что случилось? Вы не пьёте молоко и соки? Или не имеете ножниц, бумаги и скотча? ;) Задачка же хорошая! А пропадает почему-то...

Хороших выходных!

31 комментарий:

  1. Может они пылесосом водяные счетчики сматывали? хотя почему обязательно по ночам...

    ОтветитьУдалить
  2. Анонимный24.07.2011, 10:57

    Ловят комаров?

    ОтветитьУдалить
  3. Они просто пылесосили ковры каждую ночь, а потом надоело.

    ОтветитьУдалить
  4. Евгений, интересная версия! Не могу представить, как это сделать, но звучит весело :)

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

    obiwanus, это рассуждение теоретика, оно почти не помогает понять, что происходит. Почему вдруг начали пылесосить? Почему перестали? И почему именно ковры? ;)

    ОтветитьУдалить
  5. Для N = 2 вероятность выиграть составляет 1/6. Долго думал в прошлый раз, как вывести общую формулу, но так ничего и не придумал.

    > если N стремится к бесконечности, то P(N) стремится к нулю

    Да, потому что с увеличением количества игроков шансы на то, что им _всем_ попадется нужный номер уменьшаются.

    ОтветитьУдалить
  6. monkegoist, если неотрицательная функция P(N) убывает при росте параметра N, то это ещё не значит, что она приблизится к нулю сколь угодно близко. Теоретически она может стремиться не к нулю, а, например, к 1/1234, так ведь?

    ОтветитьУдалить
  7. А может они наполняли надувную кровать?

    ОтветитьУдалить
  8. Воможно это не пылесос а наружный блок от дешёвой сплит-системы.

    ОтветитьУдалить
  9. Анонимный24.07.2011, 11:46

    Уехали, а робот-пылесос запрограммировали на ежедневную чистку, так чтобы пыль не скапливалась.

    Но перепутали AM и PM )

    ОтветитьУдалить
  10. Возможно, что человек занялся каким-то делом, бизнесом, и пылесос был или частью техпроцесса (сушил клей), или он просто убирал рабочее место после работы. Я был в той же ситуации, работал один у себя дома. У меня пылесос включался, в том числе и по ночам, когда я заводил станок с ЧПУ, но такой регулярности не было (но я вообще плохо организован). Не близко?

    Тихий технический пылесос (shop vacuum) я долго искал, нашел непристойно дорогой и заказывал его из-за границы по почте, но — с уровнем шума 55dB, так что при нем можно даже разговаривать почти не напрягаясь! Именно чтобы меньше беспокоить соседей шумом по ночам.

    ПС. Илья, последний раз пишу Вам комментарий. не отправляется: каждый раз пытаюсь раз по 6, прежде чем удается! Забываю, какая из опций работает. Анонимно не получается, LiveJournal не получается. пробую дальше. Кнопка Preview просто стирает поле воода комментария, и каждая неудачная попытка — тоже. Писать больше не буду, это слишком сложно. Но все равно буду Вас читать!

    open id не сработал (3-я попытка)
    google account не сработал (4-я)
    теперь пробую из Хрома (не вышло)
    анонимно (fegimus я, если что) не вышло
    chrome/google account - trebuet зарегистрироваться в Blogger, не буду! 7 неудач уже!
    chrome/livejournal -

    ОтветитьУдалить
  11. Вопрос про пылесос напомнил произведение С.Лема "Расследование" :) Там тоже была интрига со странными звуками по ночам. И как же банально она разрешилась!

    Время (2 часа ночи) наводит на мысль, что это экономия электроэнергии. В таком случае, это может быть стиральная машина.

    ОтветитьУдалить
  12. Анонимный24.07.2011, 13:43

    Fregmius, а у тебя/Вас работают плагины Noscript или Adblock? Если да, то неудачные настройки могут к таком приводить.
    У меня никогда не было проблем с комментированием на blogspot.com, поэтому я почти уверен, что это из-за неудачных настроек компьютера/браузеров/антивирусов/файерволла/... Надо пробовать из чистой системы, а потом потихоньку донастраивать своё привычное окружение.

    ОтветитьУдалить
  13. Как вариант - пылесосом заглушались постельные звуки (живые или из телевизора).
    Начались/прекратились потому, что квартиранты заехали / съехали или (если заглушались звуки adult канала по телевизору) - подписка на канал закончилась.

    ОтветитьУдалить
  14. А вы не мой сосед??? У нас гостил дедушка, мы каждый вечер, честно - довольно поздно, так как забывали вовремя... - надували надувную кровать. Принцип - как у пылесоса, звук тоже :)

    ОтветитьУдалить
  15. Может подкачивали надувной матрас на котором спали? И был это не пылесос, а насос.

    ОтветитьУдалить
  16. 1) Накачивали надувной матрас - звук очень похожий. Звуки прекратились, потому что соседи купили себе нормальную кровать, либо съехал жилец для которого этот матрас накачивали.
    2) У соседей жил ночной зверь типа шиншиллы, который при купании разбрасывает много песка вокруг клетки, а купается только по ночам. Поэтому приходилось убираться ночью. Звуки прекратились потому что соседи не вынесли такой жизни и выгнали животинку.

    ОтветитьУдалить
  17. Анонимный24.07.2011, 22:05

    Пишет аноним из предыдущей заметки
    --К пылесошенью--
    Возможно это был некоторый автоматизированный процесс, со звуком, похожим на звук пылесоса (какой-нибудь хитрый обогреватель воздуха?..), а через полгода в нём пропала нужда (стало тепло на улице?).

    --К задачке про циклы--
    >>Это интересный способ, но как было показано в комментариях ниже, если в нашей перестановке есть циклы, то игроку придётся открывать одни и те же коробочки несколько раз, что, очевидно, неэффективно.
    Не понял сути претензий к стратегии. Если в нашей перестановке есть циклы (а они есть), то при длине цикла меньше либо равной N игрок найдёт свою карточку. При длине цикла больше либо равной N - не найдёт.

    Два вторых способа дают равные вероятности - n!^2/(2n)!, что равно n!/((n+1)...(2n))
    При N = 50 это даёт удручающий результат порядка 10^(-30).

    Оценка (при N -> inf вероятность будет стремиться к ln(2)) данная мною в предыдущем посте - неверна. Правильная оценка это 1-ln(2).

    Про максимизацию шансов в этом случае - да, доказать не могу, и вообще есть предположение, что для каждой длины "идеальная" стратегия будет своей.

    Далее идёт повтор рассуждений про вероятность (с показом ошибки, собственно):
    W(N, S) = число "хороших" перестановок из 2N элементов = число таких перестановок из 2N элементов, что в них нет циклов длины больше N = C(N) - число таких перестановок, в которых есть циклы длины больше N = C(N) - (сумма по i от 1 до N: ((число всевозможных выборок из N+i элементов для цикла)*(число всевозможных циклов из N+i элементов (фиксированных))*(число различных перестановок остальных N-i элементов)) = C(N) - (сумма по i от 1 до N: C_(2N)^(N+i)*((N+i)!/(N+i))*(N-i)!)
    n!/n получается из-за того, что у нас n! возможных порядков на множестве из n элементов, но у нас цикл.
    Раскрывая C_(2N)^(N+i) получаем вот такое выражение
    http://www.numberempire.com/equation.render?(2N!)%20-%20\sum_{i=1}^{N}%20\frac{(2N)!}{(N+i)!(N-i)!}%20\frac{(N+i)!}{N+i}(N-i)!%20=%20(2N!)(1-\sum_{i=1}^{N}%20\frac{1}{N+i})
    Поделив его на С(N) = (2N)! получим
    http://www.numberempire.com/equation.render?P(N)%20=%20(1-\sum_{i=1}^{N}%20\frac{1}{N+i})

    Обозначив за A(N) сумму http://www.numberempire.com/equation.render?A(N)%20=%20\sum_{i=1}^{N}%20\frac{1}{N+i}

    мы получим, что P(N) = 1-A(N). Далее, выполнив нехитрый вывод (http://www.numberempire.com/equation.render?A(N)%20=%20\sum_{i=1}^{N}%20\frac{1}{N+i}%20=%20\sum_{i=2}^{N-1}%20\frac{1}{N-1+i}%20+%20\frac{1}{2N}%20+%20\frac{1}{2N-1}%20=%20A(N-1)%20-%20\frac{1}{N}%20+%20\frac{1}{2N}%20+%20\frac{1}{2N-1}%20=%20A(N-1)%20+%20\frac{1}{2N-1}%20-%20\frac{1}{2N}), получаем, что
    A(N) = A(N-1) + 1/(2N-1) - 1/2N
    Т.к. A(1) = 1/2, то получаем, что A(N) = 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ... + 1/(2N-1) - 1/(2N)
    1-A(inf) таким образом равна 1-(1-1/2+1/3-1/4+...) = 1-ln(2).

    ОтветитьУдалить
  18. по пылесосу.
    звук работающего пылесоса, наряду со звуком льющейся воды, посудомойки и многих других звуков напоминающих белый шум, имеет успокаивающий эффект на некоторых плачущих младенцев. так что по-видимому соседи кого-то родили, и во время ночного кормления, вместо успокаивания звуком ш-ш-ш-ш, используют автоматизацию - пылесос.

    ОтветитьУдалить
  19. fox, поздравляю! Вы назвали ответ, который я подразумевал. Сомневающимся предлагаю ввести в поисковую машину запрос «ребёнок плачет звук пылесоса», например.
    Что касается надувных матрасов и ловли комаров, то 30 минут - это явный перебор, поэтому предлагаю такие версии не рассматривать.

    > Не понял сути претензий к стратегии. Если в нашей перестановке есть циклы (а они есть), то при длине цикла меньше либо равной N игрок найдёт свою карточку. При длине цикла больше либо равной N - не найдёт.
    Верно! Было бы здорово, если бы несколько человек заметили это... Собственно, в том и смысл таких рассуждений в заметках — учиться критически относиться к вроде бы правдоподобным высказываниям.

    Вы здорово продвинулись в решении этой задачи!

    fregimus, очень жаль, что у Вас такие сложности с оставлением комментариев. Я почти уверен, что это связано со специфическими настройками компьютера (возможно, антивирус шалит, возможно, файервол самостоятельность проявляет...). Ну и плагины надо проверить, как подсказал аноним. Сервисом блогов от Гугла успешно пользуются миллионы, поэтому я подозреваю, что какая-то вычурная настройка всему виной. Если не трудно, попробуйте, пожалуйста, проверить. Или хотя бы напишите, что значит «не сработало». Какую ошибку пишет? Что именно не так?

    ОтветитьУдалить
  20. Анонимный26.07.2011, 14:05

    >- сначала открывать коробочку со своим номером на борту,
    >а дальше (пока не нашёл табличку со своим номером)
    >открывать коробочку с тем номером, который был на
    >табличке из прошлой коробочки. Это интересный способ, но
    >как было показано в комментариях ниже, если в нашей
    >перестановке есть циклы, то игроку придётся открывать
    >одни и те же коробочки несколько раз, что, очевидно,
    >неэффективно.

    Это как раз эффективно. )
    Если игрок попадет в короткий (не более N) цикл, то он гарантированно найдет свой номер. ))

    В этом случае, действительно, остальные можно не открывать - а зачем? )

    Илья

    ОтветитьУдалить
  21. Ура, второй человек заметил!
    Здесь уже разобрано, что этот подход позволяет выигрывать с вероятностью 1-ln(2), если N стремится к бесконечности.

    Осталась мелочь — доказать, что более эффективной стратегии нет :)

    ОтветитьУдалить
  22. Анонимный27.07.2011, 11:40

    Мелочь, действительно. :)

    Я, конечно, ошибался, считая, что это еще открытый вопрос. Доказано, что так.
    Даже нашел ссылку на статью, из которой это следует (якобы).
    Вот она: http://www.daimi.au.dk/~bromille/Papers/succinct.pdf

    Как следует - просмотрел, но пока не понял. )

    Илья.

    ОтветитьУдалить
  23. Анонимный27.07.2011, 18:24

    Илья: Пробую еще раз тем же путем, что последний раз удалось. [Не вышло]

    Когда не работает, просто та же страница с пустой рамкой для комментария появляется. Под кнопкой «Просмотр» подчеркивание коротенькой красной линией.

    Антивируса нет, firewall нет.

    ОтветитьУдалить
  24. fregimus,
    последние дни ЖЖ болеет (то не открывается, то не работает), что, очевидно, мешает пройти авторизацию (чтобы у меня в блоге подписаться своим ЖЖ-ником). Поэтому эксперименты последних дней с отправкой комментариев, хоть как-либо ассоциированных с ЖЖ (open id), предлагаю считать неосмысленными.

    Более того, у Вас на компьютере какие-то хитрые настройки (или в софте дело, или в провайдере, или ещё в чём-то), так как Вы сами написали: «Странное дело: из дома так и не могу отправить комментария, ни одного, а с работы (VPN) мгновенно». Если Вы сначала в ЖЖ не можете написать комментарий, а потом в blogger.com не можете написать комментарий, то, возможно, дело не только в blogger.com...

    Я не спорю, blogger.com не идеален. Но у миллионов людей он вполне работает. Предлагаю ещё раз попробовать разобраться, какая настройка мешает Вам отправлять комментарии в ЖЖ и blogger.com.

    ОтветитьУдалить
  25. Анонимный29.07.2011, 11:41

    Раз комментировать предыдущую задачу предложили здесь, тогда так:
    Вероятность выигрыша всех 50%.
    Стратегия такая:
    1-ый заглядывает в первые N коробочек. Свой номер он найдет с вероятностью 50%. Если он не нашел свой номер, то дальше играть бессмыслено.
    Если же нашел, то
    i-ый человек в поисках своего номера всегда ищет номер i+1. (это относится и к первому человеку). После возвращения в комнату он либо встает либо к одной стенке, показывая, что в первых N коробочках он увидел номер i+1, либо к другой, показывая, что он этот номер не видел.
    Тогда i+1 человек знает, какую из половины коробочек посмотреть. Вероятность нахождения своего номера 100%, т.к. либо его видели в одной половине и он его тоже увидит, просматривая эти коробочки, либо его номер не видели, но он просмотрит оставшиеся и найдет его.
    Дмитрий

    ОтветитьУдалить
  26. Дмитрий, Вы решили другую задачу. Но спасибо, что сообщили об этом оригинальном решении!

    В исходной же постановке игроки не могут общаться между собой во время игры. То есть, всё их общение происходит до того, как первый войдёт в комнату с коробочками. После этого никакой информации они передавать не могут.

    ОтветитьУдалить
  27. Анонимный29.07.2011, 18:01

    Да. Это вопрос к тому, что мы понимаем под общением. Если запрещено общаться является запретом говорить и показывать какие-то жесты, то есть способ сигнала как я описал. Если же общаться - это вообще никаких сигналов, то в условии можно было написать так: человек проходит через комнату с коробочками в какую-то третью. Таким образом мы показываем, что у нас нет ни бита информации от предыдущего.
    Дмитрий

    ОтветитьУдалить
  28. Есть ещё версия, что сосед сверху - лунатик, и пылесосит во сне. Ну а потом или вылечился, или съехал.

    ОтветитьУдалить
  29. Обычно всё бывает проще.
    1.Муж не ночует дома. Жена снимает нервный стресс. Потом развелись.
    2.Дом новый,человек делает ремонт, а работает во вторую смену.
    Лучше - первый вариант.
    Накачка матраса отпадает - через день купишь новую кровать, чем такие проблемы.

    ОтветитьУдалить
  30. По пылесосу кроме как сектанты поклоняющиеся богу, который умеет превращать магию света (молнии) в магию ветра, я не предложу идей.

    Сам недавно стал отцом, и пока за 28 дней существования сына (в т.ч. 25-ти дней его нахождения дома) ни разу не совпали периоды в которые он ночью кричал/плакал. А тут пол года и каждый день подряд, и так точно 2:00-2:30... Какой-то уж слишком запрограммированный ребёнок.

    ОтветитьУдалить
  31. Анонимный27.10.2015, 5:53

    сосед распространял наркотики
    зачищал следы пылесосом

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний