FOFO 9 años Problema 7

Avatar de Usuario
Chino2000

OFO - Medalla de Plata FOFO 7 años - Medalla Especial FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 38
Registrado: Mar 09 Dic, 2014 10:18 pm
Medallas: 6
Nivel: 1

FOFO 9 años Problema 7

Mensaje sin leer por Chino2000 » Jue 10 Oct, 2019 11:33 pm

El Chino, todos los viernes por la noche, da un show de Stand Up en un auditorio de una sola fila. Al final de cada show, los espectadores pueden aplaudir $(A)$ si les gustó, o arrojar tomates $(T)$ si no quedaron satisfechos. El Chino, luego de cada show, dice que su público es copado, si en la primera fila no encuentra $3$ personas del público consecutivas tales que las dos personas de los extremos le arrojen tomates pero la del medio aplauda ($T-A-T$), o el público es ortiva, si no encuentra $4$ personas consecutivas en la primera fila tales que las primeras dos personas aplaudan y las última dos arrojen tomates, o viceversa ($A-A-T-T$ o $T-T-A-A$).

El Chino, además de buen comediante, es un gran matemático, y llegó a la conjetura de que la cantidad de combinaciones posibles para un público copado de $n$ personas es igual a la mitad de la cantidad de combinaciones para un público ortiva de $n+1$ personas. Ayuda al Chino a demostrar que está en lo cierto.

Avatar de Usuario
Chino2000

OFO - Medalla de Plata FOFO 7 años - Medalla Especial FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 38
Registrado: Mar 09 Dic, 2014 10:18 pm
Medallas: 6
Nivel: 1

Re: FOFO 9 años Problema 7

Mensaje sin leer por Chino2000 » Dom 13 Oct, 2019 8:34 pm

Aquí vamos a publicar la solución oficial

Avatar de Usuario
Ivan

Colaborador
Mensajes: 1009
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: FOFO 9 años Problema 7

Mensaje sin leer por Ivan » Mar 15 Oct, 2019 2:26 pm

Muy lindo problema! La solución que subo es un poco avanzada y puede parecer artificial pero a mi me resultó bastante natural. Hay dos ideas. La primera tiene que ver con autómatas finitos. La segunda es el concepto de revestimiento, que aparece en topología. Al final pongo las definiciones necesarias para que se pueda entender sin conocer estos conceptos.

Solución:
Spoiler: mostrar
Observación 1:
La cantidad de combinaciones copadas de largo $n$ es la cantidad de caminos de largo $n-2$ en el grafo $\Gamma_{copado}$:
grafo1.png
Demostración:
Spoiler: mostrar
Dada una palabra copada de largo $n$ formada por las letras $A$ y $T$ nos construimos un camino de largo $n-2$ en dicho grafo. Las primeras dos letras determinan en qué vértice comenzamos. Luego las demás letras van indicando que arista tomar. Notar que a su vez todo camino determina una palabra copada.

La clave para armar este grafo es que la etiqueta del vértice donde estamos después de caminar un rato está formada por las últimas dos letras que leimos de la palabra. Si las últimas dos letras son $TA$ no podemos leer una $T$, por eso no hay una arista $TA\to AT$ en ese grafo.
Observación 2:
La cantidad de combinaciones ortivas de largo $n+1$ es la cantidad de caminos de largo $n-2$ en el grafo $\Gamma_{ortiva}$:
grafo2n.png
Demostración:
Spoiler: mostrar
Igual que antes, a partir de una palabra copada de largo $n+1$ formada por las letras $A$ y $T$ nos construimos un camino de largo $n-2$ en dicho grafo. Las primeras tres letras determinan en qué vértice comenzamos. Luego las demás letras van indicando que arista tomar (no etiqueté en rojo las aristas como en el otro grafo, pero igual que antes cada arista representa agregar una $A$ o una $T$). Notar que a su vez todo camino determina una palabra copada.
Para concluir basta notar que hay un revestimiento $p:\Gamma_{ortiva}\to \Gamma_{copado}$ con fibra de cardinal $2$.
Spoiler: mostrar
Concretamente, el revestimiento está dado por $p(AAA)=p(TTT)=TT$, $p(AAT)=p(TTA)=TA$, $p(ATA)=p(TAT)=AA$ y $p(ATT)=p(TAA)=AT$.
Background de grafos:
Spoiler: mostrar
Definición: Un grafo (dirigido) $\Gamma$ consiste de un conjunto $V$ (los vértices de $\Gamma$) y un conjunto $E\subset V\times V$ (las aristas de $\Gamma$).

