Вход | Регистрация
 
Информационные технологии :: Математика и алгоритмы

Задача на раскраску карты

Задача на раскраску карты
Я
   Базис
 
04.10.20 - 12:27
Ребёнок решает сейчас онлайновый математический турнир. Показал задачу, как обычно - не могу понять, откуда копать:

На контурной карте России 85 регионов. Вовочка хочет покрасить на карте каждый регион в белый, синий или красный цвет так, чтобы белый и красный цвета не имели общей границы. При этом один или даже два цвета можно не использовать.
Докажите, что количество вариантов такой раскраски — нечётно.

Решение не нужно, просто подскажите идею. В силу большого числа регионов задача нерешаема на бумаге в сложных конфигурациях, значит как-то надо обосновать ограничение рассматриваемых вариантов?
   Злопчинский
 
1 - 04.10.20 - 12:32
Хм... Вышку я заканчивал более 30 лет назад, но мне помнится что задача раскраски карты 3 красками нерешаема...?
   Базис
 
2 - 04.10.20 - 12:37
Это задача 8 класса. Комбинаторика есть, топологии ещё нет. Нашёл решение, но даже понять его не могу.

NS давно тут был?
   Злопчинский
 
3 - 04.10.20 - 12:39
(2) ns давно.
   RomanYS
 
4 - 04.10.20 - 12:49
(1) Какая вышка, задача для 7 класса :)
   RomanYS
 
5 - 04.10.20 - 12:51
(0) Не идея, но подсказка: количество регионов и конфигурация (включая анклавы и острова) на решение не влияют
   Михаил Козлов
 
6 - 04.10.20 - 12:53
Может быть так подходит:
всего способов раскраски - 85^3 (каждый регион красим в один из 3-х цветов) - нечетно.
Способ раскрасок по условию = общее число способов - число способов, когда граница с одной стороны красная, с другой - белая.
А таких - четное, т.к. 1-й регион - красный, 2-й - белый. Ему соответствует наоборот: 1-й белый, 2-й красный.
   RomanYS
 
7 - 04.10.20 - 12:54
(6) Бинго!
   RomanYS
 
8 - 04.10.20 - 12:56
Модераторы. Скройте тему как-нибудь до конца дня, пожалуйста. Олимпиада он-лайн и в разгаре.
   RomanYS
 
9 - 04.10.20 - 12:59
+(8) Интересно, а как быстро тема попадает в индексы яндекса и гугла?
   Михаил Козлов
 
10 - 04.10.20 - 13:05
Ошибка: общее число = 3^85. Но тоже нечетное.
   HeKrendel
 
11 - 04.10.20 - 13:33
(10) Может общее число комбинаций соединения регионов разделить на количество вариаций покраски? а их 4, синий, красный, белый и бесцветный из которых надо вычеркнуть все комбинации с белым и красным, сочетаниями
!85/!4
   HeKrendel
 
12 - 04.10.20 - 13:33
(9) Практически моментально
   RomanYS
 
13 - 04.10.20 - 13:36
(12) Пока ни яндекс ни гугл по тексту задачи не выдает мисту
   HeKrendel
 
14 - 04.10.20 - 13:37
(13) Уже выдает в топе
   RomanYS
 
15 - 04.10.20 - 13:37
(11) Зачем придумывать, никакого бесцветного нет. Ну и решение уже озвучено
   RomanYS
 
16 - 04.10.20 - 13:38
(14) Странно, по полному тексту не выдает, а по определенным кускам выдает
   HeKrendel
 
17 - 04.10.20 - 13:40
(16) Оптимизация на заголовок темы, а не на текстовку
   RomanYS
 
18 - 04.10.20 - 13:53
А скрытые сообщения не видны без регистрации? Тогда (6) можно скрыть и посмотреть сколько школьников-чемпионов по поиску зарегистрируются сегодня :)
Модераторы!
   vvspb
 
19 - 04.10.20 - 14:13
(18) Модераторы/// в полит темах нужно ссылку на тему и попробовать привлечь внимание
   Lama12
 
20 - 04.10.20 - 15:03
(4) Ну задача то для 7 класса, но если ее решать теоретически, то это одна из задач на теорию граф.
(1)Вроде 3 цвета это минимум необходимый.
   HeKrendel
 
21 - 04.10.20 - 15:06
(19) ПОлит ветки не индексируются
   Михаил Козлов
 
22 - 04.10.20 - 15:14
(20) Минимум -5. В 4 краски произвольную карту, чтобы не было границ со станами одного цвета, не раскрасишь.
По легенде эту задачу (о 4-х красках) немцы подкинули англичанам во время войны, чтобы их математики занимались не работой.
Довольно быстро выяснили, что 5 хватает, а 3-х - нет. Более того, довольно быстро получили формулу для минимального числа красок для карты на поверхности любой топологической связности, кроме 0 (сфера или плоскость).
В результате пришли к тому, что вопрос не был решен для конечного числа стран. И, вроде бы, в МГУ в районе 90-х сделали программу, которая все эти случаи проверила (могу врать).
Окончательно: 4-х красок в общем случае карты на плоскости не хватает.
   vvspb
 
