ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98470
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Теория графов (прочее) ]
[ Делимость чисел. Общие свойства ]
[ Простые числа и их свойства ]
[ Шахматная раскраска ]
Сложность: 3+
Классы: 10,11
В корзину
Прислать комментарий

Условие

Можно ли расставить в вершинах куба натуральные числа так, чтобы в каждой паре чисел, связанных ребром, одно из них делилось на другое, а во всех других парах такого не было?


Решение

Отметим четыре вершины куба, никакие две из которых не соединены ребром, и поместим в них четыре различных простых числа (например, 2, 3, 5, 7). В каждую из остальных вершин поместим произведение чисел, стоящих в отмеченных вершинах, соединенных с ней рёбрами (их ровно три). Легко видеть, что все требования выполнены.


Ответ

Можно.

Замечания

1. Идеология. Направим на каждом ребре стрелку от делимого к делителю. Не должно возникнуть маршрутов из пар стрелок в одном направлении – иначе число в начале маршрута разделится на число в его конце, а они не соседи. Значит, надо расставить стрелки так, чтобы на каждом маршруте направления чередовались. Такая расстановка стрелок есть на любом двудольном графе (куб – его частный случай): раскрасим вершины в чёрный и белый цвета и направим все стрелки в чёрные вершины. Теперь и вся конструкция легко обобщается: в чёрные вершины поместим различные простые числа, а в каждую белую – произведение чисел на концах выходящих из неё стрелок.

2. 5 баллов.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1999/2000
Номер 21
вариант
Вариант весенний тур, тренировочный вариант, 8-9 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .