Maths Olympiad Prep

Library / /425 of 520

Combinatorics Difficulty 6.0 National olympiad Prove it

3. Let xx and nn be integers such that 1x<n1 \leq x < n. We have x+1x+1 distinct boxes and nxn-x identical balls. We call f(n,x)f(n, x) the number of ways to distribute the nxn-x balls into the x+1x+1 boxes. Let pp be a prime number. Find the integers nn greater than 1 for which the prime number pp is a divisor of f(n,x)f(n, x) for all x{1,2,,n1}x \in \{1, 2, \ldots, n-1\}.

Solution

SOLUTION. Clearly f(n,x)f(n, x) is the number of combinations with repetition of x+1x+1 elements taken from nxn-x in nxn-x. That is,

f(n,x)=CR(x+1,nx)=((x+1)+(nx)1nx)=(nx) f(n, x)=C R(x+1, n-x)=\left(\begin{array}{c} (x+1)+(n-x)-1 \\ n-x \end{array}\right)=\left(\begin{array}{l} n \\ x \end{array}\right)

We will prove that the nn sought are all of the form pap^{a} with aa a positive integer. Let mpm_{p} be the pp-part of the positive integer mm, that is, if m=paqm=p^{a} q (with q1q \geq 1 an integer), mp=pam_{p}=p^{a}, where a1a \geq 1 is an integer. Now we will prove the following preliminary result:

If mp=pam_{p}=p^{a}, then (mi)p=ip(m-i)_{p}=i_{p} for each i{1,2,,pa1}i \in\left\{1,2, \ldots, p^{a}-1\right\}.

Indeed, if ip=pki_{p}=p^{k} then k<ak<a and it is obvious that pk(mi)p^{k} \mid(m-i), so ip(mi)pi_{p} \leq(m-i)_{p}. Conversely, if (mi)p=pk(m-i)_{p}=p^{k}, it must be that k<ak<a because otherwise paip^{a} \mid i. Now, pkip^{k} \mid i because pkmp^{k} \mid m and pk(mi)p^{k} \mid(m-i). That is, (mi)pip(m-i)_{p} \leq i_{p}.

Next, we will prove that if pp is a prime and nn an integer greater than 1. Then pp divides (nx)\left(\begin{array}{l}n \\ x\end{array}\right) for all x{1,2,,n1}x \in\{1,2, \ldots, n-1\} if and only if n=pan=p^{a} with aa an integer.

If p(nx)p\left(\begin{array}{l}n \\ x\end{array}\right) for all x{1,2,,n1},p(n1)=nx \in\{1,2, \ldots, n-1\}, p\left(\begin{array}{l}n \\ 1\end{array}\right)=n. Setting np=pan_{p}=p^{a}, we have:

(npa)=n(n1)(npa+1)pa(pa1)21 \left(\begin{array}{c} n \\ p^{a} \end{array}\right)=\frac{n(n-1) \ldots\left(n-p^{a}+1\right)}{p^{a}\left(p^{a}-1\right) \ldots 2 \cdot 1}

and by the preliminary result, we conclude that the pp-part of (npa)\left(\begin{array}{c}n \\ p^{a}\end{array}\right) is 1, so n=pan=p^{a}.

Conversely, if n=pan=p^{a}, for each x{1,2,,pa1}x \in\left\{1,2, \ldots, p^{a}-1\right\},

(nx)=pa(pa1)(pax+1)x(x1)21 \left(\begin{array}{l} n \\ x \end{array}\right)=\frac{p^{a}\left(p^{a}-1\right) \ldots\left(p^{a}-x+1\right)}{x(x-1) \ldots 2 \cdot 1}

and again by the preliminary result, the pp-part of (nx)\left(\begin{array}{l}n \\ x\end{array}\right) is paxp\frac{p^{a}}{x_{p}}, which is a multiple of pp because x<pax<p^{a}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.