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

Solución. Sea $r^2$ el mayor cuadrado perfecto menor o igual que $n$ y sea $s^2$ el mayor cuadrado perfecto menor o igual que $n-r^2$. En otras palabras, $r$ y $s$ están determinados por las desigualdades \[r^2\leq n\lt (r+1)^2,\qquad s^2\leq n-r^2\lt(s+1)^2.\] Como estamos trabajando con enteros, estas desigualdades estrictas son equivalentes a las siguientes: \[r^2\leq n\leq r^2+2r,\qquad s^2\leq n-r^2\leq s^2+2s.\] Si $n=r^2+s^2$, entonces basta tomar $N=n$. En caso contrario, tenemos que $n\leq r^2+s^2-1$, en cuyo caso tomamos $N=r^2+(s+1)^2$. Para ver que se cumple lo que queremos, observemos que:

• de la desigualdad $n-r^2\lt(s+1)^2$ se deduce que $n\lt N$;
• de la desigualdad $s^2\leq n-r^2-1$, obtenemos que $N=r^2+(s+1)^2\leq n+2s$, luego \[N\leq n+2s\leq n+2\sqrt{n-r^2}\leq 2\sqrt{2r}\leq 2\sqrt{2}\sqrt[4]{n}.\]

Solución. Los múltiplos de $10$ y los múltiplos de $25$ no son números ondulantes ya que acaban en $0$, $25$ ó $75$. Vamos a probar que cualquier otro número $n$ divide a un número ondulante.

• Caso 1: $n$ no es múltiplo de $2$ ni de $5$. Dado $k\in\mathbb{N}$, se tiene que $\mathrm{mcd}((10^k-1)n,10^k)=1$, luego $10^{k\varphi(n)}\equiv 1\ (\text{mód}\ (10^k-1)n)$, donde $\varphi(n)$ es la función de Euler. Esto nos dice que \[A(k,n)=\frac{10^{k\varphi(n)}-1}{10^k-1}\] es un múltiplo de $n$ formado por ceros y unos, de forma que hay $k-1$ ceros entre cada par de unos. Por tanto, $A(2,n)$ es un múltiplo de $n$, que además es ondulante.
• Caso 2: $n$ es un múltiplo de $5$ pero no de $10$ ni de $25$. Entonces, el número $5A(2,\frac{n}{5})$ es un múltiplo de $n$ ondulante (formado por ceros y cincos).
• Caso 3: $n$ es una potencia de $2$. Veamos por inducción sobre $r$ que $2^{2r+1}$ tiene un múltiplo ondulante $B(r)$ de $2r-1$ dígitos. Si $r=1$, entonces $2^r=8$ es de por sí ondulante y tiene un dígito, luego tomamos $B(1)=8$. Supongamos que $2^{2r+1}$ tiene un múltiplo ondulante $B(r)$ de $2r-1$ dígitos, es decir, $B(r)=2^{2r+1}a$ para cierto $a\in \mathbb{N}$. Consideremos el número ondulante \[N=10^{2r}b+B(r)=2^{2r}b+2^{2r+1}a=2^{2r}(b+2a).\] Entonces $N'$ tiene $2r+1$ dígitos y $N'$ será múltiplo de $2^{2r+3}$ para algún valor de $b\in\{2,4,6,8\}$ ya que de entre cuatro números pares consecutivos ($2+2a$, $4+2a$, $6+2a$ y $8+2a$) hay uno de ellos múltiplo de $8$, luego definimos $B(r+1)=10^{2r}b+B(r)$ para tal elección de $b$.
• Caso 4: $n=2^rm$ para cierto número impar $m$ que no es múltiplo de $5$. Entonces, el número $B(r)$ es múltiplo de $2^{2r+1}$ y, por tanto, múltiplo de $2^r$. El número $A(2r+2,m)$ es múltiplo de $m$ y tiene sus unos espaciados por $2r+1$ ceros, luego $A(2r+1,m)B(r)$ es un número ondulante y múltiplo de $n=2^rm$.
Informar error

Solución. Como $n\geq p$, existirá un exponente $s$ tal que $p^s\leq n\lt p^{s+1}$. Tomando $k=p^s-1$, vamos a demostrar que $\binom{n}{k}$ es múltiplo de $p$ siempre que $n$ no es de la forma $p^sq-1$, lo que demostrará el enunciado. Para ello, escribimos $$\binom{n}{p^s-1}=\frac{n!}{(p^s-1)!(n-p^s+1)!}.$$ Observamos que el exponente de $p$ en la descomposición en factores primos del factorial $n!$ es igual a $\sum_{j=1}^s\lfloor\frac{n}{p^j}\rfloor$ ya que $n\lt p^{s+1}$. Aquí, $\lfloor x\rfloor$ denota la parte entera de un número real $x$ (es decir, el mayor entero menor o igual que $x$). Esto nos permite calcular también el exponente de $p$ en el denominador $(p^s-1)!(n-p^s+1)!$ como \begin{align*} \sum_{j=1}^s\left\lfloor\frac{p^s-1}{p^j}\right\rfloor+\sum_{j=1}^s\left\lfloor\frac{n-p^s+1}{p^j}\right\rfloor&=\sum_{j=1}^s(p^{s-j}-1)+\sum_{j=1}^s\left(\left\lfloor\frac{n+1}{p^j}\right\rfloor-p^{s-j}\right)\\ &=\sum_{j=1}^s\left(\left\lfloor\frac{n+1}{p^j}\right\rfloor-1\right). \end{align*} Observemos que $$\left\lfloor\frac{n+1}{p^j}\right\rfloor=\begin{cases} \left\lfloor\frac{n}{p^j}\right\rfloor& \text{si }n+1\text{ no es múltiplo de }p^j,\\ \left\lfloor\frac{n}{p^j}\right\rfloor+1& \text{si }n+1\text{ es múltiplo de }p^j,\end{cases}$$ para que el exponente de $p$ sea el mismo en el numerador y en el denominador de $\binom{n}{k}$, se tiene que cumplir que $n+1$ es un múltiplo de $p^j$ para todo $j$ entre $1$ y $s$, es decir, $n+1=qp^s$ para cierto $q$, que es la condición dada en el enunciado. Dicho de otro modo, hemos probado que el exponente de $p$ en el numerador de $\binom{n}{k}$ es mayor que en el denominador siempre que $n$ no es de la forma $n=qp^s-1$.

Nota. En realidad, el recíproco también es cierto en el siguiente sentido: $\binom{p^sq-1}{k}$ es múltiplo de $p$ para todo $k\in\{1,\ldots,n-1\}$. Obviamente no se puede aspirar que esto también se cumpla para $k=0$ ó $k=n-1$, ya que en tal caso el número combinatorio es igual a $1$.