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$). ( Сатылханов К. )
посмотреть в олимпиаде

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