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

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

【問題１】

(1)Ａ→Ｂ (2)Ｃ→Ｂ (3)Ａ→Ｃ (4)Ｂ→Ｃ
(5)Ｂ→Ｃ (6)Ａ→Ｂ (7)Ｃ→Ｂ (8)Ｃ→Ｂ
(9)Ｃ→Ａ (10)Ｃ→Ａ (11)Ｂ→Ａ (12)Ｂ→Ａ
(13)Ｃ→Ｂ (14)Ａ→Ｃ (15)Ａ→Ｃ (16)Ａ→Ｂ
(17)Ａ→Ｂ (18)Ｃ→Ｂ (19)Ｃ→Ｂ

１９手。

【問題２】

(1)Ａ→Ｃ (2)Ａ→Ｂ (3)Ｃ→Ａ (4)Ｃ→Ａ
(5)Ｃ→Ｂ (6)Ａ→Ｂ (7)Ａ→Ｂ (8)Ａ→Ｃ
(9)Ｂ→Ａ (10)Ｂ→Ａ (11)Ｂ→Ｃ (12)Ｂ→Ｃ
(13)Ａ→Ｃ (14)Ａ→Ｃ (15)Ａ→Ｂ (16)Ｃ→Ａ
(17)Ｃ→Ａ (18)Ｃ→Ｂ (19)Ｃ→Ｂ (20)Ａ→Ｂ
(21)Ａ→Ｂ (22)Ｃ→Ａ (23)Ｃ→Ａ (24)Ｂ→Ｃ
(25)Ｂ→Ｃ (26)Ｂ→Ａ (27)Ｂ→Ａ (28)Ｃ→Ａ
(29)Ｃ→Ａ (30)Ｃ→Ｂ (31)Ａ→Ｂ (32)Ａ→Ｂ
(33)Ａ→Ｃ (34)Ａ→Ｃ (35)Ｂ→Ｃ (36)Ｂ→Ｃ
(37)Ａ→Ｂ (38)Ａ→Ｂ (39)Ｃ→Ａ (40)Ｃ→Ａ
(41)Ｃ→Ｂ (42)Ｃ→Ｂ (43)Ａ→Ｂ (44)Ａ→Ｂ

４４手。

【問題３】

(1)Ａ→Ｂ (2)Ｃ→Ｂ (3)Ａ→Ｃ (4)Ｂ→Ｃ
(5)Ｂ→Ｃ (6)Ａ→Ｂ (7)Ｃ→Ｂ (8)Ｃ→Ｂ
(9)Ｃ→Ａ (10)Ｃ→Ａ (11)Ｂ→Ａ (12)Ｂ→Ａ
(13)Ｃ→Ｂ (14)Ａ→Ｃ (15)Ａ→Ｃ (16)Ａ→Ｂ
(17)Ａ→Ｂ (18)Ｃ→Ｂ (19)Ｃ→Ｂ (20)Ａ→Ｃ
(21)Ｂ→Ｃ (22)Ｂ→Ｃ (23)Ｂ→Ａ (24)Ｂ→Ａ
(25)Ｃ→Ａ (26)Ｃ→Ａ (27)Ｂ→Ｃ (28)Ｂ→Ｃ
(29)Ａ→Ｂ (30)Ａ→Ｂ (31)Ａ→Ｃ (32)Ａ→Ｃ
(33)Ｂ→Ｃ (34)Ｂ→Ｃ (35)Ａ→Ｂ (36)Ｃ→Ｂ
(37)Ｃ→Ｂ (38)Ｃ→Ａ (39)Ｃ→Ａ (40)Ｂ→Ａ
(41)Ｂ→Ａ (42)Ｃ→Ｂ (43)Ｃ→Ｂ (44)Ａ→Ｃ
(45)Ａ→Ｃ (46)Ａ→Ｂ (47)Ａ→Ｂ (48)Ｃ→Ｂ
(49)Ｃ→Ｂ (50)Ｃ→Ａ (51)Ｃ→Ａ (52)Ｂ→Ａ
(53)Ｂ→Ａ (54)Ｂ→Ｃ (55)Ｂ→Ｃ (56)Ａ→Ｃ
(57)Ａ→Ｃ (58)Ｂ→Ａ (59)Ｂ→Ａ (60)Ｃ→Ｂ
(61)Ｃ→Ｂ (62)Ｃ→Ａ (63)Ｃ→Ａ (64)Ｂ→Ａ
(65)Ｂ→Ａ (66)Ｃ→Ｂ (67)Ａ→Ｃ (68)Ａ→Ｃ
(69)Ａ→Ｂ (70)Ａ→Ｂ (71)Ｃ→Ｂ (72)Ｃ→Ｂ
(73)Ａ→Ｃ (74)Ａ→Ｃ (75)Ｂ→Ａ (76)Ｂ→Ａ
(77)Ｂ→Ｃ (78)Ｂ→Ｃ (79)Ａ→Ｃ (80)Ａ→Ｃ
(81)Ａ→Ｂ (82)Ａ→Ｂ (83)Ｃ→Ｂ (84)Ｃ→Ｂ
(85)Ｃ→Ａ (86)Ｃ→Ａ (87)Ｂ→Ａ (88)Ｂ→Ａ
(89)Ｃ→Ｂ (90)Ｃ→Ｂ (91)Ａ→Ｃ (92)Ａ→Ｃ
(93)Ａ→Ｂ (94)Ａ→Ｂ (95)Ｃ→Ｂ (96)Ｃ→Ｂ

