Теперь для каждой переменной X заведём две вершины, X и ¬X. И соединим их друг с другом и с базой — как раз это гарантирует, что кто-то из X и ¬X будет нулём, а кто-то единицей.

Осталось сделать что-то, раскрашивание чего будет равносильно одной "скобке" X⋁Y⋁Z (где X,Y,Z — переменные или их отрицания). Вот если бы мы нарисовали ещё один треугольник и соединили его вершины с вершинами переменных/отрицаний X, Y и Z — то значения X=Y=Z=0 мы этим бы запретили (потому что из трёх вершин треугольника хоть одна нулём да будет раскрашена). Но вот беда — мы так и X=Y=Z=1 запретим, а этого бы не хотелось!

Не работает. Дорабатывать надо!

Поэтому давайте сделаем так. Будем "подключать" переменные X, Y, Z к этому треугольнику не напрямую, а через дополнительные (специально для этой дизъюнкции выделенные) промежуточные вершины, соединённые ещё и с 1. Тогда если было X=Y=Z=0, то на промежуточных вершинах мы можем поставить только "базу" (потому что они соединены и с 0, и с 1), и продолжить раскраску на треугольник мы не сможем. Наоборот, если какая-то из переменных равна 1, то промежуточную вершину можно раскрасить как "0", и как "базу". И отсюда уже легко увидеть, что мы всегда можем раскрасить промежуточные вершины не все в один цвет — и дальше продлить эту раскраску на треугольник.

А вот так правильно!

Подключая по одному такому "удлинённому треугольнику" на каждую скобку, мы получаем граф, который можно правильно раскрасить в 3 цвета тогда и только тогда, когда есть значения переменных, обращающие булевскую формулу в истину. И вот 3-SAT сведена к 3-COL. Ура!

Так что, чтобы если X хочет нас убедить, что он умеет доказывать гипотезу Римана, не раскрывая доказательство — нужно попросить его записать его формально, в виде алгоритмически-проверяемой последовательности вывода (где каждая следующая строчка получается из предыдущих применением одного из правил вывода). Спрашиваем, какую длину его доказательство занимает (та самая пачка бумаги, которой он потрясает); резервируем под его доказательство ProofText ячейки алгоритма формальной проверки
CheckProof(RiemannHypothesis,ProofText).
Смотрим, сколько времени алгоритм будет работать, превращаем потенциальный протокол работы+"окончание работы с выводом "верно, доказано"" в булевскую формулу для 3-SAT. Переделываем её в граф для 3-COL. Ура — можно применить процедуру проверки!

И в заключение — очень хороший (и совсем о другом) текст А. А. Разборова:
https://trv-science.ru/2021/03/pervoproxodcy-teoreticheskoj-informatiki/

Берем число A, возводим в степень n, округляем до целого вверх. Бывает ли такое A, что все время (при всех натуральных n) получается число, отличающееся от полного квадрата ровно на 2?

// задача Д.Крекова на ММО сегодня, https://olympiads.mccme.ru/mmo/2021/

(теперь — с правильной ссылкой)

Да, а задача правда красивая!

https://mccme.ru/dubna/2021/

Летняя школа «Современная математика» имени Виталия Арнольда планируется в этом году с 19 по 30 июля в Дубне (в очном формате). Начинается прием заявок от школьников 10 и 11 классов и студентов I и II курсов.

Прекрасное прошлогоднее: самый обычный топологический препринт на arXiv-е: https://arxiv.org/pdf/2003.13758.pdf (картинка — одна страница оттуда).
Rami Luisto, "A non-Euclidean story or: how to persist when your geometry doesn’t."

Статья должна читаться как роман!

https://youtu.be/O85OWBJ2ayo

3blue1brown всегда интересно смотреть,

а отдельно приятно, что «The book shown at the start is Vladimir Arnold's (excellent) textbook on ordinary differential equations» ( https://biblio.mccme.ru/node/6102/ )

Экслюзив: Письмо Рохлина Гудкову о том, что он доказал его гипотезу.

"Без сомнения, это доказательство лучше выражает топологическую суть дела, чем первое. Оно не было найдено сразу просто потому, что общая топологическая теорема, на которой оно основано [т.е. сравнение κ(F)−σ(X) ≡ 2τ(F)mod 8] не была известна. Вероятно, я скоро напишу это доказательство подробно. Конечно, я пришлю его Вам. Не знаю, сможете ли Вы ещё учесть его в Вашем обзоре.

Напишите, пожалуйста, нет ли аналогичных гипотез, относящихся к другим ситуациям, например, к кри- вым нечётной степени, к поверхностям или к неплоским кривым." 21.03.1972.

Подробнее.

Эйлеровой характеристикой многогранника называется число χ=В−Р+Г, где В, Р и Г — количества его вершин, ребер и граней соответственно. Оказывается, эйлерова характеристика зависит лишь от числа «дырок» в многограннике, например для многогранников без дырок (или как говорят математики, односвязных многогранников) эйлерова характеристика равна 2. То есть для куба, тетраэдра, октаэдра и любого другого многогранника без дыр χ=2. А для многогранника с g дырами χ=2−2g. Используя эйлерову характеристику, можно доказать несуществование некоторых многогранников. Например, не существует многогранника без дыр или с одной дыркой, у которого все грани — шестиугольники, попробуйте это проверить самостоятельно. Но если убрать условие на число дырок, то такие многогранники уже можно найти. Гораздо сложнее найти такой многогранник, все грани которого — выпуклые шестиугольники. На сегодняшней картинке изображён один такой многогранник. Попробуйте вычислить число его дырок :)
#рисункиМихаилаПанова
#которисунки
#MetaPost

https://knife.media/viktor-vasilyev/

к 65-летию Виктора Анатольевича Васильева — его недавнее интервью

А ещё — давайте я вспомню "Геометрию дискриминанта" и "Ветвящиеся объёмы и группы отражений" (этот курс Васильев читал в ЛШСМ два года — в 2013 и в 2014 годах — после первого раза решив одну из открытых проблем в этой области, так что на следующий год он уже рассказывал её решение. А недавно из этих курсов получилась, как мне кажется, замечательная книга для матшкольников и студентов — куда и это решение тоже вошло!).

Давайте я выложу несколько картинок из "Ветвящихся объёмов", которые правда очень люблю: