JMO予選をグレブナー基底で解く
この記事では、2018年JMO予選6番をグレブナー基底で解こうと思います。
参考文献:
#JMO#数オリ#JMO予選 pic.twitter.com/as4N5TgXGS
— にゃんたろう@数ぽよ (@nyannyantarou00) 2018年1月8日
問題:
三角形ABCは直角二等辺三角形で、∠A=90°である。その内部に3点X,Y,Zをとったところ、三角形XYZは∠X=90°であるような直角二等辺三角形であり、さらに3点A,Y,Xおよび3点B,Z,Yおよび3点C,X,Zはそれぞれこの順に同一直線状に並んでいた。AB=1,XY=1/4のとき、線分AXの長さを求めよ。ただし、STで線分STの長さを表すものとする。
図:
解答:
幾何の問題をグレブナー基底で解くためには座標が必要なので、座標設定を行う。ここでは上図の座標をそのまま用いる。このとき、\( A(0,0), B(1,0), C(0,1) \)となる。ここから、求める量を未知数として含む連立方程式を立てる。
以下、\(X\)の座標を\( (x,y) \),\(Y\)の座標を\( (s,t) \),\(Z\)の座標を\( (u,v) \),求める長さ(\(AX\))を\(l\)とする。
このとき、∠AXC=90°であるから、
\(\overrightarrow{AX}\cdot\overrightarrow{XC}=0 \)すなわち\( -x^2+y(1-y)=0 \ \cdots(1) \)となる。
また、\(Y\)は線分\(AX\)上の点であるから、\(Y\)の座標は定数\(m (0<m<1) \)を用いて
\( s=mx, t=my \)
と表される。これをグレブナー基底として扱いやすくするために移項して右辺を0にすると、
\( s- mx=0 \ \cdots(2) \)
\( t-my=0 \ \cdots(3) \)
となる。
また、\(Z\)は線分\(BY\)上の点であるから、\(Z\)の座標は定数\(n (0<n<1) \)を用いて
\( 1-u=n(1-s), v=nt \)
と表される。これをグレブナー基底として扱いやすくするために移項して右辺を0にすると、
\( 1-u-n(1-s)=0 \ \cdots(4) \)
\( v-nt=0 \ \cdots(5) \)
となる。
また、\(X\)は線分\(CZ\)上の点であるから、\(X\)の座標は定数\(k (0<n<1) \)を用いて
\( x=ku, 1-y=k(1-v) \)
と表される。これをグレブナー基底として扱いやすくするために移項して右辺を0にすると、
\( x-ku=0 \ \cdots(6) \)
\( 1-y-k(1-v)=0 \ \cdots(7) \)
となる。
ここで、\(XY=\frac{1}{4}\)であるから、\({XY}^2=\frac{1}{16}\)なので、
\( (x-s)^2+(y-t)^2=\frac{1}{16} \)
すなわち \( 16(x-s)^2+16(y-t)^2-1=0 \ \cdots(8) \) となる。
また、三角形XYZは∠X=90°の直角二等辺三角形なので、\(XZ=XY=\frac{1}{4}\)である。
よって\( (x-u)^2+(y-v)^2=\frac{1}{16} \)
すなわち \( 16(x-u)^2+16(y-v)^2-1=0 \ \cdots(9) \) となる。
そして、求める値\(l\)は、\(l=AX\)と定義したから、\(l^2={AX}^2\)である。
よって \( x^2+y^2-l^2=0 \ \cdots(10) \)となる。
注意：ここまでに、10個の未知数(\(x,y,s,t,u,v,m,n,k,l\))と10本の式( \( (1)\sim(10) \) )があるので、理論上これは解けるはずである。
\( (1) \sim (10) \)の左辺のグレブナー基底を\(x,y,s,t,u,v,m,n,k,l\)の順の優先度の辞書的順序で計算すると(辞書的順序でないとうまくいかない)、
[-102400*l^8+240896*l^6-181936*l^4+46815*l^2-3375,-1575*k-25600*l^6+40224*l^4-18434*l^2+3810,6400*l^6+(960*n-14816)*l^4+(-1860*n+10681)*l^2+900*n-2265,-6400*l^6+15056*l^4+(3375*n^2-6750*n-7996)*l^2-3375*n^2+6750*n-660,24524800*l^6-54094592*l^4+(1350000*n+34429672)*l^2+10378125*n^3-31093875*n^2+29095875*n-14590005,-454400*l^6+978976*l^4+(25200*m+25200*n-667391)*l^2-25200*m-25200*n+142815,-65689600*l^6+168214784*l^4+(-756000*n-140983144)*l^2+(-23436000*n+23436000)*m-24215625*n^2+72576000*n-9146415,102400*l^6-240896*l^4+181936*l^2+54000*m^2-108000*m+7185,4687200*v-79078400*l^6+167671936*l^4+(151200*n-106507076)*l^2-4687200*m+4843125*n^2-14515200*n+27434415,315*u+41600*l^6-89864*l^4+(-4410*n+61359)*l^2+4725*n-13410,25200*t-454400*l^6+978976*l^4+(25200*n-667391)*l^2-25200*m-25200*n+142815,5040*s+697600*l^6-1499104*l^4+(-75600*n+1020429)*l^2+75600*n-218925,-y+l^2,-315*x-41600*l^6+89864*l^4+(4725*n-61674)*l^2-4725*n+13410]
となる。ここで、最初の式に注目すると、
-102400*l^8+240896*l^6-181936*l^4+46815*l^2-3375
と、\(l\)のみに関する複2次式になっていることがわかる。
この式が\(0\)となる正の実数\(l\)の値を頑張って探すと、(\(l=1\)が根であることと有理根定理から有限時間の手計算で求まる)
\( l=1, \frac{\sqrt{15}}{4}, \frac{\sqrt{79}-2}{20}, \frac{\sqrt{79}+2}{20} \)
となる。
このうち、明らかに\(l=1\)は除外でき、また∠CXA=90°よりXはCAを直径とする半円上にありかつ三角形ABCの内側なので\( l<\frac{\sqrt{2}}{2} \)よって\( l=\frac{\sqrt{15}}{4} \)も除外できる。
またグレブナー基底の第2式に注目すると
1575*k=25600*l^6+40224*l^4-18434*l^2+3810
であるが、\( l=\frac{\sqrt{79}-2}{20}<\frac{4\sqrt{5}-2}{20}<0.4 \)のとき\(k>1\)となり不適
以上より残った\( l=\frac{\sqrt{79}+2}{20} \)が正解となる。この解に対する\( m,n,k \)が1未満であることも有限時間で確認できる。
前前前世
【問題】コンピュータの画面に確率\( p (0<p<1) \)で「前」が表示され、確率\( 1-p \)で「世」が表示されるプログラムを考える。また、このプログラムは「前前前世」を表示したときはじめて停止するものとする。このとき、このプログラムが表示する文字数の期待値を求めよ。
【解答】
直前に「前」が一つもない状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_0 \)、
直前に「前」が1つだけある状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_1 \)、
直前に「前」が2つだけある状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_2 \)、
直前に「前」が3つ以上ある状態から「前前前世」が表示されるまでに必要な文字列の期待値を \( X_3 \)とする。
このとき、求める値は\( X_0 \)である。
ここで、\( X_3 \)について考えると、この後に「世」が出れば終了、「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_3 \)なので、
\( X_3 = (1-p) (1) + (p) (1+X_3) \)
これを解いて、 \(X_3 = \frac{1}{1-p} \)が得られる。
\( X_2 \)について考えると、この後に「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_3 \)、「世」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_0 \)なので、
\( X_2 = (p) (1+X_3) + (1-p) (1+X_0) \)
\( \therefore X_2=\frac{1}{1-p}+(1-p)X_0 \)
\( X_1 \)について考えると、この後に「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_2 \)、「世」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_0 \)なので、
\( X_1 = (p) (1+X_2) + (1-p) (1+X_0) \)
\(\begin{eqnarray} \therefore X_1 &=& 1+pX_2+(1-p)X_0 \\ &=& \frac{1}{1-p}+(1-p^2)X_0 \end{eqnarray} \)
\( X_0 \)について考えると、この後に「前」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_1 \)、「世」が出ればその後に「前前前世」が表示されるまでに必要な文字列の期待値は\( X_0 \)なので、
\( X_0 = (p) (1+X_1) + (1-p) (1+X_0) \)
\(\begin{eqnarray} \therefore X_0 &=& 1+p(X_1)+(1-p)X_0 \\ &=& \frac{1}{1-p} + (1-p^3) X_0 \end{eqnarray} \)
これを \( X_0 \)について解くことにより、
\( X_0=\frac{1}{p^3(1-p)} \)
が得られる。
【おまけ】\( X_0 \)を最小値とそのときの\(p\)の値
\( 0<p<1 \)の範囲で、\( p^3(1-p) \)を最大にすればよい。
\( \frac{d}{dp} p^3(1-p) =p^2(3-4p) \)であるから、
\(p^3(1-p)\)は\(p=\frac{3}{4}\)のとき最大値をとり、その値は\(\frac{27}{256}\)である。
よって求める最小値は\(\frac{256}{27}\ (p=\frac{3}{4}のとき) \)である。
内角の分散
この記事は、次の問題への答案用紙です。問題本文は、以下のリンクをクリックして確認してください。
parabolic-puzzles.hatenadiary.jp
まず、次のように3点をとっても一般性を失わないのでそのようにして考える：
確率密度関数が\( [0,2\pi) \) の範囲の一様分布であるような2つの独立な確率変数\( \theta, \varphi \)に対し、
\( (1,0), (\cos{\theta}, \sin{\theta}), (\cos{\varphi}, \sin{\varphi}) \)
このとき、この三角形の3つの内角はそれぞれ次のようになる。(実際の導出は\( \theta, \varphi , \pi \)の大小関係で分けて行う。
\( \theta < \varphi \)のとき
\( \frac{\varphi}{2}-\frac{\theta}{2}, \pi-\frac{\varphi}{2}, \frac{\theta}{2} \)
\( \theta \geq \varphi \)のとき
\( \frac{\theta}{2}-\frac{\varphi}{2}, \pi-\frac{\theta}{2}, \frac{\varphi}{2} \)
それぞれ分散を計算する。
どちらの場合も内角の平均は\(\frac{\pi}{3}\)であるから、
\( \theta < \varphi \)のとき
\( (分散)=\frac{1}{3} ( (\frac{\varphi}{2}-\frac{\theta}{2}-\frac{\pi}{3})^2+(\frac{2\pi}{3}-\frac{\varphi}{2})^2+(\frac{\theta}{2}-\frac{\pi}{3})^2) \)
\( =\frac{1}{18}(3\theta^2-3\theta\varphi+3\varphi^2-6\pi\varphi+4\pi^2) \)
同様に\( \theta \geq \varphi \)のとき
\( (分散)=\frac{1}{18}(3\theta^2-3\theta\varphi+3\varphi^2-6\pi\theta+4\pi^2) \)
よって、次の式で与えられる二変数関数を\( [0,2\pi)^2 \)の範囲で重積分すればよい：
\begin{eqnarray} \begin{cases}\frac{1}{18}(3\theta^2-3\theta\varphi+3\varphi^2-6\pi\varphi+4\pi^2) (\theta < \varphi) & \\\frac{1}{18}(3\theta^2-3\theta\varphi+3\varphi^2-6\pi\theta+4\pi^2) (\theta \geq \varphi) & \end{cases} \end{eqnarray}
まず、第四項以外は上下同じ式なのでその部分を重積分する：
\( \int _0 ^{2\pi} \int _0 ^{2\pi} (\frac{1}{18}(3\theta^2-3\theta\varphi+3\varphi^2+4\pi^2)) d\theta d\varphi \)
\( =\frac{1}{18}\int _0 ^{2\pi} [\theta^3-\frac{3}{2}\theta^2\varphi+(3\varphi^2+4\pi^2)\theta]_{\theta=0}^{\theta=2\pi} d\varphi \)
\( =\frac{\pi}{9}\int _0 ^{2\pi} (3\varphi^2-3\pi \varphi+8\pi^2) d\varphi \)
\( = 2\pi^4 \)
次に、第四項を重積分する：
\( -\frac{\pi}{3} (\int _0 ^{2\pi} \int _0 ^{\varphi} \varphi d\theta d\varphi + \int _0 ^{2\pi} \int _0 ^{\theta} \theta d\varphi d\theta )\)
\( =-\frac{2\pi}{3} \int _0 ^{2\pi} \int _0 ^y y dxdy \) (変数変換)
\( =-\frac{2\pi}{3} \int _0 ^{2\pi} y^2 dy \)
\( =-\frac {16} {9}\pi^4 \)
よって全体の重積分は
\( 2\pi^4 - \frac {16} {9}\pi^4 = \frac{2}{9}\pi^4 \)
よって分散の期待値は
\( \frac{\frac{2}{9}\pi^4}{(2\pi)^2}=\frac{\pi^2}{18} \)
いろんなグラフの考察
私がニコニコ動画を見ていると、こんな動画を見つけた:
しかし私はこれらのグラフを見て、「本当にこのグラフで正しいのだろうか？」と思った。
グラフ描画ソフトとしてはGRAPESが使われている。コンピューターが書いた以上、浮動小数点等の計算誤差は免れない。
そこで、私がこれらのグラフの概形を検証してみることにした。
(また、Desmosで同じ式を入力し動画に示されたグラフおよび計算結果を確認した)
(一部の検証のみ行うことにした)
Level1
\( \frac{1}{x}+\frac{1}{y}=\frac{1}{x+y} \)
このグラフは、動画ではx軸方向に1/80ごとのギザギザが入ったy=-xのグラフに見えるが、コメントで指摘されている通り、この方程式を満たす実数x,yは存在せず、グラフは空白でなければならない。以下でそれを証明する。
\( \frac{1}{x}+\frac{1}{y}=\frac{1}{x+y} \) の分母を払って
\( (x+y)^2=xy \)
\( x^2+xy+y^2=0 \)
\( (x+\frac{y}{2})^2+\frac{3}{4}y^2 =0 \)
この時、左辺は常に0以上であり、この等号が成り立つのは\( x+\frac{y}{2}=y^2=0 \) すなわちx=y=0のときに限られるが、x=y=0は元の式の分母を0にするので不適
よって元の式を満たす実数x,yは存在しない (Q.E.D.)
\( xy=\sqrt[3]{xy} \)
動画の注釈の通り、この式は \( xy^{-\frac{3}{2}}=1 \) と同値であり、これは\(xy=\pm1\)と同値であるから、動画にある通り2組の双曲線が描かれる。
Level2
\( x^2+y^2=sin(xy) \)
動画では|x|≦3.2×10^-9の範囲にのみグラフが書かれているが、実際にこれを満たす(x,y)は(0,0)のみであることを以下で証明する。
\( f(x,y)=x^2+y^2-sin(xy) \) とすると、f(x,y)≦0になることがあるのはx^2+y^2≦1の範囲内のみなので、以下-1≦x≦1,-1≦y≦1で考えることにする。
\( \frac{\partial}{\partial x}f(x,y)=2x-ycos(xy) , \frac{\partial}{\partial y}f(x,y)=2y-xcos(xy) \)であるから、
\( cos(xy)=C \)とおくと
f(x,y)が極値を取るのは \( 2x-yC=0, 2y-xC=0 \)のとき
このとき \( x(4-C^2)=0 \)となるが -1≦C≦1より x=0 よって y=0
以上より f(x,y)が極値を持つのは(x,y)=(0,0)のとき
ヘッセ行列を考えるとこれは極小値であるからこれは最小値でもある
よってf(x,y)の最小値は0(x=0,y=0のとき)なので元の式のグラフは原点のみになる。(Q.E.D.)
微妙にずれた磁石
この記事を読む前に、この動画を見ておくことをお勧めする。(詳しい説明はすべて省いた)
また、この記事を読む際は動画の11分30秒で一時停止しているものとする。
棒磁石の形状は横2a,縦b,高さ2cの直方体とする
さて、磁極を次のように定義する。(映像の右が+x方向、上が+y方向、⦿が+z方向)
NN:(-a,0,-c)
NS:(a,b,c)
SN:(a,0,0)
SS:(-a,-b,0)
ここで、地球の磁場がどの方向にかかったら原点回りの力のモーメントが0になるか考える。
磁場の向きとx軸の正の向きとがなす角をθとする。また、それぞれの磁荷が受ける力の大きさはすべて等しいので1として問題ない。
磁場ベクトルを(cosθ,sinθ)とすると
(以下工事中)
最大素数大富豪合成数問題
最大素数大富豪素数は99998888777766665555444433332222131313131313121212121111111011010101111であることが知られている。
ここでは、素数大富豪で出せる最大の合成数を求めることにする。
相手は考えない(54枚すべて使える)ものとし、ジョーカーは2ケタの数として使うものとする。すなわち、合成数は36桁となる。
上限
9で始まる36ケタの合成数が3個以上の素因数を持つとすると、(9は4枚しかないので)3個の素因数の上位桁は次のようである可能性がある(これ以外の場合、素因数の積はさらに小さくなる):
①9998..., 8..., 8...
②998..., 98..., 8...
③98..., 98..., 98...
①について、上位桁は10000×9×9=81000より小さいはずなので、9で始まることはなく不適
②について、上位桁は1000×100×9=90000より小さいはずなので、9で始まることはなく不適
③について、上位桁は99×99×99=970299より小さい。
よって、97以上で始まる36ケタの素数大富豪合成数が3個以上の素因数を持つことはありえないので、以下では素因数が2個の場合を考察する。
99で始まるもの
合成数の方で9をすでに2枚使っているので、素因数は次のようになる:
①998..., 8...
②98..., 98...
①について、上位桁は999×9=8991より小さいはずなので、99で始まることはなく不適
②について、上位桁は99×99=9801より小さいはずなので、99で始まることはなく不適
98で始まるもの
①9998..., 8... →9999×9=89991より不適
②998..., 98... →999×99=98901より適する
②(a) 98..., 98... →99×99=9801より適する
②(b) 98..., 8... →99×9=891より不適
よって2個の素因数はそれぞれ9[89]と98で始まる。
988で始まるもの
98...×98...は値が小さすぎるので2個の素因数は998と98で始まる
この段階で9と8を4枚ずつ使ってしまったので7の入り方について考えると
(7を使った後の数字の最大値は6であることに注意)
①99877776..., 986... →99877777×987=98579365899より不適
②9987776..., 9876... →9987777×9877=98649273429より不適
③998776..., 98776... →998777×98777=98656195729より不適
④99876..., 987776... →99877×987777=98656203429より不適
⑤9986..., 9877776... →9987×9877777=98649358899より不適
以上より、988で始まるものは存在しない。
987で始まるもの
7をすでに1枚使っているので、残りの7は3枚
998,98の後に8が来ないとすると
①9987776..., 986... →9987777×987=9857935899より不適
②998776..., 9876... →998777×9877=9864920429より不適
③99876..., 98776... →99877×98777=9865550429より不適
④9986..., 987776... →9987×987777=9864928899より不適
また、
①99887..., 987... →99888×988=98689344より不適
②9987..., 9887... →9988×9888=98761344より適する
このことから、2つの素因数の上4ケタは9987と9887であり、9877で始まるものは存在しない。
9876で始まるもの
9987...×9887...=9876...において7は残り1枚、6は残り3枚
①998776..., 98876...→998777×98877=98765073429より適する
②99876..., 988776...→99877×988777=98756080429より不適
下限
【数理物理学】電流と漸化式
問題：図のような回路について、次の問いに答えよ：
(1)S1のみを閉じ、十分に時間がたった時、C1,C2に蓄えられた電気量Q1,Q2を求めよ。
(2)S1を開き、続いてS2を閉じたあと十分に時間がたった時、C2,C3に蓄えられた電気量Q1',Q2'を求めよ。
(3)S2を開き、続いてS1を閉じたあと十分に時間がたった時、C1,C2に蓄えられた電気量Q1'',Q2''を求めよ。
(4)「S1を閉じ十分に時間を経過させ、S1を開きS2を閉じ十分に時間を経過させS1を開く」操作を十分に多く繰り返したとき、最終的にC2に蓄えられる電気量Qを求めよ。
解答
(1)C1,C2にかかる電圧をそれぞれV1,V2とすると、P点での電気量保存によりQ1=Q2
また、「Q=CV」によりQ1=2V1,Q2=3V2よって2V1=3V2
また、V1+V2=5であるからV1=3,V2=2
よってQ1=Q2=6(C),,
(2)十分に時間がたつと電流が流れなくなるのでC2とC3の電圧が等しくなる。
このとき「Q=CV」により電圧が一定の時電気量は電気容量に比例するので
Q1'=6*3/5=3.6(C),, , Q2'=6*2/5=2.4(C),, //このとき電圧はともに1.2V
(3) (2)が終了した段階でC1に6C,C2に3.6C溜まっているので
P点での電気量保存より-6+3.6=-Q1''+Q2''・・・①
「Q=CV」よりC1,C2にかかる電圧をそれぞれV1'',V2''とすると
Q1''=2V1'', Q2''=3V2''・・・②
また V1''+V2''=5・・・③
②を①に代入して-2V1''+3V2''=-2.4・・・④
③④を連立させて解くとV1''=3.48,V2''=1.52
よってQ1''=6.96(C), Q2''=4.56(C),,
(4)コンデンサーに電気がたまっていない状態から操作をn回繰り返したときのC1,C2,C3に蓄えられる電気量を\( a_n,b_n,c_n \)とする。この状態でS1を閉じて十分に時間が経過した時のC2に蓄えられる電気量を\(d_{n+1}\)とする。
P点での電気量保存により
\(-a_n+b_n=-a_{n+1}+d_{n+1} \)・・・①
「Q=CV」よりC1,C2にかかる電圧をそれぞれ\( U,V \)とすると
\( a_{n+1}=2U, d_{n+1}=3V \)・・・②
また \( U+V=5 \)・・・③
②を①に代入して\( -2U+3V=-a_n+b_n \)・・・④
③④を連立させて解くと\( U=\frac{a_n-b_n+15}{5}, V=\frac{b_n-a_n+10}{5} \)
よって\(a_{n+1}=\frac{2a_n-2b_n+30}{5}, d_{n+1}=\frac{3b_n-3a_n+30}{5} \)
次に、ここからS1を開きS2を閉じ十分に時間を経過させると、
電流が流れなくなるのでC2とC3の電圧が等しくなる。
このとき「Q=CV」により電圧が一定の時電気量は電気容量に比例するので
\( c_{n+1}+d_{n+1} \)の電荷がC2とC3に3:2の比で分配される。
よって \( b_{n+1}=\frac{3}{5}(c_{n}+d_{n+1})=\frac{-9a_n+9b_n+15c_n+90}{25} \)
\( c_{n+1}=\frac{2}{5}(c_{n}+d_{n+1})=\frac{-6a_n+6b_n+10c_n+60}{25} \)
\( a_{n+1}-b{n+1}-c{n+1}=a_n-b_n-c_n \)であるから、\(a_n-b_n-c_n\)は定数数列であり\(a_0-b_0-c_0=0-0-0=0\)であるから\(a_n=b_n+c_n\)(追記:これはP点での電気量保存を示す)
このとき\(c_{n+1}=\frac{4c_n+60}{25}\)となるのでこれを\(c_0=0\)の下で解いて\(c_n=-\frac{20}{7}((\frac{4}{25})^n-1) \)
\( b_n=\frac{6c_n+90}{25}=\frac{6}{35}(25-4(\frac{4}{25})^n) \)
よって、\( \lim_{x\rightarrow\infty}b_n=\frac{6}{35}\times25=\underline{\frac{30}{7}(C),,} \)
