Voy a comentar en este post el problema denominado en MaTeTaM "Clave secreta". Este problema lo subí a MaTeTaM en julio del 2008 (de acuerdo a los datos registrados), y la verdad no sé de dónde lo saqué ni por qué no incluí la solución o si ésta se perdió en alguna de las migraciones que ha hecho MaTeTaM de un software a otro. Me imagino que el problema se incluyó en uno de los selectivos aplicados a la preselección olímpica Tamaulipas 2008.
El enunciado del problema es el siguiente:
Clave secreta: a) cinco cifras (dígitos), b) el número es par, c)exactamente uno de los dígitos es impar, d)exactamente una de las cifras se repite, la que se repite es par y aparece en dos posiciones no consecutivas de la clave secreta ¿Cuántas claves (números de 5 cifras) son posibles bajo estas condiciones?
El caso es que en estos días me propuse subir la solución que ya estaba faltando desde hace algún tiempo --de hecho la solución está registrada pero está vacía. Antes de la última actualización de MaTeTaM incluía la leyenda "problema viejo y sin solución". Entonces, de tanto verlo en la página principal de MaTeTaM me dije "este problema ya debería incluir una solución".
Y me puse a resolverlo. Y me di cuenta que no es tan fácil como parecía o, más bien, como yo creía. El problema tiene 6 comentarios debido a que en 2009 Ilse aportó una solución. Pero, por los apuros del tiempo en ese entonces y también debido a una retroalimentación que aportó Sergio, yo ya no la revisé a fondo. Y así quedó. Es decir, la solución quedó en suspenso, a pesar de que Ilse pidió que le dijeran si estaba correcta.
Mi enfoque o estrategia con la que empecé fue la de clasificación del conjunto de soluciones. Pero la dificultad principal para este enfoque es que hay demasiadas variables: por el último dígito, por el dígito impar, por el dígito par que se repite; y aunado a estas tres variables están las de la posición del impar, las posiciones del dígito par que se repite...
Se me complicó, pero como ya lo había empezado me propuse terminarlo con esta estrategia. Y, después de encontrar una solución, todavía me quedó la duda de si podría haber incluido un error de omisión o bien uno de comisión. Así que le pasé la solución a Jesús y le pedí me lo revisara. Y Jesús sí me encontró un error de comisión: cometí un error en la multiplicación 25(12).
Y también me dijo que la solución de Ilse es correcta sólo que su argumento no es muy claro. ¡Mea culpa! Yo no la revisé porque Sergio la había puesto una tacha y confié en su buen juicio. (Vagamente me acordaba que Sergio había expuesto en el pizarrón una solución en los entrenamientos del 2008.)
Entonces me puse a revisar la solución de Ilse y descubrí que en verdad sí es correcta, y mucho más sencilla que la mía (la entendí mejor porque es muy parecida a la mía). Su estrategia procede en dos etapas: primero elige los dígitos y después elige las posiciones en que se pueden colocar. Y, bueno, pues aquí le ofrezco públicamente una disculpa a Ilse por no haber atendido su petición de sancionar como correcta o incorrecta su solución.
La corrección de Sergio fue que el cero no podía estar en primer lugar. Esto debido a una ambigüedad en el enunciado --mi culpa, pero así lo voy a dejar. En la pregunta del enunciado dice "¿Cuántas claves (números de 5 cifras) son posibles bajo estas condiciones?" La ambigüedad consiste en el paréntesis que especifica que la clave es un número. Y si es un número entonces no debe llevar cero al principio. Pero es clave. Entonces sí puede llevar cero al principio. (Sergio argumentó que si lleva cero al principio el problema se hace trivial --faltaría ver cómo lo resuelve Sergio así para saber por qué dijo que es trivial.)
Solución con un argumento de clasificación
Sea S el conjunto de todas las posibles claves secretas. Vamos a clasificarlas de acuerdo a las condiciones exigidas.
De acuerdo a la terminación, hay 5 clases: las que terminan en 0, las que terminan en 2, etc. Consideremos una de esas clases, digamos las claves terminadas en 0. Las terminadas en 0 las podemos clasificar por el dígito impar que incluyen. Son 5 subclases: las que incluyen el 1, las que incluyen el 3, etc.
Entonces las claves secretas posibles se agrupan en 25 subclases según el dígito par final y el digito impar que incluyen. Vamos ahora a considerar cada una de esas subclases y a clasificar sus elementos de acuerdo al par que se repite.
Caso 1: Se repite el dígito final
Si el dígito impar está en primer lugar, el dígito final que se repite solamente puede estar en los lugares 2 o 3. Entonces cada una de las 25 clases que repiten el último dígito y que tienen el dígito impar en primer lugar dan lugar a 2 clases, según el otro lugar que ocupa el dígito final que se repite.
Si el dígito impar está en segundo lugar, también se tienen dos clases por cada una de las 25 clases que repiten el último dígito y tienen el impar en segundo lugar --pues el otro lugar que puede ocupar el dígito final es el 1 o el 3.
Si el dígito impar está en tercer lugar, de nuevo la situación es como las dos anteriores.
Si el dígito impar está en cuarto lugar, se tiene en cambio que el otro lugar para el dígito final puede ser el 1, el 2 o el 3. (Este detalle es lo que hace complicado el problema.)
En resumen, hasta aquí, tenemos 50+50+50+75=225 clases que repiten el dígito final y contienen exactamente un dígito impar. Sin embargo, falta considerar en estas 225 clases los dos dígitos pares que no se repiten y su posición: por los dos dígitos pares que no se repiten son 6 pares --C(4,2)-- y por su posición son 2 posibilidades. Por tanto, cada una de las 225 categorías da lugar a 12 subcategorías.
Entonces, en total, se tienen 225(12)=2700 clases que repiten el dígito final y cumplen las otras condiciones.
Caso 2: El dígito final no es el que se repite
Tomemos de nuevo las 25 clases distinguidas por su dígito final y por el dígito impar que incluyen.
Si el dígito impar está en primer lugar, entonces quedan tres lugares por llenar. Como el dígito final no se repite, entonces cada una de estas 25 clases da lugar a 4 categorías por el dígito par que se repite y que no es el final (equivale a elegir el dígito par que se repite). Sus posiciones están obligadas a ser la 2 y la 4. Finalmente, el otro dígito par se puede elegir de 3 formas y ocupará el único lugar disponible. En resumen, cada una de las 25 categorías o clases da lugar a 12 subcategorías.
Si el dígito impar está en segundo lugar entonces, de nuevo, escojo el dígito par que se repite de 4 formas, y lo coloco en los lugares 1 y 3 o 1 y 4 (dos formas), y el otro dígito par lo elijo de 3 formas y lo coloco en el único lugar disponible. En resumen, cada una de las 25 categorías da lugar a 24 subcategorías.
Si el dígito impar está en tercer lugar, escojo el repetido de 4 formas, lo coloco de 2 formas y elijo el tercer dígito par de 3 formas y lo coloco en el único lugar disponible. De nuevo resultan 24 subctaegorías por cada una de las 25.
Si el dígito impar está en tercer lugar hay 12 subcategorías por cada una de las 25.
En resumen, en este segundo caso, cada una de las 25 categorías da lugar a 12+24+24+12=72 subcategorías o subclases. En total, en este caso, se tienen 25(72)=1800 categorías. (Y cada una de éstas consiste de una sola clave.)
Considerando ya los dos casos, el total de claves secretas es 2700+1800=4500.
La solución de Ilse
Ilse usa la siguiente notación para la primera etapa de elegir los dígitos de la clave secreta: P=par, PR=par repetido, I=impar. Después enlista todas las posibilidades en que se pueden acomodar los dígitos. Son las siguientes (y son 15):
*PR I PR P P *PR P PR I P *PR I P PR P *PR P I PR P *PR I P P PR
*PR P I P PR *PR P P I PR *I PR P PR P *P PR I PR P *I PR P P PR
*P PR I P PR *P PR P I PR *I P PR P PR *P I PR P PR *P P PR I PR
Explica también que en cada una de esas posibilidades aparecen dos PR, dos P y una I. El argumento sería entonces más o menos de la siguiente manera: un PR lo elijo de 5 formas (0,2,4,6,8), el otro de una (ya está elegido), el I también de 5 formas, uno de los P de 4 formas (porque ya se eligió el PR) y el otro de 3 (ya se eligió un PR y un P). En resumen, la elección de los dígitos se puede hacer de 5(1)(5)(4)(3)=300 formas.
La segunda etapa sería el acomodo de los dígitos. Pero eso ya lo había hecho: son 15 formas. En resumen, el número de posibles claves secretas es 15(300)=4500.
Los saluda
jmd
PD: Vaya de nuevo una disculpa para Ilse y una pregunta para Sergio ¿porque dijiste "no se considera el cero en la primera cifra ya que el problema es muy facil de esa forma"?