23 - 04.10.20 - 15:25
(21)  я о том что модераторы только в них сидят
   acht
 
24 - 04.10.20 - 15:41
(22) > 4-х красок в общем случае карты на плоскости не хватает.

Да неужели. А вот тут https://ru.wikipedia.org/wiki/Теорема_о_четырёх_красках , почему-то, обратное доказывали аж три раза - в 1976 году, в 1997 и в 2005.

Вы только в политические ветки не ходите, пожалуйста.
   acht
 
25 - 04.10.20 - 15:42
...  немцы подкинули англичанам
   Гобсек
 
26 - 04.10.20 - 15:43
"Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем (англ.) и Вольфгангом Хакеном (англ.) из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определённый набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Авторы использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать какую-нибудь из этих 1936 карт, чего нет. Это противоречие говорит о том, что контрпримера нет вообще.

Изначально доказательство было принято не всеми математиками, поскольку его невозможно проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения"
https://ru.wikipedia.org/wiki/Теорема_о_четырёх_красках
   Михаил Козлов
 
27 - 04.10.20 - 16:36
(24)(25) Вы правы: склероз детектед. Насчет немцев: ходил такой анекдот во времена моей молодости.
   TormozIT
 
28 - 04.10.20 - 23:31
"Четвёртый цвет начинает требоваться, например, тогда, когда имеется одна область, окружённая нечётным числом других, которые соприкасаются друг с другом, образуя цикл."
Не удержался и сделал иллюстрацию =) https://i.imgur.com/p6lNbGg.png
   Джегеротта
 
29 - 05.10.20 - 17:18
(1) >> задача раскраски карты 3 красками нерешаема...?

Решаема. Например, красим все регионы в красный цвет. Или все в белый. Или все в красный и белый случайным образом. Или все в синий. Короче вариантов, подходящих под условия, тысячи.
   Джегеротта
 
30 - 05.10.20 - 17:24
(28) Зачем ты ее делал? Есть же готовая в интернете, называется: "Гугл Хром Логотип"
 
 Рекламное место пустует
   Базис
 
31 - 05.10.20 - 17:47
Спасибо за советы и подсказки. Турнир ребёнок написал, эту задачу я понял и ему объяснил - там нечётное общее число вариантов, чётное - неподходящих, хначит годных нечётное.
   TormozIT
 
32 - 05.10.20 - 18:56
(30) Там 2 кольца и 5 цветов вообще то.
   Базис
 
33 - 05.10.20 - 19:11
(32) В контексте классической задачи о раскраске - там синий вообще не нужен. Так что "4 цветов, как 640К, хватит всем".
   Джегеротта
 
34 - 05.10.20 - 22:16
(32) Тупая отмазка
   TormozIT
 
35 - 05.10.20 - 22:39
(34) Тебе просто завидно, что я нарисовал крутейшую иллюстрацию, а ты нет =)
   Злопчинский
 
36 - 06.10.20 - 09:11
так все-таки если классическая задача - значит мин = 4 цвета?
   Гобсек
 
37 - 06.10.20 - 09:15
(36) да
   ManyakRus
 
38 - 06.10.20 - 10:16
3 цвета, при любой раскраске цвета можно поменять местами и будет тоже правильно.
Поэтому количество найденных решений можно умножить на 3 и будет всегда нечётно :)
   DomovoiVShoke
 
39 - 06.10.20 - 10:52
(0)Раскрасить в синий, раскрасить в сине-белый 85 раз, раскрасить в сине-красный 85 раз. Раскраска в сине-бело-крансый: сколько ты не раскрасишь, все равно можно поменять цвета наоборот и получится столько же вариантов, т.е. четное. В итоге четное плюс 2*85+1 = нечетное.
   Ненавижу 1С
 
40 - 06.10.20 - 13:21
Для каждой правильной раскраски можно получить двойственную (отличную от исходной), заменив белый цвет на красный и наоборот. Все правильные раскраски разбиваются на пары.
При этом есть чисто синяя раскраска, двойственная которой она сама.

Итого нечетное количество раскрасок.
   RomanYS
 
41 - 06.10.20 - 14:03
(38) (39) правильная идея в (6)
(40) Все НЕправильные разбиваются на пары, правильные можно не считать. Хотя может у тебя получилось :)
   mkbusiness
 
42 - 06.10.20 - 14:12
(40) Ответ правильный. Только чисто синяя, чисто белая и чисто красная.
   Йохохо
 
43 - 06.10.20 - 14:19
(42) ну, минус пару баллов есть на чем схлопотать
   RomanYS
 
