バケツを空に

 投稿者：GAI  投稿日：2013年 1月14日(月)17時38分31秒
  大きなバケツが３つあり（これをＡ，Ｂ，Ｃで表す。）
それぞれにきっちり整数リットルの蒸発しない液体が入っているとする。
（容器には十分な余裕があるものとする。）
一度に出来る操作は、あるバケツにそれ以上多くの液体が入っている他のバケツから
液体の一部を移して２倍にすること。
言いかえれば、ｘリットル入っているバケツから、ｙリットル（ただしｙ≦ｘ）入っている
バケツへｙリットルだけ移し、バケツの中身をそれぞれ、(ｘ－ｙ)リットルと(２×ｙ)リットル
にすることである。

今最初の３つのバケツの液体の量が次の時一つのバケツを空にする手順は？
例
(A,B,C)=( 6,11,14) であるとき、
      →(12,11, 8)
      →(12, 3,16)
      →( 9, 6,16)
      →( 3,12,16)
      →( 6,12,13)
      →(12,12, 7)
      →( 0,24, 7)

の7回で目的達成できる。



この操作をする限りどんな初期状態であれ、必ず一つのバケツを空にすることができるという。
このパズルを解かせる最も手数が掛かってしまう初期状態の容器にある液体の量の組合せ（１００リットル以内で）を探してくれませんか。 		 

Re: バケツを空に

 投稿者：山中和義  投稿日：2013年 1月15日(火)11時19分6秒
  > No.2956[元記事へ]

GAIさんへのお返事です。

> 例
> (A,B,C)=( 6,11,14) であるとき、
>       →(12,11, 8)
>       →(12, 3,16)
>       →( 9, 6,16)
>       →( 3,12,16)
>       →( 6,12,13)
>       →(12,12, 7)
>       →( 0,24, 7)
>
>  の7回で目的達成できる。

最後の3手
x＜yとして、組(x,2x,y) → (2x,2x,y-x) → (0,4x,y-x) となる。
これより、x+2x+y=Nとして、3x=N-y
この式を満たす(x,y)に着目する。

この場合は、6+11+14=31なので、
(x,y)=(10,1)、(9,4)、(8,7)、(7,10)、(6,13)、(5,16)、(4,19)、(3,22)、(2,25)、(1,28)
が最後の3手である。

　0: (6,11,14)
　1: (6,22,3)　←(3,22)
　2: (6,19,6)
　3: (0,19,12)


>       →( 6,12,13)
>       →(12,12, 7)
>       →( 0,24, 7)

これは、(6,13)となります。


最適解は、試行錯誤するしかないようなので、深さ優先（バックトラック法）で探索してみました。


PUBLIC NUMERIC S !手数　※上限
LET S=20
DIM A(0 TO S),B(0 TO S),C(0 TO S) !バケツの水量

LET A(0)=6
LET B(0)=11
LET C(0)=14

CALL try(0,A,B,C)
PRINT S;"回"

END

EXTERNAL SUB try(p,A(),B(),C()) !バックトラック法で検索する
IF A(p)=0 OR B(p)=0 OR C(p)=0 THEN
   IF p< S THEN
      LET S=p !更新
      FOR i=0 TO p !手順を表示する
         PRINT STR$(i);": (";STR$(A(i));",";STR$(B(i));",";STR$(C(i));")"
      NEXT i
      PRINT
   END IF
ELSE
   IF p< S THEN !手数の上限以内なら、次の6通りを試す
      IF A(p)>=B(p) THEN !A→Bとする
         LET A(p+1)=A(p)-B(p)
         LET B(p+1)=2*B(p)
         LET C(p+1)=C(p)
         CALL try(p+1,A,B,C)
      END IF
      IF A(p)>=C(p) THEN !A→Cとする
         LET A(p+1)=A(p)-C(p)
         LET C(p+1)=2*C(p)
         LET B(p+1)=B(p)
         CALL try(p+1,A,B,C)
      END IF
      IF B(p)>=C(p) THEN !B→Cとする
         LET B(p+1)=B(p)-C(p)
         LET C(p+1)=2*C(p)
         LET A(p+1)=A(p)
         CALL try(p+1,A,B,C)
      END IF
      IF B(p)>=A(p) THEN !B→Aとする
         LET B(p+1)=B(p)-A(p)
         LET A(p+1)=2*A(p)
         LET C(p+1)=C(p)
         CALL try(p+1,A,B,C)
      END IF
      IF C(p)>=A(p) THEN !C→Aとする
         LET C(p+1)=C(p)-A(p)
         LET A(p+1)=2*A(p)
         LET B(p+1)=B(p)
         CALL try(p+1,A,B,C)
      END IF
      IF C(p)>=B(p) THEN !C→Bとする
         LET C(p+1)=C(p)-B(p)
         LET B(p+1)=2*B(p)
         LET A(p+1)=A(p)
         CALL try(p+1,A,B,C)
      END IF
   END IF