９６手

【問題４】

0，2，7，19，44，96，201，413，838，1690，

上記の数列が予想されます。
漸化式は、下記が予想されます。

A(0)=0,A(1)=2
A(n)=3*A(n-1)-2*A(n-2)+3-(-1)n
2

n：偶数 ＋１,奇数 ＋２

一般項を求めることが出来ました。

A(n)=40*2n-18*n-39-(-1)n
12

0　2　7　19　44　96　201　413　838　1690　3395　6807
　2　5　12　25　52　105　212　425　852　1705　3412　
　　3　7　13　27　53　107　213　427　853　1707　　

階差数列の階差数列は数列サイトに掲載されています。
素数とも関係ある面白そうな数列のようです。

ID Number: A048573
Sequence:
2,3,7,13,27,53,107,213,427,853,1707,3413,6827,13653,27307,
54613,109227,218453,436907,873813,1747627,3495253,6990507,
13981013,27962027,55924053,111848107,223696213,447392427,
894784853,1789569707

Name:      a(n) = a(n-1) + 2a(n-2), a(0)=2, a(1)=3.
Program:
 (PARI) a(n)=(5*2n+(-1)n)/3
 (PARI) a(n)=if(n<2,n+2,a(n-1)+2*a(n-2))
See also:  a(n) = 2n+1-A001045(n).
Keywords:  nonn
Offset:    0
Author(s): Michael Somos (somos@grail.cba.csuohio.edu)

【おまけ】

階差数列がベル数、スターリング数、パスカルの三角形等に関係します。
以前「水の流れさん」のＨ．Ｐで取り上げらました。
「迷路」の問題とも考えられると思います。
完成が迷路を抜け出した状態。

したがって、最小手順を問題にしなければ、機械的に出来ます。

２，７，２１，６１，１７５，・・・

Ｎ＝３

(1)Ａ→Ｂ (2)Ｃ→Ｂ (3)Ｃ→Ａ (4)Ｂ→Ａ
(5)Ｂ→Ａ (6)Ｃ→Ｂ (7)Ａ→Ｂ (8)Ａ→Ｂ
(9)Ａ→Ｃ (10)Ａ→Ｃ (11)Ｂ→Ａ (12)Ｂ→Ｃ
(13)Ａ→Ｃ (14)Ａ→Ｂ (15)Ｃ→Ａ (16)Ｃ→Ａ
(17)Ｃ→Ｂ (18)Ｃ→Ｂ (19)Ａ→Ｃ (20)Ａ→Ｂ
(21)Ｃ→Ｂ

Ｎ＝４

(1)Ａ→Ｃ (2)Ａ→Ｂ (3)Ｃ→Ｂ (4)Ｃ→Ａ
(5)Ｂ→Ａ (6)Ｃ→Ｂ (7)Ａ→Ｃ (8)Ａ→Ｂ
(9)Ｃ→Ｂ (10)Ｃ→Ａ (11)Ｂ→Ａ (12)Ｂ→Ｃ
(13)Ａ→Ｃ (14)Ｂ→Ａ (15)Ｂ→Ａ (16)Ｃ→Ａ
(17)Ｃ→Ａ (18)Ｃ→Ｂ (19)Ａ→Ｃ (20)Ａ→Ｃ
(21)Ａ→Ｂ (22)Ａ→Ｂ (23)Ｃ→Ａ (24)Ｃ→Ｂ
(25)Ａ→Ｂ (26)Ａ→Ｃ (27)Ａ→Ｃ (28)Ｂ→Ａ
(29)Ｂ→Ｃ (30)Ａ→Ｃ (31)Ｂ→Ａ (32)Ｂ→Ａ
(33)Ｃ→Ａ (34)Ｃ→Ｂ (35)Ａ→Ｂ (36)Ａ→Ｃ
(37)Ａ→Ｃ (38)Ｂ→Ａ (39)Ｂ→Ｃ (40)Ａ→Ｃ
(41)Ａ→Ｂ (42)Ｃ→Ｂ (43)Ｃ→Ｂ (44)Ｃ→Ａ
(45)Ｃ→Ａ (46)Ｂ→Ｃ (47)Ｂ→Ａ (48)Ｃ→Ａ
(49)Ｃ→Ｂ (50)Ｃ→Ｂ (51)Ａ→Ｃ (52)Ａ→Ｂ
(53)Ｃ→Ｂ (54)Ａ→Ｃ (55)Ａ→Ｃ (56)Ｂ→Ａ
(57)Ｂ→Ａ (58)Ｃ→Ｂ (59)Ｃ→Ｂ (60)Ａ→Ｂ
(61)Ａ→Ｂ

Ｎ＝５

