две задачки
Jun. 27th, 2003 07:47 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВ комментах наверняка в какой-то момент появятся правильные решения, так что не заглядывайте туда, если хотите сами решать.
1. В круг выстроились N человек, рядом с ними стоит ведро с краской. Один из них берёт ведро и красит себя, после чего с вероятностью 1/2 передаёт его соседу справа, и с вероятностью 1/2 — соседу слева. Сосед, получивший ведро, тоже красит себя, и точно так же передаёт его одному из своих соседей. Когда ведро приходит к кому-то, кто себя уже красил, он не повторяет покраску, но всё равно передаёт его одному из своих соседей с вероятностями 1/2 и 1/2.
Посмотрим на момент времени после того, как первый участник взял ведро и покрасил себя, но до того, как он передал его одному из соседей. Найти, для всех остальных участников, распределение вероятности события "я буду покрашен последним" (иными словами, оценить для каждого из оставшихся вероятность того, что он будет покрашен последним).
2. На столе лежат 100 пуговичек, каждая из которых выкрашена в белый цвет с одной стороны, и в чёрный — с другой. Изначально 10 пуговичек лежат белой стороной кверху, 90 — чёрной. Вам завязывают глаза и после этого перемешивают пуговички на столе (не переворачивая). Теперь вы можете двигать пуговички как угодно и переворачивать их как угодно. Можете ли вы в результате таких действий разделить их на две кучки, в каждой из которых будет одинаковое количество пуговичек белой стороной кверху?
1. В круг выстроились N человек, рядом с ними стоит ведро с краской. Один из них берёт ведро и красит себя, после чего с вероятностью 1/2 передаёт его соседу справа, и с вероятностью 1/2 — соседу слева. Сосед, получивший ведро, тоже красит себя, и точно так же передаёт его одному из своих соседей. Когда ведро приходит к кому-то, кто себя уже красил, он не повторяет покраску, но всё равно передаёт его одному из своих соседей с вероятностями 1/2 и 1/2.
Посмотрим на момент времени после того, как первый участник взял ведро и покрасил себя, но до того, как он передал его одному из соседей. Найти, для всех остальных участников, распределение вероятности события "я буду покрашен последним" (иными словами, оценить для каждого из оставшихся вероятность того, что он будет покрашен последним).
2. На столе лежат 100 пуговичек, каждая из которых выкрашена в белый цвет с одной стороны, и в чёрный — с другой. Изначально 10 пуговичек лежат белой стороной кверху, 90 — чёрной. Вам завязывают глаза и после этого перемешивают пуговички на столе (не переворачивая). Теперь вы можете двигать пуговички как угодно и переворачивать их как угодно. Можете ли вы в результате таких действий разделить их на две кучки, в каждой из которых будет одинаковое количество пуговичек белой стороной кверху?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-06-27 10:29 am (UTC)Take any random 90 and flip them over. Done! The flipped and unflipped piles will have the same number of whites. :)
Basically:
If you are lucky enough to leave all black ones in the unflipped pile, then you took all whites and flipped them and now neither pile has any whites at all.
If you you left exactly one white in the unflipped pile, then you took exactly one black in the flipped pile. Hence, that one black in the flipped pile will produce exactly one white, and you will have one white in both piles.
And so on. :)
no subject
Date: 2003-06-27 10:32 am (UTC)For 10 white and 90 black, you can flip just 10.
no subject
Date: 2003-06-27 11:27 am (UTC)#2 хорошая задача про XOR, но ее уже решили.
no subject
Date: 2003-06-27 11:28 am (UTC)no subject
Date: 2003-06-27 11:46 am (UTC)мне оч нравился предмет, так как была уже приучена (Мартин Гарднера много читала и другие поп книги по математике=))
no subject
Date: 2003-06-27 12:09 pm (UTC)- Можете ли вы перечислить имена всех болельщиков на стадионе в алфавитном порядке?
- Нет. И это - правильный ответ!
no subject
Date: 2003-06-27 01:06 pm (UTC)no subject
Date: 2003-06-27 01:55 pm (UTC)Second one is easy. If the number of the white ones is X, make a pile of X buttons - there will be K <= X white ones in it and (X-K) in the other pile. Then turn all the buttons in the first pile over, making the number of white ones in it equal to zame (X-K).
no subject
Date: 2003-06-27 02:41 pm (UTC)Тогда очевидно, что хмырь с номером k останется последним, если соответствующее двоичное число содержит ровно k–2 единицы.
Рассмотрим ситуацию, когда k хмырей уже покрашено, и последний из них покрасился только что (он будет крайним). У меня получилось, что вероятность того, что следующим покрасится его сосед, то есть покраска продолжится в том же направлении, равна k/(k+1), соответственно, вероятность того, что покраска продолжится в другом направлении, равна 1/(k+1). Поэтому для двоичной последовательности a1a2…aN–2 вероятность того, что выполнится соответствующая ей последовательность покрасок, равна
f(a1,…,aN–2) = П1≤k≤N–2 (k/(k+1) + (ak⊕ak–1)(1–k)/(k+1))
Тогда для хмыря под номером p вероятность того, что он будет покрашен последним, равна
Σa1+…+aN–2=p–2 f(a1,…,aN–2)
no subject
Date: 2003-06-27 06:10 pm (UTC)no subject
Date: 2003-06-27 07:10 pm (UTC)Ха! Похоже не то. Чтобы покраситься последним, надо, чтобы ведро дошло до одного соседа, а потом - не доходя до тебя, дошло до другого соседа. Вероятность, что оно дойдет до одного из соседей 1. Вероятность, что оно потом, прежде, чем попадет к тебе, дойдет до другого должна быть такая же, как у соседей первого покрашеного. Как-то это не строго... Интересно.
no subject
Date: 2003-06-27 07:13 pm (UTC)no subject
Date: 2003-06-28 12:23 am (UTC)В коробке лежат 100 шаров. 30 красных, 30 синих, 30 зелёных, 3 чёрных и 7 белых. Какое минимальное количество шаров нужно вынуть вслепую и наугад, чтобы наверняка было 20 шаров одного цвета
:)
no subject
Date: 2003-06-28 03:33 am (UTC)Исходя из закона подлости...
Date: 2003-06-29 11:19 pm (UTC)Re: Исходя из закона подлости...
Date: 2003-06-30 12:21 am (UTC)Re: Исходя из закона подлости...
Date: 2003-06-30 02:27 am (UTC)Re: Исходя из закона подлости...
Вот что значит долго не практиковаться в устном счете. :-(
Re: Исходя из закона подлости...
Date: 2003-06-30 03:06 am (UTC)ответ в виде переписки с Шуфелем, извиняюсь за длинннн
Date: 2003-07-01 12:41 am (UTC)Мне товарищ Шуфель прилал эти задачки и вот какая у нас получилась переписочка, надеюсь он не обидится на публикацию :)
Это мой первый ответ:
1.Для каждого человека нужно что бы все левые и все правые закрасились, (две дуги туда обратно), значит для всех одна и та же вероятность быть последнем или в числах 1/(Н-1), где Н это количество людей
2. Да можно, просто: отложи 10 пуговок из 100 каждый раз переворачивая пуговку.
Если то была белая, то на одну белую в куче меньше, зато и в новой кучке белых не добавилось.
Если то была чёрная, то в куче столько же белых, зато в маленькой кучке на одну белую больше.
В общем или в каждой куче по 10 белых или меньше , до нуля, но количество одинаковое
А Шуфель мне на это ответил:
1 - ne znaiu, ne uveren. tam gde u tebia "znachit" - kak-to eto neochevidno
2 - tak tochno
Я ему и говорю:
Возьми двух соседей, у одного по левую руку больше путь чем у соседа, за то по правую путь на один шаг меньше, так как стороны симметричны, то у обоих вероятность быть последними одинаковы. Теперь возьмём другую пару , так что бы один из пары был из рассмотренных выше, там будет та же история, и т.д. и т.п. в общем все звери равны
И добавил ещё для убидительности э:
Настоящая индукция:
Возьмём ситуацию с одним не закрашенным человеком (Н = 2), его вероятность быть последним 1/(Н-1) = 1, формула верна
Не надо, но возьмём два не закрашенных, по формуле 1/(Н-1) = 1/2, (Н = 3), и это верно так как вероятность быть закрашенным первым 1/2, следовательно последним тоже 1/2
Предположим что для К человек, формула 1/(К-1) верна, проверим для К+1,
Добавим одного человека рядом с начинающим (который всегда первый), его вероятность быть закрашенным такая же как уже стоящего там человека но стоящего по другую руку от начинающего. С другой стороны сам факт его добавления не изменил равенства вероятностей для всех других игроков, так как для всех путь стал длиннее на одного игрока и для всех с одной и той же стороны, следовательно вероятность для всех (включая нового так как он как один из старых) равна, то есть верна формула 1/((К+1)-1).
Доказано по индукции что формула 1/(Н-1) верна для любого Н.
Ну что теперь веришь ?
С тебя бутылка J, только не так как в прошлый раз J
Фу устал даже
А он ну не в какую :
1) не верю. это похоже на индукцию, но вот это вот: "С другой стороны сам факт его добавления не изменил равенства вероятностей для всех других игроков, так как для всех путь стал длиннее на одного игрока и для всех с одной и той же стороны, следовательно вероятность для всех (включая нового так как он как один из старых) равна" не убеждает.
было: вероятности для всех равны; и равны 1/(к-1)
стало: вероятность добаленного равна (неизвестной в новых условиях) вероятности симметричного ему.
то, что равенство вероятсностей сохраняется для всех - как-то неявно.
т.е. я тебе на слово верю, но рассуждение не убеждает.
Ну Я опонировал:
По поводу бутылки – не говорил, а что жалко ?
В "вот этом вот" не вижу никаких математических противоречий,
Если честно решил то я используя процессы Маркова, но их описывать было лень,
Потом напишу решение, но там немного надо знать теорию…
А индукция абсолютно математична, для всех путь удлинился, нет никаких причин что бы на одного это повлияла в иной степени чем на другого, так как формулы всех связаны с предыдущем и только состоянием, например того который теперь удалился на одного от начинающего, но это уже пошли процессы Маркова
Кстати, по поводу обещаний, если не обещал, так это дело можно исправить – пообещай :)
Всё, надо работать, а Маркова я тебе всё равно опишу
Ну и что я получил в ответ :
Опиши лучше у аввы, а я почитаю. Маркова знаю в самой базовой форме.
О! А обещаю-ка я тебе бутылочку Fernet. Сам никак не выпью, гадость неимоверная :-Р
Так вот, люди, и вы достопчтенный АВВА, если вы смогли это дочитать, скажите разве я не прав ? И какое на вкус Ферне ?
в корне не верно, смотрите мой ответ :)
Date: 2003-07-01 12:50 am (UTC)Re: в корне не верно, смотрите мой ответ :)
Date: 2003-07-01 07:25 am (UTC)Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн
Date: 2003-07-01 07:40 am (UTC)По-моему, это совсем не очевидно.
> А индукция абсолютно математична
;-)
На первом курсе меня учили, проводя индукцию, сводить недоказанный случай к доказанному, а не наоборот. ;-)
Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн
Date: 2003-07-01 09:02 am (UTC)Px(last) = Px-1(painted|x not pinted)+Px+1(painted|x not pinted)
нас не интересует история ни до ни после того как произошло два события (x-1 painted|x not pinted)& (x+1 painted|x not pinted), вся зависимость от истории сводится к зависимости от последнего состояния (Марков)
история до не интересна, так как как бы не передавали ведро, если они закрашены значит все до них закрашены
история посли то же не интересна, так как не важно как будет передоваться ведро после того как мои соседи закрашены, вероятность быть закрашенным последним у х равна единице
0 <= x <= k-1
мы предположили что все вероятности равны для к, теперь предположим что цепочка состояний удленнилась (цепь Маркова а не цепь взаимного соседства, хотя если рисовать то они похожи), так как описанная система описывается процессом Маркова, то соответственно добавление ни как не повлияет на вероятность переходов из состояния в состояние, но удленнит цепь, что повлечёт ОДИНАКОВОЕ изменение вероятностей попасть в состояния (не в кругу, а в цепи Маркова) в каждое состояние следуещее из нового, то есть дополнительное состояние одинаково увеличит/уменьшит вероятность всех остальных (если Марков конечно не наврал)
Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн
Date: 2003-07-01 09:09 am (UTC)Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн
Date: 2003-07-01 05:14 pm (UTC)> мы предположили что все вероятности равны для к
Для того, чтобы распределение вероятностей состояний в момент времени i+1 зависело только от состояния в момент i (насколько я понял определение цепи Маркова), мы должны рассматривать в момент i 2(i-1) состояний системы, т. е. конфигурацию закрашенных игроков с точностью до того, кто был закрашен последним. А когда мы рассматриваем последний момент, то предполагаем (в индукции) для всех N-1 игроков равенство сумм вероятностей двух состояний: состояния, при котором последним был закрашен сосед соответственно слева и справа. Так что если Марков и доказал что-то подобное (я, признаться, не понял, какое утверждение там имелось в виду), то здесь это вряд ли поможет.
Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн
Date: 2003-07-02 12:06 am (UTC)есть состояние соседей "быть закрашенным при условии что я не закрашен"
переход из этого состояния с вероятностью 1, приведёт к закрашиванию
короче я всё таки посижу как нибудь и сформулирую описание цепи и состояний, а то получается какая-то каша, в которой я сам запутался
Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн
Date: 2003-07-02 03:39 am (UTC)> короче я всё таки посижу как нибудь и сформулирую описание цепи и состояний
Да, хорошая мысль.