?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

Кусочек прекрасного - morfizm


Jun. 5th, 2010 05:20 pm Кусочек прекрасного

Жена спросила меня по телефону "что у тебя интересненького?". Я ей рассказал, что есть известная задачка о днях рождениях, а Денни предложил другую задачку: сколько нужно минимум людей, чтобы с вероятностью 50% или больше каждый день в году был чей-то день рождения?

Можно приблизительно посчитать моделированием – это легко. Самый смак – вывести формулу. У меня пока получилась рекуррентная формула с довольно сложными комбинаторными суммами. Она правильная, работает полиномиальное время, но для такого параметра как 365 дней она работает бесконечно долго. Я запустил её считаться вчера вечером и, судя по результатам сегодняшнего дня, ей нужно ещё несколько дней поработать.

P.S. Жена спросила: "зачем ты мне это рассказываешь?". Я ответил: "отвечаю на твой вопрос". В принципе, я не собирался ей про это рассказывать. Но она же сама спросила, что у меня интересненького.

P.P.S. Если кто хочет порешать задачку, я думаю, лучше обсуждать её централизованно, в оригинальном посте.

Tags:

17 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:miris_rants
Date:June 6th, 2010 03:45 am (UTC)
(Link)
I especially like the fact that this is tagged as "beauty"

Feel myself now as a blind man to whom someone tries to describe in words how the flowers look.
From:morfizm
Date:June 6th, 2010 06:40 am (UTC)
(Link)
Я хотел вначале ввести тэг "puzzles", потом понял, что такого тэга ещё нет, и подумал: "Зачем плодить сущности? тэгов и так слишком много. Лучше грамотно обобщить."
From:tery
Date:June 6th, 2010 11:55 pm (UTC)
(Link)
при заказе цветов себе любимой на праздник, проще ссылку в гугле дать чем часами объяснять и в результате получить не то :)
From:morfizm
Date:June 7th, 2010 12:26 am (UTC)
(Link)
А что, практичная мысль: цветы добавлять в обычный вишлист :)
From:_vr_ghost
Date:June 8th, 2010 12:22 am (UTC)
(Link)
у меня получилось 253 человека.

Собственно решил я так

>>> delta = lambda takenDays: 1 - takenDays/365.
>>> people = 0
>>> days = 0
>>> while days/365. < .5:
... people += 1
... days += delta(days)


Собственно, идея в том что каждый человек добовляет в сумму количиства уникальных дней рождений вероятность того что его день рождения будет уникальной датой.
From:dennyrolling
Date:June 8th, 2010 04:30 am (UTC)
(Link)
вероятность того что при количестве людей меньше 365 каждый день в году это чей-то день рождения равна нулю.
From:_vr_ghost
Date:June 8th, 2010 11:03 am (UTC)
(Link)
да, но вопрос сформулирован "каждый день есть 50% вероятность того что у кого-то есть день рождения".

Или к чему этот комментарий?
From:morfizm
Date:June 8th, 2010 11:07 am (UTC)
(Link)
Ты изменил формулировку вопроса.
На самом деле, вопрос был сформулирован так: (цитирую пост выше) "сколько нужно минимум людей, чтобы с вероятностью 50% или больше каждый день в году был чей-то день рождения?"

Я не знаю, как можно понять вопрос иначе, чем вот так: "сколько нужно минимум людей, чтобы (с вероятностью 50% или больше) (каждый день в году был чей-то день рождения)?" (кроме, разве что, ошибки по невнимательности при чтении вопроса)
From:morfizm
Date:June 8th, 2010 11:46 am (UTC)
(Link)
Пожалуй, теперь понимаю, как можно было понять мою формулировку неправильно.
From:dennyrolling
Date:June 8th, 2010 03:10 pm (UTC)
(Link)
ничего, даже мою формулировку, которую я вообще не могу понять как неправильно можно прочитать ("how big the group needs to be that there is 50% chance that every day is someone's birthday") неправильно прочитали
From:_vr_ghost
Date:June 9th, 2010 12:16 pm (UTC)
(Link)
Даже перечитав формулировку с этими скобочками я читаю и понимаю этот вопрос также как я его и понял изначально.
И дело не в скобках. Я попытался нарисовать структуру твоего понимания и моего и у меня не получилось. Похоже что данное различие восприятия не лежит на сознательном уровне.
From:morfizm
Date:June 13th, 2010 07:10 am (UTC)
(Link)
А ты паузы пробовал мысленно вставлять после закрывающих скобочек?

Денни, кстати, выложил твой вариант задачи:
http://dennyrolling.livejournal.com/155900.html
From:dennyrolling
Date:June 8th, 2010 03:17 pm (UTC)
(Link)
тоже кстати хорошая задачка, надо подумать как ее точно решить.
From:dennyrolling
Date:June 8th, 2010 09:43 pm (UTC)
(Link)
пересчитал, получилось попроще (даже в принципе можно было бы решить на W-A, но было лень):
N=248, P=0.066898407224348
N=249, P=0.069813979344098
N=250, P=0.072153361542893
N=251, P=0.073866180810457
N=252, P=0.074919385577651
N=253, P=0.075298133741567
N=254, P=0.075005843739137
N=255, P=0.074063444052758
N=256, P=0.072507902943621
N=257, P=0.070390157700227
From:dennyrolling
Date:June 9th, 2010 07:13 am (UTC)
(Link)
кстати, а что за синтаксис? незнакомо выглядит.
From:_vr_ghost
Date:June 9th, 2010 12:07 pm (UTC)
(Link)
Python
From:dennyrolling
Date:June 9th, 2010 03:45 pm (UTC)
(Link)
а, понятно, интерактивного-то питона я и не видел