?

Log in

No account? Create an account
две задачки - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

две задачки [июн. 27, 2003|07:47 pm]
Anatoly Vorobey
В комментах наверняка в какой-то момент появятся правильные решения, так что не заглядывайте туда, если хотите сами решать.

1. В круг выстроились N человек, рядом с ними стоит ведро с краской. Один из них берёт ведро и красит себя, после чего с вероятностью 1/2 передаёт его соседу справа, и с вероятностью 1/2 — соседу слева. Сосед, получивший ведро, тоже красит себя, и точно так же передаёт его одному из своих соседей. Когда ведро приходит к кому-то, кто себя уже красил, он не повторяет покраску, но всё равно передаёт его одному из своих соседей с вероятностями 1/2 и 1/2.

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

2. На столе лежат 100 пуговичек, каждая из которых выкрашена в белый цвет с одной стороны, и в чёрный — с другой. Изначально 10 пуговичек лежат белой стороной кверху, 90 — чёрной. Вам завязывают глаза и после этого перемешивают пуговички на столе (не переворачивая). Теперь вы можете двигать пуговички как угодно и переворачивать их как угодно. Можете ли вы в результате таких действий разделить их на две кучки, в каждой из которых будет одинаковое количество пуговичек белой стороной кверху?
СсылкаОтветить

Comments:
[User Picture]From: igorlord
2003-06-27 10:29 am
#2. Ha!

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. :)
(Ответить) (Thread)
[User Picture]From: igorlord
2003-06-27 10:32 am
Ah, actually I thought that there are 90 white ones and 10 black ones.
For 10 white and 90 black, you can flip just 10.
(Ответить) (Parent) (Thread)
From: ex_p_k
2003-06-27 11:27 am
#1 - вероятность равна 1/(N-1) и не зависит от участника. Доказывается по индукции, исходя из того соображения, что если ведро находится с краю группы из M крашеных товарищей, то с вероятностью M/(M+1) следующим будет покрашен сосед, и с вероятностью 1/(M+1) - товарищ с другого конца группы.

#2 хорошая задача про XOR, но ее уже решили.
(Ответить) (Thread)
[User Picture]From: avva
2003-06-27 11:28 am
Обе задачи решили, но я пока скрываю эти комменты для желающих подумать ещё.
(Ответить) (Thread)
From: mushroomm
2003-06-27 11:46 am
на 2 курсе на теорвере кучу таких разных задач решали
мне оч нравился предмет, так как была уже приучена (Мартин Гарднера много читала и другие поп книги по математике=))
(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-06-27 12:09 pm
<<Можете ли вы в результате таких действий разделить их на две кучки, в каждой из которых будет одинаковое количество пуговичек белой стороной кверху>>

- Можете ли вы перечислить имена всех болельщиков на стадионе в алфавитном порядке?
- Нет. И это - правильный ответ!
(Ответить) (Thread)
[User Picture]From: french_man
2003-06-27 01:06 pm
Вторая легкая. Делишь на две кучи по 90 и 10. В первой х белых, во второй 10-х. Потом вторую переворачиваваешь.
(Ответить) (Thread)
[User Picture]From: arbat
2003-06-27 01:55 pm

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).
(Ответить) (Thread)
From: drw
2003-06-27 02:41 pm
Занумеруем всех хмырей числами от 1 до N против часовой стрелки, где номер 1 соответствует тому, кто покрасился первым. Далее будем описывать последовательность покрасок двоичным числом длины N–2 следующим образом: если очередная покраска произошла по направлению против часовой стрелки, то в очередном бите будет единица, если же по часовой, то ноль. Таким образом N–2 бит определяют последнего оставшегося хмыря, он и будет покрашен последним.

Тогда очевидно, что хмырь с номером 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)
(Ответить) (Thread)
[User Picture]From: french_man
2003-06-27 06:10 pm
Мне кажется, что для всех, кроме первого, вероятность одна и та же: 1/(n-1). Но доказывать лень.
(Ответить) (Parent) (Thread)
[User Picture]From: arbat
2003-06-27 07:10 pm

Ха! Похоже не то. Чтобы покраситься последним, надо, чтобы ведро дошло до одного соседа, а потом - не доходя до тебя, дошло до другого соседа. Вероятность, что оно дойдет до одного из соседей 1. Вероятность, что оно потом, прежде, чем попадет к тебе, дойдет до другого должна быть такая же, как у соседей первого покрашеного. Как-то это не строго... Интересно.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2003-06-27 07:13 pm
Я думаю, должно быть простое рассуждение, основанное на симметрии, возможно, индуктивное.
(Ответить) (Parent) (Thread)
From: drw
2003-06-28 03:33 am
Да, похоже на правду!
(Ответить) (Parent) (Thread)
[User Picture]From: veniamin
2003-07-01 12:50 am

в корне не верно, смотрите мой ответ :)

в корне не верно, смотрите мой ответ :)
(Ответить) (Parent) (Thread)
From: drw
2003-07-01 07:25 am

Re: в корне не верно, смотрите мой ответ :)

