Question

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

Answer 1

1. Нижняя оценка:
- каждое число участвует всего в 13 парах
- при каждом включении в строку, число образует не больше двух пар
=> каждое число должно быть включено в строку хотя бы 7 раз
Тогда наименьшее количество чисел не менее 7*14 = 98

2. Эта оценка достижима. Пример строки:

1 4 7 10 13 2 5 8 11 14 3 6 9 12
1 6 11 2 7 12 3 8 13 4 9 14 5 10
1 3 5 7 9 11 13
1 5 9 13 3 7 11
1 7 13 5 11 3 9 1
2 4 6 8 10 12 14
2 6 10 14 4 8 12
2 8 14 6 12 4 10 2
3 4 5 6 7 8 9 10 11 12 13 14
1 8 2 9 3 10 4 11 5 12 6 13 7 14

Ответ: 98

Answer 2

Для решения данной задачи, давайте посмотрим на минимально возможное количество чисел в строке, удовлетворяющее условию.

Наименьшее количество чисел в строке

Для того чтобы каждое из чисел от 1 до 14 встречалось рядом с другими различными числами, мы можем использовать следующую последовательность: 1, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8, 7, 9, 8, 10, 9, 11, 10, 12, 11, 13, 12, 14, 13. В этой последовательности каждое число от 1 до 14 встречается рядом с другими различными числами.

Таким образом, наименьшее количество чисел в строке, удовлетворяющее условию, составляет 27 чисел.

Ответ

Наименьшее количество чисел в данной строке, удовлетворяющее условию, составляет 27.