『今週の問題』

『今週の問題』第39回　解答

【コメント】

問題２の最短手数は不明ですが、とりあえず１１手で可能です。
いまだ指摘された方はおりません。
早い者勝ちです。どなたか発見してください。

といったら清川さんから解答が届きました。
１１手の回は他にもあるので、見つけた方はお知らせください。

◆北海道　くーりーさんからの解答。

【問題１】

桶からＢに入れて、Ｂを満杯にする。
[ＡＢ5 ]

Ｂの全ての油をＡに移す。
[Ａ5 Ｂ ]

桶からＢに入れて、Ｂを満杯にする。
[Ａ5 Ｂ5 ]

Ａが満杯になるまで、ＢからＡに移す。
[Ａ9 Ｂ1 ]

Ａの油をすべて桶に戻す（捨てる）。
[ＡＢ1 ]

Ｂの全ての油をＡに移す。
[Ａ1 Ｂ ]

桶からＢに入れて、Ｂを満杯にする。
[Ａ1 Ｂ5 ]

Ｂの全ての油をＡに移す。
[Ａ6 Ｂ ]

【問題２】

桶からＡに入れて、Ａを満杯にする。
[桶10 Ａ11 ＢＣ ]

ＡからＣに入れて、Ｃを満杯にする。
[桶10 Ａ6 ＢＣ5 ]

Ｃの油をすべて桶に戻す。
[桶15 Ａ6 ＢＣ ]

ＡからＣに入れて、Ｃを満杯にする。
[桶15 Ａ1 ＢＣ5 ]

Ｃの油をすべて桶に戻す。
[桶20 Ａ1 ＢＣ ]

Ａの油をすべてＣに入れる。
[桶20 ＡＢＣ1 ]

桶からＡに入れて、Ａを満杯にする。
[桶9 Ａ11 ＢＣ1 ]

ＡからＣに入れて、Ｃを満杯にする。
[桶9 Ａ7 ＢＣ5 ]

Ｃの油をすべて桶に戻す。
[桶14 Ａ7 ＢＣ ]

Ａの油をすべてＢに入れる。
[桶14 ＡＢ7 Ｃ ]

桶からＡに入れて、Ａを満杯にする。
[桶3 Ａ11 Ｂ7 Ｃ ]

ＡからＣに入れて、Ｃを満杯にする。
[桶3 Ａ6 Ｂ7 Ｃ5 ]

Ｃの油をすべて桶に戻す。
[桶8 Ａ6 Ｂ7 Ｃ ]

ＡからＣに入れて、Ｃを満杯にする。
[桶8 Ａ1 Ｂ7 Ｃ5 ]

Ｃの油をすべて桶に戻す。
[桶13 Ａ1 Ｂ7 Ｃ ]

Ａの油をすべてＣに入れる。
[桶13 ＡＢ7 Ｃ1 ]

桶からＡに入れて、Ａを満杯にする。
[桶2 Ａ11 Ｂ7 Ｃ1 ]

ＡからＣに入れて、Ｃを満杯にする。
[桶2 Ａ7 Ｂ7 Ｃ5 ]

Ｃの油をすべて桶に入れる。
[桶7 Ａ7 Ｂ7 Ｃ ]

◆奈良県　竹川　澄子さんからの解答。

【問題１】

おけ→Ｂ
Ｂ→Ａ
おけ→Ｂ
Ｂ→Ａ
Ａ→おけ
Ｂ→Ａ
おけ→Ｂ
Ｂ→Ａ

【問題２】

おけ→Ｂ
おけ→Ｃ
Ｂ→Ａ
Ｃ→Ｂ
おけ→Ｃ
おけ→Ｃ
Ｃ→Ａ
（ここでＣに２㍑入っているのがポイントですね。）
Ｃ→Ｂ
Ａ→おけ
Ｂ→おけ
Ｃ→Ａ
Ｃ→Ｂ
おけ→Ｃ
おけ→Ｃ
Ｃ→Ａ
Ｃ→Ｂ

