El problema 1 de la 24 OMM resultó ser un hueso duro de roer --para los concursantes que no conocían algunos trucos de acotación. Su enunciado parece tan inocente... "Encuentra todas las ternas de números naturales $(a,b,c)$ que cumplan la ecuación $abc=a+b+c+1$." Pero su inocencia aparente es una inocencia envenenada.
Mi intento (fallido) de solución:
Con alguna experimentación es fácil llegar a la solución $(1,2,4)$, con lo cual se tienen ya 6 soluciones. Y se puede sospechar que es la única solución, pero... (Debido a que era el fácil de la 23 OMM usé búsqueda exhaustiva --con la esperanza de que en algún momento se revelara la imposibilidad del resto de las soluciones.)
Sin pérdida de generalidad se puede suponer $a\leq b\leq c$. De esta manera, se pueden generar las soluciones en orden lexicográfico: resolviendo sucesivamente para los valores sucesivos de $a$ (1,2,...)
Si $a=1$ entonces $bc=b+c+2$. De aquí que $c|b+2$. Y como $b\leqc$, se sigue que $c=b,b+1,b+2$.
- Si $c=b$, entonces $b^2=2b+2$ y no hay solución en enteros.
- Si $c=b+1$, entonces $b^2+b=2b+3$ o $b(b-1)=3$ y tampoco hay solución en enteros.
- Si $c=b+2$, entonces $b^2+2b=2b+4$ y se obtiene $b=2,c=4$
Si $a=2$, entonces $2bc=b+c+3$. Y se ve que $c|b+3$. Y, de nuevo, es posible verificar las posibilidades que de aquí surgen... Pero esto es un cuento de nunca acabar...
Me dí cuenta de que el problema estaba envenenado al resolver para $a=3$, es decir, ví la necesidad de acotar las soluciones. Y aunque es claro que el valor del producto $abc$ crece muy rápido comparado con el de $a+b+c+1$, la verdadera dificultad es crear un argumento que lo demuestre.
¿Cómo acotar entonces? El problema puede llegar a ser desesperante porque no se ve una forma clara de descartar las soluciones grandes... a pesar de que es casi obvio que deben descartarse... A continuación las formas en que acotan dos expertos en el problem solving de olimpiada. (Ver la solución de Jesús y el comentario de Iwakura [1])
Acotación de Iwakura:
(El primer paso de Iwakura lleva consigo la idea de acotar vía "Si $a|b$ entonces $a\leq b$")
1. Pasando la $a$ al lado izquierdo y factorizando se obtiene $a(bc-1)=b+c+1$.
2. Y se ve que $bc-1|b+c+1$.
3. Y el truco trivial pero eficaz es: ah, entonces $bc-1\leq{b+c+1}$.
4. Otro truco de experto es despejar $b$, es decir, $b\leq{\frac{c+2}{c-1}}$.
5. Y este otro es el definitivo: $b\leq{1+\frac{3}{c-1}}$. Se concluye que $b\leq 4$.
6. Y, por la simetría de la ecuación, también $a\leq4$ y $c\leq4$.
Seis pasos elementales cuya ejecución en otros tantos renglones podría llevar a la falsa conclusión de que el problema sí era realmente fácil. Pero no. Estos 6 pasos son la punta del iceberg de una larga experiencia en el problem solving de olimpiada.
El resultado del argumento de acotación de Iwakura es que el espacio de soluciones se redujo a un tamaño manejable para aplicar una búsqueda exhaustiva. (El toque fino de Iwakura fue descartar las soluciones posibles distintas a (1,2,4) mediante un análisis de paridad hecho al principio.)
Acotación de Jesús:
El truco de Jesús es dividir la ecuación entre $abc$. Con ello --quizá teniendo en mente la solución $(1,2,4)$-- demuestra que no todas las literales pueden ser mayores o iguales a 2. Concluye que alguna debe ser 1. Esto simplifica la ecuación y llega a que las otras dos literales no pueden ambas ser mayores o iguales a 3. Por tanto alguna debe ser 1 0 2. Etcétera...
Duro y a la cabeza... (El nodo gordiano del fácil de la 24 OMM fue incapaz de resistirse al afilado machete de dividir entre $abc$ --con lo cual el problema se trivializa.) "Es un truco que aprendí en mis años de olimpiada" --me comentó Jesús Y al parecer es una técnica estándar para problemas de este tipo. Lo puedo leer entre líneas en las fotocopias de las soluciones oficiales de la 23 OMM que me facilitó Ramón.
Notemos que Iwakura acota y llega a un espacio de soluciones pequeño, en el cual obtiene la solución clave y descarta las restantes en ese espacio reducido de soluciones. Jesús, en cambio, acota de otra manera: determina valores concretos que deben asumir las literales (no todas pueden ser mayores que 1; por tanto, una de ellas es 1).
Epílogo
¿Es fácil el fácil de la 23 OMM? Bueno, el problema es fácil para quien dispone de las herramientas adecuadas... de otra manera es endiabladamente difícil.
Por otro lado, el modo de recepción adolescente es --con mucha frecuencia- típicamente descontextualizado, y no me sorprendería que --a excepción de quienes tuvieron entrenamiento nacional o parecido-- la mayoría de los participantes de la 23 OMM llegaran solamente a dar la solución (1,2,4) --y con ello salieran muy contentos diciendo "pónganme otro más difícil" (Y para su sorpresa se enteraron el miércoles que esa solución valía solamente un punto.)
En mi opinión el fácil de la 23 OMM fue una especie de Caballo de Troya para 4 de cada 5 de los concursantes.
Moraleja:
"Nunca aceptes el regalo de un griego."
Los saluda
jmd
las acotaciones de iwakura
las acotaciones de iwakura son de ayuda...
pero y si fueron sobre el conjunto de los enteros??
creo que las soluciones variarían en algo eeh