Intentaré limpiar y arreglar un poco el argumento de Prashant Sharma. Como en su respuesta, dejaré que [matemática] f (n) [/ matemática] sea la función que denota la cantidad de formas en que la persona [matemática] n [/ matemática] puede sentarse en su propia silla si hay [matemáticas] n [/ matemáticas] total de personas.
Lo primero que debe hacer es averiguar cuál es la respuesta con anticipación, porque es mucho más fácil demostrar las cosas (y no convencerse de que ha “probado” algo que en realidad es falso) si ya sabe cuál es la respuesta. No estoy siendo gracioso aquí: a menudo, una buena manera de establecerse en un problema que no sabe cómo resolver de inmediato es ensuciarse las manos. Podría sugerir una clave para encontrar la respuesta general (por ejemplo, te das cuenta de que estás llevando a cabo una relación de recurrencia que sabes traducir a matemáticas y resolver); por lo menos, podrías elegir qué tipo de objeto deberías buscar o detectar cuando cometiste un error algebraico que te llevó por un camino claramente equivocado.
Estos son los casos para [matemáticas] n = 1 [/ matemáticas] a [matemáticas] 5 [/ matemáticas]:
- ¿Es esto matemáticamente válido: si solo haces 1% al día más que los demás, entonces harás 3800% más que todos en un año?
- ¿Cuál es realmente el logaritmo y cuándo lo usaremos?
- A lo largo de una carretera se encuentra un número impar de piedras colocadas a intervalos de 10 m. Estas piedras deben ensamblarse alrededor de una piedra del medio. Una persona solo puede llevar una piedra a la vez. Un hombre terminó el trabajo con una de las piedras finales llevándolas sucesivamente, por lo que cubrió 3 km. ¿Cuál es el número de piedras?
- ¿Cómo cambiar el orden del cuantificador universal y el cuantificador existencial cambia el orden de significado de la oración?
- Hay un montón de 12 monedas, todas de igual tamaño, pero solo 11 tienen el mismo peso. ¿Puedes encontrar la moneda desigual y determinar si es más pesada o más ligera, en 3 pesadas?
1
1
2
12
3
123
213
4 4
1234
2134
3124
3214
5 5
12345
21345
31245
41235
41325
32145
42135
42315
Entonces, aparte de un pequeño inconveniente donde la función no cambia al pasar de [matemáticas] 1 [/ matemáticas] a [matemáticas] 2 [/ matemáticas], la respuesta parece ser [matemáticas] f (n) = 2 ^ {n – 2} [/ matemáticas]. Ahora que “sabemos” la respuesta, ¡vamos a probarla!
La primera persona ingresa y tiene dos opciones diferentes: sentarse en la silla [matemática] 1 [/ matemática], en cuyo caso todos se llenan de manera determinista, o tomar el asiento [matemática] [/ matemática], para algunos [matemática] i <n [/ matemáticas]; luego, los asientos [matemática] 2 [/ matemática] a [matemática] i – 1 [/ matemática] se llenan por las personas correctas, como dijo Prashant. Cuando la persona [matemática] i [/ matemática] ingresa, nuevamente tiene dos opciones: sentarse en la silla [matemática] 1 [/ matemática], en cuyo caso las otras sillas se llenan de manera determinista, o seleccionar otra silla, en la cual caso se lleva a cabo el proceso de selección aleatoria anterior. Dado que esta es exactamente la misma decisión que enfrenta la persona [matemáticas] 1 [/ matemáticas], reconocemos esto como [matemáticas] f (n – i + 1) [/ matemáticas], porque hay [matemáticas] n – i + 1 [/ math] sillas que quedan antes de que la [math] i [/ math] th persona elija (tal como quedaban [math] n [/ math] sillas antes de que la primera persona eligiera). Por lo tanto, la recurrencia correcta es
[matemáticas] f (n) = 1 + \ displaystyle {\ sum_ {i = 2} ^ {n – 1}} f (n – i + 1) = 1 + \ displaystyle {\ sum_ {j = 2} ^ { n – 1}} f (j) = [/ matemáticas] [matemáticas] \ displaystyle {\ sum_ {j = 1} ^ {n – 1}} f (j) [/ matemáticas]
Esto no se ve tan bien, hasta que te das cuenta de que
[matemáticas] f (n) = f (n – 1) + f (n – 2) +… + f (2) + f (1) [/ matemáticas]
[matemáticas] f (n – 1) = f (n – 2) +… + f (2) + f (1) [/ matemáticas]
y entonces
[matemáticas] f (n) – f (n – 1) = f (n – 1) [/ matemáticas]
[matemáticas] f (n) = 2f (n – 1), n> 2 [/ matemáticas]
Tenga en cuenta que usamos la expresión recursiva para [math] f (n – 1) [/ math] en nuestra derivación, que solo se define para [math] n – 1> 1 [/ math].
Es obvio (y no es tan difícil de mostrar rigurosamente) que la solución que queremos para esta recurrencia es de hecho
[matemáticas] f (n) = 2 ^ {n – 2}, n> 1 [/ matemáticas]
Pudimos reducir la restricción en [matemáticas] n [/ matemáticas] porque la fórmula da la respuesta correcta para [matemáticas] n = 2 [/ matemáticas], aunque todavía tenemos que decir explícitamente que [matemáticas] f (1) = 1 [/ math] (y no el absurdo [math] \ frac {1} {2} [/ math] que nos da la fórmula).
Por lo tanto, para responder a su pregunta original, hay [matemática] 2 ^ {98} [/ matemática] formas para que estas [matemática] 100 [/ matemática] se sienten como usted describió.
