1. Есть самолет. В нем 100 мест, и ровно 100 проданных билетов.
100 пассажиров построились в очередь, и начинают посадку. Первый пассажир оказался редким уродом, и сел на случайно выбранное место (может быть и на свое собственное, а может и нет). Все следующие пассажиры заходят по очереди и действуют очень просто: если их "законное" место свободно - они садятся на него, если нет - выбирают случайным образом из оставшихся свободными мест. Вы заходите последним, сотым. Очевидно, к этом моменту будет свободно только одно место. Найти вероятность того, что это будет Ваше место (указанное в билете)

2. В темной-темной комнате лежит на полу 13 монет: из них 5 - кверху орлом, 8 - решкой. Вы можете их переворачивать наощупь, не видя результата (темно). Придумать алгоритм (возможно влючающий переворачивания), разделения монет на две группы так, чтобы в каждой было одинаковое кол-во монет, которые лежат кверху решкой.

3. Решения я не знаю, не спрашивайте :)

Дана колода из 36 карт, 4х мастей. Рубашка у этих карт несимметричная - то есть верх и низ отличаются.
Вы с другом хотите угадать масть как можно большего количества карт.

Порядок действий:
1. Ваш соперник тасует колоду карт и отдает Вашему другу, который сидит в отдельной комнате. Друг может смотреть на масти карт, не может изменять порядок карт, но может поворачивать их - ориентировать вверх или вниз .
2. Колоду передают Вам, и показывают по одной карте. Вы видите только положение верхней карты (то есть - вверх или вниз она ориентирована). Вы называете какую-то масть, после чего Вам показывают значение этой карты, и переходят к следующей.

Вопрос
Для какого максимального количества карт вы с другом можете угадать масть?(идет речь о точном решение, то есть следует рассматривать худший случай)

Все было прекрасно в государстве, которым правил мудрый султан. Одно лишь обстоятельство беспокоило султана - жены его десяти визирей. Некоторые из них были неверны, причем, если жена визиря начинала "гулять", то изменяла ему со всеми мужиками Багдада от стражника до визиря. Непорядок. Султан приказал каждого визиря со своей женой посадить в отдельную камеру. И приказал убить своих жен, если они неверны. И сказал, также, что всех выпустят, как только неверные жены будут убиты. После первой ночи султан послал слугу посмотреть, выполнен ли его приказ. Слуга вернулся и сказал: "Не все неверные жены убиты". После второй ночи слуга вновь пошел проверить и вернулся с тем же сообщением. После третьей и четвертой ночи все повторилось. А после пятой ночи пришел слуга к султану и сказал "Все неверные жены убиты".

Как определили неверных жен визири? Сами жены, конечно, ничего не рассказывали. Стены камер звуко-видео-стуко-пыле-влаго-запахонепрницаемые. Слуга заходил, молча смотрел на узников и молча выходил.

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

Темнота - неправильно. Со слугой они не спали. И вообще, задача математическая. Это не загадка, это задача.

QUOTE (Preston @ Nov 9 2004, 02:38 ) Темнота - неправильно. Со слугой они не спали. И вообще, задача математическая. Это не загадка, это задача.

---

И тем не менее, решение верное и полностью удовлетворяет условию.

Слуга _заранее_ знал всех неверных жен, потому что с ним они тоже изменяли (в свое время) _по условию_. Потому ему только и оставалось смотреть, пока их прикончат :)

Собственно, единственный, кто не знал неверных жен, был сам султан - жены изменяли со всеми, кроме него ("от стражника до визиря") :)

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

Вопрос - какова должна быть стратегия прекрасной принцессы, чтобы мат
ожидание качества жениха было бы максимальным?

