Nos vemos

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 149
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Nos vemos

Mensaje sin leer por ¿hola? » Vie 09 Oct, 2020 5:42 pm

Hay $12$ personas $p_1,p_2,...,p_{12}$ jugando un juego, que consiste en que, al mismo tiempo, todos miran a un jugador y los que se miran mutuamente ganan. Determinar en cuantas posibles partidas distintas no hay ganadores.

Nota: dos partidas son distintas, si y solo si, existen personas $p_a$ y $p_b$ tal que en una partida $p_a$ mira a $p_b$ y en la otra partida no.
1  
Yes, he who

Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 971
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nos vemos

Mensaje sin leer por Fran5 » Sab 10 Oct, 2020 11:24 am

Spoiler: mostrar
El problema es equivalente a hallar el cardinal del conjunto de permutaciones que no contienen transposiciones (parejas ganadoras) ni puntos fijos (gente que no entendió las reglas del juego)

Si una persona $q_1$ mira a otra persona $q_2$ y $q_2$ mira a otra persona $q_3$ así siguiendo hasta que la persona $q_{n_k}$ mire a la persona $q_1$. Entonces tenemos un "ciclo" (o grupo) de longitud $n_k$ en nuestra permutación

Entonces todas estas permutaciones serán de tipo $n_1n_2\ldots n_k$ donde $n_i > 2$, $n_i \leq n_{i+1}$ y $\sum n_i = 12$.
Luego pueden ser:

3-3-3-3
3-3-6
3-4-5
3-9
4-4-4
4-8
5-7
6-6

En el primer caso tenemos $4$ grupos, así que podemos pensar en $\frac{12!}{4!}$ formas de armarlos ordenadamente (de la forma $(p,q,r)$). Sin embargo, en cada grupo hay que dividir por $3$ ya que la sucesión de miradas $p \to q \to r \to p$ es lo mismo que $q \to r \to p \to q$ y $r \to p \to q \to r$. Luego tenemos $\frac{12!}{3^4 \cdot 4!}$
Del mismo modo, en el caso 4-4-4 tenemos $\frac{12!}{4^3 \cdot 3!}$ y en el caso 6-6 tenemos $\frac{12!}{6^2 \cdot 2!}$

En el caso 3-3-6 usamos la misma idea, pero con una observación. Tenemos $12! $ formas de ordenar las personas, y pero sólo $2!$ formas equivalentes de armar cada grupo, ya que $(p_1 p_2 p_3)(q_1 q_2 q_3) (r_1 \ldots r_6) \neq (r_1 r_2 r_3)(r_4 r_5 r_6)(p_1 \ldots q_3)$. Ahora, en cada grupo hay $3$, $3$ y $6$ formas de ordenarlos igual (respectivamente) ya que $(p_1p_2p_3) = (p_3p_1p_2)$ y $(r_1 \ldots r_6) = (r_3 \ldots r_2)$. (cambié la notación :twisted: )
Luego tenemos $\frac{12!}{3^2 \cdot 6 \cdot 2!}$
Para los casos 3-4-5, 3-9, 4-8 y 5-7, podemos ordenarlos de $12!$ formas distintas armando siempre partidas distintas, pero dividimos por los tamaños de los grupos para no contar varias veces la misma partida (recordamos que $(p_1 p_2 p_3 p_4)(q_1 \ldots q_8) = (p_3 p_4 p_1 p_2)(q_1 \ldots q_8)$)
Luego tenemos, respectivamente, $\frac{12!}{3 \cdot 4 \cdot 5}$, $\frac{12!}{ 3\cdot 9 }$, $\frac{12!}{4 \cdot 8}$, $\frac{12!}{5 \cdot 7}$.

Le dejo al que quiera, hacer las cuentas.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 1420
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nos vemos

Mensaje sin leer por Gianni De Rico » Sab 10 Oct, 2020 12:28 pm