◆東京都　溝部　光洋さんからの解答。

【問題１】

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

【問題２】

桶→Ｃ，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ，
Ｃ→Ａ，桶→Ｃ，Ｃ→Ａ，Ｂ→桶，
桶→Ｃ，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ，
Ｂ→桶，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ　

◆広島県　清川　育男さんからの解答。

【問題１】

１）　桶からＢ
２）　ＢからＡ
３）　桶からＢ
４）　ＢからＡ
５）　Ａから桶
６）　ＢからＡ
７）　桶からＢ
８）　ＢからＡ

９と５は互いに素。

【問題２】

１）　桶からＣ
２）　ＣからＢ
３）　桶からＣ
４）　ＣからＢ
５）　Ｂから桶
６）　ＣからＢ
７）　桶からＣ
８）　ＣからＢ
９）　ＢからＡ
10）　桶からＣ
11）　ＣからＢ
12）　桶からＣ
13）　ＣからＢ
14）　Ｂから桶
15）　ＣからＢ
16）　桶からＣ
17）　ＣからＢ

以上１７手順で可能です。
桶とＢの容器とＣの容器で７リットルを作り、Aに移すところがポイントですね。

【問題２】

１) 桶からＣ
２）ＣからＡ
３）桶からＣ
４）ＣからＡ
５）桶からＣ
６）ＣからＢ
７）ＡからＢ
８）Ｂから桶
９）桶からＣ
10）ＣからＢ
11）桶からＣ
12）ＣからＢ
13）Ｂから桶
14）ＣからＢ
15）桶からＣ
16）ＣからＢ

１６手順のものは他の方法もあります。

【問題２】

１）桶からＡ
２）ＡからＣ
３）ＣからＢ
４）ＡからＣ
５）ＣからＢ
６）Ｂから桶
７）ＣからＢ
８）ＡからＣ
９）桶からＡ
10）ＡからＣ
11）ＣからＢ

まずＢに２リットルを、次にAに１リットル、残りとして桶に１８リットルを残す。

桶からＡ、ＡからＣ、ＣからＢの移動で７，７，７を作る。

これらが無駄のない移動になりますね。
桶に戻す回数は１回。

桶に戻す回数を０回ではこれらのことは出来ないので、この手順が最小手数となりますね。
一般化のイメージがおぼろげながらつかめた気がします。

【問題２】

 11手
    1
桶->A  A ->C  A ->B  C ->桶 B ->C  
C ->A  B ->C  桶->B  B ->A  A ->C  
C ->B  

    2
桶->A  A ->C  A ->B  C ->A  B ->C  
C ->桶 B ->C  桶->B  B ->A  A ->C  
C ->B  

    3
桶->A  A ->C  A ->B  C ->A  B ->C  
C ->A  B ->C  桶->B  B ->A  A ->C  
C ->桶 

    4
桶->A  A ->C  C ->桶 A ->B  B ->C  
C ->A  B ->C  桶->B  B ->A  A ->C  
C ->B  

    5
桶->A  A ->C  C ->桶 A ->C  A ->B  
C ->A  B ->C  桶->B  B ->A  A ->C  
C ->B  

    6
桶->A  A ->C  C ->桶 A ->C  C ->B  
A ->C  B ->A  桶->B  B ->A  A ->C  
C ->B  

    7
桶->A  A ->C  C ->B  A ->C  C ->桶 
A ->C  B ->A  桶->B  B ->A  A ->C  
C ->B  

    8
桶->A  A ->C  C ->B  A ->C  C ->B  
B ->桶 C ->B  A ->C  桶->A  A ->C  
C ->B

◆石川県　平田和弘さんからの解答

【問題１】

6リットルは、5リットル＋1リットルで計量することをめざして、

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

以上、8手で完了します。

