Maths Olympiad Prep

Library / /73 of 520

Number theory Difficulty 5.5 AIME, harder Prove it

17. (GBR 1) IMO3{ }^{\mathrm{IMO} 3} Let k,mk, m, and nn be positive integers such that m+k+1m+k+1 is a prime number greater than n+1n+1. Write csc_{s} for s(s+1)s(s+1). Prove that the product (cm+1−ck)(cm+2−ck)⋯(cm+n−ck)\left(c_{m+1}-c_{k}\right)\left(c_{m+2}-c_{k}\right) \cdots\left(c_{m+n}-c_{k}\right) is divisible by the product c1c2⋯cnc_{1} c_{2} \cdots c_{n}.

Solution

17. Using cr−cs=(r−s)(r+s+1)c_{r}-c_{s}=(r-s)(r+s+1) we can easily get
(cm+1−ck)⋯(cm+n−ck)c1c2⋯cn=(m−k+n)!(m−k)!n!⋅(m+k+n+1)!(m+k+1)!(n+1)! \frac{\left(c_{m+1}-c_{k}\right) \cdots\left(c_{m+n}-c_{k}\right)}{c_{1} c_{2} \cdots c_{n}}=\frac{(m-k+n)!}{(m-k)!n!} \cdot \frac{(m+k+n+1)!}{(m+k+1)!(n+1)!}
The first factor (m−k+n)!(m−k)!n!=(m−k+nn)\frac{(m-k+n)!}{(m-k)!n!}=\binom{m-k+n}{n} is clearly an integer. The second factor is also an integer because by the assumption, m+k+1m+k+1 and (m+k)!(n+1)!(m+k)!(n+1)! are coprime, and (m+k+n+1)!(m+k+n+1)! is divisible by both; hence it is also divisible by their product.

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.