16 caballeros están sentados en una mesa circular, se requieren 7 caballeros para rescatar a una niña. Todos los caballeros consecutivos son hostiles entre sí. ¿Cuántas formas de seleccionar 7 caballeros de modo que no se puedan unir 2 hostiles?

Answer 1

Selecciones lineales

Primero tenga en cuenta que si [math] n [/ math] knights están en una línea y queremos elegir [math] k [/ math] caballeros no adyacentes, entonces hay:

[matemáticas] \ dbinom {n-k + 1} {k} \ etiqueta * {} [/ matemáticas]

maneras de hacer esto.

Explicación

El problema es el mismo que contar los arreglos de [matemática] k [/ matemática] Y y [matemática] nk [/ matemática] N en una línea con al menos 1 N entre cada dos Y. Entonces, [math] k-1 [/ math] N’s debe estar entre las [math] k [/ math] Y’s (1 N entre cada dos Ys), por lo tanto, estamos realmente contando arreglos lineales de [math] n-2k + 1 [ / math] N’s y [math] k [/ math] Y’s, hay [math] \ frac {(n-2k + 1 + k)!} {(n-2k + 1)! k!} = \ binom { n-k + 1} {k} [/ math] formas de hacerlo.

Responder

O Lancelot es parte del equipo o no:

• Si es así, elija los otros 6 caballeros linealmente de los [matemáticos] 16-3 = 13 [/ matemáticos] caballeros no adyacentes a Lancelot para que no haya dos adyacentes en [matemática] \ binom {13-6 + 1} {6 } [/ math] maneras.
• Si no es así, elija 7 caballeros linealmente de los restantes [matemática] 16-1 = 15 [/ matemática] caballeros para que no haya dos adyacentes en [matemática] \ binom {15-7 + 1} {7} [/ matemática] .

[matemáticas] \ displaystyle \ text {total de selecciones no hostiles} = \ binom {8} {6} + \ binom {9} {7} = 28 + 36 = 64 \ tag {Respuesta} [/ math]

---

Editar:

Generalización

Dado que es posible generalizar las selecciones lineales de modo que los caballeros seleccionados deben estar separados por [math] r [/ math] knights, también es posible extender esta respuesta a: selecciones de caballeros en un círculo de tal manera que los caballeros seleccionados deben estar separados por [ matemática] r [/ matemática] caballeros.

La generalización de las selecciones lineales con separaciones de [math] r [/ math] knights usa la misma lógica que antes, excepto que ahora tenemos que eliminar [math] r (k-1) [/ math] de [math] n [/ math ] en lugar de [matemáticas] k-1 [/ matemáticas]. Dando

[matemáticas] \ text {selecciones lineales $ k $ de $ n $ con separaciones de al menos $ r $} = \ dbinom {nr (k-1)} {k} \ tag * {} [/ math]

A continuación, para tales elecciones de [matemáticas] s [/ matemáticas] de un círculo de caballeros [matemáticas] m [/ matemáticas], incluimos o excluimos a Lancelot como antes.

En el primer caso, podemos hacer las elecciones lineales restantes [matemáticas] k = s-1 [/ matemáticas] entre [matemáticas] n = m- (2r + 1) [/ matemáticas] los caballeros restantes que son al menos [matemáticas] r +1 [/ matemática] asientos de Lancelot en [matemática] \ binom {m- (2r + 1) -r (s-2)} {s-1} = \ binom {m-rs-1} {s-1 } [/ math] maneras.

En el último caso, podemos hacer las elecciones lineales restantes [matemáticas] k = s [/ matemáticas] entre [matemáticas] n = m-1 [/ matemáticas] los caballeros restantes en [matemáticas] \ binom {mr (s-1) – 1} {s} [/ math] maneras.

Entonces el número de selecciones circulares es la suma de estas:

[matemáticas] \ text {opciones circulares de $ s $ de $ m $ con espacios de al menos $ r $} = \ dbinom {m-rs-1} {s-1} + \ dbinom {mr (s-1) -1} {s} \ tag * {} [/ math]

En nuestra pregunta [matemática] m = 16 [/ matemática], [matemática] r = 1 [/ matemática] y [matemática] s = 7 [/ matemática] entonces obtenemos [matemática] \ binom {16-1 (7) -1} {6} + \ binom {16-1 (6) -1} {7} = \ binom {8} {6} + \ binom {9} {7} [/ math] como antes.

Son posibles más generalizaciones con el uso de funciones generadoras, pero esa es una discusión más larga.

Answer 2

Numere los caballeros alrededor de la mesa del 1 al 16. Elegiremos una selección adecuada de caballeros como opción . Hay dos especies de opciones . Un ejemplo de una opción es 1, 5, 7, 9, 11, 13, 15. Esto podría representarse como 3, 1, 1, 1, 1, 1, 1 donde los números representan el número dejado entre aquellos en el Elección . Podemos decir que el 3 comienza después del 1. Pero hay 16 formas de expresar el 3 comienza después del. Un ejemplo de la segunda especie es 1, 4, 7, 9, 11, 13, 15. Esto podría representarse, como arriba, por 2, 2, 1, 1, 1, 1, 1. Los primeros 2 pueden comenzar de 16 maneras. Para cada una de esas 16 formas, el segundo 2 puede comenzar de 6 maneras. [matemáticas] 16 \ veces 6 = 96 [/ matemáticas]. Sin embargo, cada una de estas opciones se cuenta dos veces. [matemáticas] 16 + 48 = 64. [/ matemáticas]

Una generalización inmediata, usando el mismo argumento, es que dado [matemática] n = 2k [/ matemática] caballeros de los cuales se elegirá [matemática] k-1 [/ matemática] es que se puede hacer en [matemática] \ dfrac {nk} {2} = k ^ 2 [/ math] maneras.

Answer 3

Me parece que debe haber 16 formas de seleccionar la primera, (1 de 16) Una vez que se selecciona la primera, hay 7 formas de seleccionar las siguientes seis. Esto se debe a que los seis restantes deben ser del mismo grupo en el que se seleccionó al primero, de modo que no mezclemos personas que sean hostiles entre sí. Para seleccionar seis de este grupo restante de siete se puede hacer de siete maneras. Esta es la cantidad de formas en que se seleccionará uno para dejarlo fuera. Entonces, para cada elección de la primera de las 16 formas posibles, se pueden seleccionar 6 más con 7 formas. Por lo tanto, el número total de opciones es 16 veces 7 = 112. Si no cometí un error o pasé por alto nada.