【問題２】

まず、最初の7リットルを5リットル＋2リットルで量ることを考えて、次ぎに残り7リットルを11リットルと5リットルの容器で量ります。

桶→Ｂ，桶→Ｃ，Ｃ→Ａ，Ｂ→Ａ，
桶→Ｃ，Ｃ→Ｂ，Ａ→Ｃ，Ｃ→桶，
Ａ→Ｃ，Ｃ→桶，Ａ→Ｃ，桶→Ａ，
Ａ→Ｃ，Ｃ→桶

以上、14手で完了します。

(感想)

問題２はもっと最短手順がありそうな気がしますが・・・。
問題１ができると、問題２は比較的容易にできました。

◆神奈川県　太郎冠者さんからの解答

【問題１】

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

【問題２】

桶→Ｂ，Ｂ→Ａ，桶→Ｃ，Ｃ→Ａ，
Ａ→桶，Ｃ→Ａ，桶→Ｃ，Ｃ→Ｂ，
桶→Ｃ，Ｃ→Ｂ，Ｂ→桶，Ｃ→Ｂ，
桶→Ｃ，Ｃ→Ａ，桶→Ｃ，Ｃ→Ｂ

◆東京都　Asami(☆_☆) さんからの解答

【問題１】

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

【問題２】

p,q(p＜q)が互いに素な正整数であれば、

任意の整数1≦ｋ≦q-1に対して
pχ－qｙ＝ｋとなる解

(χ,ｙ);0＜χ＜q,ｙ≧0が存在する。

このχはpリットル容器からqリットル容器への移動回数、ｙはqリットル容器から油桶に戻す回数と考えることができ、これに従って移動を繰り返せば最終的に、qリットル容器にｋリットルの油を残すことが可能となる。

ただし、問題１においては供給される油が大量にあったので、何も考える必要はないが、問題２においては予め油量が決まっているので、油桶からpリットル容器への供給を常に絶やさないために、互いに素な２つの容器の選び方は慎重を要する。
つまり、油桶≧２つの容器の和となるように選んで行く必要がある。

＜選び方の悪い例＞
始めにＢ(8リットル)容器,Ｃ(5リットル)容器を使い、Ｂに7リットルを残す。
次に、油桶(残量14リットル)からＡ(11リットル)容器,Ｃ(5リットル)容器を使い、7リットルずつに配分をしようとするやり方。
これは14＜11＋5なので、油桶からＣへの供給が不足する状況が出てくる。

上記に従えば、Ａ,Ｂのみを使ってＡに７リットル残し、次にＢ,Ｃのみを使ってＢに７リットル残せば、結果的に３等分されたことになる。
でも、このやり方は(機械的という意味で確実だけれど)だいぶ無駄の多いやり方だと思います。
実際、その規則に従ってやってみましたが……(笑)
やっぱり手数が多いです！

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
桶→Ｂ，Ｂ→Ａ，Ａ→桶，Ｂ→Ａ，
桶→Ｃ，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ，
Ｂ→桶，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ

◆神奈川県の中学校１年生　ありささんからの解答

【問題１】

まず、油桶から5リットルの容器へ油を入れる。
５リットルの容器から９リットルの容器に移す。
もう一度、油桶から５リットルの容器へ油を入れる。
その５リットルの容器の油を９リットルの容器に移す。
すると、４リットルしか入らず５リットルの容器に１リットルだけ油が残る。
９リットルの容器に入っている油を油桶に戻す。
さっき５リットルの容器に残っていた１リットルの油を、９リットルの容器に移す。
油桶から５リットルの容器に油を入れる。
その油（５リットルの油）を９リットルの容器に移すと、な・なんと！？
６リットルになったじゃないですか！！

【問題２】

