2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Строгость доказательства.
Сообщение02.04.2017, 19:16 


03/03/16
7
Вот история о том, как самая первая задача из книжки "Как решают нестандартные задачи" Канель-Белова и Ковальджи привела меня к кризису:

"В угловой клетке таблицы 5 х 5 стоит плюс, а в остальных клетках стоят минусы. Разрешается в любой строке или любом столбце поменять все знаки на противоположные. Можно ли за несколько таких операций сделать все знаки плюсами?"

Задача легкая, однако следующие задачи(в частности, в главе о причесывании задач: одна про точки на плоскости, которые игроки соединяют отрезками и другая про длину суммы векторов для точки, находящейся внутри многогранника) заставили меня задуматься о строгости моих решений. Из-за этого я решил вернуться снова к первой задаче про таблицу и строго ее доказать.

В общем, мне нужна ваша помощь, я не знаю, что делать со строгостью решения в таких задачах.
Эти задачи как бы не полностью внутри математики находятся. Должен я как-то преобразовывать, переводить условие задачи на язык математики, чтобы у меня была строгость или вводить какие-то свои аксиомы и из них выводить доказательство.
Проблема в том, что любой из этих способов строго доказать задачу в тыщу миллиардов раз сложнее чем ее решить(и это не только к этой задаче относится).

Подскажите как быть в общем со строгостью решений, можете на примере этой задачи объяснить.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 19:21 
Заслуженный участник
Аватара пользователя


09/02/14

1377
Я бы руководствовался формулой: "Доказательство - это рассуждение, которое убеждает вас настолько, что вы готовы убеждать этим рассуждением других", как оно на практике в большинстве случаев и делается.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 19:30 


19/05/10

3940
Россия
famesyasd, а где ваше то, которое нестрогое, решение этой задачи?

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 19:33 
Заслуженный участник


11/05/08
32166
famesyasd в сообщении #1205993 писал(а):
Из-за этого я решил вернуться снова к первой задаче про таблицу и строго ее доказать.

В общем, мне нужна ваша помощь, я не знаю, что делать со строгостью решения в таких задачах.

Трудно помочь, если непонятны затруднения. Как вы решали первую задачу -- и в чём видите нестрогость того решения?

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 19:52 
Заслуженный участник


27/04/09
28128
famesyasd в сообщении #1205993 писал(а):
Проблема в том, что любой из этих способов строго доказать задачу в тыщу миллиардов раз сложнее чем ее решить(и это не только к этой задаче относится).
Ой да ладно в тыщу! Никто же вас не заставляет отправляться от аксиом ZFC или арифметики. И формализуется задача просто: есть множество знаков $S = \{{+},{-}\}$ и операция смены знака $z\colon S\to S$, $z({+}) = {-}, z({-}) = {+}$; есть какое-то пятиэлементное множество индексов строки/столбца $I$ (например, $I = 1..5$, но конкретный вид вряд ли где-то понадобится) и какой-то конкретный его элемент $i_0$; есть множество состояний доски $B = I^2\to S$. Вначале доска имеет состояние $b_0$, $b_0(i, j) = (i = j = i_0)\mathbin? {+} : {-}$, возможные операции над доской — это $r_i, c_i, i\in I$, где $r_k(b)(i, j) = ((i = k)\mathbin? z : \mathrm{id})b(i, j)$, $c_k(b)(i, j) = r_k(b)(j, i)$. Множество достижимых состояний доски можно определять по-всякому. Можно определить отношение достижимости за одну операцию и потом взять транзитивное замыкание (и рефлексивное, но тут это ничего не даст), можно определить всевозможные состояния или допустимые последовательности операций индуктивно. И так далее. Вопрос формализовать получится. Готовое решение формализовать тоже должно получиться, и вот где у вас загвоздка, про то и напишите. (Если вам нужна именно предложенная формализация. Так-то я присоединяюсь к трём предыдущим постам.)

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 20:21 
Заслуженный участник
Аватара пользователя


30/01/06
72407
famesyasd в сообщении #1205993 писал(а):
Эти задачи как бы не полностью внутри математики находятся.

Не понял, а почему?

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 20:27 


03/03/16
7
Это по сути черновик еще незаконченного доказательство, я в нем уже много раз убирал и переписывал целые абзацы, так что оно не слишком понятно может быть.

Операция для меня работает так: выбираем сначала ровно одно множество из множества строк и столбцов, а затем выбираем любой соответствующий элемент в выбранном множестве и меняем его знаки на противоположные.

I.Рассмотрим то же условие, но для таблицы размера 2x2(Я буду ее еще называть маленькой таблицей).(Я хочу доказать утверждение для таблицы 2х2 сначала, а потом 5х5 свести к случаю таблицы 2х2)

