Сегодня мы разберёмся с недавней задачкой о прямых, а потом вникнем в одно доказательство, из которого вроде бы следует, что все лошади лилового цвета.
Итак, на плоскости расположено n прямых. Можно даже считать, что прямые делят плоскость на куски. И мы пытаемся понять, сколько потребуется цветов, чтобы раскрасить эти области между прямыми. Требуется так красить, чтобы по разные стороны от одного ребра были разные цвета (соседние по ребру куски должны быть разного цвета).
Давайте представим эту задачу при различных значениях n, чтобы лучше её понять:
1) n=1 - простейший случай. Одна прямая делит плоскость на две области, поэтому требуется ровно 2 цвета.
2) пусть мы уже знаем, как раскрасить плоскость, пересечённую k-1 прямой. Сколько нам понадобится цветов, чтобы раскрасить плоскость, на которой расположено на одну прямую больше?
Как минимум два - это мы знаем из первого пункта (и чувствуем отлично). Вообще, для формирования гипотезы невредно что-нибудь порисовать на бумаге. Если долгое время не получается придумать набора прямых, вынуждающего использовать больше двух цветов, то порой имеет смысл попробовать, что двух цветов хватит.
Итак, пусть k-1 прямая расположена на плоскости, причём двух цветов уже хватило, чтобы раскрасить области, образованные пересечениями прямых. Теперь произвольным образом на плоскость падает ещё одна прямая - прямая номер k. Что теперь можно сделать, чтобы восстановить корректность раскраски? Достаточно это представить или нарисовать, чтобы стало очевидно - достаточно по одну сторону от новой прямой поменять все цвета на противоположные.
Другими словами, мы доказали, что двух цветов на раскраску заведомо хватит и ощутили лишний раз мощь метода математической индукции. В некоторых задачах сложно придумать шаг индукции, в некоторых - проверить базу, в некоторых - догадаться, какую именно гипотезу проверять (да и вообще, понять, что именно мат. индукция нужна). Но бывает так, что есть решение, но не ясно, где проблема.
Предлагаю разобраться в знаменитой теореме о том, что все лошади одного цвета.
Итак, теорема о лошадях. В любом множестве лошадей, состоящем из n особей, все лошади имеют одинаковый цвет.
Доказательство: Применим метод математической индукции:
1) База индукции - пусть n=1. Очевидно, что стадо из одной лошади содержит только лошадей одного цвета
(«На первую ступеньку забрались» :)
2) Шаг индукции - пусть мы знаем, что если в стаде k-1 лошадь, то все лошади в нём одного цвета. Возьмём для рассмотрения любое стадо из k лошадей. Если убрать из него одну лошадь, то получим стадо из k-1 лошади (а про него мы уже всё знаем - в нём все лошади одного цвета). Вернём ту лошадь обратно, но уберём другую - опять получим стадо из k-1 лошади (и в нём опять все лошади одного цвета по предположению индукции). Это означает, что все k лошадей были одного цвета.
(«Это мы перелезли с произвольной ступеньки на следующую» :)
Раз так, то мы можем залезть на любую высоту - все лошади одного цвета.
Если кто-то ещё сомневается в мощности математики, то можно усилить эффект. Покрасим любую лошадь в лиловый цвет. Мы уже знаем, что все лошади одного цвета, а цвет одной из лошадей мы только что задали сами. Вывод напрашивается сам собой - все лошади имеют лиловый цвет.
Означает ли этот бред, что метод математической индукции ошибочен? Нет, это говорит о том, что любой инструмент надо применять правильно. Полагаю, скоро в комментариях можно будет прочитать об ошибке в доказательстве.
Хорошего дня и спасибо Sade и Avialaynen за быстрые и дельные мысли по поводу задачки о прямых!
22 авг. 2009 г.
Лошади и аккуратность
Темы:
математика,
образование
Подписаться на:
Комментарии к сообщению (Atom)
Понравилась заметка? Подпишитесь на
RSS-feed или email-рассылку.
Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
RSS-feed или email-рассылку.Хотите поделиться ссылкой с другими? Добавьте в закладки:
Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.
С уважением,
Илья Весенний
Предположение, что лошади любого стада из k-1 голов окрашены в один цвет, сразу говорит о том, что лошадей другого цвета не бывает. В этом утверждении и содержится ошибка.
ОтветитьУдалитьСергей, здесь как раз всё нормально.
ОтветитьУдалитьЭто предположение - естественный ход в доказательстве методом математической индукции, ведь для её применения необходимо проверить два утверждения:
1) При n=1 утверждение верно,
2) Если при n=k-1 утверждение верно, то и при n=k оно будет верно.
В данном случае мы пытаемся проверить, что если верно, что в стаде из k-1 лошади все они одного цвета, то и в стаде из k лошадей это свойство сохранится. Ведь именно это требуется для доказательства утверждения для произвольного n.
Попробую более пространное изложение.
ОтветитьУдалитьСчитаем общее число лошадей конечным. Существует много вариантов составления из них стада в k-1 голов. Предположение "Если при n=k-1 утверждение верно" означает, что утверждение верно при любом варианте такого стада из k-1 лошадей. По крайней мере оно так используется в дальнейшем доказательстве. Но само это предположение верно только тогда, когда все лошади одного цвета. В противном случае среди вариантов стада найдутся такие, для которых данное предположение не верно. Таким образом мы предполагаем то, что потом доказываем.
Замечу также, что предложение "При n=1 утверждение верно" является верным только условно. Каждая лошадь, конечно, имеет некоторый цвет. Однако, если его зафиксировать, например считать серым, то предложение становится верным только тогда, когда все лошади серые. То есть опять предполагаем то, что потом доказываем.
Пользуясь случаем благодарю Илью Весеннего за интересные статьи, заставляющие думать, и удивляюсь его работоспособности.
Классная загадка! Не сразу догадались, где именно прячется ошибка - уж больно логично всё выглядит ;)
ОтветитьУдалитьСергей, Ваши рассуждения логичны, однако они лишь показывают абсурдность исходного утверждения (все лошади - одного цвета), но не объясняют, где в доказательстве ошибка.
Используя метод математической индукции, мы предполагаем, что утверждение верно для k, и пытаемся доказать, что утверждение будет верно для k+1. В принципе, нам неважно, насколько абсурдны и противоречивы чему-либо эти утверждения, важна лишь корректность перехода от k к k+1.
Самая красота этой задачи в том, что переход от k к k+1 действительно корректен!
Вот только есть один нюанс, о котором Илья (умышленно, конечно же) умолчал: для матиндукции этот переход должен быть корректен для всех k, начиная от базы индукции.
Сергей, спасибо за чёткое изложение своей версии, это очень интересно. И благодарю за тёплые слова!
ОтветитьУдалитьЧтобы было лучше понятно, давайте перейдём от очевидно абсурдной теоремы о лошадях к более абстрактной теореме о том, что через любые n точек можно провести прямую:
При n=1 и n=2 теорема очевидно верна (нам помогают знания школьной геометрии). Остаётся проверить переход от k к k+1.
Допустим, что теорема верна при некотором n=k. Покажем, что в этом случае она будет сохранять силу и при n=k+1.
Итак, пусть произвольно заданы k+1 точек M1, M2, ..., Mk, Mk+1. По предположению индукции через k точек M1, M2, ..., Mk проходит некоторая прямая. Но (по тому же предположению) через k точек M2, ..., Mk, Mk+1 также проходит некоторая прямая. И эти две прямые имеют по крайней мере две общие точки M2 и Mk. Но две точки определяют единственную прямую. Поэтому обе прямые должны совпадать.
Следовательно, прямая, проходящая через точки M1, M2, ..., Mk, проходит и через точку Mk+1. Утверждение доказано.
Сергей, попробуйте вникнуть в это доказательство, чтобы лучше понять, где находится логическая ловушка.
7vies, спасибо за такие ясные пояснения!
Илья, благодарю за приглашение выступить еще раз. Еще одна иллюстрация к моим предыдущим словам, что Вы всячески поощряете размышления своих читателей. Но я и сам хотел выступить, так как появилась новая мысль. Включаю компьютер и вижу Ваш комментарий. Начну с того, что хотел сказать про лошадей.
ОтветитьУдалитьЕсли цвет не фиксировать, то база (n=1) верна.
Проверим доказательство шага индукции. Пусть предложение "При n=k-1 утверждение верно" справедливо. Как сказал 7vies, его абсурдность не мешает такое предположить. Как доказывается, что тогда утверждение верно при n=k? Из стада в k голов выделяется стадо в k-1 голов двумя способами. Для обоих вариантов утверждение верно. Почему тогда оно верно для стада в k голов? Это не очевидно. (Здесь нет теоремы вроде "Через две точки можно провести прямую, причем только одну"). Здесь нужны рассуждения. Они подменяются интуицией читателя, а она порой приводит к ошибкам (задача о двух конусах). Эти рассуждения не очень легко сформулировать. Однако, если попытаться их провести, то становится понятно, что лошади стада в k голов будут одного цвета, когда пересечение двух стад в k-1 голов не пусто. Т.о. шаг индукции верен только при k>2. Между базой и шагом индукции есть разрыв, т.к. при k=2 доказательства нет.
С прямыми то же самое. База индукции проведена для n=1 и n=2. Шаг индукции предполагает, что два набора по k точек в каждом имеют, по крайней мере, две общие точки. Это возможно только при k>2 и, следовательно, k+1>3. Т.о. для n=3 доказательства нет.
Да, Сергей, теперь видно, что Вы полностью разобрались :)
ОтветитьУдалитьПредлагаю следующую логическую проблему - в новой заметке есть ссылка на статью о парадоксе двух конвертов. Удачи в его понимании!
Шаг индукции надо доказывать. А тут гипотеза "если верно для к-1, то верно и для к" не доказывается, а принимается за доказанную. Отсюда ошибка.
ОтветитьУдалитьВот с прямыми все нормально. Там есть алгоритм перекрашивания, который своим существованием доказывает правомерность перехода от к-1 к к.
То доказательство, которое приводится, не корректно для к=1. Там просто нет "другой лошади".
ОтветитьУдалитьТонкий момент. Я-то думал, что знаю метод матиндукции :)
ОтветитьУдалитьСпасибо за интересную статью.
Anton, поздравляю! Вы тоже разобрались, где в этом "доказательстве" обман.
ОтветитьУдалитьНа самом деле, это, конечно, упражнение на понимание метода.
Мне понравился подход, 7vies. Но после я подумал, что то тут не так. А если мы сместим немного базу, чуть-чуть изменив условие задачи, сказав, что в стаде лошадей обязательно должны быть 2 лошади одинакового цвета или 3 точки лежат на одной прямой. После этого очевидно становится, что ошибка находится в шаге индукции.
ОтветитьУдалитьВ приведенных доказательствах по сути формулируется 2 гиппотезе,которые затем автор пытается связать и получить доказательство перехода от случая с k объектами к k+1. А для правильного доказательства шага индукции необходимо формулировать 1 гиппотезу и даказывать переход от k к k+1 используя свойства добавляемого объекта.
Худоба Евгений, я не понял Вашу идею. Можете сформулировать подробнее?
ОтветитьУдалитьЯ думаю проще будет пояснить идею на доказательстве "теоремы", что через любые n точек можно провести прямую.
ОтветитьУдалитьДоказательство базы индукции очевидно. Это следует из аксиом евклидовой геометрии.
А теперь рассмотрим, как производится доказательство шага индукции в описанном Вами (Ильей Весенним) примере:
1)Сначала формулируется одна гиппотеза(правильная): "По предположению индукции через k точек M1, M2, ..., Mk проходит некоторая прямая"
2)А потом формулируется вторая гиппотеза (неправильная; хотя автор и пытается сказать, что это одно и то же что и превая гиппотеза, но это не так. Потому что туда включается k+1-ый объект для которого все еще надо доказать): "Но (по тому же предположению) через k точек M2, ..., Mk, Mk+1 также проходит некоторая прямая"
3)Далее следует попытка сказать, что все исследуемые объекты обладают доказываемым свойством, так как им обладают объекты из гиппотезы 1 и объекты из гиппотезы 2(и вообще у них много общего :-)):"Но две точки определяют единственную прямую. Поэтому обе прямые должны совпадать."
Аналогиченые этапы доказательства можно выделить и в задаче про лиловых лошадей, а следовательно там содержится та же ошибка. А теперь давайте рассмотрим какая именно ошибка.
Главная ошибка в приведенном доказательстве шага математической индукции заключается в том, что автор не фиксирует для каких объектов можно применять предположение, а для каких нельзя. При правильном доказательстве индукционного шага мы предплагаем, что доказываемое свойство верно для k предшествующих объектов (что и составляет гиппотезу индукционного шага) и пытаемся доказать, что k+1-ый объект удовлетворяет этому же свойству. Таким образом, в доказательстве автора не правильно сформулирована гиппотеза индукционного шага, а правильной будет такая гиппотеза: "По предположению индукции через первые k точек M1, M2, ..., Mk проходит некоторая прямая". Поэтому распространять гиппотезу на объекты 2..k+1 (в данном случае точки M2, ..., Mk, Mk+1) нельзя и соответсвенно данная "теорема" не может быть доказана.
Худоба Евгений, если бы гипотеза формулировалась как «для первых k элементов такого-то нумерованного множества верно это утверждение», то Ваше возражение имело бы смысл. Более того, Вы можете так сформировать своё доказательство того, что через любые n вершин проходит прямая. И тогда в Вашем доказательстве будет та проблема, о которой Вы пишете.
ОтветитьУдалитьОднако гипотеза в предложенных выше доказательствах-упражнениях гласит «Допустим, что теорема верна при некотором n=k». Мы здесь не говорим для каких именно элементов. Поэтому Ваше указание на проблему не относится к этим доказательствам. А настоящая ошибка именно в том, что невозможно доказать первый шаг индукции.
Об этом я и хотел сказать в своем первом комментарии. Конкретно для этих задач можно сказать, что доказательство неверно, так как не подходит под доказательство первый шаг индукции. Но как мне кажется, это не единственная ошибка в приведенном доказательстве. Для того чтобы понять это, я предлагаю в эту задачу добавить небольшое условие, которое устраняет несоответствие первого шага индукции доказательству, но при этом все равно доказываемая теорема остается абсурдной. Итак, условие теоремы: через любые n точек можно провести прямую, если хотя бы 3 из них лежат на 1-ой прямой.
ОтветитьУдалитьДоказательство:
База индукции смещается до k=3 и истинна по условию теоремы.
А доказательство индукционного шага один в один копируется у вас :-) :"Допустим, что теорема верна при некотором n=k. Покажем, что в этом случае она будет сохранять силу и при n=k+1.
Итак, пусть произвольно заданы k+1 точек M1, M2, ..., Mk, Mk+1. По предположению индукции через k точек M1, M2, ..., Mk проходит некоторая прямая. Но (по тому же предположению) через k точек M2, ..., Mk, Mk+1 также проходит некоторая прямая. И эти две прямые имеют по крайней мере две общие точки M2 и Mk. Но две точки определяют единственную прямую. Поэтому обе прямые должны совпадать.
Следовательно, прямая, проходящая через точки M1, M2, ..., Mk, проходит и через точку Mk+1. Утверждение доказано".
Теперь при первом индукционном шаге k+1=4 (для k=3 верно по условию задачи - база индукции), а следовательно через точки M2 и М3 проходит только одна прямая, которая по предположению (см. доказательство) должна проходить и через все остальные точки. Первый шаг индукции доказан. Тогда в чем же тут ошибка?
Худоба Евгений, "Допустим, что теорема верна при некотором n=k." значит в точности "если в наборе из k точек три лежат на одной прямой то и все они лежат на одной прямой."
ОтветитьУдалитьИтак, пусть произвольно заданы k+1 точек M1, M2, ..., Mk, Mk+1.
Можно добавить: "Пусть три из них на одной прямой".
По предположению индукции через k точек M1, M2, ..., Mk проходит некоторая прямая.
только если в этом наборе те самые три точки на прямой
Но (по тому же предположению) через k точек M2, ..., Mk, Mk+1 также проходит некоторая прямая.
Чтоб это утверждать те самые три точки на прямой должны быть из M2, ..., Mk.
Но вот незадача, при k=3 в множестве {M2, ... , Mk} всего две точки.
Значит индукцией можно пользоваться только если есть доказательство для k=4.
Наш преподаватель по ДифУрам приводил похожую задачку (он тогда бородатый ходил) - доказывал, что все преподаватели дифУров бородаты.
ОтветитьУдалить1. база n=1 - Я сам бородат
n=2 Мой коллега тоже бородат (это было так).
Дальнейшее доказательство схоже с вашим.
И да, ошибка была в базе - для корректной базы нужно было доказать, что ЛЮБЫЕ 2 преподавателя дифуров бородаты - в вашем случае что любые 2 случайно взятые лошади окажутся лиловыми.
Антон, действительно возможно я посl7;ешил немного. Гиппотеза шага математической индукции там должна звучать так:"Предположим, что через k произвольных точек можно провести прямую".
ОтветитьУдалитьСаХаР, по вашему ходу мыслей нужно также в базе индукции доказать, что любой 1 (а правильней сказать каждый) преподаватель дифуров бородат. А зачем же тогда нужны все остальные нагромождения про шаг индукции?
Для приведённых задач все условия МИ соблюдены - база очевидна (при к=1) и переход из к в к+1 доказан.
ОтветитьУдалитьЧётко понимаю, что в доказательстве есть разрыв (для лошадей при к=2, для линий при к=3), и поэтому доказательство неверны, однако эти разрывы они очевидны, но что делать если у нас стоит задача, в которой разрыв не столь очевиден, но всё же есть при некотором большим значении к? Как определить не имея очевидных разрывов, что метод МИ применим для решения задачи?
Уважаемый аноним, ответ на Ваш вопрос простой - надо внимательно проверять корректность своих действий.
ОтветитьУдалитьВы пишете, что "переход из к в к+1 доказан", но это неверно. Правильно было бы так: "для k>2 переход из к в к+1 доказан" (так написал бы математик, делающий соответствующие выкладки). И это не позволило бы ему некорректно применять МИ.
То есть, хитрость состоит в том, что считать доказанными можно только то, что доказано, а не то, что кажется очевидным :)
Вот зараза! Я только сейчас понял где здесь ошибка! А прошло почти два месяца с момента прочтения мной этой статьи. Прочитал, подумал, так как в голове была аксиома "я знаю матиндукцию" (ведь в 11ом классе у меня был отличнейший курс элементарной математики под руководством уважаемого мной Русакова Сан Саныча), подумал, что дело в определении стада, пропустил комменты и эта задача ушла в небытие до сего дня. А сегодня рассказав за завтраком эту задачу жене, понял где собака вела земляные работы! Как неоднократно написано в комментах, что второй пункт доказательства не верен, в силу того, что мы не можем доказать для ЛЮБОГО k верность преобразования "Если при n = k верно, то верно и при n = k + 1". Ведь предложенный способ не работает при k = 1. Ух! Спасибо большое за задачу! В который раз убеждаюсь, что нужно подвергать сомнению не только "внешнюю" информацию, но и "внутреннюю" - в ней много хлама принятого по молодости за факт.
ОтветитьУдалитьyku, спасибо за такой позитивный отзыв! Вы правы, такие задачки стоит разбирать именно ради такого перепада ощущений: от "всё понимаю" до "не понимаю, что тут сложного" и обратно :)
ОтветитьУдалитьИ все-таки мне интересно узнать, разве вообще можно доказывать теоремы методом мат. индукции применяя предположение мат. индукции к двум разным множествам?Для того, чтобы того чтобы объяснить, что я имею в виду, я постараюсь предельно ясно и последовательно провести доказательство указанной мной ранее задачи.
ОтветитьУдалитьЗадача:
Доказать, что n точек лежат на одной прямой, если хотя бы 3 из них лежат на одной прямой.
Доказательство:
База индукции: при n <= 3 доказательство очевидно (1 и 2 - аксеомы геометрии, 3 - условие задачи).
Предоположение:Допустим, что через k точек можно провести прямую, при k >= 3. Покажем, что в этом случае она будет сохранять силу и при n=k+1.
Замечание: предположить можно все что угодно, даже то, что на Луне живет k зеленых человечков. Главное чтобы это предположение в итоге помогло доказать требуемое свойство.
Итак, пусть произвольно заданы k+1 точек M1, M2, ..., Mk, Mk+1 и 3 из них лежат на одной прямой. По предположению индукции через k точек M1, M2, ..., Mk проходит некоторая прямая. Но (по тому же предположению) через k точек M2, ..., Mk, Mk+1 также проходит некоторая прямая. И эти две прямые имеют по крайней мере две общие точки M2 и Mk. Но две точки определяют единственную прямую. Поэтому обе прямые должны совпадать.
Следовательно, прямая, проходящая через точки M1, M2, ..., Mk, проходит и через точку Mk+1. Утверждение доказано.
Замечание1: да действительно при k=3, либо точки М1...М3 лежат на одной прямой, либо точки М2...М4, и необязательно четвертая точка будет лежать на той же прямой. НО ведь есть предположение мат. индукции для k произвольных точек, после применения которого к разным множествам точек идет вполне логичное доказательство необходимого свойства для k+1, и по-этому мы должны верить в истинность предоположения.
P.S. приводя это доказательство еще раз я хочу сказать, что то замечание, которое высказал Антон указывает, только на то, что при k=3 в доказательстве есть какая-то ошибка. Но какая именно ошибка в применении алогоритма мат. индукции делает доказательство неверным Антон не указывает. А мне именно это хотелось бы выяснить.
Худоба Евгений, рассмотрим доказательство шага для k=3. Скопоипастил Ваше и заменил буквы на цифры.
ОтветитьУдалитьИтак, пусть произвольно заданы 4 точек M1, M2, M3, M4 и 3 из них лежат на одной прямой. (Какие 3. Ну перенумеруем пусть М1,М2,М3) По предположению индукции через 3 точки M1, M2, M3 проходит некоторая прямая. (Согласен) Но (по тому же предположению) через k точек M2, M3, M4 также проходит некоторая прямая. (Ошибка) И эти две прямые имеют по крайней мере две общие точки M2 и M3. Но две точки определяют единственную прямую. Поэтому обе прямые должны совпадать.
Доказывать шаг надо аккуратно. И все проблемы исчезнут.
Антон, перечитайте пожалуйста внимательнее замечание1 в мое предыдущем комментарии. Там я сам указываю на эту ошибку, потому, что она очевидна. Но также очевидно, что есть ошибка в применении алгоритма мат. индукции. Так вот какае из действий(доказательство базы индукции; формурирование предположения для k элементов; используя предположение для k элементов доказать для k+1 элементов) именно с позиции алгоритма мат. индукции я выполнил не корректно, что привело к указанной ошибке. И самый интересный вопрос для меня почему данное действие для алгоритма мат. индукции является не корректным.
ОтветитьУдалитьХудоба Евгений, в математике любая ошибка в рассуждении делает его некорректным. Так что для доказательства неправомерности доказательства хватит и одной.
ОтветитьУдалитьВ мат. индукции надо доказать:
1. Базу (Утверждение P(0) истинно)
2. Доказать шаг(Утверждение P(k+1) истинно если P(k) - истина. P(k)=>P(k+1) для всех k = 0,1,2, ...)
В Вашем примере не верно доказательство шага.
Сформулируем гипотезу P(k) = {"Если в наборе из к точек, три лежат на одной прямой, то все они лежат на одной прямой"}.
Попробуем доказать шаг.
Берем набор из k+1 (k>=3) точки, M1, ... , Mk+1, такие что три из них лежат на одной прямой (М1, М2, М3). Докажем, что все они на одной прямой.
Отбросим точку Мк+1.
По гипотезе: М1, ... , Мк - на одной прямой.
А вот с отбрасыванием М1 проблема. В наборе M2,...,Mk+1 есть 3 точки на одной прямой только для к>=4. А ведь только тогда можно применить гипотезу P(k).
То есть шаг мы доказали для k>=4.
А базу для k=3. Вот если-бы база была для к=4 - тогда доказательство было-бы корректным.
Антон, благодарю за такие оперативные и выверенные ответы! :)
ОтветитьУдалитьХудоба Евгений, надеюсь, теперь Вы разобрались с этой тонкостью метода математической индукции. Если у Вас ещё остались вопросы, то прочитайте, пожалуйста, статью Знакомство с методом математической индукции. В ней разобрано несколько интересных примеров, которые должны рассеять Ваши сомнения.
Если после этого вопросы останутся, то прошу их кратко сформулировать, я постараюсь подсказать.
На Ваш первый вопрос «разве вообще можно доказывать теоремы методом мат. индукции применяя предположение мат. индукции к двум разным множествам?» ответ такой: «почему бы и нет?»
Метод математической индукции оперирует не с разными или одинаковыми множествами, а с утверждениях f(n).
Школьники часто возражают по поводу этого "доказательства" о совпадении цветов лошадей так: «А разве можно применять метод математической индукции к лошадям?»
Ваш вопрос о разных множествах очень похож. Применять метод можно, если делать это правильно (т.е., соблюдая правила). Удачи!
Антон, а почему вы все время хотите изменить мою гипотезу? Ведь ваша гипотеза приводит к ошибке в дальнейшем доказательстве, а моя не приводит.
ОтветитьУдалитьХудоба Евгений, не понял.
ОтветитьУдалитьВы пишете
Предоположение: Допустим, что через k точек можно провести прямую, при k >= 3.
Но откуда оно? Если из индукции, то в нем не хватает "... если три из них лежат на одной прямой."
Если с потолка, то результатом всего доказательства будет "Если предположение верно, то утверждение доказано".
Антон, а почему бы и не "с потолка"?
ОтветитьУдалитьЯ всегда считал, что, если используя предположение относительно k элементов и строгие математические преобразования нам удалось доказать истинность свойства для k+1 элементов, то мы угадали и данные объекты обладают указанным свойством. Разве не так?
В данном случае, на шаге2 мы доказываем более общее утверждение, чем нам требуется, но так как нам еще необходимо, чтобы выполнялась база индукции, то в конечном итоге мы накладываем на предположение ограничение "... если три из них лежат на одной прямой" и получается требуемое свойство.
Худоба Евгений, сначала мат. логика, а конкретно оператор =>. Таблица истинности:
ОтветитьУдалитьA|B|A=>B
0|0|1
0|1|1
1|0|0
1|1|1
Теперь по-русски. A-гипотеза. B-утверждение. A=>B - доказательство. Если оно математически верное (A=>B)=1.
Смотрим в таблицу:
строки 1,2: Если используя неверную гипотезу можно построить доказательство, утверждение может быть как истинным так и ложным.
строки 2,4: Если используя гипотезу удалось построить доказательство заведомо верного утверждения, то гипотеза как верной, так и не верной.
строка 1: Если используя гипотезу удалось построить доказательство заведомо неверного утверждения - то гипотеза не верна (доказательство от противного).
Ctrl+v
если используя предположение относительно k элементов и строгие математические преобразования нам удалось доказать истинность свойства для k+1 элементов, то мы угадали и данные объекты обладают указанным свойством.
Только если есть база. У Вас базы нет. Ну она есть для более узкого утверждения. А значит на шаге индукции можно пользоваться только им, только оно доказано на предыдущем шаге индукции и может использоваться как верное.
Сущность метода математической индукции заключается в следующем.
ОтветитьУдалитьЕсли мы имеем гипотезу H1, которая выполняется для всех k от k0 до k1 включительно (k0 и k1 фиксированы и вполне конкретны), и мы имеем корректный переход от произвольного k до k+1, k > k1 в предположении, что для всех k утверждение гипотезы верно (т.е. гипотеза верна от k1+1 до k) А ТАКЖЕ мы имеем корректный переход от k=k1 до k=k1+1, то очевидно гипотеза H1 выполняется для произвольного k >= k0.
Вся тонкость содержится после слов А ТАКЖЕ.
Теперь перейдем к конкретным примерам.
Пример 1.
Если в качестве рабочей гипотезы принять, что в стаде из одной лошади сохраняется единый цвет (это очевидно верно), то если мы докажем, что в стаде из k+1 лошади сохраняется цвет на основании того, что в стаде из k лошадей одинаков цвет (это тоже вполне очевидно для k>=2, здесь k1=1, k > k1) А ТАКЖЕ что в стаде из двух лошадей одинаков цвет (здесь нет никакой уверенности), то мы докажем что в стаде из произвольного числа лошадей одинаков цвет. Если есть доказательство что в стаде из двух лошадей одинаков цвет - чтож, получается что в любом стаде одинаковый цвет у всех лошадей, но есть ли такое доказательство? Если такого доказательства нет, то метод матиндукции не может нам сказать ничего определенного.
Т.е. при доказательстве методом матиндукции очень важно совершить первый шаг (можно первые несколько шагов для пущей уверенности, посчитав их вручную), пока не распространяясь на общий случай. Если этот шаг верный, то тогда рассматриваем более общий случай.
Пример 2.
Если в качестве рабочей гипотезы H1 принять, что в любом стаде из одной или двух лошадей сохраняется единый цвет, то вполне корректно можно доказать, что в любом стаде из произвольного количества лошадей > 1 сохраняется единый цвет, но верна ли исходная гипотеза H1?
Уважаемый аноним, спасибо, что нашли время чётко это записать.
ОтветитьУдалитьПункт 2)(шаг индукции) особенно радостно разбирать на примере стада из 2-х лошадей: белой и черной.
ОтветитьУдалитьУважаемый аноним,
ОтветитьУдалитьсовершенно верно, для случая с двумя лошадьми доказательства нет.
Ну вы блин даёте!!))) класс прочитал статью потом один комент = интересный, второй = интересный...
ОтветитьУдалитьСпрашивается все ли коменты интересно прочитать?
условие 1) комент №1 -интересный n=1
условие 2) комент №1 и комент №2 одной темы
если условие 2 выполняется n=2 той же темы что и n=1 то n=2 комент интересный, вторая ступенька!
если до n=k условие 2 выполнялось то n=k коментов тоже интересны, мы начинаем с определения свойства сложного(интерес к всем комментариям) которое нас интересует, далее находим простое (первый интересный комент в произвольном множестве) с тем свойством которе нас интересует, усложняем простое до второй ступеньки(следующий комент, можно перебрать несколько, пока не найдём нужный) находим условие при котром свойство сохранилось (одна тема).
осталось только сложное разобрать до простого (проверить полностью прочитав текст всех коментов долго) по пути в котором сохраняется условие(проверка темы) и если тема хоть в одном коменте не совпала то и сложное отнести к интересному нельзя! В противоположном случае мы приходим к простому (произвольный комент, но один) который мы точно знаем что интересный. отсюда следует что сложное имеет тоже свойство (все коменты интересны) что и простое!(но я проверил наверняка прочитав все коменты!!!)))
"классическая дилемма при изучении неизвестных явлений: чтобы явления чётко разграничить надо знать причинный механизм, а чтоб познать причинный механизм, надо чётко разграничить явления" Станислав Лем (писатель, фантаст и не только.)
тоесть чтобы доказать принадлежит ли область (128х128)-1 к областям которую можно закрасить триминошками ми должны разграничить области на те которые можно закрасить и те которые нельзя (чуть выше эту роль играли множества с интересными комментариями и не интересными).
для этого мы должны знать причинный механизм который мы устанавливаем на простом:
-опытным путём (Вручную, в уме, итп.) - мы получили первую область в которую можно закрасить триминошками (триминошка должна состоять из 4 других триминошок).
-Далее усложняем, и находим закономерность(причинный механизм, триминошка должна состоять из 4 других триминошок (первого условия)) при которой свойство закрашивания сохраняется!
причинный механизм для получения нужных областей найден, а также теперь есть два условия:
-1 триминошками можно закрасить триминошку из 4других триминошок
((8х8-1) можно закрасить5х(2х2-1))
-2 фигура должна выглядеть как 8х8-1 " триминошка" и при этом сохраняется условие 1.
и мы можем проверять всё следующие множества тем что раскладывать сложное до простого, а если мы приходим к тому что свойство у простого присутствует, а мы двигались от сложного к простому по пути (деление на 4 минус 1 квадрат) при котором свойство нас интересующее (первое условие) сохраняется, и пришли к простому n=1 у которого присутствует свойство (закрашивания триминошками) то мы с уверенностью можем сказать что это свойство присутствует и у сложного!
одно действие, но в цикле "проверка условия перехода с сохранением начального условия". Которое установленно на простом, а используется для сворачивания сложного до интересуещего нас простого! Хотя я могу и ошибаться!!)
>Если убрать из него одну лошадь, то получим стадо из k-1 лошади (а про него мы уже всё знаем - в нём все лошади одного цвета). Вернём ту лошадь обратно, но уберём другую - опять получим стадо из k-1 лошади (и в нём опять все лошади одного цвета по предположению индукции).
ОтветитьУдалить>Это означает, что все k лошадей были одного цвета.
Нет, не означает.
Здорово, что Вы нашли время, чтобы так кратко рассказать о том, что разобрались в этой задачке.
УдалитьГде я только не встречал подобного ошибочного рассуждения про лошадей!
ОтветитьУдалитьПриведу, как пример, еще одно, тоже известное:
Докажем, что произвольное число точек лежат на одной прямой:
при n=1;n=2 -- очевидно
Переход(n=>n+1): Выберем первые n точек по предположению индукции они образуют прямую, теперь выберем все точки, кроме первой, они тоже образуют прямую. Значит и n+1 точка лежит на этой прямой. Переход доказан!
p.s. Комментарии не читал.
p.p.s. Знаю, что ошибку замаскировать не поучилось)
Исходя из: пусть мы знаем, что если в стаде k-1 лошадь, то все лошади в нём одного цвета.
ОтветитьУдалитьТут лишь один правильный ответ может быть: Лошади меняют цвет когда скучают по одной из своего стада.