На самом деле у меня ещё есть неясность - Ваша критика обоснована. Я опять таки неявно предположил, что те пути из В в А не проходят через С. Но кажется, что это несущественно. Надо подумать.
На самом деле у меня ещё есть неясность - Ваша критика обоснована. Я опять таки неявно предположил, что те пути из В в А не проходят через С. Но кажется, что это несущественно. Надо подумать.
Посмотрел на свежую голову и понял, что спорол чушь. Абсолютно правильное доказательство. Вы даже правильно усмотрели ньюанс с точкой С. Согласен, что это не создает проблему, поскольку сразу получается путь AC, не содержащий точку В.
Вот как Григорий умеет признавать свои ошибки, даже когда таких, оказывается, не было
. Когда, однако, якобы и видимо однозначные мат. абстракции начинают кучковаться и нагромождаться одна на другую, выпрыгивают коллективные эффекты, вроде отлучения или да ЛН от церкви. Оценка таких эффектов менее однозначна, к сожалению, и матемАтику лучше об этом не забывать
Я опять таки неявно предположил, что те пути из В в А не проходят через С. Но кажется, что это несущественно. Надо подумать.
Действительно несущественно(увы, думать я сейчас могу только по утрам, в другое время голова совсем не работает).
Снова изложу всё д-во.
Пусть мы уже доказали, что для всех точек расстояния не больше k от А существуют 2 непересекающихся пути в А.
Докажем это же для любой точки С, находящейся от А на расстоянии k+1.
Существует точка В, находящаяся на расстоянии 1 от С и k от А. Из неё по предположению индукции ведут в А 2 непересекающися пути.
1. Эти пути не проходят через С.
Существует путь из С в А, не проходящий через В. Если он не пересекается ни с однм из тех 2-х путей, то присоединяем к любому из них СВ, и вместе с даннным они - 2 нужных нам пути.
Если пересекается, то идём по нему до 1-ого пересечения с одним из тех 2-х, затем по тому с которым пересеклись в А. Это один путь, а 2-ой - оставшийся из В в А плюс CB .
2. Один из них проходит через С.
Идём по его части от С до А - это один путь, а 2-ой отрезок СВ плюс 2-ой из тех путей.
Новогодняя задачка, специально для любителей индукции
Рассмотрим прямоугольную решетку N x (N+1):
(здесь N=4).
Далее, каждое ребро независимо оставляем или выкидываем с вероятностями 1/2. Получаем некую случайную конфигурацию, например, такую:
Рассмотрим событие что существует путь слева направо (не обязательно единственный), и пусть p_N - вероятность этого события. Например, для предыдущей конфигурации это событие происходит (путь выделен красным):
С Новым Годом! (Красивая задачка, хотел лишь посмотреть просмотры..., а застрял на ней. Как буд-то все просто, типа 1/2 * на количество первоэлементиков. Но предполагаю, что больше. Попытаюсь решать после сегодняшних гостей. Так как задачка новогодняя, то можно попытаться угадать ответ). Не решаю, вспоминаю, что более всего поражен был когда-то тем, что сопротивление плоского квадрата любого токопроводящего материала НЕ зависит от его размеров. По такой (не)правильной аналогии, вероятность искомая может стремиться к вероятности для наименьшего квадрата (с четырмя только ребрами), для которого боковые-то и роли не играют! Итого: 1/2, а что будет взаправду, а не как буд-то надеюсь к Рождеству ув. квантофорумчане просветят. З павагай
Так если нет никаких иных данных, типа упоминаний независимости, случайности событий, то в соответствии с причинной связью из известной темы (если начисто исключить закон пакости, который заставит при единственной попытке вытащить нужный носок последним, )то будет n/2. (А не так как требует классическая математика, исходя их произведения вероятностей отдельного события и с учета нарастания количества возможных пар, так как все больше будет в наличии непарных после неудачных попыток ). Тут хоть какое-то число задано первоначально.
Если я понял правильно, то квантофорумчан надо попросить в этой теме развеять, подтвердить или решить (т.н. задачку) именно в этой теме: 6) Большой пруд зарастает зеленью. Каждый день площадь зелени увеличивается вдвое. На какой день она покроет весь пруд полностью? (Ни начальной зелени ни площади пруда не задано, что надо самому вводить их?) Или раз это тест = то на усмотрение тестируемого?
Задачку эту хочется решать по индукции. Но не надо
На самом деле, как сказал ув. РР, надо воспользоваться симметрией, чтобы получить ответ 1/2 (для любого N). Рассмотрим двойственную решетку (желтым цветом на рисунке) - в ней ребро присутствует тогда и только тогда, когда соответствующее ребро в изначальной (синей) решетке отсутствует.
И теперь ответ легко получается из того соображения, что путь слева направо на синей решетке имеется в том и только в том случае, когда нет пути сверху вниз на желтой решетке.
Удалось обобщить задачу на случай многоногих животных, которым нужно не 2 носка, а k, и которым нужно набрать комплект из ящика с n комплектами. Ответ на удивление изящен.
И теперь ответ легко получается из того соображения, что путь слева направо на синей решетке имеется в том и только в том случае, когда нет пути сверху вниз на желтой решетке.
Предположение о том, что всегда есть либо горизонтальный либо вертикальный путь, не выглядит таким уж очевидным.
Назовем событиями А / А' наличие / отсутствие синего пути, а также событиями B / B' наличие / отсутствие желтого пути.
Очевидно, что P(B) = P(A'), P(A) = P(B'). Так как если есть синий путь, то желтому его придется пересечь, что невозможно по определению. Тогда:
P(A) + P(B) = 1- P(A')+P(B) = 1 - P(B) + P(B) = 1
P(A) + P(B) = P(A) + 1 - P(B') = P(A) + 1 - P(A) = 1
P(A) + P(B) = 1
Назовем событиями А / А' наличие / отсутствие синего пути, а также событиями B / B' наличие / отсутствие желтого пути.
Очевидно, что P(B) = P(A'), P(A) = P(B'). Так как если есть синий путь, то желтому его придется пересечь, что невозможно по определению. Тогда:
P(A) + P(B) = 1- P(A')+P(B) = 1 - P(B) + P(B) = 1
P(A) + P(B) = P(A) + 1 - P(B') = P(A) + 1 - P(A) = 1
P(A) + P(B) = 1
Почему? Если произошло A, то нет желтого пути вниз, тоесть произошло событие из B'.
З.Ы. Совсем на ночь не соображаю. Только сейчас понял, да так нельзя.
Предположение о том, что всегда есть либо горизонтальный либо вертикальный путь, не выглядит таким уж очевидным.
Посмотрел я с утра, как это доказывается. В принципе не очень длинное рассуждение есть, но не в две строчки. Давайте купимся на такое физическое безобразие
Если по желтым каналам, заливать воду с верху вниз, то вода пройдет до низа тогда и только тогда, когда нет синего пути (в дне кастрюли есть дырка). Тоесть P(А') = P(B).
Если по желтым каналам, заливать воду с верху вниз, то вода пройдет до низа тогда и только тогда, когда нет синего пути (в дне кастрюли есть дырка). Тоесть P(А') = P(B).
