На доске написаны все натуральные числа от 1 до 20. Какое наименьшее количество чисел можно стереть с доски, чтобы никакие три из оставшихся не являлись последовательными членами геометрической прогрессии? Напомним, что три числа образуют геометрическую прогрессию, если квадрат второго из них равен произведению первого на третье.
Оценка: Пусть мы стёрли не больше 4 чисел. Значит, на доске осталось не меньше 16 чисел. Посмотрим, какие числа могли остаться. Числа 7, 11, 13, 14, 15, 17, 19 не могут участвовать ни в каких прогрессиях, поэтому их вычёркивание ни на что не повлияет, а лишь увеличит ответ. Осталось 13 чисел, среди которых надо оставить не меньше девяти чисел. Разобьём 12 из этих чисел на следующие тройки: (1, 3, 9); (2, 6, 18); (4, 8, 16); (5, 10, 20). Числа в каждой тройке составляют геометрическую прогрессию, а значит из каждой тройки мы можем оставить не более 2 чисел, то есть всего не более 8 чисел. Следовательно, число 12, не вошедшее ни в одну тройку, должно остаться на доске.
Прогрессии, содержащие число 12 следующие: (3, 6, 12); (9, 12, 16); (8, 12, 18). Число 12 точно осталось на доске, значит, из каждой тройки помимо числа 12 должно остаться не более одного числа, то есть суммарно из всех троек мы можем оставить на доске не более 4 чисел. Надо оставить ещё не менее 5 чисел, которые можно выбирать только среди чисел 1, 2, 4, 5, 10, 20. Однако, выбирая не менее 5 чисел, на доске останется одна из прогрессий (1, 2, 4) или (5, 10, 20), чего быть не может. Таким образом, стереть с доски меньше 5 чисел нельзя.
Ответ: 5 чисел. Пример: 4, 6, 9, 10, 12.