(1)Ａ→Ｃ (2)Ａ→Ｂ (3)Ｃ→Ｂ (4)Ｃ→Ａ 
(5)Ｂ→Ａ (6)Ｃ→Ｂ (7)Ａ→Ｃ (8)Ａ→Ｂ 
(9)Ｃ→Ｂ (10)Ａ→Ｃ (11)Ｂ→Ａ (12)Ｂ→Ｃ 
(13)Ａ→Ｃ (14)Ｂ→Ａ (15)Ｂ→Ａ (16)Ｃ→Ａ 
(17)Ｃ→Ａ (18)Ｃ→Ｂ (19)Ｃ→Ｂ (20)Ａ→Ｃ 
(21)Ａ→Ｂ (22)Ｃ→Ｂ (23)Ａ→Ｃ (24)Ａ→Ｃ 
(25)Ｂ→Ｃ (26)Ｂ→Ａ (27)Ｃ→Ａ (28)Ｃ→Ｂ 
(29)Ｃ→Ｂ (30)Ａ→Ｃ (31)Ａ→Ｂ (32)Ｃ→Ｂ 
(33)Ｃ→Ａ (34)Ｂ→Ａ (35)Ｂ→Ｃ (36)Ａ→Ｃ 
(37)Ｂ→Ａ (38)Ｂ→Ａ (39)Ｃ→Ａ (40)Ｃ→Ｂ 
(41)Ａ→Ｂ (42)Ａ→Ｃ (43)Ａ→Ｃ (44)Ｂ→Ａ 
(45)Ｂ→Ｃ (46)Ａ→Ｃ (47)Ｂ→Ａ (48)Ｂ→Ａ 
(49)Ｃ→Ｂ (50)Ｃ→Ｂ (51)Ｃ→Ａ (52)Ｃ→Ａ 
(53)Ｂ→Ｃ (54)Ｂ→Ａ (55)Ｃ→Ａ (56)Ｃ→Ｂ 
(57)Ａ→Ｂ (58)Ａ→Ｂ (59)Ａ→Ｃ (60)Ａ→Ｃ 
(61)Ｂ→Ａ (62)Ｂ→Ｃ (63)Ａ→Ｃ (64)Ａ→Ｂ 
(65)Ａ→Ｂ (66)Ｃ→Ａ (67)Ｃ→Ｂ (68)Ａ→Ｂ 
(69)Ｃ→Ａ (70)Ｃ→Ａ (71)Ｂ→Ｃ (72)Ｂ→Ｃ 
(73)Ａ→Ｂ (74)Ａ→Ｂ (75)Ｃ→Ｂ (76)Ｃ→Ｂ 
(77)Ａ→Ｃ (78)Ａ→Ｃ (79)Ｂ→Ａ (80)Ｂ→Ｃ 
(81)Ａ→Ｃ (82)Ｂ→Ａ (83)Ｂ→Ａ (84)Ｃ→Ａ 
(85)Ｃ→Ｂ (86)Ａ→Ｂ (87)Ａ→Ｃ (88)Ａ→Ｃ 
(89)Ｂ→Ａ (90)Ｂ→Ｃ (91)Ａ→Ｃ (92)Ｂ→Ａ 
(93)Ｂ→Ａ (94)Ｃ→Ａ (95)Ｃ→Ｂ (96)Ａ→Ｂ 
(97)Ｃ→Ａ (98)Ｃ→Ａ (99)Ｂ→Ａ (100)Ｂ→Ｃ 
(101)Ａ→Ｃ (102)Ａ→Ｂ (103)Ａ→Ｂ (104)Ｃ→Ａ 
(105)Ｃ→Ｂ (106)Ａ→Ｂ (107)Ａ→Ｃ (108)Ａ→Ｃ 
(109)Ｂ→Ａ (110)Ｂ→Ｃ (111)Ａ→Ｃ (112)Ｂ→Ａ 
(113)Ｂ→Ａ (114)Ｃ→Ａ (115)Ｃ→Ｂ (116)Ａ→Ｂ 
(117)Ａ→Ｃ (118)Ａ→Ｃ (119)Ｂ→Ａ (120)Ｂ→Ｃ 
(121)Ａ→Ｃ (122)Ａ→Ｂ (123)Ｃ→Ｂ (124)Ｃ→Ｂ 
(125)Ｃ→Ａ (126)Ｃ→Ａ (127)Ｂ→Ｃ (128)Ｂ→Ａ 
(129)Ｃ→Ａ (130)Ｃ→Ｂ (131)Ｃ→Ｂ (132)Ａ→Ｃ 
(133)Ａ→Ｂ (134)Ｃ→Ｂ (135)Ａ→Ｃ (136)Ａ→Ｃ 
(137)Ｂ→Ｃ (138)Ｂ→Ｃ (139)Ｂ→Ａ (140)Ｂ→Ａ 
(141)Ｃ→Ｂ (142)Ｃ→Ａ (143)Ｂ→Ａ (144)Ｃ→Ｂ 
(145)Ｃ→Ｂ (146)Ａ→Ｂ (147)Ａ→Ｃ (148)Ｂ→Ｃ 
(149)Ｂ→Ａ (150)Ｂ→Ａ (151)Ｃ→Ｂ (152)Ｃ→Ａ 
(153)Ｂ→Ａ (154)Ｃ→Ｂ (155)Ｃ→Ｂ (156)Ａ→Ｂ 
(157)Ａ→Ｂ (158)Ａ→Ｃ (159)Ａ→Ｃ (160)Ｂ→Ａ 
(161)Ｂ→Ｃ (162)Ａ→Ｃ (163)Ａ→Ｂ (164)Ａ→Ｂ 
(165)Ｃ→Ａ (166)Ｃ→Ｂ (167)Ａ→Ｂ (168)Ｃ→Ａ 
(169)Ｃ→Ａ (170)Ｂ→Ｃ (171)Ｂ→Ｃ (172)Ａ→Ｂ 
(173)Ａ→Ｂ (174)Ｃ→Ｂ (175)Ｃ→Ｂ