桶ーＣ　Ｃ－Ａ　桶ーＣ　Ｃ－Ｂ
桶ーＣ　Ｃ－Ｂ　Ｃ－Ａ　Ｂ－桶
桶ーＣ　Ｃ－Ｂ　桶ーＣ　Ｃ－Ｂ
Ｂ－桶　Ｃ－Ｂ　桶ーＣ　Ｃ－Ｂ

◆熊本県　小太りおじさんさんからの解答

【問題１】

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

一応８手でした。

【問題２】

桶→Ｃ，Ｃ→Ａ，桶→Ｃ，Ｃ→Ａ，
桶→Ｂ，Ｂ→Ａ，Ａ→桶，桶→Ｃ，
Ｃ→Ａ，桶→Ｃ，Ｃ→Ａ，桶→Ｃ，
Ｂ→桶，Ａ→Ｂ，Ｂ→Ｃ，Ｃ→Ａ

一応１６手でした。

◆東京都　岡　有さんからの解答

【問題１】

Bに5リッターいれる。
BからAに5リッターを入れる。
Bに5リッターいれる。
BからAに4リッターを入れる。（Aがいっぱいになる）
結果としてBに1リッターのこる。
Aの中身をすべて壷に戻す。
Bの1リッターをAに移す。
Bに5リッターを入れる。
BからAに5リッターを入れる。
Aに6リッター入る。

【問題２】

簡単にするため、下記のような順番で数字だけ書きます。

 油桶＝ A＝B＝C
   21＝ 0＝0＝0
    8＝ 0＝8＝5
    8＝ 5＝8＝0
    8＝11＝2＝0
    3＝11＝2＝5
    3＝11＝7＝0
    0＝11＝7＝3
    0＝ 9＝7＝5
    5＝ 9＝7＝0
    5＝ 4＝7＝5
   10＝ 4＝7＝0
   10＝ 0＝7＝4
   10＝ 7＝0＝4
    2＝ 7＝8＝4
    2＝ 7＝7＝5
    0＝ 7＝7＝7

◆熊本県　ともさんからの解答

【問題１】

まず、Ｂの5リットル容器に油をいれ、Aの9リットル容器にうつす。
A：5リットル、B：0リットル

次に再度Ｂの5リットル容器に油をいれ、またAの容器にうつすが、さきほどいれた5リットルプラスあと4リットルしかはいらないので、4リットルのみAにいれる
A：9リットル B：1リットル

次に、Aの油を油桶にかえし、Bの1リットルをAの容器にいれBに5リットルいれてそれもAの容器にうつすと、Aには6リットルの油が入る！

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

【問題２】

桶→Ｂ，Ｂ→Ａ，桶→Ｃ，Ｃ→Ａ，
Ａ→桶，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ，
Ｂ→Ａ，桶→Ｃ，Ｃ→Ｂ，桶→Ｃ，
Ｃ→Ｂ，Ｂ→桶，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ｂ

◆千葉県　五十嵐正人さんからの解答

【問題１】

　 max ∞ 9 5

回動作桶ＡＢ

０初期 n 0 0

１桶→Ｂ n-5 0 5

２Ｂ→Ａ n-5 5 0

３桶→Ｂ n-10 5 5

４Ｂ→Ａ n-10 9 1

５Ａ→桶 n-1 0 1

６Ｂ→Ａ n-1 1 0

７桶→Ｂ n-6 1 5

８Ｂ→Ａ n-6 6 0

【問題２】

　 max ∞ 11 8 5

回動作桶ＡＢＣ

０初期 21 0 0 0

１桶→Ａ 10 11 0 0

２桶→Ｂ 2 11 8 0

３桶→Ｃ 0 11 8 2

４Ａ→桶 11 0 8 2

５Ｂ→桶 19 0 0 2

６Ｃ→Ａ 19 2 0 0

７桶→Ｃ 14 2 0 5

８Ｃ→Ａ 14 7 0 0

９桶→Ｃ 9 7 0 5

10 Ｃ→Ｂ 9 7 5 0

