С обозримыми по размеру задачами всё просто - можно посадить не очень квалифицированного товарища проводить относительно простую (пусть и нудную) работу, пока он не достигнет результата (лучший вариант - компьютерный перебор). Но если в нашей задаче проводятся операции с очень большим количеством объектов, то нельзя просто сказать «дальше действуй аналогично», потому что даже с нынешней невероятной производительностью компьютеров никакой жизни не хватит для получения ответа.
Да и говорить «и так далее» весьма опасно, так как этот ход опирается только на интуицию, которая может подвести. Приведу другой пример, чтобы «освежить страх» перед «очевидными» вещами:
Пусть наш подопытный человек спустится в метро, выйдет на платформу и сядет в первый подъехавший поезд. Известно, что поезда на обоих платформах ходят через равные промежутки времени. Верно ли, что пассажир уедет с правой или с левой платформы с одинаковыми вероятностями?
На первый взгляд, ситуация абсолютно симметричная, поэтому хочется сказать «да». Полагаю, скоро в комментариях можно будет прочитать объяснения от читателей, которым такой ответ не близок. А пока мы вернёмся обратно к чистой и изящной технике - методу математической индукции.
Идея проста как лестница:
1) если мы уже стоим на первой ступеньке лестницы,
2) если мы умеем с любой ступеньки подняться на следующую,
то мы теоретически можем достичь любой ступени.
Достаточно проверить всего два узких пункта, чтобы сделать очень широкий вывод (мы не произнесли громко, что у лестницы может быть бесконечно много ступенек, но подумали это).
Если бы мы проверяли все ступеньки индивидуально, то пришлось бы быть внимательными на каждой итерации (а их может быть очень много). В случае применения метода математической индукции надо быть аккуратными только в двух пунктах.
Представьте себе доску 128х128 клеток, из которой вырезали одну клеточку. Возможно ли её покрыть г-образными фигурками, состоящими из трёх клеток (как на рисунке) так, чтобы фигурки не свисали с доски и не налезали друг на друга? (естественно, фигурки можно поворачивать)
Первая естественная мысль: раз фигурки состоят из трёх клеток, то и количество клеток доски должно делиться на 3, чтобы такое покрытие было возможно. Проверяем: 1282-1=(128-1)(128+1). Второй множитель очевидно делится на три. Другими словами, малой кровью ответить «нет» на вопрос задачки мы уже не можем.
А что можем? Можем взять листок бумаги 128 на 128 клеток, вырезать из него одну произвольную клеточку, подготовить множество триминошек... И методично пытаться уложить фишки на поле так, чтобы выполнить условие задачи. Если удастся, то надо будет попробовать вырезать из поля другую клеточку, так как требуется проверить все случаи... Представляете масштаб работы?
Что можем ещё? Можем вспомнить тему этой заметки - метод математической индукции. Если заранее не знать, то трудно придумать его применение для такой формулировки. В данном случае мы всё вспомнили, поэтому триминошки должны легко сдаться. Удачи!
В следующей заметке будет разбор этой задачи и демонстрация других применений метода. Также будет пояснено на примерах, почему очень важна аккуратность в проверке обоих пунктов.
Хорошего дня! И поделитесь своими соображениями по поводу пассажира метро :)
18 авг. 2009 г.
Математическая индукция
Темы:
математика,
образование
Подписаться на:
Комментарии к сообщению (Atom)
Понравилась заметка? Подпишитесь на
RSS-feed или email-рассылку.
Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
RSS-feed или email-рассылку.Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
Относительно метро я не согласен :)
ОтветитьУдалитьЕсть несколько причин.
Подопытному может просто так нравиться правая или левая сторона. Или не понравиться противоположная. Например, он не ходил "налево" ;)
Вполне возможно, что он уже был на этой станции, поэтому может пойти по более привычному для себя маршруту. Иногда люди неосознанно, "на автомате" идут по привычному маршруту, даже если им в другую сторону надо.
Его может заинтересовать какой-нибудь объект и он пойдёт за ним.
Когда поезда начинают выезжать из депо, то с одной стороны платформы они могут появляться чаще, чем с другой.
Такая же ситуация, когда поезда возвращаются в депо.
Утром пускают дополнительные поезда, которые не проезжают весь путь, а сворачивают в депо раньше последней станции на ветке. Таким образом на последней станции человек вообще не увидит этого состава.
В час-пик поезда могут ходить асинхронно, чтобы не вызывать массовые скопления людей на станциях.
В тот же час-пик поезда могут рассинхронизироваться из-за лезущей толпы в вагон и её нежелания закрыть двери в вагон.
Всякие форс-мажоры, например, пожар. Тогда поезда с одной стороны вообще могут не ходить.
И т.д. ;)
А с метро поди хитрость в разных фазах поездов на правой и левой платформах, да?
ОтветитьУдалитьВ метро будет иметь значение "сдвиг фаз" - соотношение времени появления поездов на путях 1-2 и 2-1 будет соответствовать вероятности попадания на тот или иной поезд.
ОтветитьУдалитьС Г-образными фигурками соображение следующее:
квадрат 2х2 можно заполнить с любым отсутствующим квадратом одной фигуркой,
квадрат 4х4 можно составить из трех квадратов 2х2 с фишками, обращенными к общему углу пустыми ячейками, в которые поместить еще одну фишку, в итоге получаем три из четырех квадратов 2х2 полностью заполненными, а в четвертый помещаем одну фигурку и остается одна ячейка свободная,
по подобию можно и дальше наращивать количество квадратов, соединяя три "лишних" пустыми углами и закрывая эти пустые углы одной фишкой, а в четвертом помещая пропуск в любое место.
Т.о. задача решается.
Sbrusentsov, спасибо за большой список жизненных причин - все они могли бы ломать реальный эксперимент, хоть и формально не очень соответствуют условию задачи )
ОтветитьУдалитьУважаемый аноним, спасибо за формулирование догадки. А Александр выразил её предельно точно и лаконично!
Также благодарю Александра за изложение решения задачки о тримино.
ну пусть поезда ходят раз в час.
ОтветитьУдалитьто вполне возможно, что один всегда отправляется в x:00, а второй в x:01.
и шансы уехать на первом в 59 раз больше :)
Уважаемый аноним, Вы придумали очень яркий и доходчивый пример, спасибо.
ОтветитьУдалитьНасчет выезда из депо - такие поезда просто стоят дольше, поэтому сесть в него вырастает, в то время как на поезд, идущий в депо, люди обычно не садятся)
ОтветитьУдалить*вероятность сесть в него вырастает
ОтветитьУдалитьЗадачу про метро встречал где-то в "художественном" варианте.
ОтветитьУдалитьНекий молодой человек заканчивает работу в случайный момент времени между 17 и 19 часами. Нигде не задерживаясь, идет в метро и садится в первый попавшийся поезд. Поезда идут по расписанию с десятиминутным интервалом и в ту, и в другую стороны. Дело в том, что у него в одном конце города живет мать, а в другом невеста. Он уверяет, что попасть к той и другой равновероятно, но мать обижается, что он у нее за месяц бывает раза два-три.
Виктор, спасибо за художественную версию, объясняющую физический смысл задачки :)
ОтветитьУдалитьПри прочих равных, а также при условии, что человек спускается на станцию параллельно движению поездов (перпендикулярно тоже впринципе работает, но схема более сложная) правая сторона платформы (по крайней мере так в Киеве) будет более вероятна, чем левая. Потому-что поезда с правой стороны движутся в одну сторону с пользователем, а значит он начинает их слышать и видеть сам поезд (свет фар не считается) раньше, чем поезда с левой стороны.
ОтветитьУдалитьЕсли сдвига фаз нет, точнее, поезда приходят в противофазах, то левая сторона более вероятна, поскольку объект некоторое время движется по платформе параллельно движению поездов. Естественно, встречных поездов будет больше, чем попутных. А если каждый раз, когда он спускается в метро, сдвиг фаз меняется случайным образом, то в общем, левая платформа будет у него в фаворе.
ОтветитьУдалитьНе нашёл у вас в блоге упоминания о сборнике задач «Смотри в корень!» Петра Маковецкого. Мне кажется, вам он был бы интересен.
ОтветитьУдалитьhttp://n-t.ru/ri/mk/sk.htm
Уважаемый аноним, спасибо за содержательную ссылку!
ОтветитьУдалитьВот она и пригодилась - вышла заметка "И так можно".
Вероятность того что человек в метро выберет поезд слева больше. Допустим что поезда приходят в разное время, тогда вероятность 50/50. А если в одно и тоже время, то поезд что слева будет казаться ближе к человеку, чем справа.
ОтветитьУдалитьЯ считаю, что задача не решаема в данном виде. Недостаточно условий. Все попытки решений связанны с допущениями.
ОтветитьУдалитьКак и в парадоксе про два конверта. В нем я тоже не вижу никакого парадокса. Там, я считаю, опять же недостаточно данных для решения. Мы в обоих случаях не можем узнать вероятность события, поскольку неизвестно что и как на него влияет.
Илья, Вы здесь так и не добавили третий необходимый пункт о том что имеется корректный переход с первой ступеньки на следующую. Я уже объяснял в одной из заметок на примере лиловой лошади, что игнорирование именно этого пункта приводит к тому что все лошади лиловые.
ОтветитьУдалитьУважаемый аноним, сформулированное Вами третье условие является частным случаем второго.
ОтветитьУдалитьЕсли мы умеем перейти с любой ступеньки на следующую, то мы автоматически умеем перейти с первой на вторую.
Другими словами, ошибка не в отсутствии третьего пункта, а в неправильном (невнимательном) доказательстве второго.
Нет Илья, Вы здесь не правы. Есть два отдельных совершенно разных пункта.
ОтветитьУдалить2. Есть рабочая гипотеза Г1, предположение о том, что "все предыдущие шаги верны вплоть до k-1". Мы на самом деле не знаем, верна ли или нет гипотеза Г1. Да нам это и не важно. Нам на это глубоко наплевать. Мы всего лишь хотим посмотреть, а что будет если вдруг Г1 верна? - можно ли сделать какой-либо вывод, в предположении что Г1 верна, насчет ситуации номер k?
Еще раз.
Т.е. мы только в данном месте и только чтобы посмотреть что получится, делаем ПРЕДПОЛОЖЕНИЕ о том что якобы для всех k-1 ситуаций имеет место выполнение доказываемого утверждения. Что мы в этом предположении можем сказать насчет k?
3. Должен быть выполнен как минимум один корректный переход из области достоверно доказанного (шаг 1) в область гипотезы Г1 (шаг 2). Без этого перехода гипотеза Г1 так и останется гипотезой, не более, как и все выводы, основанные на ней. Этот переход не может быть частным случаем пункта 2, поскольку основывается на достоверных данных.
Эти два пункта даже на листе должно размещать отдельно, чтобы не запудривать мозги читателю доказательства, чтобы он четко понимал, на чем мы сейчас стоим - на твердой почве или на предположениях.
Уважаемый аноним,
ОтветитьУдалитьесли не трудно, сообщите, пожалуйста, какую книгу Вы цитируете. Есть много разных подходов к ММИ. Судя по Вашему последнему комментарию, Вы говорите о методе трансфинитной индукции. Я ничего против неё не имею, конечно, но в этой заметке мы обсуждаем более простой случай.
Но вообще мне очень интересно, почему Вы так настаиваете, что пунктов должно быть три. Аксиомы Пеано, например, предлагают нам проверять только два пункта (базу и переход от любого к следующему). В статье wiki тоже описаны только два пункта. Но мне не столько важен авторитет источника, сколько его обоснование. Я не вижу смысла требовать проверять одну и ту же вещь дважды (а Ваш третий пункт выглядит как частный случай второго). Объясните, пожалуйста, почему Вы считаете, что он необходим.
Было выше " Без этого перехода гипотеза Г1 так и останется гипотезой, не более, как и все выводы, основанные на ней". Можете считать что я не прав, я не хочу спорить. Учились мы по лекциям и конспектам, ссылку дать не могу.
ОтветитьУдалитьНам ещё далеко до понимания, кто прав, так как сначала надо понять, в чём состоит утверждение. Поскольку мне не очень понятны Ваши аргументы, то я попросил полное название той сущности, которую Вы описываете. Возможно, если бы Вы могли указать книгу, по которой Вам читали лекции, то я бы быстрее понял, о чём мы спорим.
ОтветитьУдалитьВы зачем-то цитируете своё же высказывание, хотя оно мне уже один раз не помогло. Попробуйте раскрыть свою позицию подробнее. Я искренне хочу понять, а Вы "не хотите спорить"... Досадно.
Про поезда - дело в фазах, да?
ОтветитьУдалитьНапример, если поезд л приходит сразу после поезда п - то вероятность попасть на л будет очень мала (там формула простая).
Вопрос в том, что тут много всяких предоположений высказали в блоге, что еще направление движения играют роль, или выход из депо и т.п. - они играют в этой задаче или нет?
Еще про поезда.
ОтветитьУдалитьРазница фаз, конечно, имеет значение, но если привязаться к абсолютному направлению - все меняется. Поезда пусть у нас ходят "по часовой" и "против часовой" (относительно метрополитена, а не пассажира).
Примем вероятность ухода первого поезда в направлении "по часовой" за P1, тогда
вероятность ухода первого поезда в направлении "против часовой" - соответственно, P2=1-P1.
Но, мы не знаем - с какой стороны пассажир заходит в метро. И поэтому вынуждены считать входы равновероятными (такое себе дополнительное предположение, что входа два и они "равнодоступны"). В этом случае полная вероятность того, что первым уйдет _Левый_ поезд составит Pl=P1*Pc+(1-P1)*(1-Pc) Где Pc слева - это вероятность зайти "по часовой". В случае равновероятного выбора входов, Pl=0.5.
Независимо от того, какой поезд уходит раньше.
Как доказать методом математической индукции, что для любого натурального числа n справедливо утверждение:
ОтветитьУдалить1*1!+2*2!+…+n*n!=(n+1)!-1
У Вас возникли сложности с решением этой задачки или Вы её предлагаете в качестве полезного упражнения?
Удалить