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

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

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

Хм... Вышку я заканчивал более 30 лет назад, но мне помнится что задача раскраски карты 3 красками нерешаема...?

Это задача 8 класса. Комбинаторика есть, топологии ещё нет. Нашёл решение, но даже понять его не могу.

NS давно тут был?

(2) ns давно.

(1) Какая вышка, задача для 7 класса :)

(0) Не идея, но подсказка: количество регионов и конфигурация (включая анклавы и острова) на решение не влияют

Может быть так подходит:
всего способов раскраски - 85^3 (каждый регион красим в один из 3-х цветов) - нечетно.
Способ раскрасок по условию = общее число способов - число способов, когда граница с одной стороны красная, с другой - белая.
А таких - четное, т.к. 1-й регион - красный, 2-й - белый. Ему соответствует наоборот: 1-й белый, 2-й красный.

(6) Бинго!

Модераторы. Скройте тему как-нибудь до конца дня, пожалуйста. Олимпиада он-лайн и в разгаре.

+(8) Интересно, а как быстро тема попадает в индексы яндекса и гугла?

Ошибка: общее число = 3^85. Но тоже нечетное.

(10) Может общее число комбинаций соединения регионов разделить на количество вариаций покраски? а их 4, синий, красный, белый и бесцветный из которых надо вычеркнуть все комбинации с белым и красным, сочетаниями
!85/!4

(9) Практически моментально

(12) Пока ни яндекс ни гугл по тексту задачи не выдает мисту

(13) Уже выдает в топе

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

(14) Странно, по полному тексту не выдает, а по определенным кускам выдает

(16) Оптимизация на заголовок темы, а не на текстовку

А скрытые сообщения не видны без регистрации? Тогда (6) можно скрыть и посмотреть сколько школьников-чемпионов по поиску зарегистрируются сегодня :)
Модераторы!

(18) Модераторы/// в полит темах нужно ссылку на тему и попробовать привлечь внимание

(4) Ну задача то для 7 класса, но если ее решать теоретически, то это одна из задач на теорию граф.
(1)Вроде 3 цвета это минимум необходимый.

(19) ПОлит ветки не индексируются

(20) Минимум -5. В 4 краски произвольную карту, чтобы не было границ со станами одного цвета, не раскрасишь.
По легенде эту задачу (о 4-х красках) немцы подкинули англичанам во время войны, чтобы их математики занимались не работой.
Довольно быстро выяснили, что 5 хватает, а 3-х - нет. Более того, довольно быстро получили формулу для минимального числа красок для карты на поверхности любой топологической связности, кроме 0 (сфера или плоскость).
В результате пришли к тому, что вопрос не был решен для конечного числа стран. И, вроде бы, в МГУ в районе 90-х сделали программу, которая все эти случаи проверила (могу врать).
Окончательно: 4-х красок в общем случае карты на плоскости не хватает.

(21)  я о том что модераторы только в них сидят

(22) > 4-х красок в общем случае карты на плоскости не хватает.

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

Вы только в политические ветки не ходите, пожалуйста.

...  немцы подкинули англичанам

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

Изначально доказательство было принято не всеми математиками, поскольку его невозможно проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения"
https://ru.wikipedia.org/wiki/Теорема_о_четырёх_красках

(24)(25) Вы правы: склероз детектед. Насчет немцев: ходил такой анекдот во времена моей молодости.

"Четвёртый цвет начинает требоваться, например, тогда, когда имеется одна область, окружённая нечётным числом других, которые соприкасаются друг с другом, образуя цикл."
Не удержался и сделал иллюстрацию =) https://i.imgur.com/p6lNbGg.png

(1) >> задача раскраски карты 3 красками нерешаема...?

Решаема. Например, красим все регионы в красный цвет. Или все в белый. Или все в красный и белый случайным образом. Или все в синий. Короче вариантов, подходящих под условия, тысячи.

(28) Зачем ты ее делал? Есть же готовая в интернете, называется: "Гугл Хром Логотип"

