Можно ли написать по кругу 8 различных целых положительных чисел, не превосходящих 25, если требуется, чтобы любые два соседних числа отличались на 5 или 7? Приведите пример или докажите, что это невозможно.

У меня получилось так: 25, 20, 13, 8, 1, 6, 11, 18, круг замкнулся.

Напрашивается вопрос, обязательно ли использовать число 25? Иными словами, можно ли написать по кругу 8 различных целых положительных чисел, не превосходящих 24, если требуется, чтобы любые два соседних числа отличались на 5 или 7?

Оказывается, и это можно: 20, 13, 6, 1, 8, 3, 10, 15, круг замкнулся.

А вот можно ли, чтобы все числа не превосходили 19? У меня, почему-то, не получается.

Пожалуйста, помогите решить. Заранее благодарю.

задан 12 Янв '17 16:43

изменен 12 Янв '17 16:49

10|600 символов нужно символов осталось
1

Я нарисовал граф всех связей между числами. Картинку не могу "приаттачить", но она имеет простой вид. Это плоский граф, центрально-симметричный относительно вершины 10. Для остальных вершин, номер n симметричен номеру 20-n.

Рисуем два "ромбика": вправо от 10 идут 10-17-12 вверху и 10-5-12 внизу. Слева -- симметрично, от 10 через одно число к 8. Далее справа от 12 идёт "ромбик" к числу 14 в противоположной вершине, а для 14 противоположной будет 2. Слева всё по симметрии. Вершину 9 слева и 11 справа соединяем сверху через 4, а снизу через 16. Всё это легко рисуется.

Теперь рассуждение (его можно провести и так, но с рисунком проще проверять). В цикле из восьми вершин чередуются чётные и нечётные. Будем смотреть только на четыре чётных числа. Вершина 10 может "граничить" в цикле с 8 и 12 по разные стороны; от 12 идут связи к 2 и 14, а от 8 -- к 18 и 6. Уже отсюда ясно, что с участием 10 цикла длиной 8 с четырьмя чётными быть не может.

Если 10 не участвует, то в графе можно стереть всю "серединку". Между вершинами 11 и з возникает "двойной мост". Если по нему вообще не проходить, то граф будет несвязным, и в компонентах всего по 6 вершин. Если же от 11 до 9 проходить, то только через одну из двух вершин 4 или 16. Тогда получается две компоненты из 6 вершин, соединённые одним мостом, и циклы там могут быть только в компонентах.

ссылка

отвечен 12 Янв '17 18:43

@falcao , большое спасибо!

(12 Янв '17 18:49) Машакит Хилу...
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,404
×1,139
×376
×211
×139

задан
12 Янв '17 16:43

показан
745 раз

обновлен
12 Янв '17 18:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru