数学の部屋へもどる。【コメント】
今回話題になったのは、
宮城県 あめの さんが調べてくださったのでご覧ください。
特に３番目が否定されたのは、残念でした。
◆石川県 Takashi さんからの解答。
A 10⇒10⇒10⇒ 8⇒ 8⇒ 0
B 8⇒16⇒15⇒15⇒11⇒11
C 9⇒ 1⇒ 2⇒ 4⇒ 8⇒16
＜以上５回＞
◆広島県 清川 育男 さんからの解答。
1) A>C A(1),B(8),C(18)
2) C>A A(2),B(8),C(17)
3) C>A A(4),B(8),C(15)
4) C>A A(8),B(8),C(11)
5) A>B A(0),B(16),C(11)
これが５手で最短手順だと思います。
1) A>B A(2),B(16),C(9)
2) B>C A(2),B(7),C(18)
3) C>A A(4),B(7),C(16)
4) C>B A(4),B(14),C(9)
5) B>A A(8),B(10),C(9)
6) B>C A(8),B(1),C(18)
7) C>B A(8),B(2),C(17)
8) C>B A(8),B(4),C(15)
9) C>B A(8),B(8),C(11)
10) A>B A(0),B(16),C(11)
これは１０手。
1) C>B A(10),B(16),C(1)
2) B>C A(10,B(15),C(2)
3) A>C A(8),B(15),C(4)
4) B>C A(8),B(11),C(8)
5) A>C A(0),B(11),C(16)
これも５手で最短手順です。
上記の横道。
1) C>B A(10),B(16),C(1)
2) A>C A(9),B(16),C(2)
3) A>C A(7),B(16),C(4)
4) B>C A(7),B(12),C(8)
5) C>A A(14),B(12),C(1)
6) B>C A(14),B(11),C(2)
7) A>B A(3),B(22),C(2)
8) A>C A(1),B(22),C(4)
9) B>A A(2),B(21),C(4)
10) B>A A(4),B(19),C(4)
11) A>C A(0),B(19),C(8)
これは１１手です。
５手が最短手順です。
すべてのゲームの木を探索するためには横型生成過程のアルゴリズムでプログラミングしないと無理でしょうね。
解答その２
1) A>B A(2),B(16),C(9)
2) B>C A(2),B(7),C(18)
3) C>B A(2),B(14),C(11)
4) B>C A(2),B(3),C(22)
5) C>B A(2),B(6),C(19)
6) C>B A(2),B(12),C(13)
7) C>B A(2),B(24),C(1)
8) B>C A(2),B(23),C(2)
9) A>C A(0),B(23),C(4)
これは９手です。
これで、８＞８、４＞４、２＞２の移動が出そろいました。
７手でもあります。
最長手順の定義は無駄な繰り返しを許さないということでしょうか？
繰り返しを許せば５手以上ならすべて可能ですね。 7手
A->B B->A C->A B->A A->B
B->C A->C
( 0 , 7 , 20 )
7手
A->B C->A C->A A->C B->C
C->A A->B
( 0 , 20 , 7 )
◆海外 西野 友朗 さんからの解答。
| Ａ | Ｂ | Ｃ | ||
| ０ | 初期状態 | １０ | ８ | ９ |
| １ | Ｃ→Ｂ | １０ | １６ | １ |
| ２ | Ｂ→Ｃ | １０ | １５ | ２ |
| ３ | Ａ→Ｃ | ８ | １５ | ４ |
| ４ | Ｂ→Ｃ | ８ | １１ | ８ |
| ５ | Ａ→Ｃ | ０ | １１ | １６ |
Aを２の階乗にして数を合せていくのがコツということですね。
最初にA→CとするとAに1が残りますので、それを2，4，8のいずれかにして、あとはBとCの間で交互に油を移動させてAの量と同じにすれば完了です。
ただし、A=2でB,Cをそれぞれ10,15または5,20(それぞれ逆でも可)にすると、B,C間でその組み合わせを繰り返すだけになり、一方をAと同じ量(=2)にできなくなるので、Aの量を4または8にする必要があります。
Aの量が4,8の場合（つまり、B,Cの合計が23,19の場合)、このような循環が発生することはありません。
◆石川県 平田 和弘 さんからの解答。
いろいろ試しているうちにＣの量が１→２→４→８．．．と変化するので
解答１．
最終手の１つ前のＣの量が２になるように考えて
Ｃ→Ｂ、Ｂ→Ａ、Ａ→Ｂ、Ａ→Ｂ、Ｂ→Ｃ、Ａ→Ｃ の６手で移動できます。
解答２．
最終手の１つ前のＣの量が４になるように考えて
Ｃ→Ｂ、Ｂ→Ｃ、Ａ→Ｃ、Ｂ→Ａ、Ａ→Ｂ、Ｂ→Ａ、Ａ→Ｂ、
Ａ→Ｂ、Ｂ→Ａ、Ｂ→Ａ、Ａ→Ｂ、Ｂ→Ａ、Ｂ→Ａ、Ａ→Ｃ の１４手で移動できます。
解答３．
最終手の１つ前のＣの量が８になるように考えて
Ｃ→Ｂ、Ｂ→Ｃ、Ａ→Ｃ、Ｂ→Ｃ、Ａ→Ｃ の５手で移動できます。
(おそらくこれが最短でしょう。)
別解答１
(実験から言って最終手の一手前の量が２，４，８．．．というように２の階乗になるので)、Ｂが８(２の階乗)であることを生かすように考えて
Ａ→Ｃ、Ｃ→Ａ、Ｃ→Ａ、Ｃ→Ａ、Ａ→Ｂ の５手で可能です。
(これも最短手順でしょう。)
別解答２
方針が一貫していませんがなんとなくできました長手数です。
Ａ→Ｂ、Ｃ→Ａ、Ｂ→Ｃ、Ｃ→Ａ、Ｂ→Ａ、Ａ→Ｂ、Ａ→Ｂ、
Ａ→Ｃ、Ｂ→Ａ、Ｃ→Ｂ、Ｃ→Ｂ、Ｃ→Ｂ、Ｃ→Ｂ、Ｂ→Ａ、
Ａ→Ｃ、Ｃ→Ａ、Ｂ→Ｃ、Ａ→Ｃ、Ａ→Ｂ、Ｂ→Ａ、Ｂ→Ａ、
Ｃ→Ａ、Ａ→Ｃ の２３手です。
別解答３
初手を別解答２と同じくＡ→Ｂでスタートすると
Ａ→Ｂ、Ｂ→Ｃ、Ｂ→Ａ、Ｃ→Ａ、Ｃ→Ａ、Ａ→Ｂ、Ａ→Ｂ、
Ｂ→Ａ、Ｂ→Ａ、Ｂ→Ｃ、Ｃ→Ａ、Ａ→Ｃ の１２手でも可能です。
感想
数学の問題に置き換えるとどうなるのかよくわかりませんが、実験から言って最終手の一手前の量が２，４，８．．．というように２の階乗にしかできないのでしょうか。
たとえば最終手の一手前の量を奇数にして最後完了することは不可能でしょうか。
また長手数は何手でも可能なのでしょうか。(規則性があるとか．．．．)
◆三重県 ぐぅすか さんからの解答。
今回の「油の移動」は、第１６回の数字の並べ替え問題の時の、（実験をしている間に成功するのですが、その手順を自分が覚えていないのでもう一度やろうとするとできない）という反省から紙の上でやってみました。
解答@（５手）
Ａ→Ｃ
Ｃ→Ａ
Ｃ→Ａ
Ｃ→Ａ
Ａ→Ｂ
解答A（８手）
Ａ→Ｂ
Ｂ→Ａ
Ｂ→Ａ
Ｂ→Ｃ
Ｃ→Ｂ
Ｃ→Ｂ
Ｃ→Ｂ
Ａ→Ｂ
解答B（９手）
Ｃ→Ｂ
Ｂ→Ｃ
Ｂ→Ｃ
Ｂ→Ｃ
Ｂ→Ｃ
Ａ→Ｂ
Ｂ→Ａ
Ｂ→Ａ
Ｂ→Ａ
Ａ→Ｃ
解答Aでは３手めに、また、解答Bでは４手めに３つの容器の中の油が１０リットルと９リットルと８リットルになるのでその後は解答@と同じ手順です。
いずれにせよ、２つの容器の中の量を同じ（８リットル）にしてから、Aをからっぽにしました。
８リットル以外ではできないのでしょうか。
ここまでやってからヒントを見てみるとアレレ・・・違う！
ヒントを参考にしてできたのは、
５手で Ｃ→Ｂ Ｂ→Ｃ Ａ→Ｃ Ｂ→Ｃ Ａ→Ｃ
Ｃの油の量の変化が面白いというのがやっと納得です。
◆神奈川県 せいちゃん さんからの解答。
（１） Ｃ→Ｂ
（２） Ｂ→Ｃ
（３） Ａ→Ｃ
（４） Ｂ→Ｃ
（５） Ａ→Ｃ
ほんと、Ｃの油の量の変化が面白い。
初項１項比2の等比数列になってますね。
そうならないと出来ないのかな？
そんな事はないはずだけど。
◆千葉県 ドラゴン さんからの解答。
| Ａ | Ｂ | Ｃ | |
| １０ | ８ | ９ | |
| ＡＢ | ２ | １６ | ９ |
| ＢＣ | ２ | ７ | １８ |
| ＣＡ | ４ | ７ | １６ |
| ＣＢ | ４ | １４ | ９ |
| ＢＣ | ４ | ５ | １８ |
| ＣＡ | ８ | ５ | １４ |
| ＡＢ | ３ | １０ | １４ |
| ＣＢ | ３ | ２０ | ４ |
| ＢＡ | ６ | １７ | ４ |
| ＢＡ | １２ | １１ | ４ |
| ＡＣ | ８ | １１ | ８ |
| ＡＣ | ０ | １１ | １６ |
◆宮城県 あめの さんからの解答。
○直感で求めた答え（５手）
A->C
C->A
C->A
C->A
A->B
○とりうる最大の手数
【前提】
ここで、(3 x 6)の部分は、(23,2,2)のように同じ容量のコップがある場合であり、78 x 6 でダブって求めた手数をひいている。
○プログラムに解かせた最大手
>最後が奇数で終わる解があるか？
これに関してですが、最後の操作のときには同じ容量のコップが２つないといけません。（証明略）
しかし、以下の理由により奇数のコップが２つ以上になることはないため、奇数の解は存在しないと思います。
--- 証明 ----
「記号の定義」
容量が偶数のコップを「e」、奇数のコップを「o」とする。
「証明」
初期状態では eが２つ、oが１つあるため、
操作としては、
(1)e->e'
(2)e->o
(3)o->e
の３つのみ存在する。
ここで、上記の矢印（->）の意味は、
矢印の左のコップの方が右のコップよりも多い、
つまり、左のコップから右のコップへ水が移されることを示す。
上記の３つの操作を行った後のコップの状態は、以下の表に示されるように初期状態を保って
「eが２つ、oが１つ」のままである。
| 左のコップ | 右のコップ | |
| （１） | e-e'（偶数） | e'*2（偶数） |
| （２） | e-o （奇数） | o *2（偶数） |
| （３） | o-e （奇数） | e *2（偶数） |
よって、奇数が最後の解になることはない。
>最終手の一手前の量が２，４，８．．．というように２の階乗にしかできないか
プログラムで見たところ、最後が(10,10,7)という116手の解がありました。
証明はしていないです。
◆岐阜県立海津北高等学校情報処理科２年 さんからの解答。
１回目：Ａ→Ｃ（１，８，１８）
２回目：Ｃ→Ａ（２，８，１７）
３回目：Ｃ→Ａ（４，８，１５）
４回目：Ｃ→Ａ（８，８，１１）
５回目：Ａ→Ｂ（０，１６，１1)
以上5回で終了します。
また、授業中に他の人が別の方法で解くことが出来ましたのでそれも紹介いたします。
ちなみにその方法では６回になります。
１回目：Ａ→Ｃ（１，８．１８）
２回目：Ｃ→Ａ（２，８，１７）
３回目：Ｂ→Ａ（４，６，１７）
４回目：Ｃ→Ｂ（４，１２，１１）
５回目：Ｂ→Ａ（８，８，１１）
６回目：Ａ→Ｂ（０，１６，１１）
◆神奈川県 Yuh! さんからの解答。
出来るだけ、回数の多い方法です。
Ａ→Ｃ
Ｃ→Ｂ
Ｂ→Ｃ
Ｃ→Ａ
Ｃ→Ａ
Ｃ→Ａ
Ｃ→Ａ
Ａ→Ｂ
Ａ→Ｃ
Ｂ→Ａ
Ａ→Ｃ
◆長野県の中学校３年生 篠田 章広＆林 拓馬 さんからの解答。
| 最初 | Ａ | Ｂ | Ｃ |
| １０ | ８ | ９ | |
| Ａ→Ｃ | １ | ８ | １８ |
| Ｃ→Ｂ | １ | １６ | １０ |
| Ｃ→Ａ | ２ | １６ | ９ |
| Ｃ→Ａ | ４ | １６ | ７ |
| Ｃ→Ａ | ８ | １６ | ３ |
| Ｂ→Ｃ | ８ | １３ | ６ |
| Ａ→Ｃ | ２ | １３ | １２ |
| Ｂ→Ｃ | ２ | １ | ２４ |
| Ｃ→Ａ | ４ | １ | ２２ |
| Ｃ→Ｂ | ４ | ２ | ２１ |
| Ｃ→Ｂ | ４ | ４ | １９ |
| Ａ→Ｂ | ０ | ８ | １９ |
難問でした。解けてみるとすごくうれしいです。
◆ 問題へもどる
◆ 今週の問題へ