Fran5 escribió:
Sab 10 Oct, 2020 11:24 am
Spoiler: mostrar
Luego pueden ser:

3-3-3-3
3-3-6
3-4-5
3-9
4-4-4
4-8
5-7
6-6
Spoiler: mostrar
No falta el ciclo de $12$? ($p_i\to p_{i+1}$ para todo $i$)
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 241
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 9
Nivel: Ñandú

Re: Nos vemos

Mensaje sin leer por Monazo » Sab 10 Oct, 2020 1:40 pm

Hay algo que no me está cerrando.
Spoiler: mostrar
No revisé las cuentas en realidad, pero por lo que menciona Gallu está viendo siempre "ciclos". Por ejemplo si dividimos en la proporción $4-4-4$, cuando divide por $4$ me parece que asume que todo ese grupo es una componente fuertmente conexa, es decir que si me paro en un chabón, y me muevo por las miradas, entonces en algún momento voy a llegar nuevamente a ese loquito. Pero puede haber configuraciones del tipo:

$1 \to 2$
$2\to 3$
$3\to 4$
$4\to 2$

Y si nos paramos por primera vez en el $1$, vemos que a través de las miradas nunca llegamos nuevamente.

No sé si las cuentas de Gallu contemplan esos casitos, no me puse a verlo detalladamente.

El Diego es del Lobo! Y del Lobo no se va!

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-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
Mensajes: 280
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: Nos vemos

Mensaje sin leer por BrunZo » Sab 10 Oct, 2020 1:58 pm

Monazo escribió:
Sab 10 Oct, 2020 1:40 pm
Hay algo que no me está cerrando.
Spoiler: mostrar
No revisé las cuentas en realidad, pero por lo que menciona Gallu está viendo siempre "ciclos". Por ejemplo si dividimos en la proporción $4-4-4$, cuando divide por $4$ me parece que asume que todo ese grupo es una componente fuertmente conexa, es decir que si me paro en un chabón, y me muevo por las miradas, entonces en algún momento voy a llegar nuevamente a ese loquito. Pero puede haber configuraciones del tipo:

$1 \to 2$
$2\to 3$
$3\to 4$
$4\to 2$

Y si nos paramos por primera vez en el $1$, vemos que a través de las miradas nunca llegamos nuevamente.

No sé si las cuentas de Gallu contemplan esos casitos, no me puse a verlo detalladamente.

Spoiler: mostrar
Claro, yo pensé lo mismo. Me parece que en este caso no se tienen permutaciones sino simplemente elecciones de números. En principio uno podría pensar que hay $12^{12}$ juegos posibles (cada persona puede ver a alguna de las $12$ personas), pero tenemos que quitar los casos que tienen ciclos de longitud 1 o 2 (es decir, nadie se puede mirar a sí mismo y si A mira a B, entonces B no puede mirar a A). Yo creo que podríamos decir que el problema pide hallar la cantidad de grafos dirigidos de $12$ vértices, todos con grado saliente 1 tales que no hay ningún ciclo de 1 o de 2.
Igualmente, como $12$ es un número esencialmente chiquito, así que tengo la intuición de que la misma idea funciona pero hay que hacer otra cuenta. No estoy seguro igual...

Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 971
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nos vemos

Mensaje sin leer por Fran5 » Sab 10 Oct, 2020 3:42 pm

es verdad :roll: :roll: :roll: :roll: :roll: :roll:
Spoiler: mostrar
A ver si esto les convence....
Hacemos la cuenta y llamamos $P(12)$ a esta cantidad.
Repetimos el argumento para $11$ o menos jugadores y obtenemos $P(11), P(10),...P(1)$. Notar que $P(1) = P(2)=0$, ya que o bien no se puede jugar, o bien no se puede "no ganar".

