То да, если в голове нет какого-нибудь обхода, придется сфокусировать взгляд и найти 4х2 покрытие.
Задачи, головоломки, загадки
- Автор темы ilya saban
- Дата начала
Там помниццо была какая-то мнемоника для обхода, но, по-моему, ее запомнить не легче, чем сам обход.
Это да. Но этого не требовалось в задаче.
Ещё формальное замечание для общего случая.
Как верно заметил @Umber hulk, клетки при последовательных ходах чередуются: черная-белая. То есть, хроматическое число нашего графа равно двум. Значит наш граф -двудольный (bipartite). Далее - для квадратной доски с четным количеством клеток, очевидно (из соображений симметрии), выполняются условия теоремы Холла (теорема Холла о свадьбах), а значит, существует perfect matching, т.е. граф разбивается на пары, что есть достаточное условие для выигрышной стратегии Боба.
ПС. Причем perfect matching в двудольном графе находится за полиномиальное время.
Как верно заметил @Umber hulk, клетки при последовательных ходах чередуются: черная-белая. То есть, хроматическое число нашего графа равно двум. Значит наш граф -двудольный (bipartite). Далее - для квадратной доски с четным количеством клеток, очевидно (из соображений симметрии), выполняются условия теоремы Холла (теорема Холла о свадьбах), а значит, существует perfect matching, т.е. граф разбивается на пары, что есть достаточное условие для выигрышной стратегии Боба.
ПС. Причем perfect matching в двудольном графе находится за полиномиальное время.
Последнее редактирование:
Итак, снова пятница, а значит пришло время новой задачки. Сегодня будет из нелюбимых некоторыми - на вероятность.
Имется три лампочки А, Б и В. А загорается на мгновение каждые 2 минуты, Б - каждые 4 минуты, В - каждые 6 минут. Начали лампы загораться когда-то в преисторическое время в случайный момент, независимо друг от друга.
Вы заходите в комнату с лампами в случайный момент. С какой вероятностью первой зажжется лампа А (Б, В)?
Имется три лампочки А, Б и В. А загорается на мгновение каждые 2 минуты, Б - каждые 4 минуты, В - каждые 6 минут. Начали лампы загораться когда-то в преисторическое время в случайный момент, независимо друг от друга.
Вы заходите в комнату с лампами в случайный момент. С какой вероятностью первой зажжется лампа А (Б, В)?
Ок, попробуем тогда немного по-другому порассуждать:
1. Разобьём 6-ти минутный участок на 3 интервала по 2 минуты.
2. Допустим что все три лампы вспыхивают когда-то в первом интервале.
3. Тогда вероятности вспыхнуть у каждой в первом интервале равна и составляют 1/3
4. Во втором интервале соответственно может вспыхнуть только лампа А с вероятностью 1
5. В третьем интервале уже может вспыхнуть и лама Б, соответственно вероятность что вспыхнет А - 1/2
Далее всё повторяется.
Т.е. получаем для А: (1/3+1+1/2)/3
2. Допустим что все три лампы вспыхивают когда-то в первом интервале.
3. Тогда вероятности вспыхнуть у каждой в первом интервале равна и составляют 1/3
4. Во втором интервале соответственно может вспыхнуть только лампа А с вероятностью 1
5. В третьем интервале уже может вспыхнуть и лама Б, соответственно вероятность что вспыхнет А - 1/2
Далее всё повторяется.
Т.е. получаем для А: (1/3+1+1/2)/3
Ответ близкий к правильному, но неправильный. Напрягаем извилину ещё!
ПС. Попробуй на компьютере смоделировать.
Не понял как, но верно.
А чего тут непонятного?Не понял как, но верно.
Свои умозаключения я выкладывал постом выше, тока я там ошибся с периодом, он равен не трём а шести (те разбиваем на 6 интервалов).Или правильные бородатые математеги это как-то иначе решают?
Получается что нет.
А, понял. Ты взял период в 12 часов и разбил его на 6 интервалов по 2 часа?А чего тут непонятного?
Или правильные бородатые математеги это как-то иначе решают?
Тогда "усложняем" - что если А загорается каждые sqrt(2), Б - e, В - Pi минут?
Да, для общего решения с произвольными периодами у меня силёнок не хватает.
Чувствую что надо что-то проинтегрировать, но что именно не соображу...
Или же для решения достаточно математики школьного уровня?
Ну я считал обычной, школьной математикой.
Допустим лампы загораются с периодами a, b и c.
Допустим a - минимальный период. Тогда посчитаем вероятность что лампа A загорится первой.
Расмотрим период времени длиной a.
Вероятность что за это время загорится A равна 1, B - a/b, C - a/c.
возможны 4 разных случая:
1) Прилетят все три с вероятностью 1 x a/b x a/c.
В этом случае А будет первым с вероятностью 1/3.
2) Прилетят только A и B с вероятностью 1 x a/b x (1 - a/c). В этом случае A будет первым с вероятностью 1/2.
3) Аналогично 2) но прилетят только A и C.
4) Прилетит только A. Вероятность этого равна 1 x (1 - a/b) x (1 - a/c). Ну и А в этом случае будет первым 100%.
Осталось только сложить вероятности полученные в случаях 1-4.