Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Vamos a probar que la respuesta es afirmativa. Para ello, observamos que el problema es equivalente a determinar si existen $n,a\in\mathbb{N_0}$ tales que $3n^2+2n+2=a^2$. Trabajando módulo 8, todo cuadrado perfecto es congruente con $0$, con $1$ ó con $4$, para lo que será suficiente comprobar que $3n^2+2n+2$ no es congruente con ninguno de estos tres números módulo $8$. Usando las propiedades de las congruencias, tenemos que

• Si $n\equiv 0\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 2\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 1\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 7\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 2\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 2\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 3\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 3\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 4\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 2\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 5\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 7\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 6\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 2\ (\mathrm{mod}\ 8)$.
• Si $n\equiv 7\ (\mathrm{mod}\ 8)$, entonces $3n^2+2n+2\equiv 3\ (\mathrm{mod}\ 8)$.

Por tanto, $3n^2+2n+2$ no es congruente con $0$, $1$ ó $4$ para ningún valor de $n\in\mathbb{Z}$ y hemos terminado.

Solución. La primera parte del problema consiste en ver exactamente en qué consiste $f(n,x)$. La forma de meter $n-x$ bolas en $x+1$ cajas equivale a escoger $x$ elementos de un conjunto de $n=(n-x)+(x+1)-1$, que actúan como separadores. Por tanto, se tiene que $f(n,x)=\binom{n}{x}$.

El problema puede formularse entonces como encontrar las filas del triángulo de Pascal que sean completamente divisibles por un primo $p$ dado (excluyendo los extremos $\binom{n}{0}=\binom{n}{n}=1$). Es un resultado relativamente conocido que esto ocurre si y sólo si $n=p^a$ para cierto $a\geq 1$. Vamos a demostrarlo usando el hecho de que \[\binom{n}{x}=\frac{n!}{x!(n-x)!}\] para lo que compararemos el exponente de $p$ en el numerador y en el denominador. A este efecto, usaremos que el exponente del primo $p$ en la factorización de $x!$ está dado por \[e_p(x!)=\sum_{i=1}^\infty\left\lfloor\frac{x}{p^i}\right\rfloor,\] siendo $\lfloor z\rfloor$ la función parte entera. Distinguimos dos casos:

• Si $n=p^a$, entonces tenemos por un lado que \[e_p(n!)=\left\lfloor\frac{p^a}{p}\right\rfloor+\left\lfloor\frac{p^a}{p^2}\right\rfloor+\ldots+\left\lfloor\frac{p^a}{p^a}\right\rfloor=p^{a-1}+p^{a-2}+\ldots+1.\] Por otro lado, se cumple que \begin{align*}\left\lfloor\frac{x}{p^i}\right\rfloor+\left\lfloor\frac{p^a-x}{p^i}\right\rfloor&=\left\lfloor\frac{x}{p^i}\right\rfloor+p^{a-i}\left\lfloor\frac{-x}{p^i}\right\rfloor=\begin{cases}p^{a-i}&\text{si }p^a\mid x,\\p^{a-i}-1&\text{si }p^a\not\mid x,\end{cases} \end{align*} Para $i=a$, en la expresión anterior se tiene como resultado $-1$ ya que $p^a\not\mid x$ al ser $x\lt n= p^a$. Por lo tanto, se tiene una desigualdad estricta \[e_p(x!)+e_p((p^a-x)!)\lt p^{a-1}+p^{a-2}+\ldots+1=e_p(n!)\] y deducimos que $\binom{n}{x}$ es múltiplo de $p$.
• Supongamos ahora que $n$ no es potencia de $p$, luego existe $a$ tal que $p^a\lt n\lt p^{a+1}$. Podemos escribir entonces $n=kp^a+m$ para $0\lt k\lt p$ y $0\leq m\lt p^a$. Tomaremos $x=p^a$ y veremos que $\binom{n}{x}$ no es múltiplo de $p$. Para ello, procedemos como en el apartado anterior, calculando \begin{align*} e_p(n!)&=\left\lfloor\frac{kp^a+m}{p}\right\rfloor+\left\lfloor\frac{kp^a+m}{p^2}\right\rfloor+\ldots+\left\lfloor\frac{kp^a+m}{p^a}\right\rfloor\\ &=k(p^{a-1}+p^{a-2}+\ldots+1)+\left\lfloor\frac{m}{p}\right\rfloor+\left\lfloor\frac{m}{p^2}\right\rfloor+\ldots+\left\lfloor\frac{m}{p^{a-1}}\right\rfloor. \end{align*} Ahora bien, tenemos también que \begin{align*} e_p(x!)&=\left\lfloor\frac{p^a}{p}\right\rfloor+\left\lfloor\frac{p^a}{p^2}\right\rfloor+\ldots+\left\lfloor\frac{p^a}{p^a}\right\rfloor=p^{a-1}+p^{a-2}+\ldots+1\\ e_p((n-x)!)&=\left\lfloor\frac{(k-1)p^a+m}{p}\right\rfloor+\left\lfloor\frac{(k-1)p^a+m}{p^2}\right\rfloor+\ldots+\left\lfloor\frac{(k-1)p^a+m}{p^a}\right\rfloor\\ &=(k-1)(p^{a-1}+p^{a-2}+\ldots+1)+\left\lfloor\frac{m}{p}\right\rfloor+\left\lfloor\frac{m}{p^2}\right\rfloor+\ldots+\left\lfloor\frac{m}{p^{a-1}}\right\rfloor \end{align*} De aquí se deduce claramente que $e_p(x!)+e_p((n-x)!)=e_p(n!)$, luego $\binom{n}{x}$ no es divisible por $p$.

Nota. Un teorema muy interesante de Kummer nos dice que si $p^\alpha$ divide a $\binom{n}{k}$ si y sólo si, cuando sumamos $x$ y $n-x$ en base $p$ hay exactamente $\alpha$ llevadas. En el caso $n=p^a$, tenemos que $x+(n-x)=p^a$ tiene más cifras que $x$ y $n-x$, luego necesariamente hay alguna llevada. En el caso $n=kp^a+m$ y $x=p^a$, tenemos que $n=(k-1)p^a+m$, luego en la suma $x+(n-x)$ no hay llevadas. Esto (u otros resultados similares) podrían usarse en una olimpiada si se citan correcta e inequívocamente.