4 votos

¿Transformando rompecabezas en teoría de gráficos?

Estoy tratando de resolver el rompecabezas y estoy pensando que debería haber alguna manera de formular como un problema de contabilizar las elecciones, pero no puedo hacer que funcione. Agradecería una pista o una estrategia diferente.

N de la premier league futbolistas, todos con diferentes fechas de nacimiento, y una mujer, Natasha, se sentarán en una mesa redonda. Para evitar cualquier futbolistas llegar ignorado, cada futbolista debe sentarse junto a un joven futbolista o a Natasha. De cuántas maneras pueden los futbolistas y Natasha estar sentados?

1voto

azimut Puntos 13457

Vamos a elaborar la sugerencia de Michael Ulm:

  • Tenemos la primera sede Natasha, hay $N+1$ posibilidades.
  • El futbolista más joven no puede sentarse junto a un joven futbolista, por lo que debemos asiento de él junto a Natasha. Hay dos posibilidades.
  • El segundo futbolista más joven puede sentarse junto a Natasha o junto al futbolista más joven. Hay dos posibilidades.
  • El tercer futbolista más joven debe sentarse junto a Natasha o a uno de los dos más jóvenes futbolistas. Desde esos tres ya están sentados en una fila, nuevamente hay dos posibilidades (los dos asientos vacíos junto a ellos).

Pasando como este, tenemos 2 posibilidades para todos los futbolistas hasta el segundo más antiguo. El más antiguo futbolista va hasta el último asiento vacío.

Por lo que el número total de posibilidades es $$ (N+1)\cdot 2^{N-1}. $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X