Reine Mathematik, Physik, Logik (braingames.ru): nicht handelsbezogene Denkspiele - Seite 58
Sie verpassen Handelsmöglichkeiten:
- Freie Handelsapplikationen
- Über 8.000 Signale zum Kopieren
- Wirtschaftsnachrichten für die Lage an den Finanzmärkte
Registrierung
Einloggen
Sie stimmen der Website-Richtlinie und den Nutzungsbedingungen zu.
Wenn Sie kein Benutzerkonto haben, registrieren Sie sich
Daraus folgt: Alle Leitern haben eine klar definierte Unter- und Oberseite.
80 Megahirne standen in einem 10×8-Rechteck auf. In jeder Längsreihe fanden sie den höchsten, der niedrigste war der Megamogon mit einem Hund. Dann fanden sie den niedrigsten in jeder Querreihe, und der größte unter ihnen war ein Megamorg, der einen Hut trug. Die Frage ist, wer ist größer: der Megamogul mit dem Hund oder der mit dem Hut?
Ein ähnliches gab es auf der 4.
X >= Y >= Z --> X >= Z
(5)
Megamogg will mit einer Leiter auf das Dach seines Hauses klettern. Es gibt viele Leitern im Lagerraum, aber leider fehlen bei den meisten die Stufen. Die Leitern, bei denen zwei Sprossen in einer Reihe fehlen, können von Megamogg nicht erklommen werden. Alle seine Leitern hatten ursprünglich N-Stufen. Alle Leitern haben ein klar definiertes Unter- und Oberteil. Wie viele Varianten von Treppen kann Megamogg steigen?
Tex, es ist viel einfacher: Die Fibonacci-Folge der Kaninchen ist gezeichnet.
F(1) = 2
F(2) = 3
F(N) = F(N-1)+F(N-2)
// Ich weiß nicht, ob es eine Formel für die Nichtwiederholung gibt, ich habe sie noch nicht ausgearbeitet.
Sind Sie sicher?
F(1) = 1
F(2) = 2
F(3) = 4
F(4) = 7
F(5) = 12
F(6) = 19
F(7) = 33 (???)
Ja, sicher.
Mit einem Schritt, zwei Optionen (mit/ohne Schritt)
Mit zwei = drei Optionen (beide haben, keine erste, keine zweite)
usw.
Meine Formel ist korrekt.
Ъ
Meine Formel ist korrekt.
Rekursionsformel e, aber nicht so einfach, wie ich sie habe. Aber die Konsequenz und die Lösung selbst sind tatsächlich Fibonacci-Zahlen F(N+2). Es bleibt nur noch, einen korrekten Beweis zu erbringen. MD, woher haben Sie Ihre Formel? Nur durch das Zählen von Variationen für kleine Zahlen?
Ich habe die vollständige Herleitung der Formel. Ich werde erst einmal warten.
Bei der 4k schien es ähnlich zu sein.
X >= Y >= Z --> X >= Z
Rekursionsformel e, aber nicht so einfach, wie ich sie habe. Aber die Konsequenz und die Lösung selbst sind tatsächlich Fibonacci-Zahlen F(N+2). Es bleibt nur noch, einen korrekten Beweis zu erbringen. MD, woher haben Sie Ihre Formel? Nur durch das Zählen von Variationen für kleine Zahlen?
Ich habe die vollständige Herleitung der Formel. Ich werde erst einmal warten.
c(n) sei die Anzahl der Treppen mit n Stufen, die MM nicht steigen kann. Ziehen Sie die folgenden Optionen in Betracht:
1 0
1 0 0
Hier sind die untersten Sprossen von drei Reihen von Treppen, 1 - es gibt eine Stufe, 0 - es gibt keine Stufe. Offensichtlich, wenn n >= 2
c(n) = c(n-1) + c(n-2) + 2^(n-2), es ist klar, dass c(0) = 0, c(1) = 0 (1)
Die Gesamtzahl der Leitern, die bestiegen werden können, wird durch die folgende Formel ausgedrückt: 2^n - c(n) =? F(n+2)
Lassen Sie es uns beweisen. Definieren wir eine Funktion
f(n+2) = 2^n - c(n); wir berechnen f(2) = 1, f(3) = 2 entspricht den entsprechenden Fibonacci-Zahlen. (2)
Für n > 1 setzen wir c(n) aus (2) in (1) ein und erhalten
2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), Zweiergrade werden reduziert, wir erhalten:
f(n+2) = f(n+1) + f(n), Angesichts der berechneten Werte von f(2) = F(2) = 1, f(3) = F(3) = 2, ist es offensichtlich, dass f(n+2) = F(n+2)
Ich habe übrigens eine andere Lösung (keine zwei Stufen):
Eine Treppe wird als richtig bezeichnet, wenn MM sie hinaufsteigen kann. Die Anzahl der möglichen Stufen auf der Leiter wird als Reihenfolge bezeichnet.
Der Einfachheit halber werden wir solche Bezeichnungen einführen: die Anzahl der richtigen Treppen der Ordnung n und mit einer fehlenden Stufe bezeichnen wir als q(n; falsch), und mit einer vorhandenen Stufe bezeichnen wir als q(n; wahr). Wir bezeichnen die Anzahl aller regulären Leitern der Ordnung n als q(n).
Es gibt zwei Fälle:
1. Die obere Leiter hat eine untere Stufe. Die Gesamtzahl der "zusammengesetzten" Treppen der Ordnung N ist dann q(N-1; wahr) * 2, da die Anzahl der regulären Treppen der Ordnung 1 gleich 2 ist.
Andererseits ist natürlich q(N-1; wahr) = q(N-2). Daher ist die Gesamtzahl der richtigen Antworten in diesem Fall 2*q(N-2).
2. Die oberste Leiter hat keine unterste Sprosse. Die Gesamtzahl der zusammengesetzten Leitern der Ordnung N ist q(N-1; falsch) * 1, da die unterste Leiter der Ordnung 1 eine Stufe haben muss, damit die zusammengesetzte Leiter korrekt ist.
Andererseits ist q(N-1; falsch) = q(N-2; wahr) = q(N-3). Die Gesamtzahl der richtigen Antworten ist also q(N-3).
Daraus ergibt sich die Rekursionsbeziehung:
q(N) = 2*q(N-2) + q(N-3).
Sie ist linear und die Gleichung dafür lautet wie folgt:
z^3 - 2*z - 1 = 0.
Sie zerfällt natürlich in Multiplikatoren:
(z + 1) * (z^2 - z - 1) = 0.
Die Wurzeln sind demnach z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1.
Eine allgemeine Lösung der Gleichung ist eine Linearkombination aus
q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).
Das manuelle Zählen der ersten Auswahlmöglichkeiten ergibt die folgende Anzahl von Auswahlmöglichkeiten - Fibonacci-Zahlen (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, usw.
Die Regelmäßigkeit ist offensichtlich. Ersetzen Sie 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 (***).
Zunächst ist zu beachten, dass aus diesen drei Gleichungen C_i eindeutig bestimmt ist (die Hauptdeterminante des Systems ist fast die Vandermonde-Determinante, die nicht gleich Null ist). Andererseits erhält man die Fibonacci-Zahlen buchstäblich, wenn C_1 = 1/sqrt(5) = -C_2 und C_3 = 0.
Daraus ergibt sich die Antwort: die Anzahl der regulären Leitern der Ordnung N ist F_{N+2}.
Ich habe übrigens eine andere Lösung (keine zwei Stufen):
Die gleiche Rekursionsbeziehung gilt für Fibonacci: q(N) = 2*q(N-2) + q(N-3).
Es genügte also, das Zusammentreffen von drei aufeinanderfolgenden Werten der Reihe zu beweisen, damit die Reihe übereinstimmt