silk road castings

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

silk road castings

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: SRMC 2013 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30627 posts

#1 h Sep 2, 2018, 4:41 PM • 2 Y

Y by Adventure10, Mango247

In the film there is $n$ roles. For each $i$ ( $1 \le i \le n$ ), the role of number $i$ can play $a_i$ a person, and one person can play only one role. Every day a casting is held, in which participate people for $n$ roles, and from each role only one person. Let $p$ be a prime number such that $p \ge a_1, \ldots, a_n, n$ . Prove that you can have $p^k$ castings such that if we take any $k$ people who are tried in different roles, they together participated in some casting ( $k$ is a natural number not exceeding $n$ ).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1277 posts

#2 h Sep 2, 2018, 7:55 PM • 2 Y

Y by Adventure10, Mango247

Problem proposers are becoming professionals at hiding graph theory.

This post has been edited 3 times. Last edited by skrublord420, Sep 2, 2018, 7:56 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

578 posts

#3 h Mar 6, 2019, 12:26 AM • 2 Y

Y by Abidabi, Adventure10

Let me try to make the problem statement more clear:

In a film there are $n$ roles. For each $i$ ( $1 \leq i \leq n$ ), the $i$ th role has $a_i$ people trying out for that role, and no person is trying out for multiple roles. Every day, a tryout is held, in which exactly one competitor for each of the $n$ roles tries out. Suppose that $p$ is a prime number such that $p \geq a_1, a_2, \cdots, a_n, n.$ Show that in $p^k$ days of tryouts, we can ensure that any $k$ people trying out for different roles have acted for the film together ( $k \leq n$ ).

Solution:

Clearly, we may assume that $a_1, a_2, \cdots, a_n, n$ are all $p$ , since this would make our job "strictly harder." (In other words, if $a_i < p$ we can just take a subset of the tryouts for the case when $a_i = p$ and if $n < p$ , then we just add an $a_{n+1}$ then ignore the extra roles in each tryout for $n+1$ ). In this case, we have $p$ roles and $p$ people vying for each role. Let's label the roles $r_0, r_1, \cdots, r_{p-1}.$ Observe that there are $p^k$ integer polynomials of the form $c_{k-1} x^{k-1} + \cdots + c_1 x + c_0$ where the $c_i$ 's are all residue classes (mod $p$ ). Let $P_1, P_2, \cdots, P_{p^k}$ be these $p^k$ integer polynomials. Then, for each $P_i$ , on the $i$ th day of casting, we will let the $P_i(j)$ th person try out for the role $r_j$ . To see that this covers all groups of $k$ people in different roles, simply use Lagrange Interpolation, keeping in mind the fact that $k \leq p$ .

This post has been edited 1 time. Last edited by Pathological, Mar 6, 2019, 12:26 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a