СПбГУ 2023, отборочный этап, 10–11 классы, задача 10
( баллов) На доске написаны различных натуральных чисел. Оказалось, что для каждого написанного числа на доске найдется еще хотя бы одно число такое, что — простое число. Докажите, что можно подчеркнуть не более чисел так, чтобы для каждого неподчеркнутого числа нашлось подчеркнутое число , для которого — простое число.
Ответ
Первое решение. Рассмотрим граф, в котором вершины — числа, ребро проводится, если модуль разности этих чисел — простое число. Будем красить каждую компоненту связности этого графа в два цвета: сначала покрасим любую вершину в красный. Затем покрасим всех её соседей в синий. Затем всех соседей синих, которые ещё не покрашены, в красный. Затем соседей красных в синий. И так далее. Легко видеть, что у каждой красной вершины будет хотя бы один синий сосед, а у каждой синей — хотя бы один красный. В каждой компоненте связности выберем цвет, вершин которого не более половины, и подчеркнем вершины этого цвета. Каждая неподчеркнутая вершина будет соединена хотя бы с одной подчеркнутой.
Второе решение. В том же графе выберем наибольшее независимое множество вершин (т.е. такое множество вершин, что никакие две вершины в нем не соединены ребром). Любая вершина соединена ребром с вершинй не из , так как по условию степень каждой вершины не менее . Любая вершина не из соединена ребром хотя бы с одной вершиной из , иначе можно было бы добавить ее к и получить независимое множество еще большего размера. Значит, мы можем подчеркнуть или все вершины , или все вершины не из . Выбирая то из множеств, размер которого не превосходит половины от общего размера, получаем требуемое.