純粋数学、物理学、論理学（braingames.ru）：貿易に関連しない頭脳ゲーム - ページ 58

新しいコメント
 
DmitriyN:
それゆえすべての梯子には、底辺と上辺が明確に定義されています。
梯子には必ず上段と下段があるという意味ではなく、梯子には上段と 下段が ある、つまり逆はありえないという意味です。つまり、上下対称に鏡面加工された階段は、同じものではありません。
 
Mathemat:

80人のメガブラが10×8の長方形に立ち並びました。それぞれの縦列で、最も背の高いもの、最も低いものは犬を連れたメガモゴンであることがわかった。そして、それぞれの横列で一番低いものを見つけ、その中で一番背の高いものが、帽子をかぶったメガモルグだったのです。問題は、犬を連れたメガモーグルと、帽子をかぶったメガモーグルのどちらが背が高いかだ。

4にも同じようなものがあった。

x >= y >= z --> x >= z

 
Mathemat:

(5)

メガモグは、はしごを使って家の屋根に登りたいと思っています。書庫にはたくさんの梯子がありますが、残念ながらほとんどの梯子はステップが欠けています。2段ずつ欠けているはしごは、メガモグが登れない。彼の梯子は、もともとすべてN段でした。すべての梯子には、底辺と上辺が明確に定義されています。メガモグは何種類の階段を登れるのだろう？

もっと単純に、フィボナッチ式ウサギの 数列を描くのだ。

F(1) = 2

F(2) = 3

f(n) = f(n-1)+f(n-2)

// 非再現式があるのかどうか、まだ調べていないんです。

 
TheXpert:

本当ですか？

F(1) = 1

F(2) = 2

F(3) = 4

F(4) = 7

F(5) = 12

F(6) = 19

F(7) = 33 (???)

もちろんです。

1ステップで、2つの選択肢（ステップあり／なし）がある

二者択一＝三者択一で（両方あり、一人目なし、二人目なし）

など

私の計算式は正しい。


Ъ

 
MetaDriver:

私の計算式は正しい。

ええ、そうですね。階段全体を数えたわけではなく、6人分のどこかを数えたのが甘かったです。
 

再帰式e、しかし、私が持っているような単純なものではありません。しかし、その帰結と解そのものは、まさにフィボナッチ数F(N+2)なのである。あとは正しい証明を行うだけです。MD、どこで数式を掘り起こしたんだ？小さな数字のバリエーションを数えるだけ？

完全な導出式があるんです。今は待つことにします。

 
TheXpert:

4kでは、似たような感じだったようです。

x >= y >= z --> x >= z

バッキーとは何か、説明していただけますか？
 
Mathemat:

再帰式e、しかし、私が持っているような単純なものではありません。しかし、その帰結と解そのものは、まさにフィボナッチ数F(N+2)なのである。あとは正しい証明を行うだけです。MD、どこで数式を掘り起こしたんだ？小さな数字のバリエーションを数えるだけ？

完全な導出式があるんです。今は待つことにします。

MMが登れない段数nの階段の数をc(n)とする。次のような選択肢を考えてみてください。

1 0

1 0 0

ここに3段の階段の下段がありますが、1段は段差がある、0段は段差がない、ということです。明らかに、n >= 2の場合

c(n) = c(n-1) + c(n-2) + 2^(n-2), c(0) = 0, c(1) = 0 (1) であることは明らかである。

登れる梯子の総数は、2^n - c(n) = ?の式で表される。F(n+2)

それを証明しよう。を定義してみましょう。

f(n+2) = 2^n - c(n); f(2) = 1, f(3) = 2 が対応するフィボナッチ数と一致するように計算します。(2)

n > 1 の場合、(2) の c(n) を (1) に代入し、次のようになる。

2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), degree of twos が減少すると、次のようになります。

f(n+2) = f(n+1) + f(n), f(2) = F(2) = 1, f(3) = F(3) = 2 の計算値から、 f(n+2) = F(n+2) は自明であります。

 

ちなみに私は、別解（二の足は踏まない）です。

N >= 2と考える。1段目と2段目の間（というか、そのための場所）で、はしごを切ってみましょう。上部にN-1段の小さな梯子があり、下部には1段の梯子がある。どちらも正しいことが保証されますが、通常、いくつかのステップが欠落しています。<br /> translate="no">。
MMが登れる階段を正しい階段と呼ぶ。 梯子（はしご）の段数を「順序（オーダー）」と呼びます。

簡単のため、このような表記を導入する。次数nの階段で、ステップがない場合の正しい階段の数をq(n; false)、ステップがある場合の数をq(n; true)と表記する。ここでは、次数nのすべての正則梯子の数をq(n)と表す。

2つのケースがあります。

1.上の梯子には下の段がある。すると、次数Nの「複合」階段の総数はq(N-1; true) * 2であり、次数1の正規階段の数は2であるから、q(N-1; true) * 2である。

一方、明らかにq(N-1; true) = q(N-2)である。したがって、この場合の正しい選択肢の総数は2*q(N-2)となる。

2.上の梯子には下の段がない。次数Nの合成梯子の総数はq(N-1; false) * 1である。これは、合成梯子が正しくなるためには、次数1の最下段の梯子には段がなければならないからである。

一方、q(N-1; false) = q(N-2; true) = q(N-3)である。つまり、正しい選択肢の総数はq(N-3)である。

したがって、recurrence relationが成り立つ。

q(N) = 2*q(N-2) + q(N-3) となります。

線形であり、その方程式は以下の通りである。

z^3 - 2*z - 1 = 0 となります。

明らかに乗算に分解される。

(z + 1) * (z^2 - z - 1) = 0.

したがって、根は z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1 となる。

この方程式の一般的な解は、次のような線形結合である。

q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).

最初の数個の選択肢を手動で数えると、次のような選択肢の数になる - フィボナッチ数（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、など。

規則性は明白です。(***)で代用してください。

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 (***).

まず、この3つの式からC_iが一意に決まることに注意しよう（システムの主決定式はほぼVandermondeの決定式であり、0に等しくない）。一方、フィボナッチ数は文字通り、C_1 = 1/sqrt(5) = -C_2, C_3 = 0とすると得られる。

したがって、答えは、次数Nの正し い梯子の数はF_{N+2}である。
 
Mathemat:

ちなみに私は、別解（二の足は踏まない）です。

フィボナッチも同じ漸化式で、q(N) = 2*q(N-2) + q(N-3)である。

したがって、系列の一致は、連続する3つの値の一致を証明すれば十分であった

1...515253545556575859606162636465...229
新しいコメント