На международной студенческой олимпиаде по математике (IMC) в 2012 году была задача, предложенная санкт-петербургским математиком Фёдором Владимировичем Петровым.
Рассмотрим такие натуральные числа n, что (2012n)! делится на n!+1. Конечно или бесконечно множество таких чисел?
Здесь m!=1*2*3*...*(m-1)*m - произведение первых m натуральных чисел.
Решение задачи очень элегантно. Заметим, что числа (n!+1) и n! взаимно простые, т.е. не имеют общих делителей.
А ещё заметим, что (2012n)!/(n!)^2012 - натуральное число, потому что это решение комбинаторной задачи о разбиении 2012n различных предметов на 2012 групп по n предметов.
Значит, (2012n)!/(n!)^2012 должно делится на n!+1.
Но (2012n)!/(n!)^2012=С(2012n,n)*C(2011n,n)*...*C(3n,n)C(2n,n), где
C(n,k) - число способов выбрать k предметов из n различных предметов.
Но
C(2n,n)<2^(2n);
C(3n,n)<2^(3n);
...
C(2011n,n)<2^(2011n);
C(2012n,n)<2^(2012n).
Эти неравенства верны, потому что C(nk,n) - это число способов выбрать ровно n предметов из nk различных предметов,
а 2^(nk) - это число способов выбрать хоть сколько-нибудь предметов из nk различных предметов.
Поэтому
(2012n)!/(n!)^2012=С(2012n,n)*C(2011n,n)*...*C(3n,n)C(2n,n)<
<2^(2012n)*2^(2011n)*...*2^(3n)*2^(2n)=2^(2011*1007n).
Но известно (и даже легко доказать), что, начиная с некоторого n,
n!>2^(kn) для произвольного фиксированного k.
Значит, начиная с некоторого n,
(2012n)!/(n!)^2012 не сможет делиться нацело на n!+1.