END IF
END SUB

 		 

Re: バケツを空に

 投稿者：山中和義  投稿日：2013年 1月15日(火)12時41分8秒
  GAIさんへのお返事です。

> 最後の3手
> x＜yとして、組(x,2x,y) → (2x,2x,y-x) → (0,4x,y-x) となる。
> これより、x+2x+y=Nとして、3x=N-y
> この式を満たす(x,y)に着目する。

x＜yとして、組(x,3x,y) → (2x,3x-x,y)=(2x,2x,y) → (0,4x,y) となる。
これも条件をみたしますね。

50の範囲では、
(27,35,43) 9 回

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (30,32,43)
4: (60,2,43)
5: (60,4,41)
6: (56,8,41)
7: (48,16,41)
8: (32,32,41)
9: (0,64,41)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (30,32,43)
4: (60,2,43)
5: (60,4,41)
6: (56,8,41)
7: (48,16,41)
8: (32,32,41)
9: (64,0,41)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,13,86)
5: (6,26,73)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,13,86)
5: (6,26,73)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,16,83)
5: (12,10,83)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,16,83)
5: (12,10,83)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,4,77)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,4,77)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,16,65)
7: (48,16,41)
8: (32,32,41)
9: (0,64,41)

0: (27,35,43)
1: (54,8,43)
2: (46,16,43)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,16,65)
7: (48,16,41)
8: (32,32,41)
9: (64,0,41)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,13,86)
5: (6,26,73)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,13,86)
5: (6,26,73)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,16,83)
5: (12,10,83)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,16,83)
5: (12,10,83)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,4,77)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,4,77)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,16,65)
7: (48,16,41)
8: (32,32,41)
9: (0,64,41)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (3,16,86)
4: (6,16,83)
5: (12,16,77)
6: (24,16,65)
7: (48,16,41)
8: (32,32,41)
9: (64,0,41)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (22,8,75)
4: (14,16,75)
5: (28,2,75)
6: (28,4,73)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (22,8,75)
4: (14,16,75)
5: (28,2,75)
6: (28,4,73)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (11,16,78)
4: (22,5,78)
5: (22,10,73)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (0,32,73)

0: (27,35,43)
1: (54,8,43)
2: (11,8,86)
3: (11,16,78)
4: (22,5,78)
5: (22,10,73)
6: (12,20,73)
7: (24,8,73)
8: (16,16,73)
9: (32,0,73)

0: (27,35,43)
1: (54,35,16)
2: (38,35,32)
3: (38,3,64)
4: (76,3,26)
5: (73,6,26)
6: (73,12,20)
7: (73,24,8)
8: (73,16,16)
9: (73,0,32)

0: (27,35,43)
1: (54,35,16)
2: (38,35,32)
3: (38,3,64)
4: (76,3,26)
5: (73,6,26)
6: (73,12,20)
7: (73,24,8)
8: (73,16,16)
9: (73,32,0)

0: (27,35,43)
1: (54,35,16)
2: (38,35,32)
3: (38,3,64)
4: (76,3,26)
5: (50,3,52)
6: (100,3,2)
7: (97,6,2)
8: (97,4,4)
9: (97,0,8)

0: (27,35,43)
1: (54,35,16)
2: (38,35,32)
3: (38,3,64)
4: (76,3,26)
5: (50,3,52)
6: (100,3,2)
7: (97,6,2)
8: (97,4,4)
9: (97,8,0)

0: (27,35,43)
1: (54,35,16)
2: (38,35,32)
3: (38,3,64)
4: (38,6,61)
5: (38,12,55)
6: (38,24,43)
7: (38,48,19)
8: (38,29,38)
9: (0,29,76)

0: (27,35,43)
1: (54,35,16)
2: (38,35,32)
3: (38,3,64)
4: (38,6,61)
5: (38,12,55)
6: (38,24,43)
7: (38,48,19)
8: (38,29,38)
9: (76,29,0)

