Ñandú - Provincial - 2017 - Nivel 1 - Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Reglas del Foro
  • Las soluciones posteadas en este foro tienen que usar conocimientos aptos para un participante de Ñandú. Cualquier solución que use conocimientos demasiado avanzados será borrada.
  • Las soluciones deberán estar explicadas lo más didácticamente posible (esto es más que nada una recomendación para los más grandes).
  • Al subir un problema hay que indicar certamen, año, nivel al que pertenece y número de problema.
Pirógeno

OFO - Medalla de Bronce-OFO 2019 FOFO 9 años - Medalla Especial-FOFO 9 años OFO - Medalla de Bronce-OFO 2020
Mensajes: 271
Registrado: Vie 11 Ene, 2019 10:31 am
Medallas: 3
Nivel: Otro

Ñandú - Provincial - 2017 - Nivel 1 - Problema 3

Mensaje sin leer por Pirógeno »

Para usar la computadora del colegio se necesita una clave.
La clave tiene $5$ letras; solo se pueden usar la $X$, la $Y$ y la $Z$.
No es obligatorio usar las tres letras.
En cada clave, una sola de las letras aparece una cantidad impar de veces.
¿Cuántas claves distintas se pueden crear? Explica cómo las contaste.

Gigi
Mensajes: 2
Registrado: Lun 08 Ago, 2022 11:59 am
Nivel: 1

Re: Ñandú - Provincial - 2017 - Nivel 1 - Problema 3

Mensaje sin leer por Gigi »

Hola...alguien podrá explicarme como se plantea este problema por favor

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: Ñandú - Provincial - 2017 - Nivel 1 - Problema 3

Mensaje sin leer por sebach »

Hola Gigi!
Hay varias formas de plantear la solución, acá dejo dos:

Solución $1$:
Spoiler: mostrar
Podemos separar los casos en cuántas veces aparece la letra que aparece una cantidad impar.

Si la letra aparece $5$ veces, entonces la clave consiste de esa letra sola, repetida $5$ veces. En este caso tenemos tres posibilidades, $XXXXX, YYYYY, ZZZZZ$.
En este caso tenemos $3$ claves posibles.

Si la letra que aparece una cantidad impar aparece $3$ veces, las otras no pueden aparecer $1$ vez cada una porque $1$ es impar. Entonces una de las otras letras debe aparecer $2$ veces y la tercera letra no aparecer.
Cuántas claves posibles tenemos en este caso?
Contemos primero de una forma más "abstracta", sin escribirlas todas, y después podemos escribirlas para verificar:
Para cada letra que elijamos como "la que aparece $3$ veces", tenemos $2$ elecciones de "la que aparece $2$ veces". Entonces tenemos $6$ elecciones de letras que van a generar claves distintas.
Además, habiendo elegido, tenemos que ordenar las letras. Tenemos estos $10$ órdenes distintos: $AABBB, ABABB, ABBAB, ABBBA, BAABB, BABAB, BABBA, BBAAB, BBABA, BBBAA$ .
Hay una forma de contar estas configuraciones más genéricamente pero no me voy a meter en eso, se pueden leer apuntes de Combinatoria como por ejemplo viewtopic.php?t=7

Entonces en total, tenemos cada una de esas configuraciones reemplazando las letras $A, B$ por las $6$ parejas de letras que habíamos dicho antes.
Las $60$ posibilidades son (en una prueba no haría falta escribirlas, con la explicación anterior alcanza):
Reemplazando A por X y B por Y
XXYYY
XYXYY
XYYXY
XYYYX
YXXYY
YXYXY
YXYYX
YYXXY
YYXYX
YYYXX
Reemplazando A por X y B por Z
XXZZZ
XZXZZ
XZZXZ
XZZZX
ZXXZZ
ZXZXZ
ZXZZX
ZZXXZ
ZZXZX
ZZZXX
Reemplazando A por Y y B por X
YYXXX
YXYXX
YXXYX
YXXXY
XYYXX
XYXYX
XYXXY
XXYYX
XXYXY
XXXYY
Reemplazando A por Y y B por Z
YYZZZ
YZYZZ
YZZYZ
YZZZY
ZYYZZ
ZYZYZ
ZYZZY
ZZYYZ
ZZYZY
ZZZYY
Reemplazando A por Z y B por X
ZZXXX
ZXZXX
ZXXZX
ZXXXZ
XZZXX
XZXZX
XZXXZ
XXZZX
XXZXZ
XXXZZ
Reemplazando A por Z y B por Y
ZZYYY
ZYZYY
ZYYZY
ZYYYZ
YZZYY
YZYZY
YZYYZ
YYZZY
YYZYZ
YYYZZ

