[Jambo]

Hola! Soy yo de nuevo 

Tengo dudas sobre ciertos ejercicios, espero que alguien pueda ayudarme...

1. 8 amigos de juntan a jugar X juego (que se juega en pareja) y forman 4 equipos para jugar un campeonato. ¿Cuantos campeonatos deben jugarse para poder asegurar que todos jugaron con las mismas parejas tres veces?
Sé que se resuelve con el "Principio del Palomar", pero no me doy cuenta como definir las "palomas" y los "nidos" (en general estos ejercicios no me salen ¿algún consejo?)

2. Tengo que probar la siguiente igualdad: \( Sob(m+1,n)=n(Sob(m,n-1)+Sob(m,n))=nSob(m,n-1)+nSob(m,n) \), donde \( Sob(m,n) \) es la cantidad de funciones sobreyectivas \( f:A\rightarrow{B} \) donde la cantidad de elementos de \( A \) es \( m \) y la de \( B \) es \( n \). No entiendo porque debo multiplicar por \( n \)  (tiene que ver con el elemento que no "relaciono" usando \( Sob \)...¿pero por que por \( n \)?)

Gracias de antemano 

[Luis Fuentes]

Hola

1. 8 amigos de juntan a jugar X juego (que se juega en pareja) y forman 4 equipos para jugar un campeonato. ¿Cuantos campeonatos deben jugarse para poder asegurar que todos jugaron con las mismas parejas tres veces?
Sé que se resuelve con el "Principio del Palomar", pero no me doy cuenta como definir las "palomas" y los "nidos" (en general estos ejercicios no me salen ¿algún consejo?)

El enunciado me parece poco claro. ¿Las parejas son fijas o van variando?. ¿Cada campeonato consiste en organizar un par de enfrentamientos de dos pares de parejas?. ¿Se trata de que cada pareja se enfrente a las otras tres un total de tres veces?.

2. Tengo que probar la siguiente igualdad: \( Sob(m+1,n)=n(Sob(m,n-1)+Sob(m,n))=nSob(m,n-1)+nSob(m,n) \), donde \( Sob(m,n) \) es la cantidad de funciones sobreyectivas \( f:A\rightarrow{B} \) donde la cantidad de elementos de \( A \) es \( m \) y la de \( B \) es \( n \). No entiendo porque debo multiplicar por \( n \)  (tiene que ver con el elemento que no "relaciono" usando \( Sob \)...¿pero por que por \( n \)?)

Si \( A=\{a_1,a_2,\ldots,a_{m+1}\} \), consideramos las aplicaciones sobreyectivas de \( A \) en \( B \) con \( card(B)=n \).

Para cada una de esas aplicaciones \( f \) nos fijamos en la imagen de \( a_{m+1} \): hay \( n \) posibles imágenes.

Después los elementos restantes definen una aplicación \( A-\{a_{m+1}\}\to B \), que:

- o bien sigue siendo sobreyectiva (hay \( Sob(m,n) \) aplicaciones de este tipo).
- o bien su conjunto imagen es \( B-\{f(a_{m+1}\} \) y por tanto hay tantas aplicaciones de este tipo como \( Sob(m,n-1) \).

Saludos.

[Jambo]

Hola, gracias por contestar 

1. Por lo que yo entendí, las parejas son fijas "por campeonato", es decir, en un campeonato hay ciertas parejas, pero para otro campeonato serán otras; un campeonato consiste en "Pareja vs. Pareja", donde salen 2 parejas ganadoras, y estas 2 ultimas se enfrentan; y si, se trata de que cada pareja se enfrente a las otras tres posibles parejas un total de tres veces...

2.

-o bien sigue siendo sobreyectiva (hay \( Sob(m,n)Sob(m,n) \) aplicaciones de este tipo).

En este caso quiere decir que \( f(a_{m+1}) \) tiene dos preimagenes? (¿y en el otro caso solo una?)

[Luis Fuentes]

Hola

1. Por lo que yo entendí, las parejas son fijas "por campeonato", es decir, en un campeonato hay ciertas parejas, pero para otro campeonato serán otras; un campeonato consiste en "Pareja vs. Pareja", donde salen 2 parejas ganadoras, y estas 2 ultimas se enfrentan; y si, se trata de que cada pareja se enfrente a las otras tres posibles parejas un total de tres veces...

Sigo sin verlo claro. ¿A que llamas "cada" pareja? Supongamos que los ocho jugadores son los números 1,2,3,4,5,6,8. Entonces quieres decir que cada posible par (n,m) tiene que haberse enfrentado a cualquier otro posible par (p,q) tres veces (fíjate que en ese caso no sé porque hablas de las "otras tres posibles parejas").

Tampoco me queda claro cuando el enunciado habla de que "todos jugaron con las mismas parejas", si se refiere por ejemplo a que el jugador 1 formo equipo con el 2 tres veces ó que la pareja (1,2) jugó contra cada una de las otras posibles parejas tres veces.

2.

-o bien sigue siendo sobreyectiva (hay \( Sob(m,n)Sob(m,n) \) aplicaciones de este tipo).

En este caso quiere decir que \( f(a_{m+1}) \) tiene dos preimagenes? (¿y en el otro caso solo una?)

Si, quiere decir que tiene dos o más preimágenes.

Saludos.

[Jambo]

Hola!

1.

Sigo sin verlo claro. ¿A que llamas "cada" pareja? Supongamos que los ocho jugadores son los números 1,2,3,4,5,6,8. Entonces quieres decir que cada posible par (n,m) tiene que haberse enfrentado a cualquier otro posible par (p,q) tres veces (fíjate que en ese caso no sé porque hablas de las "otras tres posibles parejas").

Si, eso. Como por ejemplo si yo tomo a la pareja (1,2), para elegir a la "segunda pareja" voy a tener \( \binom{6}{2} \), para la "tercera" \( \binom{4}{2} \) y para la "ultima" \( \binom{2}{2} \) (para la "primera" , si no fijara el (1,2) tendría  \( \binom{8}{2} \) posibles parejas ¿no?)

Tampoco me queda claro cuando el enunciado habla de que "todos jugaron con las mismas parejas", si se refiere por ejemplo a que el jugador 1 formo equipo con el 2 tres veces ó que la pareja (1,2) jugó contra cada una de las otras posibles parejas tres veces.

Me parece que se trata del ultimo caso...

Edito: Encontré la prueba donde estaba este ejercicio, con las opciones de respuesta

Spoiler

Con cierta frecuencia, hay 8 amigos que se juntan y
forman cuatro parejas para hacer un campeonato de
truco. Determine el mínimo número de campeonatos
que deberían hacerse, para asegurarse que, en al menos
tres campeonatos distintos, todos jueguen exactamente
con las mismas parejas. (A) 107 (B) 211 (C) 315 (D) 106 (E) 5041

*El truco es un juego de cartas y desconozco las reglas, así que no sé si afecten en el resultado  De todas formas creo que el campeonato consiste en lo mismo que te he dicho antes (Pareja vs. Pareja, donde la ganadora se enfrenta con la pareja  ganadora del otro encuentro...).

[cerrar]

[Luis Fuentes]

Hola

Con cierta frecuencia, hay 8 amigos que se juntan y
forman cuatro parejas para hacer un campeonato de
truco. Determine el mínimo número de campeonatos
que deberían hacerse, para asegurarse que, en al menos
tres campeonatos distintos, todos jueguen exactamente
con las mismas parejas. (A) 107 (B) 211 (C) 315 (D) 106 (E) 5041

Vale ahora ya lo entiendo.

En cada campeonato se forman cuatro equipos, cuatro parejas.

Se trata de calcular el mínimo número de campeonatos para asegurar que se ha repetido tres veces alguna configuración de cuatro equipos.

Entonces las formas distintas de distribuir los 8 jugadores en cuatro parejas son:

\( \dfrac{\displaystyle\binom{8}{2}\displaystyle\binom{6}{2}\displaystyle\binom{4}{2}\displaystyle\binom{2}{2}}{4!}=105 \)

Spoiler

Tenemos que elegir dos entre ocho para la primera pareja; dos entre seis para la segunda; dos entre cuatro para la tercera. Pero además en realidad no importa el orden en que elegimos la pareja: si AB quedaron emparejados da igual que lo hiciesen como primera pareja que como cuarta; por eso dividimos por \( 4! \).

[cerrar]

Ahora el número mínimo de campeonatos para asegurar tres configuraciones repetidas es \( 2\cdot 105+1 \).

Saludos.

[Jambo]

Hola!

Ahora el número mínimo de campeonatos para asegurar tres configuraciones repetidas es \( 2\cdot{}105+1 \)

No entendí porque haces eso 

[Luis Fuentes]

Hola

Hola!

Ahora el número mínimo de campeonatos para asegurar tres configuraciones repetidas es \( 2\cdot{}105+1 \)

No entendí porque haces eso 

Pues es ahí donde aplicamos el Principio del palomar.

Tenemos \( 105 \) "nidos", que son las \( 105 \) posibles configuraciones de equipos posibles.

Queremos hallar el mínimo número de palomas que colocadas en los nidos nos aseguren que al menos uno tiene tres palomas.

Por tal principio el número mínimo son \( 105\cdot 2+1 \) (en el peor de los casos tendríamos dos palomas en cada nido, y en alguno de ellos una paloma más).

Saludos.

[Jambo]

En este caso multiplicas por 2 porque eran 3 campeonatos como mínimo ¿no? Si el mínimo de campeonatos fueran 2 ¿la respuesta correcta sería 106?

¿Hay alguna forma de darme cuenta que son las "palomas" y los "nidos" (en general)? 

[Luis Fuentes]

Hola

En este caso multiplicas por 2 porque eran 3 campeonatos como mínimo ¿no? Si el mínimo de campeonatos fueran 2 ¿la
respuesta correcta sería 106?

Exacto.

¿Hay alguna forma de darme cuenta que son las "palomas" y los "nidos" (en general)? 

No sabría decirte más que aplicar el sentido común.

A mi con el principio del palomar me pasa una cosa curiosa; nunca me parece necesario "invocarlo". Es decir el razonamiento intuitivo que hay detrás me parece suficientemente natural para ser aplicado y desarrollado en cada caso.

En nuestro caso: si hay \( 105 \) configuraciones distintos, la forma de conseguir el mayor número posible de partidas sin repetirlos es obviamente jugar \( 105 \) partidas una con cada una de las configuraciones; análogamente la forma de conseguir el mayor número posible de partidas sin repetir más de dos cada una es oviamente jugar \( 2\cdot 105 \) partidas repitiendo dos veces cada una de las configuraciones; y así sucesivamente.

Saludos.