Ahora, para cada $1 \leq k \leq 12$ tenemos $\binom{12}{k}$ de elegir estas $k$ personas que formen ciclos, y habrá $12-k$ personas que mirarán a alguien pero no serán miradas. Tenemos que asignarle alguna de las $11$ personas restantes sin que se formen ciclos. Entonces podemos nombrarlas como $r_{k+1}, r_{k+2}, \ldots r_{12}$ de modo que ninguna persona $r_j$ sea mirada por alguna de las primeras $k$ personas. En particular este reetiquetamiento nos permite pensar que $r_j$ mira a alguna persona $r_l$ con $l < j$ (puede ser $l \leq k$) y que si no habría un ciclo donde dijimos que no había, y por lo tanto tenemos $11 \cdot 10 \cdots k = \frac{11!}{(k-1)!}$ posibilidades para asignar las miradas. Como había $\binom{12}{k} = \frac{12!}{k!(12-k)!}$ formas de elegir los ciclos, tenemos $\frac{11!12!}{k!(k-1)!(12-k)!} P(k)$ formas de armar estos juegos, y luego sumamos en $k$
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 149
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Re: Nos vemos

Mensaje sin leer por ¿hola? » Sab 10 Oct, 2020 8:13 pm

Fran5 escribió:
Sab 10 Oct, 2020 3:42 pm
Como había $\binom{12}{k} = \frac{12!}{k!(12-k)!}$ formas de elegir los ciclos, tenemos $\frac{11!12!}{k!(k-1)!(12-k)!} P(k)$
¿Estas usando $P(k)$ como la cantidad de formas, en las que, las $k$ primeras personas pueden estar en ciclos? si entendí, esta función no cuenta eso.
Yes, he who

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-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
Mensajes: 280
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: Nos vemos

Mensaje sin leer por BrunZo » Dom 11 Oct, 2020 8:27 pm

¿Esta idea funciona?
Spoiler: mostrar

Aviso: Como $12$ es chiquito, vamos a hacer algo casos.

Lo primero es ver que la configuración que tenemos es un conjunto de partes conexas, que consisten de un único "ciclo" y "cadenas" que caen en el ciclo. Una forma de ver esto:
Spoiler: mostrar
Supongamos (por un momento) que podemos poseer a cualquier persona a nuestra elección. Supongmos que empezamos poseyendo a alguien arbitrario, digamos ¿hola?. Lo que vamos a hacer es poseer a la única persona que ¿hola? está mirando y así siguiendo. Notemos que si repetimos esto, siempre se termina llegando a un ciclo, dado que hay sólo finitas personas (el ciclo puede no contener a ¿hola?, puede ocurrir que se vuelva a una persona posterior a ¿hola?). Llamemos c al ciclo.
Ahora, llamo la vecinidad de c al conjunto de personas que, si hacemos la cadena de posesiones, se termina entrando en el ciclo c (incluyo a las personas en ese ciclo). Notemos que esta vecinidad cumple las propiedades que dijimos al principio (es un único ciclo con cadenas que caen en él). Supongamos que otra persona, digamos BrunZo, no pertenece a esta vecinidad. Si haciendo la cadena de posesiones se llega a cualquier persona en la vecinidad de c, sabemos que, por definición de vecinidad, terminaríamos entrando en c; pero como BrunZo no está en la vecinidad de c, sabemos que esto no puede pasar, así que podemos decir que la vecinidad de c es una componente conexa (es decir, no está conectada de ninguna forma al resto de personas). Repitiendo el razonamiento, ahora con BrunZo, y seguimos armándonos partes conexas, terminamos viendo lo que queremos.

Como dato aparte, este lema vale sólo porque cada persona mira a una única persona y entonces podemos formarnos "cadenas de posesiones". En grafos en general esto es claramente falso (por ejemplo, alguien podría mirar dos ciclos, uno con cada ojo).
Ahora, por la condición del enunciado, sabemos que cada ciclo tiene que medir al menos 3, y además la suma de las longitudes de los ciclos es a lo sumo 12 (y el resto de personas están en las cadenas). Bueno... Pero entonces no hay muchos casos, son sólo:

3, 4, 5, 6, 7, 8, 9, 10, 11, 12;
3-3, 3-4, 3-5, 3-6, 3-7, 3-8, 3-9, 4-4, 4-5, 4-6, 4-7, 4-8, 5-5, 5-6, 5-7, 6-6;
3-3-3, 3-3-4, 3-3-5, 3-3-6, 3-4-4, 3-4-5, 4-4-4;
3-3-3-3.

Ahora, veamos como contar la cantidad de juegos en cada caso:

Empecemos viendo como contar la cantidad de formas de armar los ciclos. Supongamos que en total hay k personas en alguno de los ciclos. Digamos que hay N formas de hacerlo. Supongamos que podemos en una fila a estas k personas, con el siguiente criterio: Primero ordenamos los ciclos por longitud, y luego "desenvolvemos" los ciclos y alineamos las personas de cada ciclo, y entonces unimos las filas de menor a mayor por longitud de ciclo. Notemos que acá estamos tomando varias decisiones: Primero que nada, para un ciclo de longitud l, el ciclo puede desenvolverse de l formas (podemos poner en primer lugar a cualquier persona). Segundo, notemos que si hay dos ciclos de la misma longitud, entonces podemos ponerlos en cualquier orden. Bueno, entonces notemos que la cantidad de formas de "desenvolver" los ciclos es (producto de longitudes de los ciclos) * (producto de s! para cada s ciclos de la misma longitud). Es decir, si hay c3 ciclos de 3, c4 ciclos de 4, etc. (posiblemente 0 o 1), entonces la cantidad de formas es 3^c3 * 4^c4 * 5^c5 * ... * c3! * c4! * c5! * ...
Ahora, como dijimos que hay N posibles configuraciones iniciales, la cantidad de filas "desenvueltas" es N * (3^c3 * 4^c4 * 5^c5 * ... * c3! * c4! * c5! * ...). Lo que quizás nos interesaría es ver que todas estas filas son distintas, pero esto se puede ver claro sabiendo que la operación inversa es posible (o sea, dada una fila podemos "envolverla" en los distintos ciclos, aunque quizás obtengamos filas repetidas). Usamos la palabra biyección y listo.

Bueno, lo que prueba esta "biyección" es que en realidad N * (3^c3 * 4^c4 * 5^c5 * ... * c3! * c4! * c5! * ... = cant. de filas posibles, o dicho de una forma más práctica
N = (cant. de filas posibles) / (3^c3 * 4^c4 * 5^c5 * ... * c3! * c4! * c5! * ...)
Bueno, pero en realidad la cantidad de filas posibles es simplemente k! (porque no hay ninguna restricción respecto a qué personas ponemos en qué ciclos), así que ya tenemos la cuenta lista.

Sólo falta ver que hacemos con los 12-k faltantes. Y bueno... Acá es donde se pone complicado... Porque estos faltantes pueden formar solo árboles (es decir, grafos sin ciclos) y entonces hay un nodo de cada árbol que se conecta a alguno de los k con ciclo... Pero la cantidad y el tamaño de los árboles es variable. Lo que si se puede usar es que la cantidad de árboles con n nodos es n^(n-2) y que si queremos elegir una "raíz" (o un nodo que conectar a alguno de los otros k), entonces hay n^(n-1), y esto tenemos que multiplicarlo por k^(cantidad de raíces), y después multiplicarlo por la otra cuenta para N.

La verdad es que de acá no sé cómo seguirlo... Son muchas cuentas, pero una persona lo suficientemente diligente podría hacerlas todas. Yo hice algunos casos chiquitos y para 3, 4, 5 y 6 personas, la cuenta me dio 2, 30, 444 y 7320 (puede ser que las haya hecho mal). Seguro hay algo un toque más elegante...

Responder