Si $\Gamma = (V,E)$ es un grafo y $v\in V$ notamos $N_+(v)=\{w \in V \,:\, (v,w)\in E\}$ y $N_-(v)=\{w \in V \,:\, (w,v)\in E\}$

Definición: Sean $\Gamma=(V,E)$ y $\Gamma'=(V',E')$ dos grafos. Un morfismo de grafos $f: \Gamma \to \Gamma'$ es una función $f:V\to V'$ tal que para toda arista $(v,w)\in E$ se tiene que $(f(v),f(w))\in E'$.

Si $f$ es morfismo de grafos también notamos $f$ a la función $f:E\to E'$ dada por $f((v,w))=(f(v),f(w))$. Notar que si $f$ es morfismo de grafos entonces $f( N_+(v) ) \subset N_+(f(v))$ y $f( N_-(v) ) \subset N_-(f(v))$.

Definición: Sean $\Gamma=(V,E)$ y $\widetilde{\Gamma}=(\widetilde{V},\widetilde{E})$ dos grafos. Un morfismo de grafos $p:\widetilde{\Gamma}\to \Gamma$ es un revestimiento si
(i) la función $p:\widetilde{V}\to V$ es sobreyectiva.
(ii) para todo vértice $\widetilde{v}\in \widetilde{V}$ $p: N_+(\widetilde{v})\to N_+(p(\widetilde{v}))$ y $p: N_-(\widetilde{v})\to N_-(p(\widetilde{v}))$ son biyectivas.

Una forma de entender intuitivamente el concepto de revestimiento es la siguiente: el grafo $\widetilde{\Gamma}$ es localmente igual al grafo $\Gamma$, pero globalmente lo reviste varias veces.

Definición: Un camino de largo $k$ en un grafo $\Gamma$ es una $(k+1)$-upla $(v_0,v_1,\ldots, v_k)$ tal que $(v_i,v_{i+1})$ es una arista para cada $i=0,\ldots,k-1$.

Lema (levantamiento único de caminos): Sea $c= (v_0,v_1,\ldots, v_k)$ un camino en $\Gamma$. Sea $p:\widetilde{\Gamma}\to \Gamma$ un revestimiento. Sea $\widetilde{v}_0\in p^{-1}(v_0)$. Entonces existe un único camino $\widetilde{c}= (\widetilde{v}_0,\widetilde{v}_1,\ldots, \widetilde{v}_k)$ en $\widetilde{\Gamma}$ tal que $p(\widetilde{v}_i)=v_i$ para todo $i$.

Definición: Un grafo $\Gamma=(V,E)$ se dice conexo si no existen subconjuntos no vacíos $V_0, V_1 \subset V$ tales que $V=V_0\cup V_1$, $V_0\cap V_1 = \emptyset$ y $E\subset (V_0\times V_0) \cup (V_1\times V_1)$.

Definición: Si $p:\widetilde{\Gamma}\to \Gamma$ es un revestimiento, la fibra de un vértice o una arista es su preimagen por $p$.

Proposición: Si $\Gamma$ es conexo, la cantidad de elementos de la fibra es constante (no depende del vértice o arista que hayamos tomado).

Corolario: Si $p:\widetilde{\Gamma}\to \Gamma$ es un revestimiento, $\Gamma$ es conexo y el cardinal de la fibra es $k$, la cantidad de caminos de largo $n$ en $\widetilde{\Gamma}$ es $k$ veces la cantidad de caminos de largo $n$ en $\Gamma$.

Demostración: Cada camino se puede levantar de $k$ formas (hay exactamente una por cada elemento en la fibra del primer vértice).
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
7  
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 183
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: FOFO 9 años Problema 7

Mensaje sin leer por BrunZo » Mar 15 Oct, 2019 4:11 pm

Ivan escribió:
Mar 15 Oct, 2019 2:26 pm
Muy lindo problema! La solución que subo es un poco avanzada y puede parecer artificial pero a mi me resultó bastante natural. Hay dos ideas. La primera tiene que ver con autómatas finitos. La segunda es el concepto de revestimiento, que aparece en topología. Al final pongo las definiciones necesarias para que se pueda entender sin conocer estos conceptos.

