Matemáticas puras, física, lógica (braingames.ru): juegos cerebrales no relacionados con el comercio - página 58
Está perdiendo oportunidades comerciales:
- Aplicaciones de trading gratuitas
- 8 000+ señales para copiar
- Noticias económicas para analizar los mercados financieros
Registro
Entrada
Usted acepta la política del sitio web y las condiciones de uso
Si no tiene cuenta de usuario, regístrese
Por lo tanto: Todas las escaleras tienen una parte inferior y superior claramente definidas.
80 megacerebros se situaron en un rectángulo de 10×8. En cada hilera longitudinal encontraron el más alto, el más bajo de los cuales era el megamogón con un perro. Entonces encontraron al más bajo de cada fila transversal, y el más alto de ellos era un megamorfo con sombrero. La pregunta es, ¿quién es más alto: el megamago con el perro o el del sombrero?
Había uno similar en el 4.
X >= Y >= Z --> X >= Z
(5)
Megamogg quiere subir al tejado de su casa con una escalera. Hay muchas escaleras en el almacén, pero por desgracia, a la mayoría les faltan peldaños. Las escaleras a las que les faltan dos peldaños seguidos no pueden ser subidas por Megamogg. Todas sus escaleras tenían originalmente N peldaños. Todas las escaleras tienen la parte inferior y superior claramente definidas. ¿Cuántas variaciones de escaleras podría subir Megamogg?
Tex, es más simple que eso. La secuencia del conejo de Fibonacci está dibujada.
F(1) = 2
F(2) = 3
F(N) = F(N-1)+F(N-2)
// No sé si existe una fórmula de no recurrencia, aún no la he resuelto.
¿Está seguro?
F(1) = 1
F(2) = 2
F(3) = 4
F(4) = 7
F(5) = 12
F(6) = 19
F(7) = 33 (???)
Claro que sí.
Con un paso, dos opciones (tener/sin paso)
Con dos = tres opciones (las dos tienen, ninguna primera, ninguna segunda)
etc.
Mi fórmula es correcta.
Ъ
Mi fórmula es correcta.
Fórmula de recurrencia e, pero no tan simple como la que tengo. Pero la consecuencia y la solución en sí son los números de Fibonacci F(N+2). Sólo queda dar una prueba correcta. MD, ¿de dónde sacaste tu fórmula? ¿Sólo contando variaciones para números pequeños?
Tengo la derivación completa de la fórmula. Esperaré por ahora.
En el 4k, parecía ser similar.
X >= Y >= Z --> X >= Z
Fórmula de recurrencia e, pero no tan simple como la que tengo. Pero la consecuencia y la solución en sí son los números de Fibonacci F(N+2). Sólo queda dar una prueba correcta. MD, ¿de dónde sacaste tu fórmula? ¿Sólo contando variaciones para números pequeños?
Tengo la derivación completa de la fórmula. Esperaré por ahora.
Sea c(n) el número de escaleras con n escalones que MM no puede subir. Considere las siguientes opciones:
1 0
1 0 0
Aquí están los peldaños inferiores de tres series de escaleras, 1 - hay un escalón, 0 - no hay ningún escalón. Obviamente, si n >= 2
c(n) = c(n-1) + c(n-2) + 2^(n-2), es evidente que c(0) = 0, c(1) = 0 (1)
El número total de escaleras que se pueden subir se expresa mediante la fórmula: 2^n - c(n) =? F(n+2)
Vamos a probarlo. Definamos una función
f(n+2) = 2^n - c(n); calculamos que f(2) = 1, f(3) = 2 coincide con los correspondientes números de Fibonacci. (2)
Para n > 1, sustituimos c(n) de (2) en (1), y obtenemos
2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), se reducen los grados de los dos, obtenemos:
f(n+2) = f(n+1) + f(n), Dados los valores calculados de f(2) = F(2) = 1, f(3) = F(3) = 2, es obvio que f(n+2) = F(n+2)
Yo, por cierto, tengo una solución diferente (sin grados de dos):
Una escalera se llama correcta si MM puede subirla. El número de posibles peldaños de la escalera se denomina orden.
Para simplificar introduciremos estas notaciones: el número de escaleras correctas de orden n y con un paso ausente lo denotamos como q(n; falso), y con un paso presente lo denotamos como q(n; verdadero). Denotamos el número de todas las escaleras regulares de orden n como q(n).
Hay dos casos:
1. La escalera superior tiene un escalón inferior. Entonces el número total de escaleras "compuestas" de orden N es q(N-1; verdadero) * 2, porque el número de escaleras regulares de orden 1 es 2.
Por otro lado, obviamente q(N-1; verdadero) = q(N-2). Por lo tanto, el número total de opciones correctas para este caso será 2*q(N-2).
2. La escalera superior no tiene peldaño inferior. El número total de escaleras compuestas de orden N es q(N-1; falso) * 1, porque la escalera inferior de orden 1 debe tener un escalón para que la escalera compuesta sea correcta.
Por otro lado, q(N-1; falso) = q(N-2; verdadero) = q(N-3). Por tanto, el número total de opciones correctas es q(N-3).
Por lo tanto, tenemos la relación de recurrencia:
q(N) = 2*q(N-2) + q(N-3).
Es lineal y su ecuación es la siguiente:
z^3 - 2*z - 1 = 0.
Obviamente, se descompone en multiplicadores:
(z + 1) * (z^2 - z - 1) = 0.
Por tanto, las raíces son z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1.
Una solución general de la ecuación es una combinación lineal de
q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).
El recuento manual de las primeras opciones da los siguientes números de opciones - números de Fibonacci (F_0 = 0, F_1 = 1):
q(1) = 2 = F_3,
q(2) = 3 = F_4,
q(3) = 5 = F_5,
q(4) = 8 = F_6,
q(5) = 13 = F_7, etc.
La regularidad es evidente. Sustituir en (***):
F_3 = C_1*z_1 + C_2*z_2 - C_3 (***).
F_4 = C_1*z_1^2 + C_2*z_2^2 + C_3 (***).
F_5 = C_1*z_1^3 + C_2*z_2^3 - C_3 (***).
En primer lugar, nótese que a partir de estas tres ecuaciones C_i está determinada de forma única (el determinante principal del sistema es casi el determinante de Vandermonde, que no es igual a cero). Por otra parte, los números de Fibonacci se obtienen literalmente si C_1 = 1/sqrt(5) = -C_2 y C_3 = 0.
De ahí la respuesta: el número de escaleras regulares de orden N es F_{N+2}.
Yo, por cierto, tengo una solución diferente (sin grados de dos):
La misma relación de recurrencia es cierta para Fibonacci: q(N) = 2*q(N-2) + q(N-3).
Por lo tanto, bastaba con probar la coincidencia de tres valores consecutivos de la serie para que ésta coincidiera