Раскраски графов
Ошибка.
Попробуйте повторить позже
На доске написаны 
различных натуральных чисел. Оказалось, что для каждого написанного числа а на доске найдется еще хотя бы
одно число в такое, что 
— простое число. Докажите, что можно подчеркнуть не более 
чисел так, чтобы для каждого
неподчеркнутого числа а нашлось подчеркнутое число 
для которого 
— простое число.
Подсказка 1
Пусть числа будут вершинами. Ребром соединим числа, модуль разности которых равен простому числу. Попробуйте разбить вершины на две группы так, чтобы в первой было не больше половины вершин и каждая вершина из второй группы была соединена с хотя бы одной вершиной из первой группы.
Подсказка 2
Попробуйте для этого применить раскраску графа в 2 цвета.
Подсказка 3
Возьмите произвольную вершину А и покрасьте еë в красный. Еë соседей покрасьте в синий. Соседей соседей, которые ещë не покрашены - в красный. Что можно увидеть в графе, раскрашенном таким образом?
Рассмотрим граф, в котором вершины — числа, ребро проводится, если модуль разности этих чисел — простое число. Будем красить каждую компоненту связности этого графа в два цвета: сначала покрасим любую вершину в красный. Затем покрасим всех её соседей в синий. Затем всех соседей синих, которые ещё не покрашены, в красный. Затем соседей красных в синий. И так далее. Легко видеть, что у каждой красной вершины будет хотя бы один синий сосед, а у каждой синей — хотя бы один красный. В каждой компоненте связности выберем цвет, вершин которого не более половины, и подчеркнем вершины этого цвета. Каждая неподчеркнутая вершина будет соединена хотя бы с одной подчеркнутой.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