11 桶→Ｃ 4 7 5 5

12 Ｃ→Ｂ 4 7 8 2

13 Ｂ→桶 12 7 0 2

14 Ｃ→Ｂ 12 7 2 0

15 桶→Ｃ 7 7 2 5

16 Ｃ→Ｂ 7 7 7 0

◆石川県の中学校３年生　水原浩介さんからの解答

【問題２】

桶→Ｂ，Ｂ→Ｃ，桶→Ａ，Ｃ→桶，
Ａ→Ｂ，Ａ→Ｃ，Ｃ→桶，Ｂ→Ｃ，
Ａ→Ｃ，Ａ→Ｂ，Ｃ→Ａ，桶→Ｃ，
Ｃ→Ｂ，Ｂ→Ａ，Ａ→Ｃ，Ｃ→Ｂ

◆広島県　ゆうこさんからの解答

【問題１】

桶→Ｂ，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ，
Ａ→桶，Ｂ→Ａ，桶→Ｂ，Ｂ→Ａ

【問題２】

桶→Ａ，桶→Ｂ，桶→Ｃ，Ｂ→桶，
Ｃ→Ｂ，Ａ→桶，桶→Ｃ，Ｃ→Ａ，
桶→Ｃ，Ｃ→Ａ，Ｂ→Ｃ，Ａ→Ｂ，
Ｂ→桶，Ｃ→Ｂ，桶→Ｃ，Ｃ→Ａ，
桶→Ｃ，Ｃ→Ｂ

◆埼玉県　斉藤　誠さんからの解答

【問題２】

『油をはかろう』を参考に、「トウィーディーによって考案されたグラフ」で検討します。

升が互いに素であれば１Ｌ刻みで全ての容量を量りとることができるので
５Ｌと１１Ｌ、５Ｌと８Ｌ升で単独に７Ｌを量りとれます。

そこで最短手順がどうなるかですが、１つ手前を考えると、
８Ｌ升から１Ｌをくみ出すと１１Ｌ升は５Ｌ升から移すしか方法がないので
　８Ｌ升　８Ｌ－１Ｌ＝７Ｌ
１１Ｌ升　２Ｌ＋５Ｌ＝７Ｌ

反対にすると
１１Ｌ升　１１Ｌ－４Ｌ＝７Ｌ
　８Ｌ升　２Ｌ＋５Ｌ＝７Ｌ

よって、５Ｌ升に１Ｌか４Ｌ残し、１１Ｌ升または８Ｌ升に２Ｌを残す方法で最短を考える。

①８Ｌ升に２Ｌ残し、５Ｌ升に１Ｌを残す。
（｛｝内は操作後の容量、０は桶を表す）

３×８Ｌ－２×１１Ｌ＝２Ｌ

０→８、８→１１｛８｝、
０→８、８｛５｝→１１｛１１｝、
１１→０、８→１１｛５｝、
０→８、８｛２｝→１１｛１１｝
で８Ｌ升に２Ｌ残る

ここでは、１１Ｌ升に５Ｌを量り入れるところがあるので
５Ｌ升から量り入れることが出来る。

１１Ｌ－２×５Ｌ＝１Ｌ

０→１１、１１｛６｝→５、
５→０、１１｛１｝→５、
５→０、１１→５｛１｝
で５Ｌ升に１Ｌ残る

ここでは、１１Ｌ升から５Ｌ升に移すところがあるので
８Ｌ升に２Ｌ残す手順と共通の手順にする。

②１１Ｌ升に２Ｌ残し、５Ｌ升に４Ｌ残す
４Ｌを残す方法に手順を短くするうまい方法が無い。

●結論手順
０→５、
５→１１｛５｝、
０→８、
８｛２｝→１１｛１１｝
（８Ｌ升に２Ｌ残る）

１１｛６｝→５、
５→０、
１１｛１｝→５、
５→０、
１１→５｛１｝
（５Ｌ升に１Ｌ残る）

