[anaiak]

  Ante todo un saludo a todos los forer@s!

 La cuestión es la siguiente:

   Hemos preparado para estas navidades el famoso juego del amigo invisible.  Consiste en hacer un regalo a cada persona y que cada persona reciba un regalo sin saber qué persona regala a quién, haciendo previamente un sorteo.

   Por tanto, si somos 9 personas y cada una recibe un regalo de otra siendo imposible que uno se haga un regalo a si mismo, ¿cuál es el número de combinaciones posibles?

     Muchas gracias de antemano y hasta pronto.

   

[Jabato]

Bueno el problema es muy sencillo, basta que ordenes a las nueve personas en fila india y les digas que cada uno debe regalar al que le sigue, y el último de la fila regala al primero.

Eso te conduce a 9! permutaciones aunque hay que tener en cuenta que hay distintas permutaciones que conducen a la misma secuencia de regalos, ya que basta con ir variando cual sea la primera persona de la fila pero dejando la secuencia idéntica, lo que te dice que de las 9! permutaciones posibles hay grupos de 9 que conducen a la misma secuencia de regalos, por lo que las combinaciones distintas en la forma de hacer los regalos son entonces:

9!/9 = 8!

Saludos, Jabato.

[Luis Fuentes]

Hola

 ¡Cáspita! Si no fuese por este tema relacionado:

http://www.rinconmatematico.com/foros/index.php/topic,9200.msg37983/topicseen.html#new

no me hubiese dado cuenta de que el razonamiento de Jabato no es correcto. Cuando lo leí la primera vez me convenció.

 El problema es que razonado como indico él no se están contando, por ejemplo, los casos en que a dos amigos les toca regalarse entre si.

 En realidad se trata del problema clásico de contar permutaciones sin punto fijo.

 Mejor que decir yo imprecisiones, remito aquí:

http://www.unizar.es/ttm/2006-07/euler.pdf

Saludos.

[Jabato]

Te entiendo, y creo que tienes razón. No es correcto el cálculo que hice porque no se contemplan soluciones con varios ciclos de orden inferior a n. Me explico:

Todas las soluciones que yo expuse contemplan una rueda entre las 9 personas, (un camino cerrado digamos, en el que cada uno regala al siguiente), pero también es posible separar a las nueve personas en dos grupos de 4 y 5 personas y formar en cada grupo una rueda, ó por ejemplo formar 3 grupos de 3 personas y formar tres ruedas, una en cada grupo. Hay por lo tanto bastantes más soluciones de las que indiqué.

Deben tenerse en cuenta las distintas formas de partir el conjunto de 9 personas, teniendo en cuenta que dichas particiones no pueden contener conjuntos con menos de dos personas, y a continuación considerar las distintas permutaciones en cada conjunto de la partición. Es bastante más complicado el cálculo de esta forma. Quizás exista otra manera más sencilla, esta parece demasiado complicada. 

Saludos, Jabato.

[Jabato]

La respuesta al problema para n personas coincide con el número de aplicaciones biyectivas entre P, conjunto de personas, y él mismo, ya que cada persona regala a una sola persona y es regalada por una sola persona, pero deben descontarse las aplicaciones biyectivas en que algún elemento es imagen de si mismo, ya que una persona no puede regalarse a si misma.

Puesto que el número de aplicaciones biyectivas coincide con n!, sabemos que éste numero es cota superior de la solución, pero ... ¿cuantas aplicaciones biyectivas existen en las que al menos un elemento es imagen de si mismo?

Esa parece ser la pregunta del millón, pero ... si yo conozco un poco al amigo Euler, la respuesta no debe ser fácil de razonar, ni nada que se le parezca.

Saludos, Jabato.

[anaiak]

  Hola de nuevo:

  Yo he tratando de sacar una regla general. Empece suponiendo que solo partipaban dos personas (n=2), con lo cual solo habria una combinacion posible, des pues siendo n=3 y n=4 (ahora no recuerdo cuales eran los resultados puesto que tire el papel donde lo hice)   pero al llegar a n=5 eran demasiadas las convinaciones y lo deje....

  Animo a ver si alguien logra dar en el clavo.

[Luis Fuentes]

Hola

Animo a ver si alguien logra dar en el clavo.

mmmm... no se si quedó clara mi anterior intervención. En el enlace que puse allí ya viene la (una) solución al problema.

Puede leerse algo también aquí (pág 42):

http://mipagina.cantv.net/jhnieto/tc.pdf

donde (por cierto) aparecen unos apuntes muy completos de teoría combinatoria.

Repito una vez más que lo que se está contando son el número de permutaciones sin puntos fijos también llamado número de desarreglos. Buscando en internet o en bibliografía sobre esos dos conceptos encontraréis mucha información.

De todas formas las fórmulas que aparecen son siempre recursivas o involucrando sumatorios.

Saludos.

[Schroder-Bernstein]

En estos días me planteé este mismo problema, y después de hacer varios casos con diferente número de personas llegué a una sucesión con término general

\( f_n=n\cdot f_{n-1}-(-1)^n \) con \( f_1=0 \)

[Luis Fuentes]

Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

En estos días me planteé este mismo problema, y después de hacer varios casos con diferente número de personas llegué a una sucesión con término general

\( f_n=n\cdot f_{n-1}-(-1)^n \) con \( f_1=0 \)

 Es (no sé si fue una errata al escribir):

\( f_n=n\cdot f_{n-1}\color{red}+\color{black}(-1)^n \) con \( f_1=0 \)

Saludos.

[Schroder-Bernstein]

Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

En estos días me planteé este mismo problema, y después de hacer varios casos con diferente número de personas llegué a una sucesión con término general

\( f_n=n\cdot f_{n-1}-(-1)^n \) con \( f_1=0 \)

 Es (no sé si fue una errata al escribir):

\( f_n=n\cdot f_{n-1}\color{red}+\color{black}(-1)^n \) con \( f_1=0 \)

Saludos.

Sí fue así, mucahs gracias por hacermelo notar y por la bienvenida. Estoy en la lectura de las reglas y Latex