Если по окружности-стадиону бежит атлет и возвращается в итоге в начальную точку — число кругов, которые он пробежал, можно посчитать, встав в любую точку стадиона и считая пересечения (если он пробежал куда надо, то с плюсом, а если обратно, то с минусом).

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

А если атлет начинал и закончил путь на разных дугах — то если добавить к пути замыкание "в положительном направлении", после которого суммы у арбитров совпадут, то один из двух арбитров его увидит, а другой нет. И уже совсем легко увидеть, что общий ответ такой:
число пересечений (с учётом знака) для арбитра A1 минус
число пересечений (с учётом знака) для арбитра А2 =
F(начала пути)-F(конца пути),
где F это 1, если мы начали на дуге от A2 к A1 (обозначенной тут +-), и 0 иначе.

Если просуммировать такое за все шаги, то получается:
Число пересечений с осью ординат для исходной кривой (которое и есть то, что мы ищем)
минус
число пересечений с осью ординат для последней кривой, к которой мы приходим (а это просто точка (1,0), которая стоит на месте и ось ординат не пересекает)
равно
сумме по всем шагам разностей F(начало пути) минус F(конца пути), где F смотрит, есть ли между P_j и P_{j+1} перемена знака.

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

Ура, победа! Мы связали топологический взгляд с классической формулировкой теоремы Штурма через число перемен знака.

Ещё — пара картинок из "Геометрии дискриминанта" В. А. Васильева:

(В. А. Васильев, "Геометрия дискриминанта")

(В. А. Васильев, "Геометрия дискриминанта")

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

А вот — страница из текста Д. В. Аносова 2003 года; как раз очень близко к тому, что мы уже видели раньше, только у него цепная дробь обычная, поэтому в ответе возникает чередование знаков:

(Д. В. Аносов, "Отображения окружности, векторные поля и их применения", МЦНМО, 2003)

Ну а часть рассказа выше (подход через степени) вошла в (онлайн)-курс топологии, который мы с коллегами ведём — собственно, уже заканчиваем — для первого курса Вышки. Кто же знал, когда всё это только задумывалось, что курс с частичным онлайном и красивыми картинками вынужденно превратится в полный онлайн...
From behind the stages:

Через пару минут начнётся объявление премии Абеля:
https://www.youtube.com/watch?v=0_NK_OkpmUY

Abel Prize 2021:
László Lovász & Avi Wigderson
“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”

Один из результатов, который упоминали на церемонии вручения премии Абеля — это Zero Knowledge Proof, доказательство с нулевым разглашением. И это действительно очень красивая идея (восходящая к работе Goldreich-Micali-Rackoff, "The Knowledge Complexity of Interactive Proof-Systems").

Как мне это когда-то рассказывали — вот представьте себе, что математик X доказал гипотезу Римана. Естественно было бы написать статью или рассказать результат на семинаре — но X опасается, что его результат украдут. Может ли X убедить коллег, что у него действительно есть доказательство — не рассказав его? И оказывается, что да, есть способ это сделать — о доказательстве вообще ничего не рассказав, кроме его длины. (Можно считать, что X потрясает пачкой бумаги со словами, "этого хватит, чтобы доказательство записать".)

Более того, — это возможно для вообще любой NP-задачи. И вот тут алгоритм придумали Oded Goldreich, Silvio Micali и Avi Wigderson: см. "How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design" (1986; https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_11.pdf )

В двух словах (я уточню ближе к концу этого рассказа) — нас интересуют ситуации, когда уже предъявленный ответ можно быстро проверить, но вот сам поиск этого ответа, возможно, безумно сложен. Например, если Вася хочет доказать, что он знает гамильтонов (посещающего каждую вершину ровно один раз) путь в графе. Как раз — проверить, что путь по 1000 вершин графа действительно проходит через каждую вершину, ровно один раз, и каждый раз переходит по ребру — легко. А вот найти такой путь (если он есть) для заданного графа — слоожно...

Тот пример, из которого всё выводится в работе Goldreich, Micali, Wigderson — это задача трёхцветной раскраски: раскрасить вершины графа в 3 цвета так, чтобы соседние вершины были бы раскрашены в разные цвета.
(Кстати: если граф планарный, то в четыре цвета его вершины правильным образом раскрасить всегда можно — и это и утверждает теорема о четырёх красках.)

