そろばんで4乗根を計算する方法
注意: 非現実的
備忘録: (a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4
手順
(平方根や立方根にはないが4乗根には現れる操作は太字で強調した。)
0. 与えられた値をそろばんに入れる。
1. 初根を求め、その4乗を与えられた値から引く。
2. 初根の2倍をそろばんの左側に置く。
(3.以下は必要な桁数分だけ繰り返す)
3. 左側に置かれている数で余りを2回割る。
3a. 10^nの位を求めたいときに割る桁数は、1回目は余りの10^(4n+1)の位まで、2回目は10^(4n+2)の位まで割る。
4. 2回割った商を既根で割り、その商(1桁)を次根とする。
5. (既根+次根)×次根を2回割った商から引く。
5a. 引けない場合は仮商修正と同様の方法で次根を1小さくする。
6. 次根の2乗の半分を2回割った商から引く。
6a. 引けない場合は(既根+次根)+(次根+1)を足すことで仮商修正を行う。
7. 2回割った商の残りを左側に置かれている数で掛けてその結果を1回割った商に足す(掛け戻し)。
8. 次根の3乗の2倍を1回割った商(に掛け戻し分を足したもの)から引く。
8a. 引けない場合は2回割った商として(既根+次根)+(次根×2+1)+1/2を追加し、これで再び掛け戻しを行う。
9. 1回割った商の残りを左側に置かれている数で掛けてその結果を余りに足す(掛け戻し)。
10. 次根の4乗を余りから引く。引けない場合は次のステップを実行する。
10a. 2回割った商として(既根+次根)+(次根×2+1)+1/2を追加し、これで再び1回割った商への掛け戻しを行う。
10b. 1回割った商に(次根)×(次根+1)×6+2を足し、これで再び余りへの掛け戻しを行う。
11. 次根の2倍を左側に置かれている数に追加する。
注意: 5,6の手順は2回割った商の10の位を一の位とみなして計算する。
注意: この手順では小数が出てくるため、そろばん上に値を入れることが不可能になる可能性がある。しかし、小数が生じるのは2回割った商のみ、それも小数以下は.0か.5しかないので、小数が生じたかどうかという情報を覚えておけばよい。また、覚えておかなくてもそろばんのどこかに1bit分の情報を持たせることは可能であろう。
具体例.
(1) 1677万7216の4乗根
1. 1296=6^4<=1677<7^4=2401であるから、初根に6が立ち、余りは381万7216となる。
2. 左側に12を置く。
3. 2回割った後の値は2650余り10余り1となる。
4. 265÷6の最初の桁は4であるから、次根を4とする。
5. 265から64×4を引く。残りは9である。
6. 16の半分の8を引く。残りは1である。
7. 掛け戻す。(1*10+0)*12+10=130が得られる。
8. 4^3*2=128を引く。残りは2である。
9. 掛け戻す。2*12+1=25が得られる。
10. 4^4=256を引く。余りがなくなったので終了する。
よって、1677万7216の4乗根は64である。
(2) 70万7281の4乗根
1. 16=2^4<=70<3^4=81であるから、初根に2が立ち、余りは54万7281となる。
2. 左側に4を置く。
3. 2回割った後の値は3420余り2余り0となる。
4. 342÷2の最初の桁は1であるが、これは100の位に立つ1であるから、次根を9とする。
5. 342から29×9を引く。残りは81である。
6. 81の半分の40.5を引く。残りは40.5である。
7. 掛け戻す。(40.5*10+0)*4+2=1622が得られる。
8. 9^3*2=1458を引く。残りは164である。
9. 掛け戻す。164*4+0=656が得られる。
10. 9^4=6561を引く。余りがなくなったので終了する。
よって、70万7281の4乗根は29である。
(3) 1055万6001の4乗根
1. 625=5^4<=1055<6^4=1296であるから、初根に5が立ち、余りは430万6001となる。
2. 左側に10を置く。
3. 2回割った後の値は4306余り0余り0となる。
4. 430÷5の最初の桁は8であるから、次根を8とする。
5. 430から58×8を引く。5×8は引けるが8×8は引けないので、修正する。
5a. 次根を7にして5を戻す。残りは31である。
6. 49の半分の24.5を引く。残りは6.5である。
7. 掛け戻す。(6.5*10+6)*10+0=710が得られる。
8. 7^3*2=686を引く。残りは24である。
9. 掛け戻す。24*10+0=240が得られる。
10. 7^4=2401を引く。余りがなくなったので終了する。
よって、1055万6001の4乗根は57である。
階乗基表現
元ネタ: https
1!=1
— 綿谷雫 (@kapt0nH) February 5, 2019
2!=10
3!=100
4!=1000
……
みたいな感じの表記法があるとして、10進法で表すのとこの表記法で表すのが同じになるような数が1以外にあるかな
://twitt
https://twitter.com/kapt0nH/status/1092823926416142336
er.com/kapt0nH/status/1092823926416142336
https://twitter.com/kapt0nH/status/1092823926416142336
問題: 階乗基表現と十進表記が等しくなるような自然数を全て求めよ。
解答:
1が条件を満たすことは自明である。
ある数nに対して十進表記が階乗基表現よりも「長大である」ことを次のように定義する:
(nの十進表記の桁数がnの階乗基表現の桁数より大きい)
または
(
(nの十進表記の桁数がnの階乗基表現の桁数と等しい)
かつ
(ある自然数mが存在して、
(nの十進表記と階乗基表現の上m-1桁が等しい)かつ(nの十進表記の上からm桁目は階乗基表現の上からm桁目より大きい)
)
)
また、階乗基表現が十進表記よりも「長大である」とは、十進表記が階乗基表現よりも長大でないかつ階乗基表現が十進表記と等しくないことである。
1以外の数に対して上限と下限を調べる。
n!~(n+1)!が十進表記でm~m+k桁の範囲を取るとすると、m+k<nであれば、階乗基表現が十進表記よりも長大であるため、この範囲には条件を満たす範囲は存在しない。
また、m>nであれば、十進表記が階乗基表現よりも長大であるため、この範囲には条件を満たす範囲は存在しない。
実際に計算すると、2!以上18!以下および25!以上では条件を満たす数が存在しないことがわかる。
例えば、n=17のとき、17!=355687428096000(15桁), 18!=6402373705728000(16桁)であるから、階乗基表現が長大である。
よって、18!<x<25!の範囲のxを調べればよい。
(a) 18!<x<19!
十進表記が18桁になるためには、10^17/18!>15であることからxは15*18!以上である必要があるが、このとき階乗基表現は最上位桁が16以上になるため、階乗基表現の方が長大である。
(b) 19!<=x<20!
十進表記が19桁になるためには、10^18/19!>8.2であることからxは8*18!以上である必要がある。したがって、十進表記と階乗基表現が一致するためには、十進表記の最上位桁が8である必要があるが、20!=2432902008176640000であるため、条件を満たすxは存在しない。
(c) 20!<=x<21!
十進表記が20桁になるためには、10^19/20!>4.1であることからxは4*19!以上である必要がある。したがって、十進表記と階乗基表現が一致するためには、十進表記の最上位桁が4以上である必要があるが、21!=51090942171709440000であるため、最上位桁が4または5で確定する。
このとき、階乗基表現の最上位が5であることから、4*20!<=x<6*20!である。しかし、
4*20!=9731608032706560000
6*20!=14597412049059840000
より、xの10^19の位を5にすることは出来ない。したがって、条件を満たすxは存在しない。
(d) 21!<=x<22!
十進表記が21桁になるためには、10^20/21!>1.9であることからこの議論では最上位桁を制限することはできない。
(c)と同様の議論により最上位桁を考えると、最上位桁をyとした場合に
y*10^20<=y*19!<(y+1)*10^20
が成り立つ必要がある。
これが成り立つyはy=1のみであるから、xの最上位桁は1となる。
また、2*21!=102181884343418880000であるから、上から2桁目は0で確定する。
しかし、1*21!+1*20!=53523844179886080000<10^20であるから、条件を満たすxは存在しない。
(e)22!<=x<23!
理論だけで計算するのは面倒なのでバックトラッキングを使用したプログラムを書き、全区間の探索を行った。その結果、解が存在しないことがわかった。
(f)23!<=x<24!
4*23!>10^23であるから、xの最上位桁は1,2,3のどれかであるが、2*23!>5*10^22であるため、xの最上位桁は1でなければならない。
しかし、このとき23!>2.5*10^22であるため、条件を満たすxは存在しない。
(g)24!<=x<25!
2*24!>10^24であるから、xの最上位桁は1と定まるが、24!>6*10^23であるため、条件を満たすxは存在しない。
以上より、条件を満たすxはx=1のみであることがわかった。
n乗連分数展開
整数aに対しα=a^(1/n)と定め、このαに対し次の操作を繰り返す:
αの整数部分を取り出しこれをbとする
1/(α-b)^nを新しいαにする
ここでは、a=1~100, n=2~5としたときに、bに面白いパターンがあるかどうかを調べる。
n=2
a=3, 45のときはゼロ除算が生じ停止する。
30ステップ目までで停止しない中で最大のbを出力するものは
a=40 (b=6, 9, 4, 86, 2, 2, 4286474, 25, 5, 2, 16, 1, 3, 3, 1, 2279, 3, 277, 2, 1, 13, 1, 22, 38, 15, 1, 6, 2, 10, 1102)
であり、
\( 6+\sqrt{\frac{1}{9+\sqrt{\frac{1}{4+\sqrt{\frac{1}{86+\sqrt{\frac{1}{2+\sqrt{\frac{1}{2}}}}}}}}}} = 6.32455532034286\cdots, \\ \left( 6+\sqrt{\frac{1}{9+\sqrt{\frac{1}{4+\sqrt{\frac{1}{86+\sqrt{\frac{1}{2+\sqrt{\frac{1}{2}}}}}}}}}} \right)^2 = 40.0000000000772 \cdots \)
が成り立つ。
これはほとんど整数とみなしてよいだろう。
n=3
特に大きな性質は見られないが、bの値が全体的にn=2のときより大きい。
n=3
特に大きな性質は見られないが、bの値が全体的にn=m=2のときより大きい。
n=4
ほとんど整数が確認された:
\( \left( 2+\sqrt[4]{\frac{1}{16829+\sqrt[4]{\frac{1}{36+\sqrt[4]{\frac{1}{509}}}}}} \right)^4 = 18.9999999999861 \cdots \)
n=5
ほとんど整数が確認された:
\( \left( 1+\sqrt[5]{\frac{1}{11+\sqrt[5]{\frac{1}{255+\sqrt[5]{\frac{1}{1418+\sqrt[5]{\frac{1}{1750+\sqrt[5]{\frac{1}{2}}}}}}}}}} \right)^4 = 10.99999999999999148 \cdots \)
センター試験数学C
この記事では0を自然数に含めることとします。
ネタバレ注意: この記事にはセンター試験の解法が含まれます。
問題(2019年数学ⅠA第3問を参考に一部改変): 赤い袋に2個の赤球と1個の白球、白い袋に1個の赤球と1個の白球が入っている。
0回目の操作では赤い袋から球を1個取り出して、球の色を確認してその袋に戻す。また、任意の自然数aに対し、a+1回目の操作ではa回目に取り出した球の色と同じ色の袋から球を1個取り出して、球の色を確認してその袋に戻す。
このとき、次の問いに答えよ。ただし、nは自然数とする。
(1) n回目の操作で白球が取り出される確率をpとするとき、n+1回目の操作で白球が取り出される確率をpを用いて表せ。
(2) n回目の操作で白球が取り出される確率をnを用いて表せ。
解答:
(1)
n+1回目に白い袋から白球を取り出す確率は\( p\cdot\frac{1}{2} \)、
n+1回目に赤い袋から白球を取り出す確率は\( (1-p)\cdot\frac{1}{3} \)であるから、
求める確率はこれらを足し合わせて
\( p\cdot\frac{1}{2}+(1-p)\cdot\frac{1}{3}=\frac{1}{6}p+\frac{1}{3} \)
(2)
n回目の操作で白球が取り出される確率を\(a_n\)とし、n回目の操作で赤球が取り出される確率を\(b_n\)とする。
このとき、(1)と同様にして
\( a_{n+1} = \frac{1}{2} a_n + \frac{1}{3} b_n \)
\( b_{n+1} = \frac{1}{2} a_n + \frac{2}{3} b_n \)
であるから、
\( \begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} \frac{1}{2} & \frac{1}{3} \\ \frac{1}{2} & \frac{2}{3} \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix} \)
となる。
そこで、
\( A = \begin{pmatrix} \frac{1}{2} & \frac{1}{3} \\ \frac{1}{2} & \frac{2}{3} \end{pmatrix} \)
とすると、
\( \begin{pmatrix} a_n \\ b_n \end{pmatrix} = A^n \begin{pmatrix} a_0 \\ b_0\end{pmatrix} \)
となる。
そのため、Aの固有値を以下で求める。
\( \begin{eqnarray} |A-\lambda E| &=& \left(\frac{1}{2}-\lambda\right)\left(\frac{2}{3}-\lambda\right)-\frac{1}{3}\cdot\frac{1}{2} \\ &=& \lambda^2-\frac{7}{6}\lambda+\frac{1}{6} \\ &=& \left(\lambda-1\right)\left(\lambda-\frac{1}{6}\right) \end{eqnarray} \)
であるから、Aの固有値は1と1/6である。
ここでは求め方を省略するが、1と1/6に対応する固有ベクトルの1つはそれぞれ(2,3),(-1,1)であるから、
\( P = \begin{pmatrix} 2 & -1 \\ 3 & 1 \end{pmatrix}, B=P^{-1}AP \)
とすると、
\( B = \begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{6} \end{pmatrix} \)
であるから、
\( B^n = \begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{6^n} \end{pmatrix} \)
である。
したがって、
\( \begin{eqnarray} A^n&=& PB^nP^{-1} \\ &=& \begin{pmatrix} 2 & -1 \\ 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \frac{1}{6^n} \end{pmatrix} \begin{pmatrix} \frac{1}{5} & \frac{1}{5} \\ -\frac{3}{5} & \frac{2}{5} \end{pmatrix} &=& \begin{pmatrix} 2 & -\frac{1}{6^n} \\ 3 & \frac{1}{6^n} \end{pmatrix} \begin{pmatrix} \frac{1}{5} & \frac{1}{5} \\ -\frac{3}{5} & \frac{2}{5} \end{pmatrix} \\ &=& \begin{pmatrix} \frac{2}{5}+\frac{3}{5}\cdot\frac{1}{6^n} & \frac{2}{5}-\frac{2}{5}\cdot\frac{1}{6^n} \\ \frac{3}{5}-\frac{3}{5}\cdot\frac{1}{6^n} & \frac{3}{5}+\frac{2}{5}\cdot\frac{1}{6^n} \end{pmatrix} \end{eqnarray} \)
であるから、
\( \begin{eqnarray} \begin{pmatrix} a_n \\ b_n \end{pmatrix} &=& \begin{pmatrix} \frac{2}{5}+\frac{3}{5}\cdot\frac{1}{6^n} & \frac{2}{5}-\frac{2}{5}\cdot\frac{1}{6^n} \\ \frac{3}{5}-\frac{3}{5}\cdot\frac{1}{6^n} & \frac{3}{5}+\frac{2}{5}\cdot\frac{1}{6^n} \end{pmatrix} \begin{pmatrix} \frac{1}{3} \\ \frac{2}{3} \end{pmatrix} \\ &=& \begin{pmatrix} \frac{2}{5}-\frac{1}{15}\cdot\frac{1}{6^n} \\ \frac{3}{5}+\frac{1}{15}\cdot\frac{1}{6^n} \end{pmatrix} \end{eqnarray}\)
である。したがって、求める確率は
\( \frac{2}{5}-\frac{1}{15}\cdot\frac{1}{6^n} \)
である。
センター試験にはポン酢が合う(2019)
ネタバレ注意: この記事にはセンター試験の解法が含まれます。
今日はセンター試験がありました。
ところで、グレブナー基底にはポン酢が合います。
というわけで、この記事では2019年度大学入試センター試験数学ⅠA第5問をグレブナー基底で解きます。
問題(一部改変):
(1)AB=4, BC=7, CA=5の△ABCの内接円をΓとする。ΓとABとの接点をD、ΓとACとの接点をEとするとき、DEの長さを求めよ。
(2)BEとCDの交点をPとし、直線CPとΓとの交点でDとは異なる点をFとする。cos∠DFEを求めよ。
(実際のセンター試験問題にはこれ以外にも求めるものがあるが、この記事と同様の方法で解けるのでここでは省略する。)
図(Geogebraにより作成):
解答(実践向きではない。コンピューターの使用を推奨する):
(1)
グレブナー基底を使用するため、全てを座標で表す。
まず、A(0,a), B(b-7,0), C(b,0)とする。
このとき、
a^2+(b-7)^2-16=0, a^2+b^2-25=0
が成り立つ。
ΓとBCの接点をHとすると、AD=AE, BD=BH, CH=HEであるから、
AD=x, BH=y, CE=zとして、
x+y-4=0, y+z-7=0, z+x-5=0
が成り立つ。
これくらいはコンピューターを使わなくても解けるのでこの場で解いてしまう。
3式足し合わせると2x+2y+2z-16=0すなわちx+y+z-8=0であるから、
x=1, y=3, z=4となる。
よって、DはBAを3:1に内分する点、EはACを1:4に内分する点であるから、D(dx,dy), E(ex,ey)とすると、
dx=(b-7)*1/4
dy=a*3/4
ex=b*1/5
ey=a*4/5
となる。したがって、
b-7-4*dx=0, a*3-4*dy=0, b-5*ex=0, a*4-5*ey=0
が成り立つ。
求める長さをlとすると、
l^2-(dx-ex)^2-(dy-ey)^2=0
が成り立つので、
{a^2+(b-7)^2-16, a^2+b^2-25, b-7-4*dx, a*3-4*dy, b-5*ex, a*4-5*ey, l^2-(dx-ex)^2-(dy-ey)^2}のグレブナー基底を求めればよい。
上の集合に対するa>b>dx>dy>ex>ey>lの順序におけるgrevlexでのグレブナー基底は、
[1225*ey^2-6144,-5*l^2+12,4*a-5*ey,7*b-29,7*dx+5,16*dy-15*ey,35*ex-29]
であるから、-5*l^2+12=0であることがわかり、l>0からl=2√15/5がわかる。
(2)
FはCD上にあるので、F(fx,fy)の座標は実数tを用いて
(b*(1-t)+dx*t, dy*t)
と表せる。
よって、
fx-b*(1-t)-dx*t=0, fy-dy*t=0
が成り立つ。
ここで、△ABCの内心をI(ix,iy)とすると、内心の位置ベクトルの公式から、
ix=(5*(b-7)+4*b)/16, iy=7*a/16であるから、
9*b-35-16*ix=0, 7*a-iy*16=0
が成り立つ。
FはΓ上にあるのでFI=EIが成り立つ。すなわち、
(ix-fx)^2+(iy-fy)^2-(ix-ex)^2-(iy-ey)^2=0
である。
さらに、DがFと異なるということを示すために、
z*(dx-fx)-1=0
という式を追加する。これは実数zを用いてdxとfxの差が1/zと表せる、すなわちdxとfxが等しくないことを意味する。
cos∠DFEは余弦定理から求めることができる。DE=lと置いたので、EF=m, FD=nとすると、cos∠DFE=(m^2+n^2-l^2)/(2*m*n)と書ける。そこで、cos∠DFE=sと置くことにすると、
m^2-(fx-ex)^2-(fy-ey)^2=0
n^2-(dx-fx)^2-(dy-fy)^2=0
2*s*m*n-(m^2+n^2-l^2)=0
となる。
よって、
{a^2+(b-7)^2-16, a^2+b^2-25, b-7-4*dx, a*3-4*dy, b-5*ex, a*4-5*ey, l^2-(dx-ex)^2-(dy-ey)^2,fx-b*(1-t)-dx*t, fy-dy*t, 9*b-35-16*ix, 7*a-iy*16, (ix-fx)^2+(iy-fy)^2-(ix-ex)^2-(iy-ey)^2, z*(dx-fx)-1, m^2-(fx-ex)^2-(fy-ey)^2, n^2-(dx-fx)^2-(dy-fy)^2, 2*s*m*n-(m^2+n^2-l^2)}のグレブナー基底を求めればよい。
上の集合に対するa>b>dx>dy>ex>ey>l>fx>fy>t>ix>iy>z>m>n>sの順序におけるgrevlexでのグレブナー基底は、
[5*l^2-12,-2*iy^2+3,35*m^2-48,-24*s+7*n*m,-7*n^2+36,5*m*s-2*n,-2*n*s+3*m,-5*s^2+3,7*a-16*iy,-7*b+29,-7*dx-5, 7*dy-12*iy,35*ex-29,-35*ey+64*iy,-49*fx+67,-49*fy+48*iy,-7*t+4,-7*ix+1,-102*z-49]
であるから、-5*s^2+3=0であることがわかり、s>0からs=√15/5がわかる。
使用したRisa/Asirのコマンド:
(1)
nd_gr([a^2+(b-7)^2-16, a^2+b^2-25, b-7-4*dx, a*3-4*dy, b-5*ex, a*4-5*ey, l^2-(dx-ex)^2-(dy-ey)^2],[a,b,dx,dy,ex,ey,l],0,0);
(2)
nd_gr([a^2+(b-7)^2-16, a^2+b^2-25, b-7-4*dx, a*3-4*dy, b-5*ex, a*4-5*ey, l^2-(dx-ex)^2-(dy-ey)^2,fx-b*(1-t)-dx*t, fy-dy*t, 9*b-35-16*ix, 7*a-iy*16, (ix-fx)^2+(iy-fy)^2-(ix-ex)^2-(iy-ey)^2, z*(dx-fx)-1, m^2-(fx-ex)^2-(fy-ey)^2, n^2-(dx-fx)^2-(dy-fy)^2, 2*s*m*n-(m^2+n^2-l^2)],[a,b,dx,dy,ex,ey,l,fx,fy,t,ix,iy,z,m,n,s],0,0);
ビンゴ行列の行列式の最大値(理論編)
前回の記事では、遺伝的アルゴリズムによりビンゴ行列の行列式の最大値を求めようとしましたが、ここでは数学的な観点から最大値を探してみようと思います。
以下、「行列式が最大になるようなビンゴ行列」を「最大ビンゴ行列」と呼ぶことにし、最大便ご行列が具体的に何であるか求める問題を最大ビンゴ行列問題と呼ぶことにします。
定理1. 最大ビンゴ行列の第j列の要素は、0,15j,15j-1,...,15j-4のいずれかである。
証明.
行列式は行列の1つの成分に関して見ると1次式である。最大ビンゴ行列をAとし、その第(i,j)成分をa_ijと書くことにする。
このとき、a_ijが0,15j,15j-1,...,15j-4のどれでもない場合を考えると、
もしAの行列式のa_ijの係数が負であれば、a_ijの値を最小すなわち0にし、
もしAの行列式のa_ijの係数が正であれば、a_ijの値を最大すなわち15j,15j-1,...,15j-4のうち第i列に現れていないものにすることで、
Aの行列式の値を更に大きくできるので、値を変える前のAは最大ビンゴ行列ではなかったことになる。
したがって、最大ビンゴ行列の第i列の要素は、0,15j,15j-1,...,15j-4のいずれかである。
定理2. 最大ビンゴ行列の第1列の要素は、0を4個以上持たない。
第1列が0を5個持たないことは自明なので、0を4個持たないことを証明する。第1列の非零の値の位置で場合分けする。以下、Aを第1列に0を4個持つ正則ビンゴ行列とする。
(i) 第1列の非零の要素が第3行以外にある場合
第3行以外の行を偶数回入れ替えることで、非零の要素を第1行に置くことができ、かつAの行列式を正にできる。
また、\( A = \left( \begin{array}{cc} a_{11} & S \\ O & T \end{array} \right) \)とすると、
\( |A|=a_{11}|T| \)であり、|A|>0より|T|>0であるから、\( a_{11}\neq 15 \)であれば\(a_{11}\neq 15 \)とすることでAの行列式を大きくできる。
また、Tに対し定理1と同様の議論を行うことで、i列目の値が0,15i,15i-1,....,15i-3であることがわかる(2<=i<=5)。
このような条件のもとで行列を全探索すると、以下の行列が最大となる。
Matrix[[15, 0, 0, 0, 0], [0, 30, 0, 0, 73], [0, 0, 0, 60, 75], [0, 0, 45, 0, 74], [0, 29, 44, 59, 0]](行列式は263256750)
この行列式は前回の記事で求めた行列の行列式よりも小さいので、これは最大ビンゴ行列とならない。
(ii) 第1列の非零の要素が第3行にある場合
(i)と同様の方法で全探索すると、以下の行列が最大となる。なお、これは(i)で求めた行列と本質的に同じである。
Matrix[[0, 30, 0, 0, 73], [0, 29, 44, 59, 0], [15, 0, 0, 0, 0], [0, 0, 0, 60, 75], [0, 0, 45, 0, 74]](行列式は263256750)
この行列式は前回の記事で求めた行列の行列式よりも小さいので、これは最大ビンゴ行列とならない。
以上(i)(ii)より、最大ビンゴ行列の第1列の要素は、0を4個以上持たないことが示された。
定理3. 最大ビンゴ行列の各行と各列には、少なくとも1個の0が存在する。
背理法で証明するために、0が存在しないような行または列をもつ最大ビンゴ行列を考え、これをAとする。
Aが0が存在しないような列を持たない場合、Aの転置を改めてAと置き直すことで、Aは0が存在しないような列を持つと仮定できる。このとき、Aの第j列に0が存在しないとする。
Aの行列式はa_1j,a_2j,...,a_5jのそれぞれについての一次式で、かつそれぞれの係数は正であるから(∵定理1の証明の議論と∀i∈[1,5], a_ij>0より)、a_1j,a_2j,...,a_5jのどれをどれだけ増加させてもAの行列式は増加する。
(以下工事中)
ビンゴ行列の行列式の最大値
この記事は、以下の記事に対する第三者によるさらに深い考察です。
私は、ビンゴ行列の行列式の最大値を、遺伝的アルゴリズムで求めてみました。
条件は以下のようにしました。
・世代数: 100
・個体数: 500
・次世代の選択方法: 上位20個体(*)はキープ、残り180個体は全世代からキープされた20個体から変異させて作る
・変異方法: 各成分に対し、20%の確率で別の値に置き換える(このとき、置き換える前と同じ値に置き換わることはないようにした)
・初期個体: ランダム
(*): なぜか上位が同じ個体で固まるため、10世代ごとにキープする個体数を1ずつ増やした。それに伴い、変異により作られる個体の数は減少する。
また、プログラミング言語にはRubyを使用しました。何回かプログラムを実行した結果、次のような行列が得られました(私のPCでは1回の実行当たり10秒程度かかりました)。
Matrix[[14, 28, 43, 59, 0], [0, 29, 42, 58, 75], [15, 30, 0, 54, 72], [12, 27, 45, 0, 73], [13, 0, 44, 60, 74]](行列式は28645603)
Matrix[[13, 0, 41, 58, 75], [14, 30, 44, 0, 72], [12, 28, 0, 60, 74], [0, 29, 45, 59, 73], [15, 27, 43, 57, 0]](行列式は287684196)
Matrix[[0, 29, 43, 59, 72], [13, 27, 42, 0, 73], [12, 28, 0, 60, 74], [15, 30, 45, 57, 0], [14, 0, 44, 58, 75]](行列式は287780688)
Matrix[[14, 28, 43, 60, 0], [12, 0, 42, 59, 73], [15, 30, 0, 58, 74], [0, 29, 45, 57, 72], [13, 27, 44, 0, 75]](行列式は287905806)
Matrix[[15, 0, 43, 58, 75], [13, 29, 45, 0, 74], [12, 30, 0, 59, 73], [0, 28, 44, 60, 72], [14, 27, 42, 57, 0]](行列式は289713264)
結果をよく見ると、各列の数字が「0と各列で可能な数が大きい方から4個」の並べ替え(1列目は0,12,13,14,15, 2列目は0,27,28,29,30, etc.)となっていることが多いことに気が付きます。そこで、このような行列を全探索することにしました。
しかし、このままでは120^5=24,883,200,000通りあって、全探索するには多すぎます。せめて1億通り以下には減らしたいものです。
そこで、改めて行列をよく見ると、0は各行、各列に2度現れないように位置していることがわかります。この場合、0の位置を最初に決めてから残りの数字の位置を決めることで、探索する行列は24*24^5=191,102,976個(∵3列目の0は必ず3行目)にまで減らせます。まだ少し多い気がしますが、これで全探索してしまいましょう。
...といってもこれが結構長いので、最初の20分ほど探索して得られた結果を示します。
Matrix[[0, 30, 42, 60, 72], [12, 0, 45, 57, 75], [15, 27, 0, 59, 73], [13, 29, 43, 0, 74], [14, 28, 44, 58, 0]](行列式は291970008)
