En los problemas de IMO es común que sea útil reducir cierto proceso a un caso más pequeño haciendo una especie de recurción. Me parece que es muy importante tener presente esa idea y saberla manejar bien, para ahorrar tiempo en un problema del estilo. Así que aquí pongo tres de ellos.
1. Sea $n\geq 1$ un entero. Un camino es un camino de $(0,0)$ a $(n,n)$ en el plano $xy$ es una sucesión de movimientos unitarios consecutivos, ya sea hacia la derecha (movimiento denotado por $D$) o hacia arriba (movimiento denotado por $A$), todos los movimientos hechos dentro del medioplano $x\geq y$. Un escalón en el camino es el suceso de dos movimientos consecutivos $DA$. Demuestra que el número de caminos de $(0,0)$ a $(n,n)$ que contienen exactamente $s$ escalones es:
$\frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1}$
(IMO SL 1999)
2. Sea $n$ un natural y $A_n$ el conjunto de las permutaciones $(a_1,..., a_n)$ del conjunto $\{ 1, 2,..., n\}$ tal que $k|2(a_1+...+a_k)$ para todo $1\leq k\leq n$.
Encuentra el número de elementos en $A_n$.
(IMO SL 2008)
(IMO SL 2008)
3. Sea $n\geq 2$ se nos da una balanza con $n$ pesas con pesos $2^0, 2^1,...,2^{n-1}$. se deben de poner las $n$ pesas sobre la balanza, una detrás de otra de modo que el plato derecho sea siempre más pesado que el plato izquierdo. En cada paso se escoge una de las pesas que no se hayan utilizado y se pone ya sea en el platillo derecho o en el izquierdo, hasta que todas las pesas se hayan puesto.
Determina el número de formas en que esto se puede hacer.
(IMO 2011)
(IMO 2011)
4 comentarios:
1. Llamo al número de caminos en el medio plano $x \ge y$ de (0,0) a (n,n) con s escalones, f(n,s). Llamo C(x,y) a un camino de (0,0) a (x,x) con y escalones en el medio plano $x \ge y$. Entonces llamemos a dos caminos entrelazados si a uno de esos caminos le puedo insertar por ahí un DA para que nos de el otro camino. Si le insertamos un DA a un C(n,s), entonces obtenemos un C(n+1,s) si se lo insertamos en un escalón (o sea, DA -> DDAA), y un C(n+1,s+1) de otra manera. Nos fijamos que para cada C(n,s) hay 2n+1-s C(n+1,s+1)'s entrelazados y por cada C(n,s+1) hay s+1 C(n+1,s+1)'s entrelazados. Cada C(n+1,s+1) está enrelazado con s+1 C(n,s) o C(n,s+1)'s. Entonces podemos usar inducción sobre n, asumiendo que f(n,s) es igual a la fórmula que queremos para todo s, y entonces tenemos
(s+1)f(n+1,s+1)=(2n+1-s)f(n,s)+(s+1)f(n,s+1)
y acabamos con álgebra.
2. Llamo a la respuesta f(n). Módulo n-1 vemos que el último a, (a_n) debe ser 1 o n. Entonces si acaba con n vemos que tenemos f(n-1) maneras de completar la permutación, y si acaba con 1 entonces podemos olvidarnos de ese 1, restarle 1 a todos los otros a_i y ver que hay f(n-1) maneras de completar. Entonces, tenemos f(n)=2f(n-1). Entonces $f(n)=2^{n-1}f(1)$ con $n \ge 1$ entonces como f(1)=1, la respuesta es $2^{n-1}$.
3. Llamo f(n) la respuesta. Me tomo la sucesión b1, b2, ..., b2n, y la defino con las siguientes reglas:
(A) $b_{2k}=0$ si el k-ésimo peso que puse lo puse en el plato izquierdo.
(B) $b_{2k-1}=0$ si el k-ésimo peso que puse lo puse en el plato derecho.
(C) $b_{2k}=2^i$ si el k-ésimo peso que puse lo puse en el plato derecho y pesaba $2^i$.
(D) $b_{2k-1}=2^i$ si el k-ésimo peso que puse lo puse en el plato izquierdo y pesaba $2^i$.
Ahora bien, veamos que hay exactamente un $b_i$ que es igual a 1, y que no puede ser $b_1$ por la regla del plato pesado. Sin embargo, si ya decidí cuál $b_i$ será 1, entonces puedo definir una nueva secuencia $c_1$,...,$c_{2n-2}$ como:
(A) Si $j \textless \lceil \frac{i}{2} \rceil -1$, entonces defino $c_j = \frac{b_j}{2}$.
(B) Si $j \ge 2\lceil \frac{i}{2} \rceil -1$, entonces defino $c_j = \frac{b_{j+2}}{2}$.
Entonces la secuencia c representa una manera de poner los pesos, pero para n-1, no n. Entonces tengo que, como hay 2n-1 maneras de decidir que $b_i$ es 1, tengo que $f(n)=(2n-1)f(n-1)$. Ahora veamos $f(1)=1$. Así, podemos acabar con:
$f(n)=(2n-1)!!$.
Muy bien juan, Solo checa que en el problema 2 cuando lo ves módulos $n-1$ hay también solución con $n+1/2$ así que hay que hacer algo más para descartar ese caso.
Si, perdón. n-2 vemos que el penúltimo termino es también (n mas 1)/2.
Publicar un comentario