13-ші «Жібек жолы» математикалық олимпиадасы, 2013 жыл

Фильмде $n$ рөл бар. Әр $i$ үшін $(1\le i\le n)$, $i$ рөлін ${{a}_{i}}$ адам ойнай алады және де бір адам тек бір ғана рөл ойнай алады. Әр күн сайын $n$ рөлдің адамдары кастингке қатысады, және әр рөлден тек бір адам қатысады. Жай $p$ саны $p \ge {{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{n}}$, $n$ болатындай сан болсын. Егер әр түрлі рөлдерде ойнайтын кез келген $k$ адам алсақ, олар қандай да бір кастингке бірге қатысатындай ${{p}^{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$ человек разных ролей нужный кастинг был проведен.