Решение задачи 243

Условие:

Дан произвольный граф. Надо расставить в его вершинах целые числа так, чтобы выполнялись два условия:

1) если две вершины соединены ребром, то числа в них имеют общий делитель;

2) если две вершины не соединены ребром, то числа в них взаимно просты.

Всегда ли можно так сделать?

Решение:

Можно. Пусть дан произвольный граф. Сначала к каждой вершине припишем число 1. Пронумеруем все ребра от 1 до n. Для всех i от 1 до n рассмотрим две вершины, которые соединены ребром с номером i. Домножим числа, которые к ним приписаны, на p_i (i-ое простое число). Тогда числа в вершинах, соединенные ребром, будут иметь общий делитель. Также из построения следует, что для любого p_i (1≤i≤n) ровно два числа из всех приписанных к ребрам делятся на p_i, причем они соединены ребром. Значит, числа, не соединенные ребром, взаимно просты.

Ответ: Да.