【おまけ問題予想】

２，７，２１，６１，１７５，４９９(?)，１４１９(?)，

表を作って整理してみました。
手数が同じになる手順は規則性のある方を採用して、次の段に手を渡すようにしました。

　123456計
12　　　　　2
252　　　　7
31443　　　21
4411343　　61
5122331343　175
636581?3313 43 499?

最下段 ２，５，１４，４１，１２２，３６５，

a(n)=3*a(n-1)-1

a(n)=3n+1
2
が予想されます。
これは間違いないと思います。

その上の段が予想出来れば、仮説(?)は完成するのですが、、、。

別の角度からの推理。

変則ハノイの塔の三角形

0 2721 61175499(?) 1419(?)
2514 40114324 920
39 2674210 596
617 48136386
11 3188 250
20 57162
37105
68

２，３，６，１１，２０，３７，６８，

a(1)=2,a(2)=3,a(3)=11
a(n)=a(n-1)+a(n-2)+a(n-3)
a(4)=6+3+2=11
a(5)=11+6+3=20
a(6)=20+11+6=37
a(7)=37+20+11=68

「変則ハノイの塔」の三角形には、トリボナッチ数列が関係しているのではないかと思います。

５，９，１７，３１，５７，１０５，

a(1)=5,a(2)=9,a(3)=17
a(n)=a(n-1)+a(n-2)+a(n-2)
a(4)=17+9+5=31
a(5)=31+17+9=57
a(6)=57+31+17=105

１４，２６，４８，８８，１６２，

a(1)=14,a(2)=26,a(3)=48
a(4)=48+26+14=88
a(5)=88+48+26=162

こじつけの予想ですが、それらしく思えないでしょうか？。

【おまけ問題予想２】

前回の表で、条件を同じにして次の段に手を渡すことを厳守すれば、以下のようになり、この方がスッキリして、数学的帰納法の可能性が出てきます。

2　　　　　
52　　　　　
145　2　　　
4113　52　　
12233　1352　
36581(?)331352

２段目を、
２，５，１３，３３，８１，
とすれば、

a(n)=n*2n-1+1 が予想されます。

トリボナッチの方は修正しなければなりませんが、基本は生かせるのでは、、、。
後は数学的証明が待たれます。

一般項の予想

a(n)=3n+1
2		 +n-1
Σ
k=1		(k*2k-1+1) ，a(1)=2，n≧2

2 ，7 ，21 ，61 ，175 ，499
1421 ，4057 ，11643 ，33631

トリボナッチ数列の規則性はなくなりましたが、この方がスッキリしていると思います。
Basicでのプログラムで確認するには時間的に困難です。
４９９までは正しいと思います。

一般項が整理出来ました。

a(n)=3n+(n-2)*2n+2*n+1
2		 ，a(1)=2，n≧2

掲載されている手順と予想２の手順が異なっているので、
「同じ条件にして次の段に手を渡す」手順を送ります。
急がば回れ的手順が含まれます。

Ｎ＝４
４１　１３　５　２

