Cantidad máxima de palabras

robert123
Mensajes: 11
Registrado: Dom 11 Feb, 2018 12:43 pm
Nivel: 3

Cantidad máxima de palabras

Mensaje sin leer por robert123 »

Un lenguaje extraterrestre utiliza $16$ letras y todas sus palabras tienen $3$ letras. Es imposible encontrar dos palabras con la propiedad de que la última letra de la primera palabra sea la misma que la primera de la segunda la primera y la última letra son distintas en cada palabra. ¿Cuál es el máximo número de palabras en este lenguaje?
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Cantidad máxima de palabras

Mensaje sin leer por Joacoini »

Spoiler: mostrar
Como la segunda letra de las palabras no afecta a la propiedad podemos buscar la cantidad máxima de palabras de $2$ letras que no cumplen la propiedad y luego multiplicarlas por $16$.

Sean $l_1$, $l_2$, $l_3$...$l_{16}$ las letras del abecedario, sean $j$ y $i$ enteros positivos, $j,i<17$ y $j\neq i$ llamamos tipo $1$ a las palabras de la forma $l_j l_j$ y tipo 2 a las palabras de la forma $l_j l_i$

Sea $C$ el conjunto que contiene la máxima cantidad de palabras de dos dígitos que no cumplen la propiedad, en $C$ hay $n$ palabras del tipo 1, sean $l_a$ y $l_b$ dos letras que no forman ninguna palabra del tipo 1, supongamos que la palabra $l_a l_b$ se encuentra en $C$ lo que provoca qué no puede haber ninguna palabra qué empiece con $l_b$ excepto $l_b l_b$, ahora sea $C´$ el conjunto que contiene las misma palabras qué $C$ con la inclusión de $l_b l_b$ las palabras de este conjunto siguen sin cumplir la propiedad del enunciado, pero habíamos dicho qué $C$ tenía la máxima cantidad de palabras, contradicción por lo tanto la palabra $l_a l_b$ no se encuentra en $C$ por lo tanto con cualquier $l_a$ (recordar que $l_a$ no forma parte de ninguna palabra del tipo 1) solo puede formar $n$ palabras las cuales todas empiezan con $l_a$ y siguen con una letra que se uso en una palabra del tipo 1, como hay $16-n$ letras que no forman parte de ninguna palabra del tipo 1 la cantidad de palabras en $C$ es igual a:

$n+(16-n)n=-n^{2}+17n$ lo cual es una parábola descendente la cual toma su máximo valor cuando $n=X_v$ donde $X_v$ es igual a la coordenada $X$ del vértice de la parábola

$X_v=\frac{-b}{2a}=\frac{-17}{-2}=8,5$ como $n$ tiene que ser entero los dos valores mas cercanos son $8$ y $9$

$-8^{2}+17\times 8=-9^{2}+17\times 9=72$

$C$ contiene $72$ elementos por lo tanto el máximo número de palabras del lenguaje es $72\times 16=1152$
NO HAY ANÁLISIS.
robert123
Mensajes: 11
Registrado: Dom 11 Feb, 2018 12:43 pm
Nivel: 3

Re: Cantidad máxima de palabras

Mensaje sin leer por robert123 »

La respuesta es 1024
Avatar de Usuario
Elsa Muray

OFO - Medalla de Bronce-OFO 2018
Mensajes: 23
Registrado: Vie 26 Ene, 2018 3:10 pm
Medallas: 1
Nivel: 1
Ubicación: La Plata

Re: Cantidad máxima de palabras

Mensaje sin leer por Elsa Muray »

No se si esta bien, corrijanme en todo caso
Spoiler: mostrar

Denominamos $a b c$ a la palabra.
Sabemos que la letra $b$ puede tomar cualquier valor, así que tiene $16$ posibilidades.
Si una letra aparece una sola vez adelante, significa que nunca más podrá aparecer al final, ni siquiera en la misma palabra. Por lo tanto, si aparecen $x$ letras distintas adelante, al final como máximo aparecerán $16-x$ posibilidades. Finalmente, la máxima cantidad de posibilidades está dada por:

$x.16.(16-x)$

Como nos piden hallar el máximo, aplicamos una desigualdad conocida, llamada $AM GM$. por lo que obtenemos:

$\sqrt{x.(16-x)} \leq \frac{x+16-x}{2}$

Por lo que obtenemos que:

$x.(16-x) \leq 64$ con igualdad cuando $x=8$

Finalmente obtenemos:

$x.16.(16-x) \leq 1024$ Para el caso $x=8$

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Cantidad máxima de palabras

Mensaje sin leer por Joacoini »

Spoiler: mostrar
Si $ABCDEFGHIJKLMNOP$ son los caracteres de las palabras.

$AA, BB, CC, DD, EE, FF, GG, HH$
$IA, IB, IC, ID, IE, IF, IG, IH $
$JA, JB, JC, JD, JE, JF, JG, JH$
$KA, KB, KC, KD, KE, KF, KG, KH$
$LA, LB, LC, LD, LE, LF, LG, LH $
$MA, MB, MC, MD, ME, MF, MG, MH$
$NA, NB, NC, ND, NE, NF, NG, NH$
$OA, OB, OC, OD, OE, OF, OG, OH$
$PA, PB, PC, PD, PE, PF, PG, PH$
Son un ejemplo de las $72$ combinaciones de dígitos que pueden ir en los extremos de las palabras, luego para cada combinación hay 16 letras centrales posibles por lo que la cantidad total de palabras es $72×16=1152$
NO HAY ANÁLISIS.
Avatar de Usuario
Elsa Muray

OFO - Medalla de Bronce-OFO 2018
Mensajes: 23
Registrado: Vie 26 Ene, 2018 3:10 pm
Medallas: 1
Nivel: 1
Ubicación: La Plata

Re: Cantidad máxima de palabras

Mensaje sin leer por Elsa Muray »

Joacoini escribió: Mié 21 Feb, 2018 11:44 pm
Spoiler: mostrar
Si $ABCDEFGHIJKLMNOP$ son los caracteres de las palabras.

$AA, BB, CC, DD, EE, FF, GG, HH$
$IA, IB, IC, ID, IE, IF, IG, IH $
$JA, JB, JC, JD, JE, JF, JG, JH$
$KA, KB, KC, KD, KE, KF, KG, KH$
$LA, LB, LC, LD, LE, LF, LG, LH $
$MA, MB, MC, MD, ME, MF, MG, MH$
$NA, NB, NC, ND, NE, NF, NG, NH$
$OA, OB, OC, OD, OE, OF, OG, OH$
$PA, PB, PC, PD, PE, PF, PG, PH$
Son un ejemplo de las $72$ combinaciones de dígitos que pueden ir en los extremos de las palabras, luego para cada combinación hay 16 letras centrales posibles por lo que la cantidad total de palabras es $72×16=1152$
Spoiler: mostrar

Estas contando casos de más. Acordate que la primera letra es distinta que la última (dentro de la misma palabra tampoco puede pasar).
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Cantidad máxima de palabras

Mensaje sin leer por Joacoini »

Elsa Muray escribió: Mié 21 Feb, 2018 11:49 pm
Joacoini escribió: Mié 21 Feb, 2018 11:44 pm
Spoiler: mostrar
Si $ABCDEFGHIJKLMNOP$ son los caracteres de las palabras.

$AA, BB, CC, DD, EE, FF, GG, HH$
$IA, IB, IC, ID, IE, IF, IG, IH $
$JA, JB, JC, JD, JE, JF, JG, JH$
$KA, KB, KC, KD, KE, KF, KG, KH$
$LA, LB, LC, LD, LE, LF, LG, LH $
$MA, MB, MC, MD, ME, MF, MG, MH$
$NA, NB, NC, ND, NE, NF, NG, NH$
$OA, OB, OC, OD, OE, OF, OG, OH$
$PA, PB, PC, PD, PE, PF, PG, PH$
Son un ejemplo de las $72$ combinaciones de dígitos que pueden ir en los extremos de las palabras, luego para cada combinación hay 16 letras centrales posibles por lo que la cantidad total de palabras es $72×16=1152$
Spoiler: mostrar

Estas contando casos de más. Acordate que la primera letra es distinta que la última (dentro de la misma palabra tampoco puede pasar).
Al parecer no entendi el enunciado, es medio trabalenguas

Aca subo la parte final con la coma que le faltaba.

Es imposible encontrar dos palabras con la propiedad de que la última letra de la primera palabra sea la misma que la primera de la segunda, la primera y la última letra son distintas en cada palabra.
NO HAY ANÁLISIS.
Avatar de Usuario
DiegoLedesma
Mensajes: 78
Registrado: Vie 28 Jul, 2017 9:21 pm
Nivel: Otro

Re: Cantidad máxima de palabras

Mensaje sin leer por DiegoLedesma »

Llamemos $xyz$ a toda palabra conformada con las condiciones pedidas. Del enunciado se desprende que las posibilidades en el lugar $y$ son $16$, ya que no hay ninguna restricción para las letras que ocupen dicho lugar.
Ahora bien, si decidimos generar todas las palabras posibles utilizando las $16$ letras en el lugar $x$, esto será imposible, pues en el lugar $z$ cualquier letra que coloquemos ya habrá sido utilizada en el lugar $x$.
Con este mismo razonamiento, si en el lugar $x$ buscamos todas las posibles combinaciones utilizando $15$ letras, en el lugar $z$ sólo podremos colocar aquella letra que no se haya utilizado en el lugar $x$... Entonces, para los $2$ casos anteriormente abordados, las posibles cantidades de palabras generadas serán: $16.16.0=0$ y $15.16.1=240$... De forma genérica, esto puede expresarse como: $(16-z).16.z$
Al ser $x+z=16-z+z=16$ (constante), el máximo de palabras posibles se dará cuando $x=z$ $\Rightarrow$ $16-z=z$ $\Rightarrow$ $z=8$ $\Rightarrow$ $x=8$
$\therefore$ El máximo número de palabras será: $8.16.8=1024$
Responder