En este caso tenemos $60$ claves posibles.

Y si, por último, la que aparece una cantidad impar de veces aparece $1$ vez, entonces tenemos dos casos:
Caso 1) Otra letra aparece $4$ veces. En este caso, por cada elección de letras (que de vuelta tenemos $6$), tenemos $5$ configuraciones: $ABBBB, BABBB, BBABB, BBBAB, BBBBA$.
En este caso tenemos $6*5 = 30$ claves posibles.

Caso 2) Las otras dos letras aparecen $2$ veces. Ahora, veamos, similarmente a como hicimos antes, cuántas configuraciones hay para una $A$, dos $B$ y dos $C$. Después es cuestión de reemplazar esas letras por $X, Y, Z$.
Por cada uno de los $5$ lugares en donde ponemos la $A$, tenemos $6$ formas de ordenar las cuatro letras restantes, por ejemplo, si la $A$ queda en el primer lugar, tendríamos $ABBCC, ABCBC, ABCCB, ACBBC, ACBCB, ACCBB$.
Ahora, veamos que si fijamos qué letra ocupa el lugar de la $A$ en las configuraciones anteriores (la impar), es indistinto cuál toma el lugar de la $B$ y cuál de la $C$. Por ejemplo, si $X$ aparece $1$ vez, luego reemplazando $B$ por $Y$ y $C$ por $Z$, la primera clave queda $XYYZZ$, y si reemplazáramos $B$ por $Z$ y $C$ por $Y$, entonces la sexta quedaría $XYYZZ$. Entonces en esas $6$ configuraciones contamos ya todas las posibilidades dada la letra impar.
Entonces, para cada una de las $5 * 6 = 30$ configuraciones para $A, B, C$ (a la $A$ que veníamos poniendo al principio la podemos poner en cualquier de los $5$ lugares), tenemos que elegir cuál es la letra que reemplaza a la $A$ ($3$ posibilidades).
Entonces en este caso tenemos $3 * 5 * 6 = 90$ claves posibles.

La respuesta final sería $3 + 60 + 30 + 90 = 183$
Solución $2$:
Spoiler: mostrar
Podemos contar, de las claves con $5$ letras formadas por $X, Y, Z$, cuántas hay en total y cuántas son inválidas según los requisitos de las claves, y luego la diferecia va a ser la respuesta.

En total hay $3^5 = 243$ claves formadas por $X, Y, Z$, dado que en cada lugar hay $3$ posibilidades, y tenemos $5$ lugares. Podemos pensar gráficamente en una configuración de árbol que por cada letra que pongamos primero, se abren otras $3$ ramas para la segunda letra, y así $5$ niveles, uno por posición.

Y cuántas de esas son inválidas? Las claves en las que no sólo una letra aparece una cantidad impar de veces. Si $x$ es la cantidad de veces que aparece la $X$, e igualmente con $y$ y $z$, entonces $x + y + z = 5$. Como la suma ($5$) es impar, o bien hay un sólo número de esos que es impar o bien lo son los tres. Porque si hubiera dos impares y uno par, la suma de los dos impares da un número par, y al sumar un número par la suma total sería par, y no podría ser $5$.
Entonces hay que contar cuántas claves tienen una cantidad impar de cada letra. La única forma de sumar $5$ con $3$ números impares (y positivos) es $1 + 1 + 3$, en algún orden.
Entonces, las claves inválidas tienen $3$ veces una misma letra, y una vez cada una de las otras dos.

Contémoslas.
Supongamos que la $X$ es la que aparece $3$ veces, entonces la $Y$ y la $Z$ aparecen una vez. Si contamos estas claves, después multiplicando por $3$ vamos a tenerlas todas, que resulta de cambiar la letra que aparece $3$ veces por $Y$ y por $Z$.
Entonces, la cantidad de estas claves es la cantidad de formas de ubicar $3$ letras en $5$ lugares, multiplicada por $2$ (poner $Y,Z$ en los lugares faltantes o al revés, $Z,Y$.)
Y cuántas configuraciones así hay? $10$: $AAAxx, AAxAx, AAxxA, AxAAx, AxAxA, AxxAA, xAAAx, xAAxA, xAxAA, xxAAA$. (También se puede contar con lo de los números combinatorios que mencioné arriba.)
Entonces por cada letra que elijamos para que aparezca $3$ veces, tenemos $2*10 = 20$ claves. Entonces en total hay $3 * 20 = 60$ claves inválidas.

Finalmente, hay en total $243 - 60 = 183$ claves válidas distintas.
Espero que se haya entendido. Si no, o por cualquier cosa, preguntá que alguien te va a responder :)

Responder