Про самолет. Докажем, что когда остается n незанятых мест, вероятность того что когда очередной пассажир заходит, его место будет свободным = n/100. Тогда ответ будет 1/100.
Для первого пассажира это верно. Когда заходит второй, с вероятностью 1/100 первый сел на его место, с 99/100 на другое, и место второго свободно. Пока все правильно.
Индуктивный переход: остается n незанятых мест. Заходит пассажир, с вероятностью n/100 его место свободно и он на него сядет, (100-n)/100 - занятно, и он сядет на чужое. Определим, вероятность свободности места для следующего за ним пассажира.
В первом случае (наш садится на свое) это будет (n-1)/100 по предположению. Во втором требуется чтобы наш пассажир [с вероятностью (n-1)/n] не сел на место следующего, и была вероятность n/100 того что его место свободно к этому моменту.
В итоге получаем [n/100] * [(n-1)/100] + [(100-n)/100] * [n/100] * [(n-1)/n] = [n*(n-1)+(100-n)*(n-1)]/[100*100]=(n-1)/100 ч.и.т.д.

Про монеты, вопрос. Может ли человек, одновременно ощупывая 2 монеты определить наощупь одинаковый ли у них рельеф?

QUOTE (alex14san @ Nov 8 2004, 22:49 ) Про самолет. Докажем, что когда остается n незанятых мест, вероятность того что когда очередной пассажир заходит, его место будет свободным = n/100. Тогда ответ будет 1/100.
Для первого пассажира это верно. Когда заходит второй, с вероятностью 1/100 первый сел на его место, с 99/100 на другое, и место второго свободно. Пока все правильно.
Индуктивный переход: остается n незанятых мест. Заходит пассажир, с вероятностью n/100 его место свободно и он на него сядет, (100-n)/100 - занятно, и он сядет на чужое. Определим, вероятность свободности места для следующего за ним пассажира.
В первом случае (наш садится на свое) это будет (n-1)/100 по предположению. Во втором требуется чтобы наш пассажир [с вероятностью (n-1)/n] не сел на место следующего, и была вероятность n/100 того что его место свободно к этому моменту.
В итоге получаем [n/100] * [(n-1)/100] + [(100-n)/100] * [n/100] * [(n-1)/n] = [n*(n-1)+(100-n)*(n-1)]/[100*100]=(n-1)/100 ч.и.т.д.

---

"Рекурсия!" подумал Штирлиц.

С монетами все просто - складываем все монеты в одну кучу и перекладываем из этой кучи 8 монет во вторую кучу попутно их переворачивая. Или, что одно и то же, делим монеты на две кучи в которых 8 и 5 монет соответственно и переворачиваем ту кучу в которой восемь. Допустим мы случайно разделили монеты так, что в куче с 8 монетами все оказались кверху решкой. После переворота мы будем иметь в обоих кучах 0 монет кверху решкой. Допустим теперь в первой куче 4 орла и 1 решка, а во второй 1 орел и 7 решек. При перевороте второй кучи в ней станет 1 решка, как и в первой куче. То же самое справедливо для 2, 3 и т.д.

С картами первое что приходит в голову, это возможность угадать 6 мастей в колоде из 36 карт и 10 карт в колоде из 52 карт. Пояснять надо?

QUOTE (Миша @ Nov 9 2004, 12:26 ) С картами первое что приходит в голову, это возможность угадать 6 мастей в колоде из 36 карт

---

ну каждую вторую не проблема угадать - для кодирования масти достаточно 2 бит, т.е. двух ориентаций рубашки, дальше думаю ясно. Можно ли угадать больше - вопрос

а, ну больше и нельзя т.к. друг может передать столько бит информации, сколько карт в колоде, и никак не больше

QUOTE (alex14san @ Nov 9 2004, 00:38 )ну каждую вторую не проблема угадать - для кодирования масти достаточно 2 бит, т.е. двух ориентаций рубашки, дальше думаю ясно.

---

Нет, не ясно как двумя ориентациями закодировать масть одной карты :) Максимум что можно угадать у каждой второй - это цвет масти. Точнее у 35 карт из 36 или у 51 из 52.

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

QUOTE для кодирования масти достаточно 2 бит, т.е. двух ориентаций рубашки, дальше думаю ясно

---

Две ориентации рубашки - это ОДИН бит ;)

В задаче с самолетом, вероятность того что 100-й пассажир сядет на свое место равна 50%.