0: (27,35,43)
1: (54,35,16)
2: (54,19,32)
3: (54,38,13)
4: (41,38,26)
5: (41,12,52)
6: (41,24,40)
7: (41,48,16)
8: (41,32,32)
9: (41,0,64)

0: (27,35,43)
1: (54,35,16)
2: (54,19,32)
3: (54,38,13)
4: (41,38,26)
5: (41,12,52)
6: (41,24,40)
7: (41,48,16)
8: (41,32,32)
9: (41,64,0)

0: (27,35,43)
1: (54,35,16)
2: (54,19,32)
3: (54,38,13)
4: (54,25,26)
5: (54,50,1)
6: (4,100,1)
7: (4,99,2)
8: (4,97,4)
9: (0,97,8)

0: (27,35,43)
1: (54,35,16)
2: (54,19,32)
3: (54,38,13)
4: (54,25,26)
5: (54,50,1)
6: (4,100,1)
7: (4,99,2)
8: (4,97,4)
9: (8,97,0)


つづく

 		 

Re: バケツを空に

 投稿者：山中和義  投稿日：2013年 1月15日(火)12時44分47秒
  > No.2958[元記事へ]

GAIさんへのお返事です。

> 50の範囲では、
> (27,35,43) 9 回

つづき

(36,41,46) 9 回

0: (36,41,46)
1: (72,5,46)
2: (67,10,46)
3: (67,20,36)
4: (67,40,16)
5: (67,24,32)
6: (67,48,8)
7: (59,48,16)
8: (59,32,32)
9: (59,0,64)

0: (36,41,46)
1: (72,5,46)
2: (67,10,46)
3: (67,20,36)
4: (67,40,16)
5: (67,24,32)
6: (67,48,8)
7: (59,48,16)
8: (59,32,32)
9: (59,64,0)

0: (36,41,46)
1: (72,5,46)
2: (26,5,92)
3: (52,5,66)
4: (104,5,14)
5: (99,10,14)
6: (99,20,4)
7: (99,16,8)
8: (91,16,16)
9: (91,0,32)

0: (36,41,46)
1: (72,5,46)
2: (26,5,92)
3: (52,5,66)
4: (104,5,14)
5: (99,10,14)
6: (99,20,4)
7: (99,16,8)
8: (91,16,16)
9: (91,32,0)

0: (36,41,46)
1: (72,5,46)
2: (26,5,92)
3: (26,10,87)
4: (16,20,87)
5: (32,4,87)
6: (32,8,83)
7: (32,16,75)
8: (32,32,59)
9: (0,64,59)

0: (36,41,46)
1: (72,5,46)
2: (26,5,92)
3: (26,10,87)
4: (16,20,87)
5: (32,4,87)
6: (32,8,83)
7: (32,16,75)
8: (32,32,59)
9: (64,0,59)

0: (36,41,46)
1: (72,41,10)
2: (31,82,10)
3: (62,51,10)
4: (11,102,10)
5: (22,91,10)
6: (12,91,20)
7: (24,91,8)
8: (16,91,16)
9: (0,91,32)

0: (36,41,46)
1: (72,41,10)
2: (31,82,10)
3: (62,51,10)
4: (11,102,10)
5: (22,91,10)
6: (12,91,20)
7: (24,91,8)
8: (16,91,16)
9: (32,91,0)

0: (36,41,46)
1: (72,41,10)
2: (62,41,20)
3: (62,21,40)
4: (22,21,80)
5: (44,21,58)
6: (88,21,14)
7: (67,42,14)
8: (67,28,28)
9: (67,0,56)

0: (36,41,46)
1: (72,41,10)
2: (62,41,20)
3: (62,21,40)
4: (22,21,80)
5: (44,21,58)
6: (88,21,14)
7: (67,42,14)
8: (67,28,28)
9: (67,56,0)

0: (36,41,46)
1: (72,41,10)
2: (72,31,20)
3: (52,31,40)
4: (12,31,80)
5: (12,62,49)
6: (24,50,49)
7: (48,50,25)
8: (23,50,50)
9: (23,0,100)

0: (36,41,46)
1: (72,41,10)
2: (72,31,20)
3: (52,31,40)
4: (12,31,80)
5: (12,62,49)
6: (24,50,49)
7: (48,50,25)
8: (23,50,50)
9: (23,100,0)

0: (36,41,46)
1: (72,41,10)
2: (72,31,20)
3: (52,31,40)
4: (52,62,9)
5: (52,53,18)
6: (34,53,36)
7: (34,17,72)
8: (34,34,55)
9: (0,68,55)

