Возможно ли доказать теорему о 4-х красках при помощи компью

[Aleksand]

Думаю, что нет. Как именно доказывать?

[мат-ламер]

Aleksand в сообщении #636682 писал(а):

Как именно доказывать?

Для начала попробуйте доказать, что достаточно конечное число красок. (Число не зависит от карты).

[Aleksand]

Ну пять-то красок хватит. Причём сам доказал, без чьей-либо помощи.

-- 28.10.2012, 00:19 --

Это с чего это Вы взяли, что "число цветов не зависит от карты". Есть 4-х цветные карты. Возможно, что при большом числе стран буду 5-цветные карты. Далее 6-и, 7-и, 8-и цветные.

[arseniiv]

Aleksand в сообщении #636691 писал(а):

Ну пять-то красок хватит.

Aleksand в сообщении #636691 писал(а):

Далее 6-и, 7-и, 8-и цветные.

Противоречие.

[Toucan]

Тема перемещена из форума «Дискуссионные темы (Ф)» в форум «Computer Science»

[Aleksand]

Это и есть доказательство "от противного". Правильно. Это противоречие. Шестицветных карт не бывает. А из пятицветных сразу семицветные не получатся.

-- 28.10.2012, 01:50 --

Ещё уточню свой вопрос. Я его уже задавал на другом форуме, и мне ответили, что было доказано, что если все карты с числом стран, скажем, менее 10 000 окрашиваются в 4 цвета, то при большем числе стран пятицветных карт уже не будет. Вот на компьютере перебрали карты до 10 000 стран, пятицветных там не оказалось, а значит их нет вообще.

От такого доказательства у меня волосы дыбом встали.

[arseniiv]

Aleksand в сообщении #636711 писал(а):

От такого доказательства у меня волосы дыбом встали.

Странно. Доказательства с проверкой двух-пяти альтернативных вариантов ничем качественно не отличаются от доказательств с проверкой миллиарда вариантов.

(Внимание!)

Aleksand в сообщении #636711 писал(а):

доказательство "от противного"

Кавычки лишние.

[Aleksand]

Я не знаю что такое "доказательства с проверкой двух-пяти альтернативных вариантов".

(Оффтоп)

а здесь кавычки не лишние, т.к. это цитата.

Теорема либо доказана, либо недоказана, либо её невозможно доказать. И всякие альтернативы неуместны. Во всяком случае мне такое неизвестно.

[Nemiroff]

Aleksand в сообщении #636715 писал(а):

Я не знаю что такое "доказательства с проверкой двух-пяти альтернативных вариантов".

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

[longstreet]

(Оффтоп)

Nemiroff в сообщении #636718 писал(а):

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

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

[Aleksand]

longstreet в сообщении #636720 писал(а):

Nemiroff в сообщении #636718 писал(а):

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

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

Ах, вон Вы про что. Я не сомневаюсь что компьютер правильно расчитал варианты. Просто теорема будет доказана только для карт с числом стран менее 10 000.

-- 28.10.2012, 07:32 --

Меня бы устроило, если бы доказывающий сказал примерно так:
Вероятность появления 5-цветной карты с увеличением числа стран не увеличивается, а уменьшается. Причём не стремится к нулю, а в точке 10 000 точно равен нулю. А дальше график пересекает ось абсцисс и уходит вниз. То есть нет смысла рассматривать все карты. Достаточно рассмотреть карты с числом стран менее 10000. А это можно перебрать на компьютере. И если ничего не найдём, то дальше там ничего не будет.
Но как расчитать вероятность появления 5-и цветной карты, если их никто не видел? Да так ли это? С увеличением числа стран трудность раскраски карты увеличивается. Поэтому и возникла эта задача.
Вот я и хочу спросить, куда же можно приспособить этот компьютер? Что им перебирать?

[longstreet]

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

[Aleksand]

Да нет у меня "нормальных" источников. Я не предлагаю алгоритма перебора. Это просто мои предположения. А вот то, что достаточно перебрать только часть вариантов... А вот с этим я не очень согласен...

[longstreet]

Aleksand в сообщении #636842 писал(а):

А вот то, что достаточно перебрать только часть вариантов... А вот с этим я не очень согласен...

Вы что, не слышите?

longstreet в сообщении #636778 писал(а):

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

Как вы можете быть не согласны с доказательством, если вы с ним не разобрались?

-- 28.10.2012, 13:49 --

Материала полно (кликните; если не ошибаюсь, то что вас интересует - изложено в главе Reducibility). Может, и на русском полное изложение идеи доказательства есть $-$ не знаю.

[arseniiv]

(Ещё одно уточнение.)

Aleksand в сообщении #636715 писал(а):

Теорема либо доказана, либо недоказана, либо её невозможно доказать. И всякие альтернативы неуместны. Во всяком случае мне такое неизвестно.

Когда теорему невозможно доказать, она одновременно не доказана (на все времена). Т. е. из ваших «альтернатив» в конкретное время реализуется либо первая, либо вторая, либо третья и вторая вместе — надо было их немного переформулировать.