(1)Ａ→Ｃ (2)Ａ→Ｂ (3)Ｃ→Ｂ (4)Ｃ→Ａ 
(5)Ｂ→Ａ (6)Ｃ→Ｂ (7)Ａ→Ｃ (8)Ａ→Ｂ 
(9)Ｃ→Ｂ (10)Ｃ→Ａ (11)Ｂ→Ａ (12)Ｂ→Ｃ 
(13)Ａ→Ｃ (14)Ｂ→Ａ (15)Ｂ→Ａ (16)Ｃ→Ａ 
(17)Ｃ→Ａ (18)Ｃ→Ｂ (19)Ａ→Ｃ (20)Ａ→Ｃ 
(21)Ａ→Ｂ (22)Ａ→Ｂ (23)Ｃ→Ａ (24)Ｃ→Ｂ 
(25)Ａ→Ｂ (26)Ａ→Ｃ (27)Ａ→Ｃ (28)Ｂ→Ａ 
(29)Ｂ→Ｃ (30)Ａ→Ｃ (31)Ｂ→Ａ (32)Ｂ→Ａ 
(33)Ｃ→Ａ (34)Ｃ→Ｂ (35)Ａ→Ｂ (36)Ａ→Ｃ 
(37)Ａ→Ｃ (38)Ｂ→Ａ (39)Ｂ→Ｃ (40)Ａ→Ｃ 
(41)Ａ→Ｂ (42)Ｃ→Ａ (43)Ｃ→Ａ (44)Ｃ→Ｂ 
(45)Ｃ→Ｂ (46)Ａ→Ｃ (47)Ａ→Ｃ (48)Ｂ→Ａ 
(49)Ｂ→Ａ (50)Ｃ→Ｂ (51)Ｃ→Ａ (52)Ｂ→Ａ 
(53)Ｃ→Ｂ (54)Ｃ→Ｂ (55)Ａ→Ｂ (56)Ａ→Ｃ 
(57)Ｂ→Ｃ (58)Ａ→Ｂ (59)Ａ→Ｂ (60)Ｃ→Ｂ 
(61)Ｃ→Ｂ
Ｎ＝５
１２２　３３　１３　５　２
(1)Ａ→Ｃ (2)Ａ→Ｂ (3)Ｃ→Ｂ (4)Ｃ→Ａ 
(5)Ｂ→Ａ (6)Ｃ→Ｂ (7)Ａ→Ｃ (8)Ａ→Ｂ 
(9)Ｃ→Ｂ (10)Ａ→Ｃ (11)Ｂ→Ａ (12)Ｂ→Ｃ 
(13)Ａ→Ｃ (14)Ｂ→Ａ (15)Ｂ→Ａ (16)Ｃ→Ａ 
(17)Ｃ→Ａ (18)Ｃ→Ｂ (19)Ｃ→Ｂ (20)Ａ→Ｃ 
(21)Ａ→Ｂ (22)Ｃ→Ｂ (23)Ａ→Ｃ (24)Ａ→Ｃ 
(25)Ｂ→Ｃ (26)Ｂ→Ａ (27)Ｃ→Ａ (28)Ｃ→Ｂ 
(29)Ｃ→Ｂ (30)Ａ→Ｃ (31)Ａ→Ｂ (32)Ｃ→Ｂ 
(33)Ｃ→Ａ (34)Ｂ→Ａ (35)Ｂ→Ｃ (36)Ａ→Ｃ 
(37)Ｂ→Ａ (38)Ｂ→Ａ (39)Ｃ→Ａ (40)Ｃ→Ｂ 
(41)Ａ→Ｂ (42)Ａ→Ｃ (43)Ａ→Ｃ (44)Ｂ→Ａ 
(45)Ｂ→Ｃ (46)Ａ→Ｃ (47)Ｂ→Ａ (48)Ｂ→Ａ 
(49)Ｃ→Ｂ (50)Ｃ→Ｂ (51)Ｃ→Ａ (52)Ｃ→Ａ 
(53)Ｂ→Ｃ (54)Ｂ→Ａ (55)Ｃ→Ａ (56)Ｃ→Ｂ 
(57)Ａ→Ｂ (58)Ａ→Ｂ (59)Ａ→Ｃ (60)Ａ→Ｃ 
(61)Ｂ→Ａ (62)Ｂ→Ｃ (63)Ａ→Ｃ (64)Ａ→Ｂ 
(65)Ａ→Ｂ (66)Ｃ→Ａ (67)Ｃ→Ｂ (68)Ａ→Ｂ 
(69)Ｃ→Ａ (70)Ｃ→Ａ (71)Ｂ→Ｃ (72)Ｂ→Ｃ 
(73)Ａ→Ｂ (74)Ａ→Ｂ (75)Ｃ→Ｂ (76)Ｃ→Ｂ 
(77)Ａ→Ｃ (78)Ａ→Ｃ (79)Ｂ→Ａ (80)Ｂ→Ｃ 
(81)Ａ→Ｃ (82)Ｂ→Ａ (83)Ｂ→Ａ (84)Ｃ→Ａ 
(85)Ｃ→Ｂ (86)Ａ→Ｂ (87)Ａ→Ｃ (88)Ａ→Ｃ 
(89)Ｂ→Ａ (90)Ｂ→Ｃ (91)Ａ→Ｃ (92)Ｂ→Ａ 
(93)Ｂ→Ａ (94)Ｃ→Ａ (95)Ｃ→Ｂ (96)Ａ→Ｂ 
(97)Ｃ→Ａ (98)Ｃ→Ａ (99)Ｂ→Ａ (100)Ｂ→Ｃ 
(101)Ａ→Ｃ (102)Ａ→Ｂ (103)Ａ→Ｂ (104)Ｃ→Ａ 
(105)Ｃ→Ｂ (106)Ａ→Ｂ (107)Ａ→Ｃ (108)Ａ→Ｃ 
(109)Ｂ→Ａ (110)Ｂ→Ｃ (111)Ａ→Ｃ (112)Ｂ→Ａ 
(113)Ｂ→Ａ (114)Ｃ→Ａ (115)Ｃ→Ｂ (116)Ａ→Ｂ 
(117)Ａ→Ｃ (118)Ａ→Ｃ (119)Ｂ→Ａ (120)Ｂ→Ｃ 
(121)Ａ→Ｃ (122)Ａ→Ｂ (123)Ｃ→Ｂ (124)Ｃ→Ｂ 
(125)Ｃ→Ａ (126)Ｃ→Ａ (127)Ｂ→Ｃ (128)Ｂ→Ａ 
(129)Ｃ→Ａ (130)Ｃ→Ｂ (131)Ｃ→Ｂ (132)Ａ→Ｃ 
(133)Ａ→Ｂ (134)Ｃ→Ｂ (135)Ａ→Ｃ (136)Ａ→Ｃ 
(137)Ｂ→Ｃ (138)Ｂ→Ｃ (139)Ｂ→Ａ (140)Ｂ→Ａ 
(141)Ｃ→Ｂ (142)Ｃ→Ａ (143)Ｂ→Ａ (144)Ｃ→Ｂ 
(145)Ｃ→Ｂ (146)Ａ→Ｂ (147)Ａ→Ｃ (148)Ｂ→Ｃ 
(149)Ｂ→Ａ (150)Ｂ→Ａ (151)Ｃ→Ｂ (152)Ｃ→Ａ 
(153)Ｂ→Ａ (154)Ｃ→Ｂ (155)Ｃ→Ｂ (156)Ａ→Ｃ 
(157)Ａ→Ｃ (158)Ａ→Ｂ (159)Ａ→Ｂ (160)Ｃ→Ａ 
(161)Ｃ→Ａ (162)Ｂ→Ｃ (163)Ｂ→Ｃ (164)Ａ→Ｂ 
(165)Ａ→Ｃ (166)Ｂ→Ｃ (167)Ａ→Ｂ (168)Ａ→Ｂ 
(169)Ｃ→Ｂ (170)Ｃ→Ａ (171)Ｂ→Ａ (172)Ｃ→Ｂ 
(173)Ｃ→Ｂ (174)Ａ→Ｂ (175)Ａ→Ｂ

