Областная олимпиада по математике, 2023 год, 11 класс

В графе $G$ вершины пронумерованы числами от 1 до $(p-1)$, где $p>3$ простое. Между любыми двумя вершинами $x$ и $y$ ставится ребро, если существует натуральное $n$, для которого $x^n+y^n$ делится на $p$. Докажите, что в $G$ существует цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.

Комментарий/решение

Не знаю правильно это или нет но думаю задача решаеться так

Во-первых, заметим, что если в графе существует ребро между вершинами x и y, то существует ребро между вершинами y и x (поскольку x^n + y^n = y^n + x^n). Следовательно, граф неориентированный.

Далее заметим, что для любых двух различных вершин x и y существует натуральное число n такое, что x^n + y^n делится на p тогда и только тогда, когда x^(p-1) + y^(p- 1) делится на p (по малой теореме Ферма). Следовательно, мы можем построить граф, используя мощности каждой вершины по модулю p-1 вместо использования всех натуральных чисел.

Пусть V_i будет вершиной, соответствующей номеру i в графе. Для каждой вершины V_i мы рассматриваем множество вершин S_i = {V_j : i^(p-1) + j^(p-1) делится на p}. Отметим, что если i и j различны, то i^(p-1) + j^(p-1) не может делиться на p, если только i и j не взаимно просты с p (поскольку p простое число). Следовательно, S_i является подмножеством множества вершин, взаимно простых с p. Поскольку существует (p-1)/2 вершины, взаимно простые с p, и каждая вершина может принадлежать не более чем двум наборам S_i (по одному для каждой вершины, с которой она имеет общее ребро), должна быть хотя бы одна вершина, которая ни в одном из наборов S_i.

Пусть V_1 — вершина, не входящая ни в одно из множеств S_i. Мы строим цикл, начиная с V_1, выбирая произвольного соседа V_2 для V_1 и продолжая выбирать соседей жадным образом. В частности, на шаге i мы выбираем соседа V_{i+1} для V_i, который еще не был посещен, и мы знаем, что такой сосед существует, поскольку V_i не входит в множество S_j для любого j<i (иначе мы уже бы посетил V_j). Поскольку существует (p-1)/2 вершин, взаимно простых с p, и каждую вершину можно посетить не более одного раза, цикл должен проходить через все вершины графа.

Наконец, отметим, что цикл замкнут, так как последняя выбранная вершина V_k является соседом V_1. Таким образом, мы показали, что граф содержит цикл, который проходит через каждую вершину ровно один раз, что и требовалось.