Всего вариантов применения операции к этой маленькой таблице 4. (Мы можем ее применить к первой строке, второй строке, первому столбцу, второму столбцу). Больше вариантов не имеется.

В самом деле, если бы существовал хотя бы один вариант, отличный от наших четырех,то по условию выбирали бы мы его так: сначала выбираем множество строк или столбцов. Пусть мы выбрали множество строк. По предположению вариант должен отличаться от первой и второй строки, т.е. иметь хотя бы номер отличный от первых двух строк, а так как нумерация строк начинается с единицы, то его номер должен быть больше двух, т.е. в нашей таблице 2х2 содержится строка, номер которой больше двух,т.е. в ней получается больше двух строк, но по определению понятия таблицы 2х2 такого быть не может, значит противоречие), значит он может быть только столбцом, но по той же причине им он тоже быть не может, значит все доказано.

Теперь строим всевозможные варианты расположения плюсов и минусов в нашей маленькой таблице.См. рисунок.(Не знаю как его прикрепить). Отсюда получается, (это как бы экспериментальный факт, я не доказывал это теоретически, просто вот так получилось) что применяя любую операцию к любому из существующих на рисунке вариантов мы получаем снова один из них же.(Стоит заметить, что среди этих вариантов содержатся 4 начальных позиции,(это те,когда плюс в одном из углов таблички)). Значит других вариантов, кроме этих не существует.

Действительно, если бы существовал вариант отличный от них, то он должен был бы отличаться и от начальных позиций, а значит мы должны к нему придти через последовательность операций, начиная с одной из начальных позиций. Рассмотрим эту последовательность, Начиная с самого начала мы из любой начальной позиции, применяя любой вариант операции можем получить лишь один из уже существующих вариантов расположения плюсов и минусов(это из-за экспериментального факта), далее применяя к полученному варианту любую операцию(в том числе ту, которая в последовательности) мы снова получим один из уже существующих вариантов(эксп. факт). И далее, из-за этого экспериментального факта на каждом следующем шаге у нас будет получаться один из уже существующих вариантов, в том числе на последнем шаге тоже будет один из них же. Однако, мы предполагали, что вариант полученный на последнем шаге будет от них отличаться. Противоречие.

Отсюда следует, что не существует такой последовательности операций, в результате которой все знаки стали бы плюсами. Так как на каждом ее шаге будет один из возможных вариантов, которые мы открыли, в том числе и последний. Но ни один из этих вариантов не является искомым(тем у которого все знаки - плюсы).

Таким образом, мы доказали, что не существует такой последовательности операций в маленькой таблице в результате которых все знаки в ней становятся плюсами.

II Тот угол в большой таблице, в котором находится плюс, окаймляем соответствующей маленькой 2х2 таблицей. Теперь доказываем от противного: если существует последовательность действий, делающая все знаки в таблице плюсами, то она также должна делать все знаки плюсами и в маленькой угловой таблице 2x2(Иначе в маленькой не все знаки стали плюсами, т.е. (из условия следует?) существует хотя бы один знак минус, но так как минус содержится в маленькой таблице, а она сама в большой, то(транзитивность?) минус содержится и в большой таблице, противоречие).
(Здесь так сразу нельзя сказать, то что такой последовательности по доказанному в первом пункте быть не может, потому что там это было доказано про последовательности "длины 2", а здесь длины 5, поэтому ее надо заменить на последовательность длины 2, обладающей тем же конечным эффектом).

В нашей предполагаемой последовательности шаги делятся на два типа: которые влияют на расположение знаков в таблице 2х2 и которые не влияют(Закон исключенного третьего). Докажем, что нашу последовательность можно заменить другой, без шагов второго типа. Действительно, идем по порядку предполагаемой последовательности, пока не встретим шаг первого типа все будет оставаться на своих местах, после шага первого типа зафиксируем изменения в маленькой таблице и двинемся дальше)Надо как-то получше сформулировать этот пункт). До встречи со следующим шагом второго типа все будет таким же как и раньше. После чего снова изменение фиксируем и двигаемся дальше, таким образом,соответствующая ей последовательность без шагов второго типа имеет тот же конечный эффект(результат), что и наша первая последовательность.
Далее новую последовательность аналогично заменяем такой же по эффекту последовательностью с обрубленными хвостами. Таким образом, получается существует последовательность маленьких шагов в результате которой тот же эффект, что и у второй, а значит тот же эффект, что и у первой, но по выводу из первого пункта эта последовательность точно не может сделать все знаки плюсами, а значит этого не может сделать и наша предполагаемая. Ч.т.д.

