Алгебра, сложное задание Маша написала на доске k>3 различных натуральных чисел, каждое из которых меньше (k−1)! Саша рассмотрел все возможные пары этих чисел, для каждой из них поделил большее число на меньшее с остатком и записал себе в тетрадку полученное неполное частное. Могут ли все Сашины числа оказаться различными?
Очень прошу обосновать ответ

Предыдущий
вопрос Следующий
вопрос

Давайте рассмотрим сначала число (k-1)!.

Поскольку все числа, написанные на доске Машей, меньше (k-1)!, то при делении на (k-1)! любого из этих чисел остаток будет не больше, чем (k-1).

Предположим, что все числа из тетрадки Саши оказались различными. Значит, у нас есть k(k-1)/2 различных неполных частных, где k - количество чисел Маши.

Поскольку каждое неполное частное при делении на (k-1)! имеет остаток не больше, чем (k-1), то количество возможных неполных частных не может превышать (k-1). При этом у нас есть k(k-1)/2 неполных частных, которые все различны. Противоречие, так как количество возможных неполных частных должно быть меньше, чем количество всех неполных частных.

Следовательно, все числа из тетрадки Саши не могут оказаться различными.