OFO 2020 Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 952
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

OFO 2020 Problema 2

Mensaje sin leer por Matías V5 » Mié 22 Ene, 2020 12:04 am

Consideramos todas las palabras de $8$ letras que se pueden escribir usando solamente las letras $O$ y $F$. En estas palabras, llamamos sílaba a cualquier par de letras que aparezcan en posiciones consecutivas dentro de la palabra. Así, toda palabra contiene $7$ sílabas.
Decimos que una palabra es oficial si la sílaba $OF$ aparece más veces que la sílaba $FO$. Por ejemplo, la palabra $OFOFFOOF$ es oficial, porque la sílaba $OF$ aparece $3$ veces y la sílaba $FO$ aparece $2$ veces.
Franco hizo la lista de todas las palabras oficiales de $8$ letras. ¿Cuántas palabras tiene la lista de Franco? Explicar cómo las contaste.
4  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 952
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Re: OFO 2020 Problema 2

Mensaje sin leer por Matías V5 » Sab 01 Feb, 2020 12:28 am

Aquí vamos a publicar la solución oficial.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Sandy

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 90
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 2
Nivel: 3

Re: OFO 2020 Problema 2

Mensaje sin leer por Sandy » Sab 01 Feb, 2020 12:43 am

Spoiler: mostrar
Notemos primero lo siguiente: En cada palabra se alternan bloques de letras $O$ y letras $F$, y las sílabas $OF$ se dan cuando se pasa de un bloque de $O$ a un bloque de $F$, mientras que las sílabas $FO$ se dan cuan se pasa de un bloque de $F$ a un bloque de $O$.
Esto implica que las sílabas $OF$ y $FO$ deben estar alternadas, ya que cada cambio de bloque coincide con una de estas sílabas, y los cambios de bloque deben ser alternados. Por lo tanto, si la cantidad de cambios de bloque (sea de $O$ a $F$ o de $F$ a $O$) es par, habrá igual cantidad de sílabas $OF$ que $FO$. La cantidad de cambios de bloque es igual a la cantidad de bloques menos $1$ (ya que todos los bloques cambian menos el último).

Por lo tanto si la cantidad de bloques es impar (implicando que la letra inicial es la misma que la final), la cantidad de cambios de bloque será par y habrá igual cantidad de sílabas $OF$ que $FO$.

Es decir que, para que se repita más veces una sílaba que la otra, la letra inicial y la final deben ser distintas.
Como queremos que haya más sílabas $OF$ que $FO$, necesitamos que el primer (y el último) cambio de bloque sea de $O$ a $F$ (y que entonces impliquen sílabas $OF$).

Por lo tanto todas las palabras oficiales son las que tienen como primera letra $O$ y última letra $F$. Como quedan los $6$ lugares del medio, y en cada uno puede ir una de dos letras, hay $2^6=64$ palabras oficiales en la lista de Franco.
2  

Fedex

OFO - Medalla de Plata
Mensajes: 4
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 1
Nivel: 3

Re: OFO 2020 Problema 2

Mensaje sin leer por Fedex » Mié 19 Feb, 2020 5:37 pm

Noooo Federico, se la complicó al pedo Federico
Spoiler: mostrar
Si tomamos una palabra y la espejamos, transformando todas las $O$ en $F$ y las $F$ en $O$ podemos formar una pareja entre una palabra en donde hay más $OF$ que $FO$ (oficial) y su espejada no-oficial. Porque toda silaba $OF$ se torna en $FO$ y viceversa, así que si en determinada palabra hay más de alguna silaba, en su espejada hay más de la otra. Llamemos $S$ al valor de todas las palabras oficiales y no-oficiales, por lo que acabo de explicar, $\frac{S}{2}$ es el valor de las palabras oficiales.
Ahora llamemos $T$ al valor de todas las palabras que pueden formarse. Es fácil ver como:
$T=2^8$
Porque en cada posición (que son 8) se puede meter una $F$ o una $O$ y nos importa mucho el orden en el que aparecen

Ahora veamos lo siguiente: No solo existen silabas $OF$ y $FO$, también pueden aparecer $OO$ y $FF$ que las llamaremos silabas mudas, porque no intervienen en la pelea entre $FO’s$ y $OF’s$.
Una "Palabra muda" es aquella en la que el valor de $OF’s$ y $FO’s$ es el mismo. Notemos que si espejamos una palabra muda, su espejada es muda también, porque en la primera $OF=FO$ y en la segunda las invertimos y $FO=OF$, que es lo mismo. (Una silaba muda espejada $OO$ o $FF$ al ser espejada se vuelve una silaba muda también)
Llamemos $M$ al valor de la cantidad de palabras mudas, tenemos lo siguiente:
$T=S+M$
$S=T-M$

Por lo que, ahora tenemos que contar caso por caso la cantidad de palabras mudas teniendo en cuenta esto: Sin perdida de generalidad, vamos a tomar una palabra muda empezada por $F$, al espejarla obtendremos una palabra muda empezada por $O$, por lo que podemos agruparlas en parejas de 2 y el total de palabras mudas, será el doble del valor de palabras mudas empezadas por $F$.

Caso 1: $OF=FO=0$
En este caso si empezamos con una $F$, no podemos agregar ninguna $O$ a su derecha porque de lo contrario aparece una silaba $FO$ y nosotros buscamos que no haya ninguna de las dos. Por lo que la unica que puede formarse es $FFFFFFFF$y su inversa $OOOOOOOO$.
2 Palabras

Caso 2: $OF=FO=1$
En este caso empecemos con lo que buscamos, que empaten en 1 las $F$ y las $O$. Así que vamos a empezar con $F$ y formar la base $F_O_F_$.
Nos quedan 5 letras mas que pueden ser tanto $F’s$ o $O’s$ y deberán estar ubicadas en los espacios entre las letras de la base. Las que aparezcan situadas a la derecha de una $F$ deberán ser una $F$ ya que darán lugar a una silaba muda que no influye y seguirá formando una silaba $FO$ con la $O$ a su derecha (En caso de que haya una). Pasando lo contrario con las letras ubicadas a la derecha de una $O$.
Y ahora es como si las letras fueran bolitas y los espacios cajitas (que pueden estar vacias sin problema), siendo el numero combinatorio resultante:
$\binom{5+3-1}{3-1}$
y el resultado de las palabras mudas totales:
$\binom{7}{2}.2=42$
(El $.2$ es porque en el numero combinatorio estamos contando unicamente las palabras empezadas con $F$ y debemos contar tambien las espejadas empezadas con $O$)
42 Palabras

Caso 3: $OF=FO=2$
Acá voy a seguir con la misma lógica, la base es $F_O_F_O_F_$, quedan 3 letras, hay 5 cajas, por lo que el resultado de palabras de este tipo es:
$\binom{3+5-1}{5-1}.2 = \binom{7}{4}.2 = 70$
70 Palabras

Caso 4: $OF=FO=3$
La base es $F_O_F_O_F_O_F_$, queda 1 letra, 7 cajas, el combinatorio es:
$\binom{7}{6}.2 = 14$
14 Palabras

$M=2+42+70+14=128$

Por lo que:
$S=T-M$
$S=2^{8}-128=128$

Recordemos que por lo que explique al comienzo, $\frac{S}{2}$ es la cantidad de palabras oficiales:
$\frac{S}{2}= \frac{128}{2} = 64$

Respuesta final: Hay $64$ palabras oficiales.
4  
$B_{ruh}$ $M_{oment}$

Responder