Понятно, что это задача как раз такого класса: найти раскраску может быть очень сложно — но вот когда раскраска уже предъявлена, проверить, что это действительно правильная раскраска, занимает вполне разумное время.

Так вот — допустим, что X знает правильную трёхцветную раскраску данного графа. Как ему убедить в этом Y, не раскрывая никакой информации?

Сделаем вот что: пусть X выберет случайным образом одну из 6 перестановок цветов (ведь если перекрасить все красные вершины в зелёный, а все зелёные в красный — правильная раскраска останется правильной). И положит у каждой вершины запечатанный конверт с цветом получившейся правильной раскраски.

Теперь проверяющий Y выберет две соседние вершины. И вскроет соответствующие им конверты (все остальные конверты немедленно сжигаются).

Дальше может быть одно из двух:
1) Если Y обнаружил совпадающие цвета, то он говорит X "ах ты нехороший человек, обмануть хотел? Не прокатило!". На этом протокол прекращается, а X объявляется жуликом.
2) Если цвета разные, то процедура повторяется. X выбирает новую случайную перестановку, раскладывает конверты, Y выбирает две соседние вершины, вскрывает конверты в них, и так далее.

При этом — если X играет честно и выбирает каждый раз равномерно случайную перестановку, то никакой информации о раскраске (кроме того, что она, похоже, правильная) Y не получает: любая пара соседних вершин может быть равновероятно окрашена любым из 6 способов.

Наоборот, если Y выбирает проверяемое ребро случайным образом, то шанс поймать X, если он жульничает — по меньшей мере 1/N, где N — число рёбер в графе. За 100N раундов шанс, что на самом деле не знающий раскраски обманщик не будет пойман, становится меньше
(1- 1/N)^{100N} ~ e^{-100} < 10^{-40}.
(Ну и, естественно, такая вероятность может быть сделана сколь угодно малой, если 10^{-40} нам почему-то недостаточно.)

==
Вообще-то говоря, я тут смешал в одно описание ("что будет происходить") две вещи: протокол и стратегию игроков . Если их разделять — а это правильно сделать — то протокол состоит в том, что на каждой итерации X кладёт конверты, а Y выбирает из них два, отвечающих соседним вершинам, после чего они вскрываются. И если обнаруживают два одинаковых цвета, то X проиграл, а если за данное большое число раундов X не пойман, то считается, что он Y убедил.
А дальше — честный X с помощью стратегии случайной перестановки цветов на каждом шаге гарантирует, что информация не утечёт при любых действиях Y (какое бы ребро Y ни выбрал, он получает просто равновероятную пару цветов).
Наоборот, честный Y с помощью стратегии случайного выбора ребра на каждом шаге гарантирует, что вероятность для жулика-X проскочить не больше, чем 10^{-40} (и вообще экспоненциально мала по количеству итераций протокола).

А вообще протоколы, стратегии и атаки на протоколы — это большая тонкая наука (и туда мы сейчас точно не пойдём 🙂 ).
==

Вот тут есть демонстрация этого алгоритма со стороны проверяющего:
http://web.mit.edu/~ezyang/Public/graph/noscript.html
Там предлагают выбрать граф — и в одном из случаев к нам пришёл человек с честной раскраской, а в другом нас пытаются обмануть. Confidence внизу отвечает за оценку на "1 минус вероятность того, что обманщику столько раундов подряд бы везло".

==
Да, ещё одно — как можно реализовать конверты: хэшем. Если есть (объявлена публично) односторонняя функция F (которую трудно обратить, но которая тем не менее взаимно-однозначна), то пусть X на каждом шаге для каждой вершины j вычисляет
f_j=F(c_j R_j),
где с_j — пара бит, кодирущих цвет в этой вершине, а R_j — ещё куча-куча "мусорных бит", и объявляет результат вычисления f_j публично. (Мусор нужен, чтобы Y не мог просто перебрать три варианта цвета и вычислить от них F; если я правильно понимаю, такой мусор в криптографии называется "солью").

И протокол дополняется тем, как происходит "вскрытие конвертов": Y говорит, какие именно конверты вскрывает, X для них объявляет c_j и R_j, после чего Y проверяет, что F от заявленных c_j R_j это действительно ранее объявленные f_j.

А стратегия X — тем, что мусорные биты нужно выбирать совершенно случайными, чтобы объявление f_j и впрямь не приводило ни к какой (значимой) утечке информации.
==