WEB форумы на jedi
[Форум] [Помощь] [Поиск] [Выйти]
Добро пожаловать, [info]User

WEB форумы на jedi [ПОИСК] [Архив до 03.2006]

Тема Задачка2 К предыдущему сообщению На следующее сообщение главная ;)

Отправил Big в 22:06 07.10.2002[Ответить]
Гляжу, тут Кей появился :) (Азарика, подтолкни там 125-го админа :)

http://193.233.210.121:8080/files/2.JPG

В русле реки есть 6 островов, соединенных мостами.
Наши должны форсировать реку. Кульминацией предполагается переход генерала на противоположный берег.
Враги про это прознали, решили нанести бомбовый удар.
Вероятность разрушения моста после налета - 1/2.

Найти и обосновать вероятность перехода генерала на противоположный берег.


Отправил Ondulyansion в 22:14 07.10.2002[Ответить]
Как в том анекдоте - вероятность 50 на 50 - или перейдёт, или нет :о)


Отправил Big в 22:18 07.10.2002[Ответить]
Обоснуй


Отправил Ondulyansion в 22:29 07.10.2002[Ответить]
Анекдот: спрашивают мужчину: какая вероятность встретить на улице динозавра? ответ - одна триллионная
женщина: 50 на 50 - или встречу или нет
:)


Отправил Big в 22:42 07.10.2002[Ответить]
За отмаз не катит.


Отправил Ondulyansion в 22:43 07.10.2002[Ответить]
Да я и не отвечал:) Но, видимо, ответ правильный :)


Отправил Big в 23:21 07.10.2002[Ответить]
Не-а, не видимо.


Отправил Ondulyansion в 00:17 08.10.2002[Ответить]
Будем рассуждать логически методом математического перебора :)))
если дженерал начинает идти по левому мосту вероятность его прохода рана: 0.5(первый мост)* вероятность прохода с острова на ту сторону. Эта вероятность равна сумме вероятностей прохода по всем путям с этого острова.
Эта сумма: 1/4 (прямо, прямо) + 1/8 (прямо, направо, прямо)+1/16 (прямо, направо, направо, прямо) + 1/64 (прямо, направо, назад, направо, прямо, прямо) + 1/8 (направо, прямо, прямо)+ 1/16 (направо,прямо, налево, прямо) +1/16 (направо, прямо, направо, прямо) +1/16 (направо, направо, прямо, прямо) + 1/32 (направо, направо, прямо, налево, прямо) + 1/64 (направо, напрво, прямо, налево, налево, прямо)
получаем 26/32, а вероятность прохода по левому мосту 0.5*26/32=13/32
по среднему мосту аналогично: 0.5 * (1/4 (прямо, прямо)+1/8(прямо, направо, прямо)+1/8(прямо,налево,прямо)+1/8(направо, прямо, прямо)+1/16(направо,прямо,налево,прямо)+1/32(направо,прямо,налево,налево,прямо)+1/8(налево, прямо, прямо)+1/16(налево,прямо,направо,прямо)+1/32 (налево, прямо, направо, направо, прямо) ) = 0.5*30/32=15/32
По третьему мосту вероятность такая же как по первому
Таким образом, получаем 13/32+15/32+13/32=41/32 , то есть больше единицы. Прорвёмся :)
ЗЫ За такие вот методы без знания формул комбинаторики меня ругал Лапшин А.Б. :о)


Отправил Ondulyansion в 00:33 08.10.2002[Ответить]
Хотя тут вроде чё-то не так.
ведь вероятность того что все три нижних моста убиты = 1/8
такая де вероятность что все верхних убиты
то есть вероятность того что не пройдет - 1/4
Что-то не сходится :(


Отправил Key в 02:14 08.10.2002[Ответить]
если дженерал начинает идти по левому мосту вероятность его прохода рана: 0.5(первый мост)* вероятность прохода с острова на ту сторону
Совсем не так. p(A!B) = p(AB) / ( p(A)*p(B) ).

Эта вероятность равна сумме вероятностей прохода по всем путям с этого острова
Опять не угадал: p(A+B) = p(A) + p(B) - p(AB).

Бтв, перебор поможет только компу, бо перебирать 2^13 вариантов.


Отправил Ondulyansion в 02:50 08.10.2002[Ответить]
век живи, век учись, сказал Ржевский и переложил портсигар...(с) анекдот


Отправил Big в 16:08 08.10.2002[Ответить]
Илья, ты не мудри, ты пальцем покажи :)
(админу не помогай :)


