Олимпиадная задача по комбинаторике: пирожные Алёши и Серёжи — 10-11 класс
У Алёши есть пирожные, разложенные в несколько коробок. Алёша записал, сколько пирожных в каждой коробке. Серёжа взял по одному пирожному из каждой коробки и положил их на первый поднос. Затем он снова взял по одному пирожному из каждой непустой коробки и положил их на второй поднос – и так далее, пока все пирожные не оказались разложенными по подносам. После этого Серёжа записал, сколько пирожных на каждом подносе. Докажите, что количество различных чисел среди записанных Алёшей равно количеству различных чисел среди записанных Серёжей.
Разобрать решение
Пусть Алёша записал k различных чисел n1 < n2 < ... < nk. Первое из записанных Серёжей чисел равно числу N1 коробок. Оно будет записано ровно n1 раз. После этого часть коробок опустеет, и следующее по величине число N2, записанное Серёжей, равно количеству коробок, где изначально было более n1 пирожных. Оно будет записано n2 раз. И т.д. Последнее по величине из записанных Серёжей чисел (Nk) равно количеству коробок, где изначально было nk пирожных.
Обсуждение
0Комментариев пока нет.