Почему сразу «в корне неверно»? Если аккуратно считать по моей формуле, то как раз 1/(N-1) и получается.
(Ответить) (Parent) (Thread)
[User Picture]From: bugabuga
2003-06-28 12:23 am
Понимаю, что просто но:
В коробке лежат 100 шаров. 30 красных, 30 синих, 30 зелёных, 3 чёрных и 7 белых. Какое минимальное количество шаров нужно вынуть вслепую и наугад, чтобы наверняка было 20 шаров одного цвета
:)
(Ответить) (Thread)
[User Picture]From: ok_66
2003-06-29 11:19 pm

Исходя из закона подлости...

Сначала 10 черно белых, потом по 19 красно-сине-зеленых и один для контроля. 58, однако.
(Ответить) (Parent) (Thread)
[User Picture]From: bugabuga
2003-06-30 12:21 am

Re: Исходя из закона подлости...

Ответ неверный :)
(Ответить) (Parent) (Thread)
[User Picture]From: krimsky
2003-06-30 02:27 am

Re: Исходя из закона подлости...

То что ты написал равняется 67-ми, если не ошибаюсь.
(Ответить) (Parent) (Thread)
[User Picture]From: ok_66
2003-06-30 03:01 am

Re: Исходя из закона подлости...

Ошибаешся. 68.
Вот что значит долго не практиковаться в устном счете. :-(
(Ответить) (Parent) (Thread)
[User Picture]From: krimsky
2003-06-30 03:06 am

Re: Исходя из закона подлости...

Ну да, ну да.
(Ответить) (Parent) (Thread)
[User Picture]From: veniamin
2003-07-01 12:41 am

ответ в виде переписки с Шуфелем, извиняюсь за длинннн

ответ в виде переписки с Шуфелем, извиняюсь за длинннннннноооооое письмо

Мне товарищ Шуфель прилал эти задачки и вот какая у нас получилась переписочка, надеюсь он не обидится на публикацию :)

Это мой первый ответ:

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. Сам никак не выпью, гадость неимоверная :-Р

Так вот, люди, и вы достопчтенный АВВА, если вы смогли это дочитать, скажите разве я не прав ? И какое на вкус Ферне ?


(Ответить) (Thread)
From: drw
2003-07-01 07:40 am

Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн

> С другой стороны сам факт его добавления не изменил равенства вероятностей для всех других игроков

По-моему, это совсем не очевидно.

> А индукция абсолютно математична

;-)

На первом курсе меня учили, проводя индукцию, сводить недоказанный случай к доказанному, а не наоборот. ;-)
(Ответить) (Parent) (Thread)
[User Picture]From: veniamin
2003-07-01 09:02 am

Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн

вероятность быть закрашенным последним зависит только от вероятности что оба твои соседа закрашены (а ты нет)
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
мы предположили что все вероятности равны для к, теперь предположим что цепочка состояний удленнилась (цепь Маркова а не цепь взаимного соседства, хотя если рисовать то они похожи), так как описанная система описывается процессом Маркова, то соответственно добавление ни как не повлияет на вероятность переходов из состояния в состояние, но удленнит цепь, что повлечёт ОДИНАКОВОЕ изменение вероятностей попасть в состояния (не в кругу, а в цепи Маркова) в каждое состояние следуещее из нового, то есть дополнительное состояние одинаково увеличит/уменьшит вероятность всех остальных (если Марков конечно не наврал)
(Ответить) (Parent) (Thread)
From: drw
2003-07-01 09:09 am

Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн

Я не знаю, что такое цепь Маркова, извините.
(Ответить) (Parent) (Thread)
From: drw
2003-07-01 05:14 pm

Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн

По-моему, это всё же неверно.

> мы предположили что все вероятности равны для к

Для того, чтобы распределение вероятностей состояний в момент времени i+1 зависело только от состояния в момент i (насколько я понял определение цепи Маркова), мы должны рассматривать в момент i 2(i-1) состояний системы, т. е. конфигурацию закрашенных игроков с точностью до того, кто был закрашен последним. А когда мы рассматриваем последний момент, то предполагаем (в индукции) для всех N-1 игроков равенство сумм вероятностей двух состояний: состояния, при котором последним был закрашен сосед соответственно слева и справа. Так что если Марков и доказал что-то подобное (я, признаться, не понял, какое утверждение там имелось в виду), то здесь это вряд ли поможет.
(Ответить) (Parent) (Thread)
[User Picture]From: veniamin
2003-07-02 12:06 am

Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн

я описал состояние как - быть закрашенным, мне не интересны переходы от игрока к игроку
есть состояние соседей "быть закрашенным при условии что я не закрашен"
переход из этого состояния с вероятностью 1, приведёт к закрашиванию

короче я всё таки посижу как нибудь и сформулирую описание цепи и состояний, а то получается какая-то каша, в которой я сам запутался
(Ответить) (Parent) (Thread)
From: drw
2003-07-02 03:39 am

Re: ответ в виде переписки с Шуфелем, извиняюсь за длинн

Да, но если мы добавляем одного человека, то у нас с вероятностью 1/(N-1) остаётся определённая пара соседних незакрашенных игроков. А для каждого игрока из этой пары вероятность того, что он будет закрашен последним, зависит от того, кто из соседей этой пары был закрашен позже.

> короче я всё таки посижу как нибудь и сформулирую описание цепи и состояний

Да, хорошая мысль.
(Ответить) (Parent) (Thread)