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

Решается данная задача следующим образом 9 чисел расставить можно, например, так: 10, 5, 1, 9, 3, 6, 2, 4, 8. Докажем, что десять чисел расставить нельзя. Если бы это можно было сделать, то число 7 стояло бы с краю рядом с числом 1. Отбросим эти два числа и попытаемся расставить остальные 8 чисел. Очевидно, что с краю должно стоять число 5 (рядом с числом 10), а с другого края - число 9 (рядом с числом 3). Тогда числа 2, 4, 8 должны стоять внутри, при этом 4 должно находиться между 2 и 8, а 8 - между 2 и 4. Противоречие доказывает, что 9 чисел - наилучший вариант.