Archimedes' Cattle Problem
[2001.06.16]Archimedesの家畜の問題
■古来より有名なArchimedesの家畜の問題を紹介する。
賢人であるO strangerがSunという人の家畜---４種類の色(白色、黒色、黄色、ぶち)の牛(雄牛と雌牛)---の総数を求めるという問題である。その問題を要約すると、以下の通りである。
白色の雄牛の数は、黒色の雄牛の(1/2+1/3)と黄色の牛(雄牛と雌牛の合計)の数に等しく、
黒色の雄牛の数は、ぶちの雄牛の(1/4+1/5)と黄色の牛の数に等しく、
ぶちの雄牛の数は、白色の雄牛の(1/6+1/7)と黄色の牛の数に等しく、
白色の雌牛の数は、黒色の牛の(1/3+1/4)の数に等しく、
黒色の雌牛の数は、ぶちの牛の(1/4+1/5)の数に等しく、
ぶちの雌牛の数は、黄色の牛の(1/5+1/6)の数に等しく、
黄色の雌牛の数は、白色の牛の(1/6+1/7)の数に等しく、
白色の雄牛と黒色の雄牛の合計の数は、平方数に等しく、
黄色の雄牛とぶちの雄牛の合計の数は、三角数に等しい。
家畜(牛)は全部で何頭いるか？
ここで、三角数とは、1+2+3+..+n=n(n+1)/2の形の整数である。
参考文献[1]に、この問題の解法が記述されているが、ここでは、[1]の解法に従って、パソコンでその解を具体的に計算してみることにする。
白色の雄牛と雌牛の数をW,wとし、同様に、黒色,黄色,ぶちの雄牛と雌牛の数をそれぞれ,X,x,Y,y,Z,zとする。
条件は、以下のようになる。
W = (1/2+1/3)X+Y ------------------- (1)
X = (1/4+1/5)Z+Y ------------------- (2)
Z = (1/6+1/7)W+Y ------------------- (3)
w = (1/3+1/4)(X+x) ----------------- (4)
x = (1/4+1/5)(Z+z) ----------------- (5)
y = (1/6+1/7)(W+w) ----------------- (6)
z = (1/5+1/6)(Y+y) ----------------- (7)
W+Xは平方数 -------------------- (8)
Y+Zは三角数 -------------------- (9)
ここで、表記を簡潔にするため、
a1 = 1/2+1/3
a2 = 1/4+1/5
a3 = 1/6+1/7
b1 = 1/3+1/4
b2 = 1/4+1/5
b3 = 1/6+1/7
b4 = 1/5+1/6
とする。
■X,Y,Z,x,y,z,wをWで表す。
(1)に(2)を代入すると、
W = a1a2Z+(a1+1)Y ------- (10)
(10)に(3)を代入すると、
W = a1a2a3W+(a1a2+a1+1)Y
よって、
Y = {(1-a1a2a3)/(a1a2+a1+1)}W = (297/742)W ------- (11)
(2)に(11)を代入すると、
W = a1X+(297/742)W
X = {(1-297/742)/a1}W = (267/371)W ------ (12)
(3)に(11)を代入すると、
Z = a3W+(297/742)W = (790/1113)W ------ (13)
(4)に(5)を代入すると、
w = b1{X+b2(Z+z)}
={b1X+b1b2Z}+b1b2z ------ (14)
(14)に(7)を代入すると、
w = {b1X+b1b2Z}+b1b2b4(Y+y)
= {b1X+b1b2Z+b1b2b4Y}+b1b2b4y ------ (15)
(15)に(6)を代入すると、
w = {b1X+b1b2Z+b1b2b4Y}+b1b2b4b3(W+w)
= {b1X+b1b2Z+b1b2b4Y+b1b2b3b4W}+b1b2b3b4w
よって、(11),(12),(13)より、
w = {b1X+b1b2Z+b1b2b4Y+b1b2b3b4W}/{1-b1b2b3b4}
= (171580/246821)W ------ (16)
(6)に(16)を代入すると、
y = b3{W+(171580/246821)W}
= (1813071/3455494)W ------ (17)
(7)に(17),(11)を代入すると、
z = b4{(297/742)W + (1813071/3455494)W}
= (83710/246821)W ------ (18)
(5)に(18),(13)を代入すると、
x = b2{(790/1113)W+(83710/246821)W}
= (815541/1727747)W ------ (19)
まとめると、
(W,X,Y,Z,w,x,y,z)
= (1,267/371,297/742,790/1113,
171580/246821,815541/1727747,1813071/3455494,83710/246821)W ------ (20)
となる。
■Wの条件を考える。
W,X,Y,Z,w,x,y,zは全て正整数なので、Wは
lcm(1,371,742,1113,246821,1727747,3455494,246821) = 10366482
の倍数となり、ある正整数nに対して、
(W,X,Y,Z,w,x,y,z)
= (10366482,7460514,4149387,7358060,
7206360,4893246,5439213,3515820)n ------ (21)
となる。全家畜数Sは、
S = W+X+Y+Z+w+x+y+z = 50389082n ------ (22)
となる。
■W+Xの条件(8)を考える。
W+X = 17826996n = 22*3*11*29*4657n
が平方数なので、ある正整数mが存在して、
n = 3*11*29*4657m2 ------- (23)
よって、(21)より、
(W,X,Y,Z,w,x,y,z)
= (46200808287018,33249638308986,18492776362863,32793026546940,
32116937723640,21807969217254,24241207098537,15669127269180)m2 ------ (24)
となる。
■Y+Zの条件(9)を考える。
ある正整数qが存在して、
Y+Z = 51285802909803m2 = q(q+1)/2
となる。よって、
q2+q-2*51285802909803m2 = 0
が整数解を持つのは、正整数kが存在して、
1+4*2*51285802909803m2 = k2
となる時に限る。このとき、q = (k-1)/2となる。
4*2*51285802909803m2 = 23*3*7*11*29*353*46572m2
= 2*3*7*11*29*353*(2*4657m)2 = 4729494*(2*4657m)2
なので、
r = 2*4657m ---------- (25)
とおくと、Pell方程式
k2 - 4729494r2 = 1 -------- (26)
ただし、(2*4657)|r -------- (27)
を解けばよい。
■Pell方程式(26)を連分数を使って解く。
sqrt(4729494)を連分数展開する。
sqrt(4729494) = [2174,1,2,1,5,2,25,3,1,1,1,1,1,1,15,1,2,16,1,2,1,1,
8,6,1,21,1,1,3,1,1,1,2,2,6,1,1,5,1,17,1,1,47,3,1,1,
6,1,1,3,47,1,1,17,1,5,1,1,6,2,2,1,1,1,3,1,1,21,1,6,
8,1,1,2,1,16,2,1,15,1,1,1,1,1,1,3,25,2,5,1,2,1,4348,...]
ここで、連分数の循環節は1,2,1,5,2,...,4348の部分である。
4348の直前までの連分数展開を有理数に変換すると、
109931986732829734979866232821433543901088049/50549485234315033074477819735540408986340
となる。つまり、(26)の最小解は、
k = 109931986732829734979866232821433543901088049
r = 50549485234315033074477819735540408986340
である。(26)の基本解は、Q(sqrt(4729494))の単数
ε = 109931986732829734979866232821433543901088049+
50549485234315033074477819735540408986340sqrt(4729494)
で表される。Pell方程式(26)の全ての解(kd,rd)は、
εd = kd+rdsqrt(4729494) -------- (28)
で表される。最小解rは2で割り切れるので、rdも2で割り切れる。よって、(27)より4657で割り切れるrdを求めれば良い。
■(27)を満たす(4657で割り切れる)解rdを探す。
sqrt(4729494 mod 4657) = sqrt(2639)より、
ε≡ 4406+3051sqrt(2639) (mod 4657)
Legendre symbol(2639/4657) = -1なので、2639は有限体Z/4657Z上で平方数ではない。
よって、Q(ε)/4657ZはZ/4657Z上の２次拡大である。
1/εd = kd-rdsqrt(4729494)
から、rd≡0 (mod 4657)は、
εd-1/εd ≡0 (mod 4657)
よって、
ε2d ≡ 1 (mod 4657)
と同値である。これを満たす最小のd>0を求める。
一般に、素数pに対して、Dがmod pで平方数でないならば、
x=a+b*sqrt(D)
から、
xp≡ap+D(p-1)/2bp*sqrt(D)≡a-b*sqrt(D) (mod p)
を得るので、p=4657,D=4729494とすると、(26)より、
εp+1 = (kp+rpsqrt(D))(kp-rpsqrt(D))≡ 1 (mod p)
となる。よって、dは(p+1)/2=2329=17*137を割り切る。d=1,17,137,17*137について、調べると、
ε2*1 ≡ 262+551sqrt(2639) \not\equiv 1 (mod 4657)
ε2*17 ≡ 106+3078sqrt(2639) \not\equiv 1 (mod 4657)
ε2*137 ≡ 3651+4575sqrt(2639) \not\equiv 1(mod 4657)
ε2*2329 ≡ 1 (mod 4657)
つまり、d=2329である。一般解は、正整数tを使って、
d = 2329t
となる。
■(26),(27)を満たす解(kd,rd)=(k2329t,r2329t)を計算する。
ε2329t = k2329t+r2329tsqrt(4729494)
(25)より、
m = r2329t/(2*4567)
m2 = r2329t2/86750596
(22),(23)より、
S = 50389082*3*11*29*4657m2
= 50389082*3*11*29*4657r2329t2/86750596
= (24111175737/9314)r2329t2
となる。
■Sの最小解(t=1のとき)を計算する。
正確な値はここを参照してください。
r2329 = 173139985895177105642941796992613865495547234352140322821270153546171578326612....
....(途中省略)....
...9144450183111866853602847087281920969633659511483388923538402891212883491745860
S = 7760271406486818269530232833213886664232322405923376103150619226903215930614069....
....(途中省略)....
...8835138492561669543896048155005994630144292500354883118973723406626719455081800
何と、r2329は103270桁、Sの最小解は206545桁の巨大な整数である。
[参考文献]
- [1]Ilan Varid, "Archimedes' Cattle Problem".
- [2]Antti Nygr\'en, "A Simple Solution to Archimedes' Cattle Problem", March 12, 2001, ISBN951-42-5932-7, p1-40.
| Last Update: 2020.11.23 |
| H.Nakao |