Maths Olympiad Prep

Library / /22 of 28

Number theory Difficulty 8.2 Shortlist Prove it Hong Kong

a. Given that (1+x)p2=1+a1x+a2x2++ap2xp2(1+x)^{p-2} = 1 + a_1x + a_2x^2 + \dots + a_{p-2}x^{p-2} where pp is an odd prime number, prove that a1+2,a23,a3+4,,ap3(p2)a_1 + 2, a_2 - 3, a_3 + 4, \dots, a_{p-3} - (p-2) and ap2+(p1)a_{p-2} + (p-1) are all multiples of pp.

b. How many integer solutions are there to the equation x1+x2+x3+x4=100x_1 + x_2 + x_3 + x_4 = 100 where 1x110,0x211,1x312-1 \le x_1 \le 10, 0 \le x_2 \le 11, 1 \le x_3 \le 12 and x450x_4 \ge 50?

Solution

a.
Note that the numbers are
ak+(1)k+1(k+1)=(p2k)+(1)k+1(k+1)=(p2)(p3)(p1k)k!+(1)k+1(k+1) \begin{aligned} a_k + (-1)^{k+1}(k+1) &= \binom{p-2}{k} + (-1)^{k+1}(k+1) \\ &= \frac{(p-2)(p-3)\cdots(p-1-k)}{k!} + (-1)^{k+1}(k+1) \end{aligned}
where 1kp21 \le k \le p-2. Since
(p2)(p3)(p1k)(2)(3)(1k)=(1)k(k+1)!(modp) (p-2)(p-3)\cdots(p-1-k) \equiv (-2)(-3)\cdots(-1-k) = (-1)^k(k+1)! \pmod{p}
and pk!p \nmid k!, we have
ak+(1)k+1(k+1)(1)k(k+1)+(1)k+1(k+1)=0(modp). a_k + (-1)^{k+1}(k+1) \equiv (-1)^k(k+1) + (-1)^{k+1}(k+1) = 0 \pmod{p}.

b.
The answer is 1728.
For each choice of x1,x2,x3x_1, x_2, x_3 satisfying the inequalities, we have
x4=100x1x2x3100101112>50. x_4 = 100 - x_1 - x_2 - x_3 \ge 100 - 10 - 11 - 12 > 50.
Therefore, it suffices to count the number of triples (x1,x2,x3)(x_1, x_2, x_3) satisfying the inequalities. The answer is
(10(1)+1)(110+1)(121+1)=123=1728. (10 - (-1) + 1)(11 - 0 + 1)(12 - 1 + 1) = 12^3 = 1728.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.