Но здесь еще все равно до кучи мест, где можно поставить знаки вопроса

-- 02.04.2017, 21:40 --

Munin в сообщении #1206023 писал(а):
famesyasd в сообщении #1205993 писал(а):
Эти задачи как бы не полностью внутри математики находятся.

Не понял, а почему?


Сам не могу толком понять, эти задачи что ли требуют какого очень сложного дополнительного перевода на язык строгости?
вот например другая задача, из той же книжки:

"В кладовой лежат 300 сапог: 100 хромовых, 100 кирзовых и 100 яловых, причём левых и правых поровну | по 150.
Докажите, что из имеющихся сапог можно составить по крайней мере 50 пар."

И вот мое решение:
Исходные обозначение: x-числа левых хромовых сапог, y-число левых кирзвоых сапог,z-число левых яловых сапог, z'-число правых яловых сапог.

Возьмем произвольные x,y,z удовлетворяющие условиям задачи. Без ограничения общности можно считать, что z>z',в противном случае поменяем местами буквы для левых и правых яловых сапог, и z=/=z', так иначе z=50, и это удовлетворяет условию задачи при любых x и y. Пусть число пар сапог образованных этими числами равно N.

Теперь перекинем один сапог из z в x или y. Так как z>50 число пар яловых сапог увеличится на 1, а число пар образованных x или y либо уменьшится на 1, либо увеличится на 1, таким образом общее число пар N точно не уменьшится, далее будем перекидывать z в x или y пока z не станет равным 50, но N по доказанному у нас на каждом шаге не убывало, и потому N>=50. И это, повторюсь, было для произвольных x,y,z. Следовательно из имеющихся пар сапог действительно можно составить не менее 50 пар.

И там, и там надо доказать; и там, в формулировке не чисто математические термины, и я придерживаюсь принципа: Доказательство - это рассуждение, которое убеждает вас настолько, что вы готовы убеждать этим рассуждением других", но почему-то решение этой задачи меня абсолютно не гложет, в отличие от задачи про таблички.

Просто вот так получается, что обе задачи в плане решения простые, но в задаче про сапоги строгость сама по себе получается, а в табличках аспект строгости в тыщу раз сложнее решения задачи.

-- 02.04.2017, 21:48 --

mihailm в сообщении #1205998 писал(а):
famesyasd, а где ваше то, которое нестрогое, решение этой задачи?

То, которое я выше написал, это над которым я долго думал, а изначально, у меня было практически авторское решение:

Рассмотрим таблицу 2х2, здесь я перебираю варианты таким образом:в силу соображений симметрии можно считать, что плюс находится в левом верхнем углу, если операция касается плюсика, то он перемещается в другой угол, иначе она меняется линию минусиков и они становятся плюсами и получается ситуация, когда у нас один минус в углу, а все остальные клетки плюсики, т.е. суть ситуация, когда плюс в углу и все остальные минусы. Значит, в 2х2 все знаки плюсами сделать невозможно, а так как большая таблица содержит эту маленькую, то в ней тем более.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 20:54 
Заслуженный участник
Аватара пользователя


30/01/06
72407
famesyasd в сообщении #1206028 писал(а):
Всего вариантов применения операции к этой маленькой таблице 4. (Мы можем ее применить к первой строке, второй строке, первому столбцу, второму столбцу). Больше вариантов не имеется. В самом деле...

Это дальше разжёвывать не надо.

famesyasd в сообщении #1206028 писал(а):
Отсюда получается, (это как бы экспериментальный факт, я не доказывал это теоретически, просто вот так получилось)

А вот это как раз надо доказать. То есть, обосновать логически, почему так получается. Для тех, кто ваших экспериментов не видел, или кто им не доверяет.

Впрочем, можно решить задачу полным перебором. Но это "плохое" решение, некачественное. Надо искать красивое, основанное на глубоких принципах.

famesyasd в сообщении #1206028 писал(а):
Тот угол в большой таблице, в котором находится плюс, окаймляем соответствующей маленькой 2х2 таблицей.

Идея доказательства ясная и красивая. А дальше опять идут излишние разжёвывания.

famesyasd в сообщении #1206028 писал(а):
Докажем, что нашу последовательность можно заменить другой, без шагов второго типа.

Не сказано, в каком смысле заменить.

-- 02.04.2017 20:57:59 --

famesyasd в сообщении #1206028 писал(а):
Сам не могу толком понять, эти задачи что ли требуют какого очень сложного дополнительного перевода на язык строгости?

Задача про плюсы и минусы - вообще никакого перевода не требует. Она и так уже целиком внутри математики. Поэтому и удивительно то, что вы говорите.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 20:59 


03/03/16
7
arseniiv в сообщении #1206011 писал(а):
famesyasd в сообщении #1205993 писал(а):
Проблема в том, что любой из этих способов строго доказать задачу в тыщу миллиардов раз сложнее чем ее решить(и это не только к этой задаче относится).
Ой да ладно в тыщу!

Да, я думал переводить условие на язык чистой математики, просто я не вижу есть ли в этом смысл, так как не знаю какие утверждения про функции или еще какие-то математические конструкции помогут мне в решении этой задачи.

-- 02.04.2017, 22:14 --

Munin в сообщении #1206035 писал(а):
famesyasd в сообщении #1206028 писал(а):
Всего вариантов применения операции к этой маленькой таблице 4. (Мы можем ее применить к первой строке, второй строке, первому столбцу, второму столбцу). Больше вариантов не имеется. В самом деле...

Это дальше разжёвывать не надо.
На самом деле я здесь даже урезал много:) Здесь все дело в том, что как только я решил строго доказать задачу, я начал критически относиться вообще к любым вещам в моем доказательстве. В том числе и к тому, почему я могу утверждать, что вариантов ровно 4.

famesyasd в сообщении #1206028 писал(а):
Докажем, что нашу последовательность можно заменить другой, без шагов второго типа.

Не сказано, в каком смысле заменить.
Я ее хочу заменить последовательностью, у которой конечный результат такой же как и моей предполагаемой(в таблице все знаки плюсы), но которая будет подходить еще и под условия доказанного в первом пункте.
-- 02.04.2017 20:57:59 --

famesyasd в сообщении #1206028 писал(а):
Сам не могу толком понять, эти задачи что ли требуют какого очень сложного дополнительного перевода на язык строгости?

Задача про плюсы и минусы - вообще никакого перевода не требует. Она и так уже целиком внутри математики. Поэтому и удивительно то, что вы говорите.
Ну эта задача требует совершенно другого подхода, в отличие от задачи про сапоги. В сапогах уже достаточно только логики. А в табличках чисто логики почему-то не хватает, а может и хватает, но гораздо сложнее все. Вот например, решение сапогов это мое чисто интуитивное, первоначальное.. А в табличках мне пришлось, практически все первоначальное интуитивное решение перекроить и построить другое.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 21:37 
Заслуженный участник


27/04/09
28128
famesyasd в сообщении #1206036 писал(а):
Да, я думал переводить условие на язык чистой математики, просто я не вижу есть ли в этом смысл, так как не знаю какие утверждения про функции или еще какие-то математические конструкции помогут мне в решении этой задачи.
Ну, я тоже не вижу, зачем вот так формализовать, но по крайней мере это весьма легко делается. В один заход.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение02.04.2017, 22:00 


19/05/10

3940
Россия
Если первую(!) задачу с приведенным там же решением (!!!) не получается понять, нафига спрашивается вообще эту книгу открывать??? Эта книга очень жесткая и без значительного предварительного опыта (или тренера) открывать ее нету никакого смысла.

 Профиль  
                  
 
 Posted automatically
Сообщение03.04.2017, 07:47 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Беседы на околонаучные темы»
Причина переноса: в соответствующий раздел

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение03.04.2017, 13:08 


03/03/16
7
mihailm в сообщении #1206046 писал(а):
Если первую(!) задачу с приведенным там же решением (!!!) не получается понять, нафига спрашивается вообще эту книгу открывать??? Эта книга очень жесткая и без значительного предварительного опыта (или тренера) открывать ее нету никакого смысла.


Да нет, решения самих задач мне доступны и вообще мне эта книжка очень нравится, только суть в том, (я сейчас еще поясню примерами), что в ней задачи как будто делятся на два типа. Одни решать по кайфу и когда оглядываешься на свое решение прям радуешься какое оно красивое и строгое, а другие решать тоже по кайфу, но когда смотришь на решение оно красивое, но более расплывчатое такое и для того, чтобы чуть-чуть усилить его строгость надо просто горы свернуть.

Вот сейчас покажу:

Задача первого типа,когда решение красивое и сразу строгое(ну в том смысле, что если потребуется можно легко и просто пояснить каждый шаг.)

По кругу расставлены 100 чисел. Известно, что каждое число равно среднему арифметическому двух соседних. Докажите, что все числа равны.

