Задача 064 — Задачи на Графы

Докажите, что у любого конечного множества $A$ натуральных чисел существует подмножество $B$ , удовлетворяющее следующим условиям: если $b_{1}, b_{2} \in B$ различны, то ни одно из чисел $b_{1}, b_{2}$ не делится на другое и ни одно из чисел $b_{1}+1, b_{2}+1$ не делится на другое, а также для любого $a \in A$ найдётся $b \in B$ такое, что или $b$ делится на $a$ , или $a+1$ делится на $b+1$ .

Подсказка

Решение

Рассмотрим двуцветный ориентированный граф, у которого вершинами будут элементы множества $A$ , и от вершины $b$ к вершине $a$ идет синяя стрелка, если $b$ делится на $a$ , и красная, если $a+1$ делится на $b+1$ . Тогда мы хотим выбрать независимое подмножество вершин $B$ такое, что в любую вершину множества $A \backslash B$ ведет стрелка из $B$ .

Поделим вершины на три группы: исходные, выбранные и хорошие (вершины будут перемещаться из группы в группу, но никакая вершина на может находиться в двух группах одновременно). Изначально все вершины находятся в группе исходных. Выберем среди них такие, в которые не входит ни одна синяя стрелка и отправим их в группу выбранных. Тогда, в силу транзитивности синих стрелок, в каждую исходную вершину ведет хотя бы одна синяя стрелка из выбранных вершин. Если так случилось, что между выбранными вершинами нет красных стрелок, то, приняв за $B$ множество выбранных вершин, мы решим задачу. Если же красные стрелки есть, то найдем все выбранные вершины, в которые ведет хотя бы одна красная стрелка из других выбранных, и отправим их в группу хороших. После этого, могло оказаться, что в некоторые исходные вершины не идет синей стрелки из выбранных. В этом случае добавим в множество выбранных те вершины из исходных, в которые синие стрелки приходят только из хороших вершин. После этого снова отправим в группу хороших те из выбранных вершин, в которые ведет хотя бы одна красная стрелка из других выбранных. В силу транзитивности теперь уже красных стрелок, в любую хорошую вершину все еще ведет хотя бы одна красная стрелка из выбранных. Будем продолжать такие перемещения (из исходных в выбранные, из выбранных в хорошие). Заметим, что если в некоторый момент мы не смогли уменьшить множество исходных вершин, то задача решена,а так как изначально там конечное число вершин, этот момент обязательно наступит.