44 - 06.10.20 - 14:20
(42) чисто белая и чисто красная как раз пару образуют.
В общем (40) выглядит вполне годно, хотя казалось, что (6) поизящнее
   mkbusiness
 
45 - 06.10.20 - 15:43
(44) По условиям задачи не должно быть пар красная-белая. Поэтому чисто белая и чисто красная раскраски являются решением.
   RomanYS
 
46 - 06.10.20 - 15:46
(45) Всё так. При замене красного на белый одна превращается в другую и по этому принципу образует пару правильных решений. В итоге всё по парам кроме полностью синей.
   Базис
 
47 - 06.10.20 - 15:54
Давайте уже закопаем стюардессу?

Следующая задача. Найти целые различные a,b,c,d такие, что a^b=c^d и b^a=d^c
   Йохохо
 
48 - 06.10.20 - 15:57
(47) только среди степеней двойки?
   mkbusiness
 
49 - 06.10.20 - 16:05
(46) Да, да. Это я ступил.
   Базис
 
50 - 06.10.20 - 16:08
(48) Целые различные.
   Йохохо
 
51 - 06.10.20 - 16:18
(50) ну, "Найти целые различные 2^a,2^b,2^c,2^d такие, что ab*log4=cd*log4 и ba*log4=dc*log4", или всё забыл
   RomanYS
 
52 - 06.10.20 - 16:43
(47) Навскидку решения нет. Попозже попробую доказать.
Это тоже с Ломоносовской?
   Базис
 
53 - 06.10.20 - 16:50
(52) Я тоже не сразу нашёл. Да, Турнир Ломоносова.
   RomanYS
 
54 - 06.10.20 - 17:07
(53) Нашёл решения, или что их нет?
   RomanYS
 
55 - 06.10.20 - 17:11
(53) Понял. С отрицательными есть.
   Krendel
 
56 - 06.10.20 - 17:34
(52) 1
   RomanYS
 
57 - 06.10.20 - 17:55
(56) Что 1? Решение - да, похоже одно.
   DomovoiVShoke
 
58 - 06.10.20 - 18:01
-2,4,2,-4
   Джегеротта
 
59 - 06.10.20 - 18:01
(38) >> Поэтому количество найденных решений можно умножить на 3 и будет всегда нечётно :)    

Если 100 умножить на 3 получится нечетно?
   RomanYS
 
60 - 06.10.20 - 18:02
(58) Порядок не верный, а так да - похоже единственное решение
 
 Рекламное место пустует
   DomovoiVShoke
 
61 - 06.10.20 - 18:02
+(58)Точнее -2,4,-4,2
   Базис
 
62 - 06.10.20 - 18:13
Решений больше.
   RomanYS
 
63 - 06.10.20 - 18:15
(62) лево с право можно переставить. Или есть принципиально отличающиеся решения (из другого набора чисел)?
   Базис
 
64 - 06.10.20 - 18:27
Да, совсем другие наборы. Я перебором их нашёл, хотя моя реализация отрицательных степеней дала много ошибок округления.
   RomanYS
 
65 - 06.10.20 - 18:33
(64)Эээ... округления!? Задача же целочисленная.
Покажи, что нашёл :)
   Михаил Козлов
 
66 - 06.10.20 - 20:03
(0) Выскажу предположение, что число способов = 3^85-2^85.
   RomanYS
 
67 - 06.10.20 - 20:14
(66) Точно не верно в общем случае.
Если регион один, то вариантов 3.
Если 85 регионов без общих границ (острова), то вариантов 3^85.
Вероятность попадания такого ответа именно в конфигурацию РФ - практически ноль
   Михаил Козлов
 
68 - 06.10.20 - 20:58
(67) Да, я уже понял. Для регионов = 2 число способов = 7, а по (66) - 5.
   RomanYS
 
69 - 06.10.20 - 21:03
(68) Два региона могут не иметь общей границы, тогда вариантов 9. Т.е. в общем случае число вариантов зависит от конфигурации регионов и найти его очень сложно
   Михаил Козлов
 
70 - 06.10.20 - 23:46
(66)+ Поспешишь, людей насмешишь. Ясно, что простой общей формулы не может быть: зависит от карты.
Это 1С виновата: х..к, х..к и в продакшен.
   Ненавижу 1С
 
71 - 06.10.20 - 23:56
(62) с точностью до расстановки знаков и порядка оно одно выходит
   Сияющий в темноте
 
72 - 08.10.20 - 00:10
во-первых,одно решение есть всегда-это все стние регионв,и оно особенноне,в нем если поменять белый и красный местами,то другое решение не получится.
для остальных решений,если они существуют,замена красныого на белый или наоборот дает другое решение.
то есть решений для использования хоть одного цвета из пары красный белый четное число
и еще одно,где не используютмя цвета

в итоге,их нечетное число.
   Ненавижу 1С
 
73 - 08.10.20 - 10:54
(72) точно, см. (40)


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.