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