０→１１、
１１｛７｝→５
（１１Ｌ升に７Ｌ）

５→８｛７｝
（８Ｌ升に７Ｌ）

以上１２手が最短手順と思います。

◆石川県の中学校１年生　おのじ　＆　ゆうじさんからの解答

桶から、５リットルの容器に油を満タンに入れる。
次に、９リットルの容器に５リットルの容器の油を移す。
５リットルの容器に１リットル残るので９リットルの容器に入っている油は桶に戻す。
もう１度、この作業を行う。
５リットルの容器の中に入っている油を、９リットルの容器に移す。
５リットルの容器にまた、満タンに油を入れる。
５リットルの容器に入っている油を、９リットルの容器に、移し変えれば完成！。

最低　８手で出来る。

◆石川県　Takashi さんからの解答

≪Ⅰ≫

桶→Ｂ、Ｂ→Ａ、桶→Ｂ、Ｂ→Ａ（４リットル）

これだけの作業をすると、Ａに９リットル、Ｂに１リットルの油が入っている。

次に、
Ａ→桶、Ｂ→Ａ、桶→Ｂ、Ｂ→Ａ　とすると、Ａには６リットルの油が入っている。

≪Ⅱ≫

まず、
桶→Ｂ、桶→Ｃ、Ｃ→Ａ、Ｂ→Ａ（６リットル）とすると、Ｂに２リットルの油が残る。
　【A=11,C=0】

次に、
Ａ→Ｃ、Ｃ→Ｂとすると、Ｂに７リットルの油が入っている。
　【A=6,C=0】

次に、
Ａ→Ｃ、Ｃ→桶、Ａ→Ｃ、桶→Ａ、Ａ→Ｃ（４リットル）とすると、Ａに７リットルの油が入っている。
　【C=5】

最後に、Ｃ→桶とすると、桶とＡとＢに７リットルずつの油を入れる事が出来る。

≪感想≫

問題２はやや難しいです。
５、８、１１の３つの数を足したり引いたりしながら、７や２や１や４等を作ることが出来たら、油を７リットルに出来る様です。
ただ、自分の解法では、総量が２１リットルである事を全く活用していないので、ひょっとしたらもっと手数の短い答えがあるかなと思うのですがどうでしょうか。

　◆　問題へもどる

　◆　今週の問題へ

数学の部屋へもどる

	max	∞	9	5
回	動作	桶	Ａ	Ｂ
０	初期	n	0	0
１	桶→Ｂ	n-5	0	5
２	Ｂ→Ａ	n-5	5	0
３	桶→Ｂ	n-10	5	5
４	Ｂ→Ａ	n-10	9	1
５	Ａ→桶	n-1	0	1
６	Ｂ→Ａ	n-1	1	0
７	桶→Ｂ	n-6	1	5
８	Ｂ→Ａ	n-6	6	0

	max	∞	11	8	5
回	動作	桶	Ａ	Ｂ	Ｃ
０	初期	21	0	0	0
１	桶→Ａ	10	11	0	0
２	桶→Ｂ	2	11	8	0
３	桶→Ｃ	0	11	8	2
４	Ａ→桶	11	0	8	2
５	Ｂ→桶	19	0	0	2
６	Ｃ→Ａ	19	2	0	0
７	桶→Ｃ	14	2	0	5
８	Ｃ→Ａ	14	7	0	0
９	桶→Ｃ	9	7	0	5
10	Ｃ→Ｂ	9	7	5	0
11	桶→Ｃ	4	7	5	5
12	Ｃ→Ｂ	4	7	8	2
13	Ｂ→桶	12	7	0	2
14	Ｃ→Ｂ	12	7	2	0
15	桶→Ｃ	7	7	2	5
16	Ｃ→Ｂ	7	7	7	0

『今週の問題』第39回 解答

『今週の問題』第39回　解答