СПбГУ 2023, 10-11 классы, задача 1
( баллов) В каждой клетке таблицы записано натуральное число. В каждой строке имеется по крайней мере различных чисел, а в каждых четырех последовательных строках не более различных чисел. Какое наибольшее количество различных чисел может быть в таблице?
Ответ: .
Решение. В одной строке не менее различных чисел, поэтому в следующих трех строках вместе появляется не более новых чисел. Стало быть, первые четыре строки содержат не более различных чисел, а каждые следующие три строки дают не более новых чисел и всего чисел не больше, чем .
Приведем пример на чисел. Занумеруем строки числами от до . В первой строке поставим числа от до , а в строке с номерами от до поставим числа до и числа от до . Тогда в каждой ствоке будет уникальных чисел и еще числа от до , т.е. ровно различных чисел, а в каждых четырех строках будет ровно различных чисел. Таким образом, в таблице будут числа от до .
Замечание. Доказать, что количество различных чисел в таблице не превосходит можно доказать и по индукции. А именно, доказать, что в любых подряд идущих строках расположено не более чем различных чисел. База верна по условию. Установим переход от к . Рассмотрим подряд идущие строки. Пусть в четвертой с конца строке имеется различных чисел. Тогда в трех самых нижних строках не более чем различных чисел. А в оставшихся строке по индукционному предположению не больше чисел. Поэтому всего различных чисел будет более чем .