6
1

Мохно ли натуральные числа от 1 до 32 расположить в ряд так, чтобы сумма любых двух рядом стоящих чисел являлась точным квадратом? Можно ли расположить эти же числа по кругу с выполнением того же условия? Оценить единственность решения.

задан 14 Дек '16 2:24

изменен 11 Янв 1:58

%D0%9A%D0%B0%D0%B7%D0%B2%D0%B5%D1%80%D1%82%D0%B5%D0%BD%D0%BE%D1%87%D0%BA%D0%B0's gravatar image


4.8k210

1

В ряд удалось расположить, а по кругу пока нет. Решение не единственно. Там надо немного "прикинуть" и проверить. Задача весьма симпатично звучит, и хорошо интерпретируется в терминах графов как иллюстрация некоторых понятий.

(14 Дек '16 11:35) falcao

@falcao интересно, а какие там иллюстрируются понятия кроме Гамильтоновой цепи в неориентированном графе?

(14 Дек '16 15:20) abc
1

@abc: помимо гамильтоновости, ещё полугамильтоновость. Разницу часто иллюстрируют на примере графа Петерсена. Но этот пример интереснее по содержанию.

(14 Дек '16 18:25) falcao
2

@falcao, на всякий случай указываю источник задачи, - Н.Х. Агаханов и др..., "Всероссийские олимпиады...", №_105. Только там 16 чисел, и задача существенно проще. А ещё 16 чисел я "от нашего столика" добавил...

(14 Дек '16 20:53) kipot_l
2

@kipot_l: и получилась отличная задача! Дело в том, что циклическое решение здесь существует и единственно. Я вчера нашёл "цепочку", а сегодня в процессе рассуждений нашёл цикл, и заодно доказал, что он всего один. Сейчас изложу.

(14 Дек '16 21:47) falcao
10|600 символов нужно символов осталось
5

Для начала пример цикла из 32 чисел:

1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

Теперь дадим набросок доказательства единственности (всё делалось вручную, без использования компьютера).

Для некоторых чисел однозначно определяется, между чем и чем они находятся в цикле. Например, соседями 32 могут быть только 4 и 17. Аналогично для чисел 31, 30, ... , 25.

Мы получаем несколько "цепочек", и теперь их начинаем "склеивать" там, где это однозначно. Обратим внимание на тройку 5 31 18. Дальше может идти только 7 ввиду невозможности группировки с самим собой, и получается 5 31 18 7 29 20. Здесь новая "склейка": поскольку 20 нельзя соединить с 5 из-за короткого цикла, дальше может идти только 16, которое в сумме уже не даёт 49, и за ним следует 9. А это число уже было как сосед 27, и мы получили такую цепь: 5 31 18 7 29 20 16 9 27 22. Всё это совершенно однозначно.

Теперь соседи числа 30, а это 6 и 19, не могут "замкнуться", и тогда за 19 идёт только 17, что уже было, и мы имеем вторую длинную цепь 6 30 19 17 32 4. В итоге половина чисел уже "оприходована". Беря соседей 28, видим, что 8 не группируется с собой, а число 17 уже занято. Остаётся единственная возможность в виде единицы, что даёт 1 8 28 21.

Теперь обратим внимание на число 2, которое само с собой не группируется, а 7 уже занято. Значит, оно расположено между 14 и 23. Получаем цепочку 10 26 23 2 14. Наконец, для 13 теперь пропала возможность 23, что даёт цепочку 3 13 12.

Все числа были упомянуты кроме 15, у которого в принципе может быть три соседа: 1, 10, 21. Ясно, что 1 и 21 одновременно быть не могут, так как это начало и конец цепочки. Значит, 15 находится рядом с 10.

Далее остаётся два варианта. Случай, когда по другую сторону от 15 находится 1, однозначно ведёт к построенному выше примеру. Второй случай приводит к противоречию. Цепочка 14 -- 10 15 21 -- 1 3 -- 12 может быть продолжена или числом 4, или числом 24. Но после 4 далее будет 6 (по цепочке), а к нему подходят только уже использованные 3 и 10. А после 24 у нас идёт цепочка к 11, а за ней 5, так как на 14 замыкать раньше времени нельзя. Потом 5 -- 22, и далее только к 14, что даёт более короткий цикл, в котором отсутствует цепь между 4 и 6.

ссылка

отвечен 14 Дек '16 22:17

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×294
×5

задан
14 Дек '16 2:24

показан
698 раз

обновлен
11 Янв 1:58

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

по почте:

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

по RSS:

Ответы

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

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