Фишка находится на расстоянии n клеток от заветной. Бросаем игральную кость (кубик) и, в зависимости от выпавшей суммы очков (от 1 до 6), перемещаем фишку к заветной клетке. В общем, все как в детской игре. Если мы еще не достигли заветной клетки, продолжаем этот процесс. Если мы после очередного хода оказались (ура!) в заветной клетке, мы выиграли. Если же мы проскочили (увы) заветную клетку, мы проиграли.
При каком n вероятность выигрыша максимальна?
Интуиция подсказывает, что при n=6. Есть шанс сразу выиграть и бросить еще в случае недоброса, ну и конечно нет шансов проиграть в один бросок.
P.S. Как то вот так это можно строго записать
If(n6) P(n) = 1/6(P(n-1) + P(n-2) + ... + P(n-6)) max(P(i), i=1,...,6), если только все вероятности не одинаковы, что очевидно.
If(n=6) P(n) = 1/6 + sum(m=1,m=n-1) P(n-m)/6
Справа положительный ряд чем длинее тем лучше, можно и явно записатъ
что касается случая n=6, можно еще так это показать (это называется coupling): рассмотрим 2 процесса, один стартует с расстояния 6, другой - с расстояния k, k6. Бросаем кость, пусть выпало j очков; тогда второй процесс (из k) прыгает на j шагов вперед, а первый (из 6)
на 6-k+j шагов вперед, если j=k,
на j-k шагов вперед, если jk.
Тогда (внимание, трюк!)
- либо второй процесс не перескочил и первый будет в той же точке, что и второй (и значит шанс дальнейшего успеха для них уже одинаков);
- либо второй процесс перескочил, а первый нет, и значит он еще имеет шанс.
ММ3
Hекий путешественник, идя по доpоге в стpане, где живут pыцаpи и лжецы, встpетил гpуппу из нескольких местных жителей. Каждый из встpеченных по-очеpеди пpоизнес две фpазы (причем первые фразы зависели от порядкового номера говорящих, а вторые были одинаковы). k-й по счету сказал:
Сpеди нас не более k pыцаpей. Сpеди моих спутников есть лжецы.
Сколько человек встpетил путешественник?
Hапомню, что в задачках такого типа pыцаpи всегда говоpят пpавду, а лжецы всегда лгут.
Правильно ли я понимаю, что первые k-1 человек сказали одну и ту же вторую фразу, но не ту, что к-человек?
И к - это не максимум?
Т.е мы имеем
1. либо к-1 лжецов.
2. либо к-1 рыцарей первых
А. к-человек должен быть либо рыцарем
Б. либо лжецом
Варианты
1A Не более к рыцарей. Число лжецов N неизвестно - вплоть до бесконечности.
1Б.
не бывает
2А к рыцарей и N лжецов Число лжецов N неизвестно
2Б Более к рыцарей.
Я тоже так думаю.
Остается добавить, что с увеличением расстояния до заветной клетки вероятность наступить на нее неограниченно приближается к 2/7, что понятно и без вычислений: 7/2 - это средняя длина хода.
Сразу ясно, что в группе есть лжецы, причем по словам одного из них выясняется, что он только один.
Первым спрашивали именно его (иначе противоречие), и из его слов следует, что рыцарей больше одного. Уже из слов второго спрошенного - рыцаря - следует, что рыцарей не более 2. Т.е. лжец один, рыцарей двое.
с увеличением расстояния до заветной клетки вероятность наступить на нее неограниченно приближается к 7/2
Хмм .. это какая-то новая вероятность, которая больше 1
Уже исправил на 2/7.
Теперь касательно вероятности 7/2. Подумаешь, невидаль! Могу привести пример, в котором вероятность события будет, например, -3/2:
В пустую урну положим 5 белых шаров. Затем вытащим три шара обратно. Какова вероятность, что четвертый вытащенный шар окажется черным, три условии, что при предыдущих оказались черными? Считаем по классическому определению вероятности: всего шаров в урне - 5 - 3 = 2. Из них черных - 0 - 3 = -3. Таким образом искомая вероятность будет -3/2.
Описать ситуацию, в которой вероятность события будет достигать 7/2 предлагается читателям в качестве легкого упражнения.
В пустую урну положим 5 белых шаров. Затем вытащим три шара обратно. Какова вероятность, что четвертый вытащенный шар окажется черным, три условии, что три предыдущих оказались черными?
Какова вероятность, что четвертый вытащенный шар окажется черным, три условии, что три предыдущих оказались черными? Считаем по классическому определению вероятности:
Ладно, шутки в сторону. С ММ1 и ММ3 разобрались. А как с остальными? А как с конкурсными?
Если быть честным, ув. val, то задачи типа про Футбольные команды обычно сводятся к нудному перебору разных вариантов и исключению невозможного.
Исключения бывают, но очень редко IMHO.
Доказать, что в любой группе людей число тех, кто знаком с нечетным числом членов группы, четно.
Ну в матрице смежности неориентированного графа общее количество 1 четное. - любое ребро добавляет 2 единички. (Петель естественно нет, т.е. человек знаком сам с собой, но мы это не считаем
)
Тогда те, кто знаком с четным числом членов группы дают в сумме чет - (сумма по строкам матрицы.)
Соответственно и те, кто знаком с нечетным числом членов группы должны давать чет.
Как то так.
Эта кривая называется Лемниската Бернулли (типа матзнак бесконечности) - от любой точки произведение расстояний до 2-х фокальных точек постоянное (==a^2, в данном случае а=sqrt(2) ).
А длина дуги это эллиптический интеграл (d phi / sqrt(cos (2 phi))). Но как связать это с условием, что произведение косинусов для данных 2-х углов это 1/sqrt(2).
Ладно, шутки в сторону. С ММ1 и ММ3 разобрались. А как с остальными? А как с конкурсными?.
Если быть честным, ув. val, то задачи типа про Футбольные команды обычно сводятся к нудному перебору разных вариантов и исключению невозможного.
Исключения бывают, но очень редко IMHO.
Я только что отвечал на это же обвинение (в другом форуме и по поводу другой задачки, но тоже на восстановление таблицы). Придется повториться.
Разумеется. подобные задачки можно решать полным перебором, например, написав программку (и мне известны случаи именно такого решения). Но гораздо привлекательнее рассуждательные решения, когда шаг за шагом табличка заполняется единственно возможным способом.
Продублирую и еще одно свое замечание.
Я полагаю, что все задачи по большому счету переборные: перебираются известные алгоритмы; перебираются подходы и идеи, оказавшиеся полезными при решении других задач; перебираются частные и предельные случаи, в надежде набрести на идею...
Исключение составляют ситуации, когда мы сразу видим стандартный план решения. Но это тот случай, когда и задачи, как таковой нет. Так, упражнение...
To All:
Кстати, истекает срок приема решений конкурсных задач ММ111 (эта задачка совсем устная. но даже в ней есть маленький подвох, не все присланные решения верны) и ММ112 (уж эта-то задачка точно не переборная... в классическом понимании этого термина)
PS: Напоминаю, что решения конкурсных задач следует присылать лично мне.