ハノイの塔問題・考察（１）を示します。 考察（１） n枚の円盤の移動回数をf(n)として求めてみる。 まず、手順(ア)にしたがって、棒Ｘの上からn-1枚の円盤を棒Ｚに移動するのにf(n-1)回の移動回数が必要である。 つぎに、手順(イ)にしたがって、棒Ｘのn枚目…

ハノイの塔問題（２）の解答例を示します。 問題（２）の解 円盤の枚数nに関する数学的帰納法で証明する。 （Ａ）円盤の枚数nの値が1のとき、明らかに条件を守りながら円盤は移動可能。 したがって、命題は正しい。 （Ｂ）円盤の枚数nの値がkのとき、２つの…

ハノイの塔問題（２）を紹介します。 問題（２） 一枚の板に３本の棒Ｘ,Ｙ,Ｚが立てられており、棒Ｘにはまん中に穴のあいた円盤が下から上へ小さくなる順にn枚はめられているとする。 つぎの２つの条件にしたがって、棒Ｘにはめられたn枚の円盤を棒Ｙに移す…

ハノイの塔問題（１）の解答例を示します。 問題（１）の解

ハノイの塔問題（１）を紹介します。 問題（１） 一枚の板に３本の棒Ｘ,Ｙ,Ｚが立てられており、棒Ｘにはまん中に穴のあいた円盤が下から上へ小さくなる順に3枚はめられているとする。 つぎの２つの条件にしたがって、棒Ｘにはめられた3枚の円盤を棒Ｙに移す…

農夫の渡河問題（７）の解答例を示します。 問題（７）の解

農夫の渡河問題（７）を紹介します。 問題（７） ボートには農夫のほかに最大２つ乗せることができる。農夫が運ぶ物を{犬１,犬２,犬３,猫１,猫２}とする。共存関係がつぎのようなとき、農夫が５匹を右岸に運ぶ方法を考察せよ。

農夫の渡河問題（６）の解答例を示します。 問題（６）の解

農夫の渡河問題（６）を紹介します。 問題（６） ボートには農夫のほかに最大２つ乗せることができる。農夫が運ぶ物を{犬１,犬２,犬３,猫１}とする。共存関係がつぎのようなとき、農夫が４匹を右岸に運ぶ方法を考察せよ。

農夫の渡河問題（５）の解答例を示します。 問題（５）の解 ●共存関係（○は共存可能、×は共存不可能） 農夫が一郎を乗せて、左岸から右岸に移動するとき、松子と竹子が左岸に残るので、移動できない。二郎の場合も同様。 農夫が松子を乗せて、左岸から右岸に…

農夫の渡河問題（５）を紹介します。 問題（５） ボートには農夫のほかに最大１人乗せることができる。 農夫が運ぶ人を{一郎,二郎,松子,竹子}とし、人xと人yが共存可能の場合○、共存不可能の場合×とする。共存関係がつぎのようなとき、農夫が４人を右岸に運…

農夫の渡河問題（４）の考察を示します。 問題（４）の考察 男性2人（一郎と二郎）、女性n（≧1）人において、男性同志は互いに共存不可能、女性とは共存可能、女性は、誰とでも共存可能であるとする。 このとき、最小2n+3回の移動回数で、全員を左岸から右岸…

農夫の渡河問題（４）の解答例を示します。 問題（４）の解

農夫の渡河問題（４）を紹介します。 問題（４） ボートには農夫のほかに最大１人乗せることができる。 農夫が運ぶ人を{一郎,二郎,松子,竹子}とし、人xと人yが共存可能の場合○、共存不可能の場合×とする。共存関係がつぎようなとき、農夫が４人を右岸に運ぶ…

農夫の渡河問題（３）の解答例を示します。 問題（３）の解

農夫の渡河問題（３）を紹介します。 問題（３） ボートには農夫のほかに最大１人乗せることができる。 農夫が運ぶ人を{一郎,二郎,松子}とし、人xと人yが共存可能の場合○、共存不可能の場合×とする。共存関係がつぎのようなとき、農夫が３人を右岸に運ぶ方法…

