XII математическая олимпиада «Шелковый путь», 2013 год

В фильме есть $n$ ролей. Для каждого $i$ ($1 \le i \le n$), роль номер $i$ могут сыграть $a_i$ человек, причем один человек может играть только одну роль. Ежедневно проводится кастинг, в котором участвуют люди из $n$ ролей, причем от каждой роли только один человек. Пусть $p$ простое число такое, что $p \ge a_1, \ldots, a_n, n$. Докажите, что можно провести $p^k$ кастингов таких, что если взять любые $k$ человек, которые снимаются в разных ролях, то они вместе участвовали в каком-то кастинге ($k$ натуральное число, не превосходящее $n$).

Комментарий/решение

Очевидно, что можно взять $n=p,a_1=\ldots=a_p=p.$ Давайте для каждой роли пронумеруем ее участников числами $0, 1, \ldots, p-1.$ Теперь рассмотрим все многочлены $g(x)=a_1+a_2x+\ldots+a_kx^{k-1},$ где $a_i=0, 1, \ldots, p-1.$ Их количество ровно $p^k.$ Давайте проведем кастинги

$$\{g(0), g(1), \ldots, g(p-1)\},$$

где на $j$ роли играет участник под номером $g(j-1) \mod p.$

По интерполяционному многочлену Лагранжа можно подобрать такой искомый $g,$ что $g(\alpha_j)\equiv \beta_j \pmod p,$ для $j=1,\ldots, k$ и любых $\alpha_j,\beta_j\in \{0,1,\ldots, p-1\},$ где $\alpha_j$ попарно различные. Отсюда легко вывести, что для любого набора из $k$ человек разных ролей нужный кастинг был проведен.