◆解答Part２へ
(BasicとＣ++のプログラムがあります。)

◆宮城県　アンパンマン さんからの解答

【問題１】

19手

(1)Ａ→Ｂ (2)Ｃ→Ｂ (3)Ａ→Ｃ (4)Ｂ→Ｃ
(5)Ｂ→Ｃ (6)Ａ→Ｂ (7)Ｃ→Ｂ (8)Ｃ→Ｂ
(9)Ｃ→Ａ (10)Ｃ→Ａ (11)Ｂ→Ａ (12)Ｂ→Ａ
(13)Ｃ→Ｂ (14)Ａ→Ｃ (15)Ａ→Ｃ (16)Ａ→Ｂ
(17)Ａ→Ｂ (18)Ｃ→Ｂ (19)Ｃ→Ｂ

【問題２】

44手

(1)Ａ→Ｃ (2)Ａ→Ｂ (3)Ｃ→Ａ (4)Ｃ→Ａ
(5)Ｃ→Ｂ (6)Ａ→Ｂ (7)Ａ→Ｂ (8)Ａ→Ｃ
(9)Ｂ→Ａ (10)Ｂ→Ａ (11)Ｂ→Ｃ (12)Ｂ→Ｃ
(13)Ａ→Ｃ (14)Ａ→Ｃ (15)Ａ→Ｂ (16)Ｃ→Ａ
(17)Ｃ→Ａ (18)Ｃ→Ｂ (19)Ｃ→Ｂ (20)Ａ→Ｂ
(21)Ａ→Ｂ (22)Ｃ→Ａ (23)Ｃ→Ａ (24)Ｂ→Ｃ
(25)Ｂ→Ｃ (26)Ｂ→Ａ (27)Ｂ→Ａ (28)Ｃ→Ａ
(29)Ｃ→Ａ (30)Ｃ→Ｂ (31)Ａ→Ｂ (32)Ａ→Ｂ
(33)Ａ→Ｃ (34)Ａ→Ｃ (35)Ｂ→Ｃ (36)Ｂ→Ｃ
(37)Ａ→Ｂ (38)Ａ→Ｂ (39)Ｃ→Ａ (40)Ｃ→Ａ
(41)Ｃ→Ｂ (42)Ｃ→Ｂ (43)Ａ→Ｂ (44)Ａ→Ｂ

【問題３】

96手