Отправил Key в 01:35 09.10.2002[Ответить]
Мехмату был дан один день. Типа не справились ;) с них, Паш, угостить нас в Ростиксе чем-нибудь вкусненьким.

Значит так: после бобмежки будет картинка из мостов. Различных таких картинок - 8К. Так как вероятность разрушения каждого моста 0.5 и события независимые, то вероятность появления каждой такой картинки одинакова и равна 1/8К. След-но вероятность перехода генерала равна отношению кол-ва картинок с путем прохода к общему кол-ву картинок.
Судя по симметричности мостов это отношение должно быть 0.5. Докажем, показав, что каждой картинке с путем соответсвует одна и только одна картинка без путя.

Представим, что это не мосты, а дамбы, и нарисуем возможности прохода воды через нее. Получится такая же картинка, только повернутая на пи пополам (или три пи пополам ;) - привет мехмату).

Если генерал сможет пройти, значит дамба сохранилась, вода не протечет, и наоборот, соответственно. Взаимооднозначное соответствие найдено, доказано.

П.С. Гад ты, Паш, после работы заставляешь таким маятся ;)


Отправил Ondulyansion в 11:03 09.10.2002[Ответить]
Кей, чё то не уловил, где доказательство что одной проходной картинке соответствует одна и только одна непроходная?


Отправил Key в 19:10 09.10.2002[Ответить]
Рисуем по Биговой картинке красным: http://useic.ru/~key/temp/2.gif

Смотрим на это дело после бомбежки и строим свою картинку. Если есть мост-дамба, значит в красном графе нет ребра (вода не течет), если мост разрушен - есть ребро (течет).
Как строим - понятно?

Теперь:
1. Ясно, что полученный красный граф, если его повернуть, один-в-один картинка с мостами, только разрушенных как-то по-другому. То есть мы построили соответствие - каждой картинке с мостами некую другую картинку.
2. Ясно, что двум различным картинкам соответсвует различные две красные картинки. (Док-во от противного - если соответствуют одинаковые, делаем обратное преобразование, оно должно привести к одинаковым графам, что не так). Значит построенное соответствие взаимооднозначное.
3. И последнее - это соответствие на самом деле (вот и фокус!) между картинками с переходом и без перехода. Действительно, если генерал может пройти по дамбам, значит вода протечь не может (красная картинка без прохода) и наоборот.

То есть множество картинок с переходом равномощно множеству без перехода.

Пардон, если не понятно сразу объяснил, спать хотел - убиться веником.


Отправил Big в 17:09 10.10.2002[Ответить]
> Типа не справились ;)

Ай-яй-яй...

> с них, Паш, угостить нас

Ой-ей-ей :) Вызов принят :)

> должно быть 0.5

Все правильно :) Жму руку :)


Отправил Key в 17:19 10.10.2002[Ответить]
Молчат только, как партизаны.. Будем применять силовые методы.


Отправил Nika в 23:21 07.10.2002[Ответить]
> Вероятность разрушения моста после налета - 1/2.

если все правильно написано, то 100% :)
потом что мостА, а их 13 на картинке :) при чем разрушение любого не повлечет за собой ничего страшного, т.к всегда есть обход :)


Отправил Big в 16:07 08.10.2002[Ответить]
Любого, каждого моста, Юль.


Отправил olica в 06:29 09.10.2002[Ответить]
Вероятность разрушения моста 0,5. Вероятность того, что мост сохранится 1-0,5=0,5.
Поскольку в данном случае повреждение каждого отдельного моста является событием независимым будем исходить из соображений, что: р(А+В)=р(А)+р(В)-р(А)*р(В), соответственно р(А+В+С)=р(А)+р(В)+р(С)+р(А)*р(В)*р(С)-р(А)*р(В)-р(А)*р(С)-р(В)*р(С).
Для определенности обозначим острова слева направо и сверху вниз соответственно буквами A, B, C, D, E, F.
Для удобства разбиваем прохождение реки на три этапа: с берега на 1-ю группу островов, с 1-ой группы островов на 2-ю и со второй на противоположный берег.
Вероятность попадания в т.D непосредственно с берега, через т.Е с берега или через т.Е и т.F c берега будет:
р(D + E + EF) = 1/2 + 1/4 + 1/8 + 1/2*1/4*1/8 - 1/2*1/4 - 1/2*1/8 - 1/4*1/8 = 43/64 = 0,671875
Вероятность попадания в т.Е:
p(D + E + F) = 1/4 + 1/2 + 1/4 + 1/32 - 1/8 - 1/16 - 1/8 = 23/32 = 0,71875
Вероятность попадания в т.F, такая же как и в т.D, т.е 0,671875.
В т.А можно попасть через т.D, т.В (при условии попадания в т.Е) и т.В и С (при условии попадания в т.F):
p(A +B +BC) = 43/128 + 23/128 + 43/512 + 42527/8388608 - 989/16384 - 1849/65536 - 989/65536 = 4202783/8388608 = 0,50101077556610107421875
Для т.В:
p(A + B + C) = 43/256 + 23/64 + 43/256 + 42527/4194304 - 989/16384 - 1849/65536 - 989/16384 = 2334175/4194304 = 0,5565106868743896484375
Вероятность попадания в т.C, такая же как и в т.A, т.е 0,50101077556610107421875.
Соответственно вероятность попадания на противоположный берег приблизительно:
p(A + B + C) = 0,2505 + 0,2783 + 0,2505 + 0,017463394575 - 0,06971415 - 0,06275025 - 0,06971415 = 0,594584844575
Соответственно имеем вероятность попадания на противоположный берег порядка 60%.


Отправил Key в 08:35 09.10.2002[Ответить]
Неверно:
Для удобства разбиваем прохождение реки на три этапа: с берега на 1-ю группу островов, с 1-ой группы островов на 2-ю и со второй на противоположный берег.

Тогда такие пути, как FCBEDA выпадают из рассмотрения.


Отправил olica в 23:01 09.10.2002[Ответить]
Абсолютно верно. И еще есть симметричный ему DABEFC. Их, кстати, всего два и получается (если не ошибаюсь). Учесть их можно аналогично.
Вероятность прохождения по каждому из этих путей
p = (1/2)^7 = 1/128 = 0,0078125
Соответственно, общая вероятность прохождения хотя бы по одному из выше указанных путей примерно:
Р = 0,0078 + 0,5946 + 0,0078 + 0,000036175464 - 0,00463788 - 0,00006084 - 0,00463788 = 0,600899575464
Так что получаем как раз 60%.


Отправил Key в 00:31 10.10.2002[Ответить]
Нда.. найти ошибку в неправильном док-ве оказалось сложнее, чем правильно решить задачу. Беру фору до завтра, разбираться в завалах больно ;)
Кстати, из чувства солидарности, мое попробуйте уронить.


Отправил olica в 02:24 10.10.2002[Ответить]
->Так как вероятность разрушения каждого моста 0.5 и события независимые, то вероятность появления каждой такой картинки одинакова и равна 1/8К.
По-моему вероятность появления картинок разная будет, например:
вероятность разрушения одного моста 1/2, а сразу двух уже 1/4.
Хотя я на правильности своего решения не настаиваю - вполне могла и запутаться.


Отправил Key в 09:43 10.10.2002[Ответить]
Забудем про мосты, представим классические в тервере монетки. Если орел - моста нет, решка мост выжил. Тогда перефразируя получим: сидят 13 мужиков, и одновременно и независимо подкидывают по идеальной ( р = 1/2 ) монетке, а потом смотрят, что получилось. Вероятность выпадания каждой из последовательностей в тринадцатать монеток одинакова, так?

Но: действительно, если убрать 11 мужиков и оставить двух, то получим, что вероятность того, что они выкинут два орла 1/4 (погибнут два моста). Потому что событий без двух орлов три: 00, 01, 10, а с орлами - одно 11.
Ты путаешь события.


Отправил AleX_ в 12:10 10.10.2002[Ответить]
так, короче, где вы видели генералов которые ХОДЯТ?
btw прикажет параллельно мостам поставить понтонную переправу и уложатся солдаты гораздо быстрее чем вы сосчитаете эту вероятность ))


Отправил olica в 14:49 10.10.2002[Ответить]
Ok, замечание по поводу картинок забираю.