Предположим, что не все числа равны. (Т.е. минимум два разные) Пусть это будут a1 и a2. Без ограничения общности можно считать, что a1>a2. Но так как по условию a1=(a2+a100)/2 следует, что a1<a100. Аналогично, для a100 из равенства a100=(a1+a99)/2 следует, что a100<a99 и т.д. a99<a98, a98<a97, ..., a3<a2,a2<a1. Получается, с одной стороны по предположению, что a2<a1, a с другой из наших неравенств, что a1<a100<a99<...<a3<a2. Противоречие.

А вот задача другого типа(решение красивое, но если захочется прояснить некоторые моменты, то это будет очень сложно и непонятно как сделать).

На плоскости нарисовано несколько точек. Двое по очереди соединяют их отрезками. Отрезки могут выходить из одной точки, но не должны пересекаться. Кто не может сделать ход, проигрывает. Докажите, что при любых ходах игроков победителем будет один и тот же, а кто именно определяется лишь начальной позицией.

Рассмотрим произвольную конфигурацию точек на плоскости, например как на рисунке.
Изображение
Соединив граничные точки отрезками получим выпуклый многоугольник внутри которого могут находиться внутренние точки.(На рисунке получается пятиугольник, внутри которого две точки).
Изображение
Игра закончится, когда вся область внутри многоугольника разобьется на треугольники. Иначе, в соответствующих многоугольниках просто проведем дополнительные диагонали, разбив их на треугольники.
Изображение
Теперь будем последовательно, стирать с границы построенные игроками отрезки(ребра), (оставляя после каждого шага другой, но многоугольник), пока на рисунке не останется ровно один треугольник. Т.е., так не будем делать:
Изображение
Мы будем это делать шагами двух типов: первый стирает два ребра и, как следствие, одну вершину, а второй стирает только одно ребро, но при этом он превращает одну из внутренних точек в граничную(первый тип так делать не может). Оба шага стирают также и треугольник.
Изображение
Теперь пусть на рисунке n точек, из них k, находящихся на начальной границе, а n-k внутренних. Так как в результате нашей последовательности действий на рисунке останется только один треугольник, то значит мы стерли n-3 вершины, а так как вершины может стирать только шаг первого типа, то у нас в последовательности ровно n-3 таких шагов, однако, чтобы стереть внутренние точки надо сделать их граничными, а это может только шаг второго типа, значит у нас было ровно n-k таких шагов. Вспомним, что шаг первого типа стирает два ребра, шаг второго - одно ребро, и учтем, что у нас в конце остался треугольник, т.е. еще 3 ребра, у нас получается какое-то число отрезков, важно то, что оно зависит только от числа точек на рисунке и числа внутренних точек(т.е. не зависит от действий игроков). А это по сути и есть то, что требовалось доказать.

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение03.04.2017, 17:20 
Заслуженный участник


13/12/05
4517
famesyasd в сообщении #1206028 писал(а):
Это по сути черновик еще незаконченного доказательство, я в нем уже много раз убирал и переписывал целые абзацы, так что оно не слишком понятно может быть.

В доказательство не вчитывался, но судя по объему, оно как раз не строгое и в нем есть ошибки )

-- Пн апр 03, 2017 20:21:14 --

famesyasd в сообщении #1206153 писал(а):
(решение красивое, но если захочется прояснить некоторые моменты, то это будет очень сложно и непонятно как сделать)

Значит НЕ красивое

-- Пн апр 03, 2017 20:26:44 --

famesyasd в сообщении #1205993 писал(а):
Подскажите как быть в общем со строгостью решений, можете на примере этой задачи объяснить.

Решение будет строгим тогда, когда в нем нет ничего лишнего, и каждый шаг рассуждений очевиден и не оставляет недомолвок, нерассмотренных случаев и т.д. То есть рассуждение все время должно идти в жестких рамках. Шаг влево, шаг вправо - противоречие )

 Профиль  
                  
 
 Re: Строгость доказательства.
Сообщение03.04.2017, 18:03 


03/03/16
7
Padawan в сообщении #1206226 писал(а):
Решение будет строгим тогда, когда в нем нет ничего лишнего, и каждый шаг рассуждений очевиден и не оставляет недомолвок, нерассмотренных случаев и т.д. То есть рассуждение все время должно идти в жестких рамках. Шаг влево, шаг вправо - противоречие )

А все короче, пока писал ответ уже разобрался в своей проблеме:)

Я понял как буду теперь относиться к строгости в доказательствах своих и чужих. Если я буду его читать и у меня не будет возникать совершенно никаких вопросов, то для меня это будет 100% строгое доказательство. А проблема моей чрезмерной сложности состояла в том, что я стал задавать вопросы без особой надобности к абсолютно всем местам, даже к тем, что изначально у меня вопросов не вызывали.

Всем спасибо!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group