(1)Ａ→Ｂ (2)Ｃ→Ｂ (3)Ａ→Ｃ (4)Ｂ→Ｃ
(5)Ｂ→Ｃ (6)Ａ→Ｂ (7)Ｃ→Ｂ (8)Ｃ→Ｂ
(9)Ｃ→Ａ (10)Ｃ→Ａ (11)Ｂ→Ａ (12)Ｂ→Ａ
(13)Ｃ→Ｂ (14)Ａ→Ｃ (15)Ａ→Ｃ (16)Ａ→Ｂ
(17)Ａ→Ｂ (18)Ｃ→Ｂ (19)Ｃ→Ｂ (20)Ａ→Ｃ
(21)Ｂ→Ｃ (22)Ｂ→Ｃ (23)Ｂ→Ａ (24)Ｂ→Ａ
(25)Ｃ→Ａ (26)Ｃ→Ａ (27)Ｂ→Ｃ (28)Ｂ→Ｃ
(29)Ａ→Ｂ (30)Ａ→Ｂ (31)Ａ→Ｃ (32)Ａ→Ｃ
(33)Ｂ→Ｃ (34)Ｂ→Ｃ (35)Ａ→Ｂ (36)Ｃ→Ｂ
(37)Ｃ→Ｂ (38)Ｃ→Ａ (39)Ｃ→Ａ (40)Ｂ→Ａ
(41)Ｂ→Ａ (42)Ｃ→Ｂ (43)Ｃ→Ｂ (44)Ａ→Ｃ
(45)Ａ→Ｃ (46)Ａ→Ｂ (47)Ａ→Ｂ (48)Ｃ→Ｂ
(49)Ｃ→Ｂ (50)Ｃ→Ａ (51)Ｃ→Ａ (52)Ｂ→Ａ
(53)Ｂ→Ａ (54)Ｂ→Ｃ (55)Ｂ→Ｃ (56)Ａ→Ｃ
(57)Ａ→Ｃ (58)Ｂ→Ａ (59)Ｂ→Ａ (60)Ｃ→Ｂ
(61)Ｃ→Ｂ (62)Ｃ→Ａ (63)Ｃ→Ａ (64)Ｂ→Ａ
(65)Ｂ→Ａ (66)Ｃ→Ｂ (67)Ａ→Ｃ (68)Ａ→Ｃ
(69)Ａ→Ｂ (70)Ａ→Ｂ (71)Ｃ→Ｂ (72)Ｃ→Ｂ
(73)Ａ→Ｃ (74)Ａ→Ｃ (75)Ｂ→Ａ (76)Ｂ→Ａ
(77)Ｂ→Ｃ (78)Ｂ→Ｃ (79)Ａ→Ｃ (80)Ａ→Ｃ
(81)Ａ→Ｂ (82)Ａ→Ｂ (83)Ｃ→Ｂ (84)Ｃ→Ｂ
(85)Ｃ→Ａ (86)Ｃ→Ａ (87)Ｂ→Ａ (88)Ｂ→Ａ
(89)Ｃ→Ｂ (90)Ｃ→Ｂ (91)Ａ→Ｃ (92)Ａ→Ｃ
(93)Ａ→Ｂ (94)Ａ→Ｂ (95)Ｃ→Ｂ (96)Ｃ→Ｂ

【問題４】

an=最短手数

a0=0，a1=2,
a2=7，a3=19,
a4=44，a5=96

Y=黄色、G=緑 A:
B:Y
C:G/YG/YG/.../YG

bn=最初の状態から上記の状態になる最短手数

an=bn-1+1+2n+1-3
an=bn-1+2n+1-2


bn=an-1+1+2(2n-1-1)
bn=an-1+2n-1

つまり
an=an-2+5*2n-1-3; n≧2


a2n=5(22n-1+22n-3+...+21)-3n+a0
a2n=10(4n-1)/3-3n; n≧0

a2n-1=5(22n-2+22n-4+...+22)-3(n-1)+a1
a2n-1=5(4n-1)/3-3n; n≧1

【おまけ】

an=色交互のときの最短手数

Ｂ１
A:Y/G/Y/G/Y/G/.../Y/G
B:
C:G/Y/G/Y/G/Y/.../G/Y

Ｂ２
A:Y
B:
C:G/YG/YG/YG/YG/.../YG

bn=B1からB2になる2n枚移動の最短手数

Ｃ１
A:
B:GY
C:YG/YG/YG/YG/YG/.../YG

Ｃ２
A:GY/GY/GY/.../GY
B:GY
C:YG

cn=C1からC2になる2n枚移動の最短手数

Ｅ１
A:Y/G/Y/G/Y/G/.../Y/G
B:
C:G/Y/G/Y/G/Y/.../G/Y

Ｅ２
A:Y/G
B:YG/YG/YG/YG/YG/YG/.../YG
C:G/Y

en=E1からE2になる2n枚移動の最短手数

Ｆ１
A:
B:GY
C:GY/GY/GY/GY/.../GY

Ｆ２
A:
B:GY/GY/GY/GY/GY/.../GY
C:

fn=F1からF2になる2n枚移動の最短手数

Ｇ１
A:
B:GY
C:YG/YG/YG/YG/.../YG

Ｇ２
A:
B:GY/GY/GY/GY/.../GY
C:

gn=G1からG2になる2n枚移動の最短手数

Ｈ１
A:
B:GY
C:GY/GY/GY/GY/GY/.../GY

Ｈ２
A:
B:GY/GY/GY/GY/GY/.../GY
C:GY

hn=H1からH2になる2n枚移動の最短手数

Ｋ１
A:
B:GY
C:YG/YG/YG/YG/.../YG

Ｋ２
A:
B:GY/GY/GY/GY/GY/.../GY
C:YG

kn=K1からK2になる2n枚移動の最短手数

Ｐ１
A:GY
B:YG
C:GY/GY/GY/.../GY

Ｐ２
A:GY/GY/GY/GY/.../GY
B:YG
C:

pn=P1からP2になる2n枚移動の最短手数

Ｑ１
A:GY
B:YG
C:GY/GY/GY/.../GY

Ｑ２
A:GY
B:YG/YG/YG/.../YG
C:

qn=Q1からQ2になる2n枚移動の最短手数

Ｒ１
A:GY
B:YG
C:GY/GY/GY/.../GY

Ｒ２
A:GY/GY/GY/.../GY
B:YG
C:GY

rn=R1からR2になる2n枚移動の最短手数 

