Homeに戻る  一覧に戻る 

Archimedes' Cattle Problem


[2001.06.16]Archimedesの家畜の問題


■古来より有名なArchimedesの家畜の問題を紹介する。

賢人であるO strangerがSunという人の家畜---4種類の色(白色、黒色、黄色、ぶち)の牛(雄牛と雌牛)---の総数を求めるという問題である。その問題を要約すると、以下の通りである。

     白色の雄牛の数は、黒色の雄牛の(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(ε)/4657ZZ/4657Z上の2次拡大である。
     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桁の巨大な整数である。


[参考文献]


Last Update: 2020.11.23
H.Nakao

Homeに戻る[Homeに戻る]  一覧に戻る[一覧に戻る]