$\text{gcd}(\binom{n}{k},\ldots,\binom{n+k}{k})=1$

[jordan]

Mostrare che se $n,k$ sono interi positivi tali che $n\ge k$ allora
$$\text{gcd}\left(\binom{n}{k},\binom{n+1}{k},\ldots,\binom{n+k}{k}\right)=1.$$

[Gottinger95]

Se diamo per buono il Teorema di Lucas (http://en.wikipedia.org/wiki/Lucas_theorem), allora il problema si riduce a

Testo nascosto:

Dimostrare che per ogni primo \(p\) esiste \(0 \le a_p \le k\) tale che le cifre di \(n+a_p\) in base \(p\) sono tutte maggiori o uguali alle cifre in base \(p\) di \(k\).
Per il teorema di Lucas, questo implica che \( p \nmid \binom{n+a_p}{k}\).

D'altronde, siano \(n= b_m p^m + \ldots + b_0, \ \ \ k = c_m p^m + \ldots + c_0\); consideriamo \(a_p = d_m p^m + \ldots + d_0\), dove
\[ d_i = \begin{cases} c_i - b_i, & \mbox{ se } c_i > b_i \\ 0, & \mbox{ altrimenti} \end{cases} \]
Evidentemente, guardando alle cifre, \(0 \le a_p \le k\) e le cifre di \(n+a_p\) sono uguali a quelle di \(k\) dove quelle di \(n\) sono minori, e maggiori di quelle di \(k\) dove quelle di \(n\) sono maggiori.

Ma forse è barare?

[jordan]

Non so se il teorema di Lucas sarebbe accettato in gara, ma oramai è diventato una tecnica standard di soluzione. Nonostante questo, esistono soluzioni piu' alla mano