Можно ли поставить в ряд все натуральные числа от 1 до 100 так, чтобы каждые два соседних числа отличались либо на 3, либо в три раза?

задан 18 Мар '17 11:59

2

Задача напомнила эту. Здесь возникает несколько "вынужденных" фрагментов цепочки (если она существует), но появляются разветвления, и требуется какой-то перебор. Ответ, скорее всего, положительный, но конкретный пример я пока не построил.

(18 Мар '17 13:51) falcao
1

@falcao , пока большое спасибо и на этом.

(18 Мар '17 16:55) Аллочка Шакед
10|600 символов нужно символов осталось
1

Построил-таки пример. Самому понравилось!

Для начала создадим цепочку, в который входят все числа, не делящиеся на три, а также 3, 6 и 9. Легко понять, что цепочка на концах должна иметь числа 100 и 98. От 100 образуем арифметическую прогрессию из всех чисел, дающих остаток 1 от деления на три: 100, 97, ... , 4, 1. От 98 образуем такую же прогрессию из чисел, для которых остаток равен двум: 98, 95, ... , 5, 2. Теперь соединяем концы следующим образом: 1, 3, 9, 6, 2. Осталось "пристроить" числа, кратные трём, от 12 до 99, что мы сейчас и сделаем.

Для удобства произведём временную перекодировку: будем рассматривать числа, уменьшенные втрое, от 4 до 33. При этом соседние числа должны будут отличаться или на 1, или в три раза. Построим две такие цепочки: 14, 15, 16, ... , 33, 11 и 13, 12, 4, 5, 6, ... , 10. Теперь утроим все эти значения, получая цепочки от 42 до 33 и от 39 до 30. Добавим к ним слева и справа по числу: 14, 42, ... , 33, 11 и 13, 39, ... , 30, 10. Теперь заметим, что в том "малом" цикле, который мы построили в начале, числа 14 и 11 соседствуют, и то же для чисел 13 и 10. Осталось разорвать каждое из этих двух соседств, и вставить на это место две приготовленные цепочки.

Итоговая конструкция выглядит так: 100, 97, 94, 91, 88, 85, 82, 79, 76, 73, 70, 67, 64, 61, 58, 55, 52, 49, 46, 43, 40, 37, 34, 31, 28, 25, 22, 19, 16, 13, 39, 36, 12, 15, 18, 21, 24, 27, 30, 10, 7, 4, 1, 3, 9, 6, 2, 5, 8, 11, 33, 99, 96, 93, 90, 87, 84, 81, 78, 75, 72, 69, 66, 63, 60, 57, 54, 51, 48, 45, 42, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98.

Будучи по специальности "комбинаторщиком", получил истинное удовольствие от этой задачи!

ссылка

отвечен 18 Мар '17 22:46

@falcao , ой, циклопическое Вам спасибо! Мне Ваш пример тоже чудовищно понравился.

(19 Мар '17 1:12) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,066
×1,032
×336
×225
×209

задан
18 Мар '17 11:59

показан
1649 раз

обновлен
19 Мар '17 1:12

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

по почте:

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

по RSS:

Ответы

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

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