Отправлено: 25.09.06 16:54. Заголовок: еще одна задачка (вероятностная)

Имеется n копилок. К каждой копилке имеется один ключ (каждый ключ подходит ровно одной копилке). В каждую копилку бросают наугад один ключ (довольно необдуманный шаг, но что поделаешь). В надежде исправить ситуацию, разбивают две копилки и достают оттуда два ключа.

Вопрос: какова вероятность, что теперь удастся открыть все оставшиеся копилки?

 Отправлено: 25.09.06 17:14. Заголовок: Re:

Рассуждение такое:

Мы не сможем открыть все копилки только в следующих случаях:

1. Если каждая из обеих разбитых копилок содержала внутри ключ от самой себя
2. Или каждая из обеих разбитых копилок содержала внутри ключ от другой разбитой копилки.

В любом другом случае, мы сможем с помощью добытого ключа (ключей) запустить "цепную реакцию".

Значит, вероятность равна единице за вычетом вероятностей двух вышеописанных случаев.

 Отправлено: 25.09.06 17:25. Заголовок: Re:

Vraad

А по-моему не так... извини.

 Отправлено: 25.09.06 17:32. Заголовок: Re:

Vraad
да, не так, т.к. если хотя бы один ключ из разбитой копилки будет открывать другую, целую, то в той, целой, может оказаться ключ от уже разбитой...

 Отправлено: 25.09.06 17:32. Заголовок: Re:

Уже понял...

 Отправлено: 25.09.06 17:35. Заголовок: Re:

Ну, тогда 50 процентов - либо откроем, либо нет.

 Отправлено: 25.09.06 18:52. Заголовок: Re:

не люблю комбинаторику =((

 Отправлено: 25.09.06 18:58. Заголовок: Re:

Igor

А и не надо. Задачу можно и без нее решить.

 Отправлено: 25.09.06 22:00. Заголовок: Re:

[реклама вместо картинки]

пальцем в небо)

 Отправлено: 26.09.06 10:56. Заголовок: Re:

Ответ совсем простенький!

 Отправлено: 26.09.06 11:15. Заголовок: Re:

Лучше разбивать k копилок, а не две. :)

 Отправлено: 26.09.06 13:29. Заголовок: Re:

немного непонятно. если мы вначале забрасываем в копилку ключ, а потом второй, подходящий к ней ключ, то она откроется?
вообще в первый раз слышу "забросить ключ в копилку". всю жизнь разбивал и не представляю как заброшенными копилку ключами можно открыть копилку...

 Отправлено: 26.09.06 14:15. Заголовок: Re:

zabrosit kluch v kopilku znachit vlojit ego tuda, kuda obichno monetki kidaut. ne v skvajinu. zabrasivanie klucha ne imeet otnoshenia k otkrivaniu.

 Отправлено: 26.09.06 16:08. Заголовок: Re:

philvel

а если в последней копилке с номером N будет лежать ключ 2
то есть мы открыли все копилки)
так же и с двумя рядами копилок, если в последних будут чудовищно-страшные-ключи то мы же их все равно откроем)

 Отправлено: 26.09.06 20:17. Заголовок: Re:

tiger пишет:

цитата:

Лучше разбивать k копилок, а не две. :)

Абсолютно согласен! Предлагаю k=n

 Отправлено: 27.09.06 02:39. Заголовок: Re:

Я предлагаю начать решение от обратного. допустим часть копилок открыта, когда оставшиеся копилки невозможно открыть? правильно, когда они в сумме содержат только ключи которые им и соответсвуют. например, в 3-й копилке 5-й ключ и в 5-й копилке - 3-й - такую систему вскрыть нельзя. все остальные можно - ведь в таком случае найдется копилка, ключ которой нам доступен.
остается посчитать для любого n вероятность того, что среди последних n-2 копилок будет такого рода замкнутая система. это и будет вероятность невскрытия всех копилок.
методология ясна, а вот считать в 2.45 не особо хочется...

 Отправлено: 27.09.06 08:42. Заголовок: Re:

Придеться играть древним! Вероятность будет равна
=1/n*(1/n+1 + 1/n+2 + 1/n-k), где n - кол-во наблюдений, к<n и k не равняется n, вощем прогрессия должна быть!

Надеюсь, старперы хоть че то помнют! )))

 Отправлено: 27.09.06 18:05. Заголовок: Re:

Увы, правильный ответ так и не прозвучал.

 Отправлено: 27.09.06 19:48. Заголовок: Re:

Могу предположить, что k/n, если разбивают k копилок, но это только "вероятностная интуиция". Доказывать долго.

 Отправлено: 29.09.06 08:41. Заголовок: Re:

[(n-1)!+(n-2)!]/n! Мне так кажется... Если правильно, то могу решение написать.

Вот точно уверен, что если разбивать только одну, то (n-1)!/n!, так как копилки должны так или иначе образовывать единую цепь переходов из одной в другую.

 Отправлено: 29.09.06 09:02. Заголовок: Re:

Действительно, правильный ответ (в исходной задаче) - 2/n.

Potekhin совершенно прав относительно разбиения одной только копилки, и точка зрения на эту задачу как на задачу наличия циклов прямо-таки со смаком обсуждалась одним нашим профессиональным алгебраистом. :)

 Отправлено: 29.09.06 13:30. Заголовок: Re:

Есть еще вариации на тему задачи:

а) Разбивается одна копилка. Каково ожидаемое количество взятых ключей?


б) Пасьянс. Две колоды карт по 36 карт. Раскладываем две колоды в два ряда, одну карту над другой.
Нижний ряд открываем. В верхнем ряду открываем те карты, которые находятся над тузами.
Затем в верхнем ряду перекладываем открытые карты на места над такими же картами в нижнем ряду. Карты лежавшие на этих местах открываем и перекладываем туда, куда они указывают. И т.д.
Какова вероятность того, что пасьянс сойдется?

 Отправлено: 07.11.06 02:13. Заголовок: Re:

Что-то понравилась мне эта задача...

Тут случайно появилась гипотеза:
Фразу: "В каждую копилку бросают наугад один ключ" можно заменить на
"n ключей произвольным образом разбрасывают по n копилкам (можно хоть все в одну )" и никак это ответ не изменит.

 Отправлено: 07.11.06 02:22. Заголовок: Re:

tiger
все ключи бросаем в одну копилку, разбиваем самую тяжёлую и вопрос решён.

 Отправлено: 07.11.06 11:12. Заголовок: Re:

zhek
commonsense на уровне

 Отправлено: 07.11.06 12:31. Заголовок: Re:

zhek пишет:

цитата:

tiger все ключи бросаем в одну копилку, разбиваем самую тяжёлую и вопрос решён.

Жек, теперь высчитывай вероятность, что человек догадается это сделать)))