Pure maths, physics, logic (braingames.ru): non-trade-related brain games - page 58
You are missing trading opportunities:
- Free trading apps
- Over 8,000 signals for copying
- Economic news for exploring financial markets
Registration
Log in
You agree to website policy and terms of use
If you do not have an account, please register
Hence: All ladders have a clearly defined bottom and top.
80 megabrains stood up in a 10×8 rectangle. In each longitudinal row they found the tallest one, the lowest of which was the megamogon with a dog. Then they found the lowest one in each transverse row, and the tallest among them was a megamorg wearing a hat. The question is, who is taller: the megamoggle with the dog or the one with the hat?
There was a similar one on the 4.
X >= Y >= Z --> X >= Z
(5)
Megamogg wants to climb to the roof of his house with a ladder. There are many ladders in the storeroom, but unfortunately, most of them are missing steps. The ladders that are missing two rungs in a row cannot be climbed by Megamogg. All of his ladders originally had N steps. All ladders have clearly defined bottom and top. How many variations of stairs could Megamogg climb?
Tex, it's simpler than that. The Fibonacci rabbit sequence is drawn.
F(1) = 2
F(2) = 3
F(N) = F(N-1)+F(N-2)
// I don't know if there is a nonrecurrence formula, I haven't worked it out yet.
Are you sure?
F(1) = 1
F(2) = 2
F(3) = 4
F(4) = 7
F(5) = 12
F(6) = 19
F(7) = 33 (???)
Sure.
With one step, two options (have/no step)
With two = three options (both have, no first, no second)
etc.
My formula is correct.
Ъ
My formula is correct.
Recurrence formula e, but not as simple as I have. But the consequence and the solution itself is indeed Fibonacci numbers F(N+2). It only remains to give a correct proof. MD, where did you dig up your formula? Just by counting variations for small numbers?
I have the full derivation of the formula. I'll wait for now.
On the 4k, it seemed to be similar.
X >= Y >= Z --> X >= Z
Recurrence formula e, but not as simple as I have. But the consequence and the solution itself is indeed Fibonacci numbers F(N+2). It only remains to give a correct proof. MD, where did you dig up your formula? Just by counting variations for small numbers?
I have the full derivation of the formula. I'll wait for now.
Let c(n) be the number of stairs with n steps that MM cannot climb. Consider the following options:
1 0
1 0 0
Here are the bottom rungs of three series of stairs, 1 - there is a step, 0 - there is no step. Obviously, if n >= 2
c(n) = c(n-1) + c(n-2) + 2^(n-2), it is clear that c(0) = 0, c(1) = 0 (1)
The total number of ladders that can be climbed is expressed by the formula: 2^n - c(n) =? F(n+2)
Let us prove it. Let us define a function
f(n+2) = 2^n - c(n); we calculate f(2) = 1, f(3) = 2 matches the corresponding Fibonacci numbers. (2)
For n > 1, we substitute c(n) from (2) into (1), and obtain
2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), degrees of twos are reduced, we get:
f(n+2) = f(n+1) + f(n), Given the calculated values of f(2) = F(2) = 1, f(3) = F(3) = 2, it is obvious that f(n+2) = F(n+2)
I, by the way, have a different solution (no degrees of two):
A staircase is called correct if MM can climb it. The number of potential steps on the ladder is called its order.
For simplicity we will introduce such notations: the number of correct stairs of order n and with a missing step we denote as q(n; false), and with a step present we denote as q(n; true). We denote the number of all regular staircases of order n as q(n).
There are two cases:
1. The upper ladder has a lower step. Then the total number of "compound" stairs of order N is q(N-1; true) * 2, because the number of regular stairs of order 1 is 2.
On the other hand, obviously q(N-1; true) = q(N-2). Therefore the total number of correct choices for this case will be 2*q(N-2).
2. The top ladder has no bottom rung. The total number of composite ladders of order N is q(N-1; false) * 1, because the bottom ladder of order 1 must have a step for the composite ladder to be correct.
On the other hand, q(N-1; false) = q(N-2; true) = q(N-3). So the total number of correct choices is q(N-3).
Hence, we have the recurrence relation:
q(N) = 2*q(N-2) + q(N-3).
It is linear, and the equation for it is as follows:
z^3 - 2*z - 1 = 0.
It obviously decomposes into multipliers:
(z + 1) * (z^2 - z - 1) = 0.
Hence the roots are z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1.
A general solution of the equation is a linear combination of
q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).
Manual counting for the first few choices yields the following numbers of choices - Fibonacci numbers(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.
The regularity is obvious. Substitute in (***):
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 (***).
Firstly, note that from these three equations C_i is uniquely determined (the main determinant of the system is almost the Vandermonde determinant, which is not equal to zero). On the other hand, the Fibonacci numbers are literally obtained if C_1 = 1/sqrt(5) = -C_2 and C_3 = 0.
Hence the answer: the number of regular ladders of order N is F_{N+2}.
I, by the way, have a different solution (no degrees of two):
The same recurrence relation is true for Fibonacci: q(N) = 2*q(N-2) + q(N-3).
Therefore it was sufficient to prove the coincidence of three consecutive values of the series for the series to coincide