農夫の渡河問題（２）の解答例を示します。 問題（２）の解

農夫の渡河問題（２）を紹介します。 問題（２） ボートには農夫のほかに最大２つ乗せることができる。農夫が運ぶ物を{オオカミ,ヤギ,キャベツ}とし、物xと物yが共存可能の場合○、共存不可能の場合×とする。 共存関係が問題（１）と同じとき、農夫が、オオカ…

農夫の渡河問題（１）の解答例を示します。 問題（１）の解２

農夫の渡河問題（１）の解答例を示します。 問題（１）の解１ オオカミ、ヤギ、キャベツ、農夫がそれぞれ川の左岸にいるときに L 右岸にいるときに R で表わすと、最初の状態は、LLLL となる。目標の状態は、RRRR である。最初の状態を親節点とすると、最初…

農夫の渡河問題（１）を紹介します。 問題（１） 一そうのボートを使って、農夫がオオカミとヤギとキャベツを向こう岸に運ぶことになった。ところで、ボートには農夫のほかに最大１つ乗せることができる。また、農夫がいないとオオカミはヤギをヤギはキャベ…

直方体と串の問題（７）の解答例を示します。 問題（７）の解 縦方向に４回、水平方向に３回、横方向に５回切る。線分AHの長さを１としてそれぞれの切断点の位置を表すと、 縦方向で、1/5, 2/5, 3/5、4/5、 水平方向で、1/4, 2/4, 3/4、 横方向で、1/6, 2/6,…

直方体と串の問題（７）を紹介します。 問題（７） １×１×１の小立方体を積み重ねて、５×６×４の直方体をつくる。点Aと点Hを直線で結ぶとき、何個の小立方体を通過するか考察せよ。

直方体と串の問題（６）の解答例を示します。 問題（６）の解 縦方向に４回、水平方向に３回、横方向に４回切る。線分AGの長さを１としてそれぞれの切断点の位置を表すと、 縦方向で、1/5, 2/5, 3/5、4/5、 水平方向で、1/4, 2/4, 3/4、 横方向で、1/5, 2/5,…

直方体と串の問題（６）を紹介します。 問題（６） １×１×１の小立方体を積み重ねて、５×５×４の直方体をつくる。点Aと点Gを直線で結ぶとき、何個の小立方体を通過するか考察せよ。

直方体と串の問題（５）の解答例を示します。 問題（５）の解 縦方向に４回、水平方向に３回、横方向に３回切る。線分AFの長さを１としてそれぞれの切断点の位置を表すと、 縦方向で、1/5, 2/5, 3/5、4/5、 水平方向で、1/4, 2/4, 3/4、 横方向で、1/4, 2/4,…

直方体と串の問題（５）を紹介します。 問題（５） １×１×１の小立方体を積み重ねて、５×４×４の直方体をつくる。点Aと点Fを直線で結ぶとき、何個の小立方体を通過するか考察せよ。

直方体と串の問題（４）の解答例を示します。 問題（４）の解 縦方向に４回、水平方向に３回、横方向に２回切る。線分AEの長さを１としてそれぞれの切断点の位置を表すと、 縦方向で、1/5, 2/5, 3/5、4/5、 水平方向で、1/4, 2/4, 3/4、 横方向で、1/3, 2/3 …

直方体と串の問題（４）を紹介します。 問題（４） １×１×１の小立方体を積み重ねて、５×３×４の直方体をつくる。点Aと点Eを直線で結ぶとき、何個の小立方体を通過するか考察せよ。

直方体と串の問題（３）の解答例を示します。 問題（３）の解 縦方向に４回、水平方向に３回、横方向に１回切る。線分ADの長さを１としてそれぞれの切断点の位置を表すと、 縦方向で、1/5, 2/5, 3/5、4/5、 水平方向で、1/4, 2/4, 3/4、 横方向で、1/2 とな…