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 OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 164
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 9
Nivel: Exolímpico
Contactar:

Nos vemos

Mensaje sin leer por ¿hola? »

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 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nos vemos

Mensaje sin leer por Fran5 »

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 //
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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 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: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nos vemos

Mensaje sin leer por Gianni De Rico »

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$)
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años 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
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
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Re: Nos vemos

Mensaje sin leer por Monazo »

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.

Soy una Estufa en Piloto
:shock:
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 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Nos vemos

Mensaje sin leer por BrunZo »

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 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nos vemos

Mensaje sin leer por Fran5 »

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 //
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 OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 164
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 9
Nivel: Exolímpico
Contactar:

Re: Nos vemos

Mensaje sin leer por ¿hola? »

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 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Nos vemos

Mensaje sin leer por BrunZo »

¿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...
Carlos V.
Mensajes: 13
Registrado: Lun 19 Oct, 2020 10:14 pm

Re: Nos vemos

Mensaje sin leer por Carlos V. »

Spoiler: mostrar
Retomo un poco la idea de Fran 5 de la recurrencia.
Supongamos que llamo P(k) a la cantidad de partidas en las que " no hay ganadores en un grupo de k-personas". Es decir que nos interesa P(12).

Supongamos resuelto el problema para el caso P(n), n<12.
Si agregamos una nueva persona:
P(n+1)=n*P(n)+n*(n-1)^n

Explico brevemente de dónde salen los factores:

n*P(n) corresponde a que por cada combinación "no ganadora" en el caso de n-personas agrego una nueva persona que puede mirar a n-personas (sin ser mirada por el resto).
Por otro lado el factor n*(n-1)^n corresponde a que la nueva persona, digamos p_(n+1) , debe ser mirada por al menos una persona: supongamos que p_(1) ve a p_(n+1), luego p_(n+1) tiene n-1 posibilidades (no puede mirar a p_(1)), y así sucesivamente cada persona puede optar por n-1 posibilidades. Por lo tanto, como p_(1) es arbitrario tenemos el factor n.
El resultado se sigue reemplazando en la recurrencia:
P(3)=2, P(4)=30, P(5)=444, P(6)=7340, P(7)=137790, etc
Responder