Хитрые задачи

[Forever Free]

Теперь понял.

 

[Trotil]

Ответ, вероятно... 1/2.

Входит первый пассажир, будем считать, что его место - k-оe, а он сел на первое (вер. 1/100).

C такой же вероятностью (вер. 1/100) последним может войти человек с первым местом и занять k-тое вместо своего.

 

[Forever Free]

Вот вопросец появился:
Тут же события зависимые ? От вероятности какое место займет первый пассажир зависит вероятность какое место займет следующий, и последний ?

 

[Изменившаяся]

Тут же события зависимые ? От вероятности какое место займет первый пассажир зависит вероятность какое место займет следующий, и последний

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

 

[Forever Free]

Если бы не это условие в задаче ----->

Все последующие пассажиры ведут себя следующим образом: если их "правильное" место еще не занято, они садятся туда

тогда число всех равновозможных случаев посадки пассажиров 100!,
а вероятность посадки пассажира на свое место 1/100!. Но вот это условие, черт возьми, меня смущает ...

 

[Trotil]

1/100!

Это всех пассажиров одновременно на свои места. А для каждого 1/100.

(если бы не это условие в задаче )

 

[server ne naiden]

Нам сказано, что пассажири заходят по дному. Может тогда так:
вероятность первого 1/100, второго 2/100, а последного 99/100?

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

А может так:
Раз первый выбирает не своё место, то он тогда выбирает, как сказал Forever Free из 99. тогда вероятность второго 1/100, и так далее... А последнего - 99/100...

короче, сама уже запуталась

 

[Forever Free]

Это всех пассажиров одновременно на свои места. А для каждого 1/100.

Это если считать что каждый заходит в пустой салон, ведь так ? Т.е. 1/100 справедливо только для первого.

 

[Trotil]

Решаем задачу сначала на малых числах перебором... Пусть у первого пассажира первое место, у второго - второе, ..., у n-того - n-тое. Они входят по-очереди и первый выбирает любое место.

n=2. Здесь всего два варианта - удачный и нет. p(2)=1/2

n=3. 3 варианта выбора первым кресла.
1/3 - удачный выбор, (1 кресло)
1/3 - неудачный (2-ое)
1/3 - неудачный (3-ее)

(1) - тогда все пассажиры автоматически садятся на свое место - последний садится с вер. p=1 на свое место
(2) - второй с p=1/2 выберет не третье место, значит p=1/2 третье место будет свободно и что последний сядет на свое место
(3) - первый занял место последжнего пассажира. Последний туда точно не сядет!



Теперь это нужно обобщить на большее кол-во мест.


Для произвольного n:

Первый пассажир выбирает произвольно из n мест:

1/n - первое место => p=1 для последнего
1/n - второе место - второй оказывается в положении первого - задача сводится к нахождению p(n-1)
1/n - третье место - второй садится на свое, третий оказывается в положении первого - задача сводится к нахождению p(n-2)
...
1/n - n-тое место - последний на свое место точно не сядет - оно занято!

=1/n*1+1/n*p(n-1)+1/n+1/n*p(n-2)+...+1/n*p(2)+1/n*0=1/n*(1+p(n-1)+p(n-2)+...+p(2))" src="http://graph.mixei.ru/Formula/formula.php?f=p=1/n*1+1/n*p(n-1)+1/n+1/n*p(n-2)+...+1/n*p(2)+1/n*0=1/n*(1+p(n-1)+p(n-2)+...+p(2))">

Далее нужно ее решить )

+p(n-1)+p(n-2)+...+p(2))" src="http://graph.mixei.ru/Formula/formula.php?f=p(n+1)=1/(n+1)*(1+p+p(n-1)+p(n-2)+...+p(2))"> или

n*p=1+p(n-1)+p(n-2)+...+p(2)) (из первого)
(n+1)*p(n+1)=1+p+p(n-1)+p(n-2)+...+p(2)) (из второго)

-> n*p=(n+1)*p(n+1)-p
=> p=p(n+1)=const =1/2 (мы ее получили на малых числах n=2,3)

Можно тоже самое доказать безо всяких вычислений, кстати. Заметим, что у нас только два крайних случая - выбор кресла первого пассажира и выбор кресла последнего. Выбор между ними осуществляется равновероятный.

Выбор любого другого кресла по сути ничего не решает. Допустим, первый пассажир выбрал k-тое место. Пассажиры 2, 3, ..., (k-1)-ый садятся на свое место, т.к. они свободно.

K-тый пассажир оказывается в положении первого: если он выберет 1-ое кресло - все садятся на свои места и последний тоже, если на последнее - неудачный исход. Если выбирает любое другое - момент "x" снова откладывается )

то если считать что каждый заходит в пустой салон, ведь так ?

Нет, для любого, хоть для первого, хоть для последнего.

 

[Serjo_she]

Ого, здорово

 

[Diver]

классно надо запомнить!!!
а ты увлекаешься криптографией или просто решил поделиться интересной информацией?

 

[Trotil]

а ты увлекаешься криптографией или просто решил поделиться интересной информацией?

И то, и другое Криптография - одно из направлений по моей специальности )

Отсюда публиковать какие-нить алгоритмы типа DES, RSA, MD5 я пока не планирую , но в криптографии встречаются жизненные задачки с изящными решениями, они могут заинтересовать здесь кого-нить )

 

[elek]

здорово
а мне никогда не быть криптографом - так как ума, может, и хватит решать такие задачки, а вот терпения не хватает никогда Мне почему-то скучно сидеть и перебирать разные варианты выпадения монеток и т.п.
Поэтому в таких задачах предпочитаю прочитать ответ, а не думать самой , хоть это и не есть гуд

 

[Trotil]

Посвящена новой избирательный системе )

Как это делалось в Анчурии
В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 миллионов избирателей, из которых только один процент поддерживает Мирафлореса (регулярная армия Анчурии). Мирафлорес, естественно, хочет быть избранным, но, с другой стороны, он хочет, чтобы выборы были демократическими. ``Демократическим голосованием'' Мирафлорес называет вот что: все избиратели разбиваются на равные группы; каждая из этих групп вновь разбивается на некоторое количество равных групп, причём большие группы могут разбиваться на разное количество меньших групп, затем эти группы снова разбиваются и т.д. В самых мелких группах выбирают представителя группы — выборщика — для голосования в большей группе: выборщики в этой большей группе выбирают выборщика для голосования в ещё большей группе и т.д. Наконец, представители самых больших групп выбирают президента. Мирафлорес делит избирателей на группы по своей воле и инструктирует своих сторонников, как им голосовать. Сможет ли он так организовать ``демократические'' выборы, чтобы его выбрали? (В каждой группе выборщики выбирают своего представителя простым большинством. При равенстве голосов побеждает оппозиция.)

Решение этой задачи такое:

сначала разберем условие задачи на "тройках":

1 уровень: 2 "за", 1 против. Побеждает "за". Потребовалось 66% голосов "за".

2 уровень: формируем 2 тройки по принципу 1-ого уровня, третья тройка может быть состоять из одних противников - она ни на что не влияет:
2 "за", 1 против. -> "за"
2 "за", 1 против. -> "за" -------> "за"
0 "за", 3 против. -> "против"

4 "за" 5 "против" Потребовалось только 44,4% числа сторонников.

3 уровень:формируем 2 "девятки" по принципу 2-ого уровня, третья девятка может быть состоять из одних противников - она ни на что не влияет:

2 "за", 1 против. -> "за"
2 "за", 1 против. -> "за" -------> "за"
0 "за", 3 против. -> "против"

2 "за", 1 против. -> "за"
2 "за", 1 против. -> "за" -------> "за" --------> "за"
0 "за", 3 против. -> "против"

0 "за", 3 против. -> "за"
0 "за", 3 против. -> "за" -------> "против"
0 "за", 3 против. -> "против"

8 "за", 19 "против" - побеждает "за", хотя их 30% и так далее...

"ЗА" "Против" "Выборщиков" "% За"
2 1 3 66.67%
4 5 9 44.44%
8 19 27 29.63%
16 65 81 19.75%
32 211 243 13.17%
64 665 729 8.78%
128 2 059 2 187 5.85%
256 6 305 6 561 3.90%
512 19 171 19 683 2.60%
1 024 58 025 59 049 1.73%
2 048 175 099 177 147 1.16%
4 096 527 345 531 441 0.77%
8 192 1 586 131 1 594 323 0.51%
16 384 4 766 585 4 782 969 0.34%
32 768 14 316 139 14 348 907 0.23%
65 536 42 981 185 43 046 721 0.15%

Но нам нужно разбивать 20 миллионов (на тройки разбить не получится), поэтому этот алгоритм нужно модифицировать.

И еще интересен общий вопрос: какое наименьшее число сторонников должен иметь Мирафлорес, чтобы победить на демократических выборах'', если общее количество избирателей N?

 

[Федот Стрелец]

Я видел такую интерпритацию:

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

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

 

[Тимур]

1. Можно ли в квадрате 5х5 закрасить 16 клеток так, чтобы в любом квадрате 2х2 было закрашено не более двух клеток?

2. Биссектриса угла A параллелограмма АВСD пересекает сторону ВС в точке М, а биссектриса угла AMC проходит через точку D. Найдите углы параллелограмма, если известно, что угол МОС = 45°,
3. Сумма четырех натуральных чисел равна 1995. Какое наименьшее значение может принимать их НОК?
6. Найдите наименьшее натуральное число, не делящёеся на 11 и такое, что при замене любой его цифры на цифру, отличаюшуюся на 1 (например, З на 2 или 4, 9 на 8), получается число, деляшееся на 11.
7. Пусть х больше и равно 0. Докажите неравенство (1+х-х в квадрате+...+х в 100 стпени) (1+хв 100 стпени) больше и равно 200х в 100 стпени
8. Квадратный трехчлен Р(х) = ах в квадрате +Ьх+с (а, Ь, с
— целые числа, с — нечетное) имеет целые корни. Может ли Р(2009) быть нечетным числом?
9. Прожектор освещает раздвинутый угол (180°). Можно ли расположить 19 прожекторов так, чтобы никакие З не находились на одной прямой и каждый прожектор освещал бы только один другой прожектор?
10. Существуют ли 2009 непелых
рациональных чисел, произведение любых двух из которых — целое число?

 

[Д@ша]

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

Разорвать ту бумажку которую выбрал ) На оставшейся будет написано "обед" так что получится что на разорванной написано "свобода"