Дана строка, состоящая из целых чисел от 1 до 15. Любые два различных числа от 1 до 15 встречаются рядом в этой строке. Какое наименьшее количество чисел может быть в этой строке?

Спасибо огромное!!!!

Сначала ограничим ответ снизу.Очевидно, самый оптимальный вариант - когда ни одна пара чисел в строке не повторяется. Т.е., каждый раз, когда какое-то число (кроме первого) встречается в строке, оно "исключает" двух своих соседей. Тогда каждое число должно встретиться в строке хотя бы 7 раз, т.к. входит состав 14 различных пар чисел. Число, которое стоит первым в строке, должно встретиться хотя бы 8 раз, т.к. на первой позиции у него только один "сосед".Получаем нижнюю границу 14*7 + 8 = 106Покажем, что эта граница достижима. Для этого достаточно привести пример такой строки. Далее я опишу один из возможных способов.Выпишем все возможные (цикличные) цепочки чисел 1..15 со сдвигами 1..71:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12:1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 13:1 4 7 10 13 12 5 8 11 14 13 6 9 12 15 14:1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 15:1 6 11 12 7 12 23 8 13 34 9 14 45 10 15 56:1 7 13 4 10 12 8 14 5 11 23 9 15 6 12 37:1 8 15 7 14 6 13 5 12 4 11 3 10 2 9 1{кстати, можно заметить, что цепочки из 15 чисел образуются сдвигами, не имеющими общих делителей с числом 15, хотя это не имеет особого значения для задачи}Очевидно, что в цепочках с разными сдвигами не могут встретиться одинаковые пары чисел.Так же заметим, что числа в строке можно заменять на цепочки, начинающиеся и оканчивающиеся на это число, и это не образует одинаковых пар чисел.То есть, чтобы построить искомую строку, можно взять цепочку 1 2 .. 14 15 1 и по своему усмотрению вставить в нее цепочки с другими сдвигами. Например:1 4 7 10 13 1 6 11 1 7 13 4 10 12 5 8 11 14 2 7 12 2 8 14 5 11 23 6 9 12 15 3 8 13 3 9 15 6 12 34 9 14 45 10 15 56 7 8 9 10 11 12 13 14 151 3 5 7 9 11 13 15 2 4 6 8 10 12 141 5 9 13 2 6 10 14 3 7 11 15 4 8 121 8 15 7 14 6 13 5 12 4 11 3 10 2 9 1{здесь я заменил числа 1, 2, 3 на тройки коротких цепочек, числа 4, 5 на короткие цепочки, а число 1, стоящее в конце, на три длинные цепочки}Получилась строка из 106 чисел, где каждая пара встречается один раз, что и требовалось.