Solución:
Spoiler: mostrar
(No voy a citar todo el post de arriba)
Background de grafos:
Spoiler: mostrar
(Ídem)
Traducción:
Spoiler: mostrar
Resultá que en un show con $n+1$ personas ocurrió lo siguiente: para cada una de las parejas de personas consecutivas, si eran ambas del mismo tipo, $AA$ ó $TT$, emerge en el medio una de tipo $T$, y si eran de distinto tipo, emerge en el medio una de tipo $A$, resultando $n$ personas. Finalmente, las $n+1$ personas originales salen del lugar.
Ejemplo:
p7.png
Y el argumento de Iván se centra en ver que
(a) Las parejas de públicos "opuestos" de $n+1$ personas que se obtienen al cambiar $A\to T$ y $T\to A$ se vuelven un mismo público (p. ej.: $AATTA$ y $TTAAT$ se vueven $TATA$) , mientras que cada público de $n$ personas puede emerger de una sola pareja de públicos opuestos ($TATA$ sólo puedo venir de esos dos públicos).
(b) Las secuencias $AATT$ y $TTAA$ se vuelven ambas $TAT$, mientras que $TAT$ sólo puede emerger de $AATT$ ó $TTAA$.
La clave está en que esto último implica que el público del principio es ortiva si y sólo si el público del final es copado, por lo que combinando esto con (a), se ve que cada un público copado de $n$ personas, hay dos públicos ortivas de $n+1$ personas y viceversa, lo que demuestra el problema.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Última edición por BrunZo el Mié 16 Oct, 2019 4:41 pm, editado 1 vez en total.
2  

Avatar de Usuario
Joacoini

OFO - Medalla de Plata FOFO 8 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 208
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 4
Nivel: 2
Ubicación: Ciudad Gotica

Re: FOFO 9 años Problema 7

Mensaje sin leer por Joacoini » Mié 16 Oct, 2019 1:02 pm

Spoiler: mostrar
Sea $c_n$ la cantidad de combinaciones posibles para un público copado de $n$ personas y $o_n$ la cantidad de combinaciones para un público ortiva de $n$ personas.

Si $d_n$ la cantidad de combinaciones posibles para un público copado de $n$ personas que terminan en $T-A$ y $p_n$ la cantidad de combinaciones para un público ortiva de $n$ personas que terminan en $A-A-T$ (que también es la cantidad de combinaciones para un público ortiva de $n$ personas que terminan en $T-T-A$, ya que al invertir las $T$ por $A$ y viceversa tenemos una biyección).

(1) $c_n=2c_{n-1}-d_{n-1}$ ya que a cada tira de $n-1$ copada le podes agregar una $T$ o una $A$ al final y obtener otra tira copada excepto cuando termina en $T-A$.

(2) $d_{n-1}=c_{n-3}-d_{n-3}$ ya que una tira de $n-1$ copada que termina en $T-A$ empieza con una tira de $n-3$ copada que no termina en $T-A$ y luego le sigue $T-A$.

De (1) sacamos que $d_{n-1}=2c_{n-1}-c_n$ y que $d_{n-3}=2c_{n-3}-c_{n-2}$, combinando esto con (2)
$2c_{n-1}-c_n=c_{n-3}-2c_{n-3}+c_{n-2}\Rightarrow c_n=2c_{n-1}-c_{n-2}+c_{n-3}$

(4) $o_{n+1}=2o_n-2p_n$ ya que a cada tira de $n$ ortiva le podes agregar una $T$ o una $A$ al final y obtener otra tira ortiva excepto cuando termina en $T-T-A$ o $A-A-T$.

(5) $p_n=o_{n-3}-p_{n-3}-p_{n-2}$ ya que una tira de $n$ ortiva que termina en $A-A-T$ empieza con una tira de $n-3$ ortiva que no termina en $T-T-A$ ni en $T-T$ (notar que si a una tira de $n-3$ ortiva que termina en $T-T$ le agregas una $A$ tenes una tira de $n-2$ ortiva que termina en $T-T-A$ por lo que tenemos una biyección) y luego le sigue $A-A-T$.

De (4) obtenemos $2p_n=2o_n-o_{n+1}$, $2p_{n-2}=2o_{n-2}-o_{n-1}$ y $2p_{n-3}=2o_{n-3}-o_{n-2}$, multiplicando (5) por $2$ y remplazando.

$2o_n-o_{n+1}=2o_{n-3}-2o_{n-3}+o_{n-2}-2o_{n-2}+o_{n-1}\Rightarrow o_{n+1}=2o_n-o_{n-1}+o_{n-2}$

Tenemos que $c_1=o_1=2$, $c_2=o_2=4$, $c_3=7$, $o_3=8$, $c_4=12$ y $o_4=14$.
Tenemos que para $i$ igual a $1, 2$ ó $3$ se cumple que $2c_i=o_{i+1}$

Supongamos que para $i\leq n-1$ con $3\leq n-1$ se cumple que $2c_i=o_{i+1}$.
Tenemos que $2c_n=4c_{n-1}-2c_{n-2}+2c_{n-3}=2o_n-o_{n-1}+o_{n-2}=o_{n+1}$

Completada la inducción nos damos cuenta que el Chino tenia razón.

3  
NO HAY ANÁLISIS.

Responder