tag:blogger.com,1999:blog-6846929136376245264.post7178909597663038550..comments2024-01-03T12:54:39.457+03:00Comments on Привычка не думать: Общая цельИлья Весеннийhttp://www.blogger.com/profile/12075968879288943233noreply@blogger.comBlogger29125tag:blogger.com,1999:blog-6846929136376245264.post-76488660603227210402011-07-24T10:35:00.028+04:002011-07-24T10:35:00.028+04:00Олег, таким образом Вы делаете лишь оценку вероятн...Олег, таким образом Вы делаете лишь оценку вероятности, а не вычисляете честную вероятность (так как проводите это уточнение только для последнего игрока, хотя и у предшествующих игроков иногда вероятность была не ровно 1/2, а чуть лучше).<br /><br />Предлагаю продолжить обсуждение в <a href="http://my-tribune.blogspot.com/2011/07/blog-post_24.html" rel="nofollow">следующей заметке</a>.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-86036569777722500962011-07-21T11:09:08.400+04:002011-07-21T11:09:08.400+04:00Я имел ввиду случай статичной стратегии, где все з...Я имел ввиду случай статичной стратегии, где все заранее решено кто какие открывает коробочки (например чет-нечет).<br />Значит когда заходит последний четный уже точно известно что он найдет свой номер в пуле четных коробочек, тк все нечетные уже нашли до него.<br />ОлегAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-90852759793884929692011-07-21T09:56:10.352+04:002011-07-21T09:56:10.352+04:00> Уточнение: (1/2)^(2n-1)
Ибо последний человек...> <i>Уточнение: (1/2)^(2n-1)<br />Ибо последний человек уже точно найдет свой номер.</i><br />А какие у нас есть основания надеяться, что последний точно найдёт?<br /><br />> <i>А могут ли люди которые еще не заходили в комнату учитывать как быстро вызывают следующего?</i><br />Нет, бесчеловечный диктатор так всё устроил, что время всегда получается одинаковое, поэтому этот аспект учитывать никак нельзя.Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-86919286262828510282011-07-20T19:12:21.780+04:002011-07-20T19:12:21.780+04:00Все-таки нечетные фишки окажутся в нечетных коробк...Все-таки нечетные фишки окажутся в нечетных коробках с вероятностью (N!)^2/(2N)!<br /><br />ДмитрийAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-34408060971839661692011-07-20T16:35:57.604+04:002011-07-20T16:35:57.604+04:00А могут ли люди которые еще не заходили в комнату ...А могут ли люди которые еще не заходили в комнату учитывать как быстро вызывают следующего? <br />ОлегAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-18627349422615148122011-07-20T11:51:57.694+04:002011-07-20T11:51:57.694+04:00Уточнение: (1/2)^(2n-1)
Ибо последний человек уже ...Уточнение: (1/2)^(2n-1)<br />Ибо последний человек уже точно найдет свой номер.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-34121537455379351192011-07-20T10:31:56.350+04:002011-07-20T10:31:56.350+04:00Думаю что оценка в (1/2)^2n
можно улучшить если ка...Думаю что оценка в (1/2)^2n<br />можно улучшить если как-то использовать знание о том, что раз испытание продолжается, то это значит что предыдущие попытки закончились успешно. В этом смысле использование статичной стратегии (чет/нечет например) приводит к тому, что у последующих попыток вероятность успеха будет на самом деле не равно 1/2. Из-за то что например в пуле четных коробочек _точно_ есть k номеров предыдущих попыток. <br />Стало быль вероятность успеха попытки k (для четного случая на пример): p(k) = (n-k)/(2n)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-72317004827140597052011-07-20T09:55:44.533+04:002011-07-20T09:55:44.533+04:00Насколько мне известно, этого пока никто не может ...Насколько мне известно, этого пока никто не может доказать. )<br /><br />Илья.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-54828623982234490082011-07-20T06:55:00.329+04:002011-07-20T06:55:00.329+04:00Уважаемый аноним, а Вы можете доказать, что более ...Уважаемый аноним, а Вы можете доказать, что более эффективного подхода не существует?Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-19316869362903352712011-07-19T14:16:24.558+04:002011-07-19T14:16:24.558+04:00В лоб:
Четные номера открывают четные коробочки, н...В лоб:<br />Четные номера открывают четные коробочки, нечетные- нечетные<br />Итоговая вероятность успеха (1/2)^2nAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-33940618487741326502011-07-16T12:34:15.468+04:002011-07-16T12:34:15.468+04:00Тио, увы, в таком случае вероятность жестко 0%. Ни...Тио, увы, в таком случае вероятность жестко 0%. Ни меньше, ни больше =)Илья К.noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-61466467414349489392011-07-16T12:26:51.669+04:002011-07-16T12:26:51.669+04:00*предыдущий анонимный комментатор.
Нет, оно не б...*предыдущий анонимный комментатор. <br /><br />Нет, оно не будет меньше нуля, поскольку \sum_{i=N+1}^{2N} 1/i<br />сводится к последовательности <br />a(1) = 1/2<br />a(n) = a(n-1) - 1/(n) + 1/(2n) + 1/(2n-1) = a(n-1) - 1/(2n) + 1/(2n-1) = a(n-1) - 1/(2n) + 1/(2n-1)<br />Таким образом итоговая вероятность 1-a(n) представляет собой сумму знакопеременного гармонического ряда. И стремится при n -> inf к log(2).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-76818563689564344602011-07-16T11:50:38.190+04:002011-07-16T11:50:38.190+04:00*Предыдущий анонимный комментатор
Извиняюсь за ра...*Предыдущий анонимный комментатор <br />Извиняюсь за разведённый флуд. Я не учёл, что порядок элементов в "длинном" цикле так же имеет значение. Если не ошибаюсь, то для каждого i будет (i-1)! различных циклов. Таким образом вероятность получается <br />(1 - \sum_{i=N+1}^{2N} 1/i)<br />С другой стороны это решение тоже не очень похоже на правду, поскольку при больших N оно, кажется, будет меньше нуля.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-25538701182097121052011-07-16T11:43:07.495+04:002011-07-16T11:43:07.495+04:00*Предыдущий анонимный комментатор.
Поправка, вероя...*Предыдущий анонимный комментатор.<br />Поправка, вероятность победы равна<br />(1 - \sum_{i=N+1}^{2N} 1/i!)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-52433420453070499532011-07-16T11:41:21.711+04:002011-07-16T11:41:21.711+04:00>>Все люди смотрят одну половину коробочек.
...>>Все люди смотрят одну половину коробочек.<br />Вероятность ровно 0, поскольку люди, у которых карточки лежат в коробочках N+1...2N никогда не найдут свою карточку. <br /><br />Относительно перестановок - да, решение довольно неплохо увеличивает шансы на победу. В случаях, когда нет циклов из N+1...2N элементов - будет победа. Всего обратных случаев<br />сумма по i от N+1 до 2N C^{i}_{2N}*(2N-i)! = сумма по i от N+1 до 2N ((2N)!/i!). Т.к. это надо поделить на (2N)! - число случаев вообще, то получим, что вероятность победы равна<br />\sum_{i=1}^N 1/i!<br /><br />Теперь более сложная задача, на которую я, увы, не знаю ответа - доказать, что это максимально возможная вероятность, либо показать, что это не так.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-70728617399709874772011-07-16T10:44:11.836+04:002011-07-16T10:44:11.836+04:00Все люди смотрят одну половину коробочек.
вероятно...Все люди смотрят одну половину коробочек.<br />вероятность жестко 50%. Ни меньше, ни больше =)<br /><br />Тио.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-31874553415781234892011-07-14T10:11:09.922+04:002011-07-14T10:11:09.922+04:00Задача известная, и довольно аддиктивная. )
По су...Задача известная, и довольно аддиктивная. )<br /><br />По сути, раскладка 2N карточек в 2N занумерованных коробочек являкется перестановкой из 2N элементов.<br /><br />Если попробовать такую стратегию: сначала открыть коробочку со своим номером, посмотреть, какая там карточка, открыть коробочку с тем номером, который был на предыдущей карточки и так далее, пока не закончится число попыток или не будет найдена карточка со своим номером - тогда вероятность победы равна вероятности того, что в рассматриваемой перестановке нет циклов длиннее чем N. Насколько я понимаю в арифметике, при случайном выборе перестановки эта величина не зависит от N. Остается вопрос: как ее эффективно оценить? )<br />Т.е. как посчитать количество перестановок без длинных циклов.<br /><br />Илья.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-63913253520366772352011-07-13T15:55:45.382+04:002011-07-13T15:55:45.382+04:00Поддержу zmior:
Коробочки делятся на две части. П...Поддержу zmior:<br /><br />Коробочки делятся на две части. Первая половина людей открывает эти коробочки, а вторая половина - остальные.<br /><br />В этом случае вероятность того что все найдут свои коробочки<br /><br />N!*N!/2N!<br /><br />Если открывать циклически (1,2,..; 2,3..; 3,4..), то вероятность снижается. Какая именно не считал. Проверил эмпирически в Екселе :)Vitaliihttps://www.blogger.com/profile/12720364210713708106noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-42764493059219721902011-07-13T12:57:03.605+04:002011-07-13T12:57:03.605+04:00Если они не могут общаться, то какая разница, каки...Если они не могут общаться, то какая разница, какие коробки откроет предыдущий участник? Если потом они все останутся закрытыми и никто никому ничего не скажет — как порядок открытия коробок предыдущим участником максимизирует вероятность найти свой номер следующему?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-85826713909940553992011-07-13T12:19:14.622+04:002011-07-13T12:19:14.622+04:00> Или я непонимаю, если они не могут общаться, ...> <i>Или я непонимаю, если они не могут общаться, и между ними не происходит никакого обмена, и свой номер с коробкой не забирается</i><br />Они могут договориться заранее, кто какие коробки откроет, чтобы максимизировать вероятность того, что все они найдут свой номер.<br /><br />> <i>Какой смысл второму открывать вторую коробку, если его номер — в первой?</i><br />Никакого! В этом и идея решения.<br /><br />> <i>И первый участник видел это.</i><br />Не важно, что видел первый, если он ничего не может сообщить второму, так ведь?Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-5235572938298727692011-07-13T12:07:16.519+04:002011-07-13T12:07:16.519+04:00Имхо, вероятность, что все найдут свой номер = 0.5...Имхо, вероятность, что все найдут свой номер = 0.5^2N.<br /><br />Или я непонимаю, если они не могут общаться, и между ними не происходит никакого обмена, и свой номер с коробкой не забирается — тогда каждый просто заходит и смотрит любой набор из половины коробок.<br /><br />Какой смысл второму открывать вторую коробку, если его номер — в первой? И первый участник видел это.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-35230500802716907192011-07-12T21:40:56.969+04:002011-07-12T21:40:56.969+04:00Илья, я оставался в рамках формулировки "коро...Илья, я оставался в рамках формулировки "коробочки закрыты, ничего не сдвинуто". Про содержимое коробочек в условии ничего не было :)<br /><br />Ход мыслей zmior: если все первые N нашли свои карточки, значит в первых N коробочках находятся карточки с 1 до N. И в коробочках с N+1 до 2N будут и соответствующие карточки.<br />Ошибка в рассуждении - только у первого шанс будет 1/2. У второго уже - (N-1)/(2N-1).<br /><br />При рассуждении, возможно, стоит поставить себя на место коробочки, а не участника. Если я коробочка и меня открывало Х участников, то шансов что меня открыл участник с номером, совпадающим с номером на моей карточке, Х/2N. Теперь сравним вероятность для 2-х коробочек, когда X равно N и когда одну проверили на 1 раз больше, а другую - на 1 раз меньше.<br />Или ((N-1)/2N)*((N+1)/2N) сравнить с (N/2N)*(N/2N). Получаем (N^2-1)/4N^2=1/4-(1/4N^2), что определенно меньше чем просто 1/4.<br />Итого максимизация шансов достигается тогда, когда каждую коробочку проверили одинаковое количество раз.<br />А вот что за цифра получается - пока не готов ответить.Denterhttps://www.blogger.com/profile/15002118256989626616noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-19859372608463778752011-07-12T19:53:01.543+04:002011-07-12T19:53:01.543+04:00Denter, Вы предложили интересное решение, хоть и р...<b>Denter</b>, Вы предложили интересное решение, хоть и решали другую задачу. По условию состояние комнаты перед входом каждого участника делают исходным (т.е. они не могут что-то менять в комнате, а могут только заглядывать в N коробочек).<br /><br /><b>zmior</b>, действительно, вскрыв N коробочек из 2N, игрок найдёт свою карточку с вероятностью 1/2. А вот продолжение Вашего решения я не понимаю. Можете пояснить?Илья Весеннийhttps://www.blogger.com/profile/12075968879288943233noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-42010642861068981342011-07-12T19:30:58.804+04:002011-07-12T19:30:58.804+04:001/2^N
Ящики и людей нужно разделить пополам. перва...1/2^N<br />Ящики и людей нужно разделить пополам. первая половина населения заглядывает в первую половину ящиков, вторая - во вторую. Или наоборот. Для каждого из первой половины шанс найти свой номер 1/2, для всех из первой половины 1/2^N. если они все найдут свои номера, то вторая половина людей найдут свой номер с вероятностью 100%.zmiorhttps://www.blogger.com/profile/09751996340528064518noreply@blogger.comtag:blogger.com,1999:blog-6846929136376245264.post-46598152079098412762011-07-12T19:11:50.790+04:002011-07-12T19:11:50.790+04:00обгоняя по обочине, не факт что в итоге он не увел...обгоняя по обочине, не факт что в итоге он не увеличит пропускную способность..Anonymousnoreply@blogger.com