|
|
 |
Условие
Можно ли расставить в вершинах куба натуральные числа так, чтобы в каждой паре чисел, связанных ребром, одно из них делилось на другое, а во всех других парах такого не было?
Решение
Отметим четыре вершины куба, никакие две из которых не соединены ребром, и поместим в них четыре различных простых числа (например, 2, 3, 5, 7). В каждую из остальных вершин поместим произведение чисел, стоящих в отмеченных вершинах, соединенных с ней рёбрами (их ровно три). Легко видеть, что все требования выполнены.
Ответ
Можно.
Замечания
1. Идеология. Направим на каждом ребре стрелку от делимого к делителю. Не должно возникнуть маршрутов из пар стрелок в одном направлении – иначе число в начале маршрута разделится на число в его конце, а они не соседи. Значит, надо расставить стрелки так, чтобы на каждом маршруте направления чередовались. Такая расстановка стрелок есть на любом двудольном графе (куб – его частный случай): раскрасим вершины в чёрный и белый цвета и направим все стрелки в чёрные вершины. Теперь и вся конструкция легко обобщается: в чёрные вершины поместим различные простые числа, а в каждую белую – произведение чисел на концах выходящих из неё стрелок.
2. 5 баллов.