an=bn-1+1+cn-1+1+gn-1                1)
bn=en-1+1+qn-1                          2)
en=bn-1+1+rn-1+1+rn-1                3)
cn=kn-1+2+rn-1                          4)
fn=hn-1+2+cn-1+2+gn-1                5)
gn=cn-1+2+fn-1                          6)
hn=hn-1+2+rn-1+2+fn-1                7)
kn=cn-1+2+pn-1                          8)
pn=pn-1+2+cn-1+2+qn-1                9) 
qn=pn-1+2+kn-1                         10)
rn=rn-1+2+rn-1+2+rn-1=3rn-1+4    11)

r0=0,r1=3より　rn=5*3n-1-2;   n≧1
4),8)より
pn-1=kn-kn-2-rn-2-4　　12)

9),10)より
pn=pn-1+cn-1+pn-2+6+kn-2　　13)

4),12,13)より

kn+1-kn-1-rn-1-4
=kn-kn-2-rn-2-4+kn-2+2+rn-2+kn-1-kn-3-rn-3-4+6+kn-2

kn+1-kn-2kn-1-kn-2+kn-3
=4+40*3n-4      14)
pn,qn,hn,cn も14)の漸化式を満たします。

x4-x3-2x2-x+1=0の解は

qn=A1*(x1)n+A2*(x2)n+A3*(x3)n+A4*(x4)n+(20/17)3n-4-2; n≧6
cn=B1*(x1)n+B2*(x2)n+B3*(x3)n+B4*(x4)n+(20/17)3n-4-2; n≧6
hn=C1*(x1)n+C2*(x2)n+C3*(x3)n+C4*(x4)n+(20/17)3n-4-2; n≧6
qn,cn,hnの初値よりqn,cn,hnが決まります。

5),6)より

gn=gn-2+cn-1+cn-2+hn-2+6
g2n=n
Σ
i=4		 [c2i-1+c2i-2+h2i-2]+6(n-3)+g6; n≧4

g2n-1=n-1
Σ
i=3		 [c2i+c2i-1+h2i-1]+6(n-3)+g5; n≧4

2),3)より

bn=bn-2+qn-1+2rn-2+3
bn=bn-2+qn-1+10*3n-3-1

b2n=n
Σ
i=4		 [q2i-1+10*32i-3]-n+4+b6
b2n=n
Σ
i=4		 [q2i-1]+5*35* 32n-4-1
4 		-n+3+b6; n≧4

b2n-1=n
Σ
i=4		 [q2i-2+10*32i-4]-n+3+b5
b2n-1=n
Σ
i=4		 [q2i-1]+5*34* 32n-4-1
4 		-n+3+b5; n≧4

1)よりanが得られます。

anの式は次のように表せます。 

an=K1*(x1)n+K2*(x2)n+K3*(x3)n+K4*(x4)n+K5*(3)n+K6*(-1)n+K7*n+K8。
K1,K2,...,K8はanの初値
(例えばa7,a8,a9,a10,a11,a12,a13,a14) から決められます。

◆愛知県　Y.M.Ojisan さんからの解答

チェックに用いたエクセルのマクロ move.xls だそうです。
実際に動きを確認できるので試してみてください。

【問題解答】

下図のように
中央に集める最小手数をＣN、
サイドに集める最小手数をＳN、
普通のハノイの塔の最小手数をＨNとするとき、必然の手順は下図である。即ち

ＳN＝ＣN-1＋１＋２×ＨN-1
ＣN＝ＳN-1＋２＋４×ＨN-1

以上の漸化式にＨN＝２N−１　を代入して解くと

ＣN＝３Ｎ
２		 ＋１０(２N−１)
３		　Ｎ：偶数
ＣN＝３Ｎ
２		 ＋１０(２N−１)
３		＋１
６		　Ｎ：奇数

【おまけ解答】

色なしの上記手順において、２段積みハノイの塔の移動を除いては、色が重なる手順はない。
よって、色付２段積みハノイの手数を考える。
なお、上記手順表では２段積みのハノイの塔移動は色順を逆転（色が変わる）させる方法のみで示しているが、全部平行移動でも可能である。
しかし下図に示すように逆転移動の方が手順が少なく、得策ではない。

サイドに寄せる手順の場合、どちらのサイドに寄せるか選択の余地があり、常に逆転移動可能である。
一方中央に寄せる場合は、ＳＴＥＰ２移動の移動元にまだ輪が残っている場合は、ＳＴＥＰ３では平行移動のみ可能であり，
逆に残りが無い場合の最後のｎ＝Ｎのときのみ逆転移動可能である。即ち

Ｓn＝Ｃn-1＋１＋ＨＡn-1

Ｃn＝Ｓn-1＋２＋２×ＨＡn-1　　：ｎ＝Ｎ
Ｃn＝Ｓn-1＋２＋２×ＨＣn-1　　：ｎ＜Ｎ

従っておまけの手順数は多くてもＮ＞１に対し以下である。
なお、Ｃ1＝２。

ＣN=115×3N-2＋12N+21
16		 　Ｎ：偶数
ＣN=115×3N-2-12N+21
16		+3
8		　Ｎ：奇数

計算すると下表である。
奇数の式で切り捨てすれば偶数の値なのでガウス記号を使った。

最小かどうかは　？。
Ｃｎ'はn＜NにおけるＣｎである。

　◆　解答Part２へ

　◆　問題へもどる

　◆　今週の問題へ

数学の部屋へもどる