Question

Оля написала в строчку несколько различных натуральных чисел, не превосходящих 10. София заметила, что в любой паре соседних чисел одно из них делится на другое. Какое наибольшее количество чисел могла выписать Оля?

Answer 1

Заметим, что среди натуральных чисел от 1 до 10, для числа 7 может быть парой цифра 1 и только. Поэтому если выписали число 7, то оно будет скраю.

Число 5 может быть в паре с 1 или 10. Таким образом, если встречается число 5, то оно будет между 1 и 10.

Пока получается последовательность 7, 1, 5, 10.

В паре к 10 будет 2. Далее 6, 3, 9 или 4, 8 (для максимального кол-ва).

Получаем следующие последовательности:

7, 1, 5, 10, 2, 6, 3, 9 (8 чисел);

7, 1, 5, 10, 2, 4, 8 (7 чисел).

Если бы число 5 не встречалось, то максимум получилось 10-1-1=8 чисел.

А теперь, рассмотрим случай, когда число 7 не выписывали. Тогда максимум может быть 10-1=9 чисел.

5, 10, 1, 9, 3, 6, 2, 4, 8 (9 чисел).

Наибольшее количество чисел 9.

Ответ: 9.

Answer 2

Наибольшее количество чисел, которое могла выписать Оля, равно 4.

Чтобы показать это, рассмотрим все возможные комбинации пар чисел, которые могут быть записаны Олей:

1. (1, 1) - оба числа делятся друг на друга.
2. (2, 1) - 2 делится на 1.
3. (3, 1) - 3 делится на 1.
4. (4, 1) - 4 делится на 1.
5. (2, 2) - оба числа делятся друг на друга.
6. (3, 2) - 3 делится на 2.
7. (4, 2) - 4 делится на 2.
8. (3, 3) - оба числа делятся друг на друга.
9. (4, 3) - 4 делится на 3.
10. (4, 4) - оба числа делятся друг на друга.

Всего получаем 10 пар чисел. Однако, каждая пара чисел может быть представлена только одним числом, так как одно из чисел делится на другое. Таким образом, Оля может выписать не более 10/2 = 5 чисел. Однако, из условия задачи следует, что все числа должны быть различными, поэтому наибольшее количество чисел, которое может выписать Оля, равно 4.