Спасибо за советы и подсказки. Турнир ребёнок написал, эту задачу я понял и ему объяснил - там нечётное общее число вариантов, чётное - неподходящих, хначит годных нечётное.

(30) Там 2 кольца и 5 цветов вообще то.

(32) В контексте классической задачи о раскраске - там синий вообще не нужен. Так что "4 цветов, как 640К, хватит всем".

(32) Тупая отмазка

(34) Тебе просто завидно, что я нарисовал крутейшую иллюстрацию, а ты нет =)

так все-таки если классическая задача - значит мин = 4 цвета?

(36) да

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

(0)Раскрасить в синий, раскрасить в сине-белый 85 раз, раскрасить в сине-красный 85 раз. Раскраска в сине-бело-крансый: сколько ты не раскрасишь, все равно можно поменять цвета наоборот и получится столько же вариантов, т.е. четное. В итоге четное плюс 2*85+1 = нечетное.

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

Итого нечетное количество раскрасок.

(38) (39) правильная идея в (6)
(40) Все НЕправильные разбиваются на пары, правильные можно не считать. Хотя может у тебя получилось :)

(40) Ответ правильный. Только чисто синяя, чисто белая и чисто красная.

(42) ну, минус пару баллов есть на чем схлопотать

(42) чисто белая и чисто красная как раз пару образуют.
В общем (40) выглядит вполне годно, хотя казалось, что (6) поизящнее

(44) По условиям задачи не должно быть пар красная-белая. Поэтому чисто белая и чисто красная раскраски являются решением.

(45) Всё так. При замене красного на белый одна превращается в другую и по этому принципу образует пару правильных решений. В итоге всё по парам кроме полностью синей.

Давайте уже закопаем стюардессу?

Следующая задача. Найти целые различные a,b,c,d такие, что a^b=c^d и b^a=d^c

(47) только среди степеней двойки?

(46) Да, да. Это я ступил.

(48) Целые различные.

(50) ну, "Найти целые различные 2^a,2^b,2^c,2^d такие, что ab*log4=cd*log4 и ba*log4=dc*log4", или всё забыл

(47) Навскидку решения нет. Попозже попробую доказать.
Это тоже с Ломоносовской?

(52) Я тоже не сразу нашёл. Да, Турнир Ломоносова.

(53) Нашёл решения, или что их нет?

(53) Понял. С отрицательными есть.

(52) 1

(56) Что 1? Решение - да, похоже одно.

-2,4,2,-4

(38) >> Поэтому количество найденных решений можно умножить на 3 и будет всегда нечётно :)    

Если 100 умножить на 3 получится нечетно?

(58) Порядок не верный, а так да - похоже единственное решение

+(58)Точнее -2,4,-4,2

Решений больше.

(62) лево с право можно переставить. Или есть принципиально отличающиеся решения (из другого набора чисел)?

Да, совсем другие наборы. Я перебором их нашёл, хотя моя реализация отрицательных степеней дала много ошибок округления.

(64)Эээ... округления!? Задача же целочисленная.
Покажи, что нашёл :)

(0) Выскажу предположение, что число способов = 3^85-2^85.

(66) Точно не верно в общем случае.
Если регион один, то вариантов 3.
Если 85 регионов без общих границ (острова), то вариантов 3^85.
Вероятность попадания такого ответа именно в конфигурацию РФ - практически ноль

(67) Да, я уже понял. Для регионов = 2 число способов = 7, а по (66) - 5.

(68) Два региона могут не иметь общей границы, тогда вариантов 9. Т.е. в общем случае число вариантов зависит от конфигурации регионов и найти его очень сложно

(66)+ Поспешишь, людей насмешишь. Ясно, что простой общей формулы не может быть: зависит от карты.
Это 1С виновата: х..к, х..к и в продакшен.

(62) с точностью до расстановки знаков и порядка оно одно выходит

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

в итоге,их нечетное число.

(72) точно, см. (40)