0: (36,41,46)
1: (72,41,10)
2: (72,31,20)
3: (52,31,40)
4: (52,62,9)
5: (52,53,18)
6: (34,53,36)
7: (34,17,72)
8: (34,34,55)
9: (68,0,55)

0: (36,41,46)
1: (72,41,10)
2: (72,31,20)
3: (72,11,40)
4: (72,22,29)
5: (72,44,7)
6: (28,88,7)
7: (28,81,14)
8: (28,67,28)
9: (0,67,56)

0: (36,41,46)
1: (72,41,10)
2: (72,31,20)
3: (72,11,40)
4: (72,22,29)
5: (72,44,7)
6: (28,88,7)
7: (28,81,14)
8: (28,67,28)
9: (56,67,0)

0: (36,41,46)
1: (36,82,5)
2: (31,82,10)
3: (62,51,10)
4: (11,102,10)
5: (22,91,10)
6: (12,91,20)
7: (24,91,8)
8: (16,91,16)
9: (0,91,32)

0: (36,41,46)
1: (36,82,5)
2: (31,82,10)
3: (62,51,10)
4: (11,102,10)
5: (22,91,10)
6: (12,91,20)
7: (24,91,8)
8: (16,91,16)
9: (32,91,0)

0: (36,41,46)
1: (36,82,5)
2: (36,77,10)
3: (26,77,20)
4: (6,77,40)
5: (12,71,40)
6: (24,59,40)
7: (48,59,16)
8: (32,59,32)
9: (0,59,64)

0: (36,41,46)
1: (36,82,5)
2: (36,77,10)
3: (26,77,20)
4: (6,77,40)
5: (12,71,40)
6: (24,59,40)
7: (48,59,16)
8: (32,59,32)
9: (64,59,0)

0: (36,41,46)
1: (36,82,5)
2: (36,77,10)
3: (36,67,20)
4: (16,67,40)
5: (32,67,24)
6: (8,67,48)
7: (16,59,48)
8: (32,59,32)
9: (0,59,64)

0: (36,41,46)
1: (36,82,5)
2: (36,77,10)
3: (36,67,20)
4: (16,67,40)
5: (32,67,24)
6: (8,67,48)
7: (16,59,48)
8: (32,59,32)
9: (64,59,0)

 		 

Re: バケツを空に

 投稿者：山中和義  投稿日：2013年 1月16日(水)10時56分23秒
  > No.2959[元記事へ]

次の流れに早く持ち込めれば最少手数になるようです。

●最後の2手
組(x,x,y) → (0,2x,y) となる。（yを使わない）

●最後の3手
・x＜yとして、組(x,2x,y) → (2x,2x,y-x) → (0,4x,y-x) となる。
・組(x,3x,y) → (2x,3x-x,y)=(2x,2x,y) → (0,4x,y) となる。（yを使わない）

●既約
(kx,ky,kz)は、(x,y,z)と同じ

●2のべき乗
a,bを正の整数とする。互いに素で、a+b=2^kを満たすとき、(ax,bx,y)はk回となる。
例 2^4=16のとき、4手
　(x,15x,y) → (2x,14x,y) → (4x,12x,y) → (8x,8x,y) → (0,16x,y)
　(3x,13x,y) → (6x,10x,y) → (12x,4x,y) → (8x,8x,y) → (0,16x,y)
　(5x,11x,y) → (10x,6x,y) → (4x,12x,y) → (8x,8x,y) → (0,16x,y)
　(7x,9x,y) → (14x,2x,y) → (12x,4x,y) → (8x,8x,y) → (0,16x,y)
（考察）
k=1のとき、
　a+b=2^1なので、a=1,b=1
　(x,x,y) → (0,2x,y)
　yを使わず、1（=k）回である。　※最後の2手
k=2のとき、
　a+b=2^2なので、a=1,b=3
　(x,3x,y) → (2x,3x-x,y)=(2x,2x,y) → (0,4x,y)
　yを使わず、2（=k）回である。　※最後の3手のひとつ
k≧3のとき、
　a＜bとすると、(ax,bx,y)=(ax,(2^k-a)x,y) → (2ax,(2^k-a)x-ax,y)=(2ax,2(2^(k-1)-a)x,y)
　(ax,(2^(k-1)-a)x,y)は(k-1)回と仮定すると、k回となる。
　実際は、途中に現れるaxとbxの小さい方を2倍していくことになる。
（終り）
 		 

戻る