三角関数の加法定理の証明

問題: [1999東大改]

(1)複素数\(\theta\)に対して\(\sin{\theta}, \cos{\theta}\)の定義を述べよ.

(2) (1)で述べた定義にもとづき, 複素数\(\alpha,\beta\)に対して

\( \sin{(\alpha+\beta)}=\sin{\alpha}\cos{\beta}+\cos{\alpha}\sin{\beta}, \)

\( \cos{(\alpha+\beta)}=\cos{\alpha}\cos{\beta}-\sin{\alpha}\sin{\beta} \) を証明せよ.

解答:

(1)

\( \sin{\theta}=\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}{\theta}^{2k+1}}{(2k+1)!}} \)

\( \cos{\theta}=\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}{\theta}^{2k}}{(2k)!}} \)

(2)

\( \begin{eqnarray} \sin{(\alpha+\beta)}&=&\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}{(\alpha+\beta)}^{2k+1}}{(2k+1)!}} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k+1)!}\sum_{l=0}^{2k+1}\alpha^l\beta^{2k+1-l}\ _{2k+1}C_{l} \right) }\end{eqnarray} \)

\( \begin{eqnarray} \sin{\alpha}\cos{\beta}&=&\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}\alpha^{2k+1}}{(2k+1)!}\cdot\sum_{k=0}^{\infty}\frac{(-1)^{k}\beta^{2k}}{(2k)!}} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^l\alpha^{2l+1}}{(2l+1)!}\frac{(-1)^{(k-l)}\beta^{2k-2l}}{(2k-2l)!} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^k}{(2l+1)!}\frac{1}{(2k-2l)!} \alpha^{2l+1}\beta^{2k-2l} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+1)!} \sum_{l=0}^{k}\frac{(2k-2l+2l+1)!}{(2l+1)!(2k-2l)!} \alpha^{2l+1}\beta^{2k-2l} \right)} \\&=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+1)!} \sum_{l=0}^{k} \alpha^{2l+1}\beta^{2k-2l}\ _{2k+1}C_{2l+1} \right)} \end{eqnarray} \)

これは\(\displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k+1)!}\sum_{l=0}^{2k+1}\alpha^l\beta^{2k+1-l}\ _{2k+1}C_{l} \right) }\)において\(\alpha\)の奇数次の項のみを取り出したものである

\( \begin{eqnarray} \cos{\alpha}\sin{\beta}&=&\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}\beta^{2k+1}}{(2k+1)!}\cdot\sum_{k=0}^{\infty}\frac{(-1)^{k}\alpha^{2k}}{(2k)!}} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^l\beta^{2l+1}}{(2l+1)!}\frac{(-1)^{(k-l)}\alpha^{2k-2l}}{(2k-2l)!} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^k}{(2l+1)!}\frac{1}{(2k-2l)!} \alpha^{2k-2l}\beta^{2l+1} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+1)!} \sum_{l=0}^{k}\frac{(2k-2l+2l+1)!}{(2l+1)!(2k-2l)!} \alpha^{2k-2l}\beta^{2l+1} \right)} \\&=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+1)!} \sum_{l=0}^{k} \alpha^{2k-2l}\beta^{2l+1}\ _{2k+1}C_{2l+1} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+1)!} \sum_{l=0}^{k} \alpha^{2l}\beta^{2k-2l+1}\ _{2k+1}C_{2k-2l+1} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+1)!} \sum_{l=0}^{k} \alpha^{2l}\beta^{2k-2l+1}\ _{2k+1}C_{2l} \right)} \end{eqnarray} \)

これは\(\displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k+1)!}\sum_{l=0}^{2k+1}\alpha^l\beta^{2k+1-l}\ _{2k+1}C_{l} \right) }\)において\(\alpha\)の偶数次の項のみを取り出したものである

よって

\( \begin{eqnarray} \sin{(\alpha+\beta)}= \displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k+1)!}\sum_{l=0}^{2k+1}\alpha^l\beta^{2k+1-l}\ _{2k+1}C_{l} \right) } = \sin{\alpha}\cos{\beta}+ \cos{\alpha}\sin{\beta} \end{eqnarray} \)

\( \begin{eqnarray} \cos{(\alpha+\beta)}&=&\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}{(\alpha+\beta)}^{2k}}{(2k)!}} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k)!}\sum_{l=0}^{2k}\alpha^l\beta^{2k-l}\ _{2k}C_{l} \right) }\end{eqnarray} \)

\(\begin{eqnarray} \cos{\alpha}\cos{\beta}&=&\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}\alpha^{2k}}{(2k)!}\cdot\sum_{k=0}^{\infty}\frac{(-1)^{k}\beta^{2k}}{(2k)!}} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^l\alpha^{2l}}{(2l)!}\frac{(-1)^{(k-l)}\beta^{2k-2l}}{(2k-2l)!} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^k}{(2l)!}\frac{1}{(2k-2l)!} \alpha^{2l}\beta^{2k-2l} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k)!} \sum_{l=0}^{k}\frac{(2k-2l+2l)!}{(2l)!(2k-2l)!} \alpha^{2l}\beta^{2k-2l} \right)} \\&=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k)!} \sum_{l=0}^{k} \alpha^{2l}\beta^{2k-2l}\ _{2k}C_{2l} \right)} \end{eqnarray}\)

これは\( \displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k)!}\sum_{l=0}^{2k}\alpha^l\beta^{2k-l}\ _{2k}C_{l} \right) }\)の偶数次の項のみを取り出したものである

\( \begin{eqnarray} \sin{\alpha}\sin{\beta}&=&\displaystyle{\sum_{k=0}^{\infty}\frac{(-1)^{k}\alpha^{2k+1}}{(2k+1)!}\cdot\sum_{k=0}^{\infty}\frac{(-1)^{k}\beta^{2k+1}}{(2k+1)!}} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^l\alpha^{2l+1}}{(2l+1)!}\frac{(-1)^{(k-l)}\beta^{2k-2l+1}}{(2k-2l+1)!} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \sum_{l=0}^{k}\frac{(-1)^k}{(2l+1)!}\frac{1}{(2k-2l+1)!} \alpha^{2l+1}\beta^{2k-2l+1} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+2)!} \sum_{l=0}^{k}\frac{(2l+1+2k-2l+1)!}{(2l+1)!(2k-2l+1)!} \alpha^{2l+1}\beta^{2k-2l+1} \right)} \\&=& \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^k}{(2k+2)!} \sum_{l=0}^{k} \alpha^{2l+1}\beta^{2k-2l+1}\ _{2k+2}C_{2l+1} \right)} \\ &=& \displaystyle{\sum_{k=0}^{\infty}\left(- \frac{(-1)^k}{(2k)!} \sum_{l=0}^{k - 1} \alpha^{2l+1}\beta^{2k-2l-1}\ _{2k}C_{2l+1} \right)} \end{eqnarray} \)

これは\( \displaystyle{\sum_{k=0}^{\infty}\left(\frac{(-1)^{k}}{(2k)!}\sum_{l=0}^{2k}\alpha^l\beta^{2k-l}\ _{2k}C_{l} \right) }\)の奇数次の項のみを取り出したものの-1倍である

よって

\( \cos{(\alpha+\beta)} = \displaystyle{\sum_{k=0}^{\infty}\left( \frac{(-1)^{k}}{(2k)!} \sum_{l=0}^{2k}\alpha^l \beta^{2k-l}\ _{2k}C_{l} \right) } = \cos{\alpha}\cos{\beta}- \sin{\alpha}\sin{\beta} \)

ポプテピピックで竹●房破壊

【Aパート】

問題：

画面上に「ポ」「プ」「テ」「ピピック」が等確率でランダムに表示される。画面上に「ポプテピピック」の文字列が完成すると竹●房が破壊される。このとき、竹●房が破壊されるまでに画面に表示される文字数の期待値を求めよ。

解答：

いつもの。

画面上に表示された最後の文字が「ポ」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a \),

画面上に表示された最後の文字列が「ポプ」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( b \),

画面上に表示された最後の文字列が「ポプテ」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( c \),

画面上に表示された最後の文字列が上記のどれでもないとき(空であるときも含む)竹●房が破壊されるまでに追加で表示される文字数の期待値を\( x \)とすると

次の連立方程式が成り立つ。

\( a=\frac{1}{4}(1+a)+\frac{1}{4}(1+b)+\frac{1}{4}(1+x)+\frac{1}{4}(4+x) \)

\( b=\frac{1}{4}(1+a)+\frac{1}{4}(1+x)+\frac{1}{4}(1+c)+\frac{1}{4}(4+x) \)

\( c=\frac{1}{4}(1+a)+\frac{1}{4}(1+x)+\frac{1}{4}(1+x)+\frac{1}{4}(4) \)

\( x=\frac{1}{4}(1+a)+\frac{1}{4}(1+x)+\frac{1}{4}(1+x)+\frac{1}{4}(4+x) \)

あとはこの方程式をグレブナー基底でも何でも使って解くと、

\( a=441, b=420, c=336, x=448 \)

となるので、求める答えは448文字である。

【Bパート】

問題：

画面上に「\(c_1\)」「\(c_2\)」\( \cdots \)「\(c_{n-1}\)」「\(c_nc_n \cdots c_n\)」( \(c_n\)が\(n\)文字 )が等確率でランダムに表示される。画面上に文字列「\(c_1c_2\cdots c_{n-1}c_nc_n \cdots c_n\)」( \(c_n\)が\(n\)文字 )が完成すると竹●房が破壊される。このとき、竹●房が破壊されるまでに画面に表示される文字数の期待値を求めよ。

解答：

画面上に表示された最後の文字が「\(c_1\)」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a_1 \),

画面上に表示された最後の文字列が「\(c_1c_2\)」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a_2 \),

\( \cdots \)

画面上に表示された最後の文字列が「\(c_1c_2\cdots c_{n-1} \)」のとき竹●房が破壊されるまでに追加で表示される文字数の期待値を\( a_{n-1} \),

画面上に表示された最後の文字列が上記のどれでもないとき(空であるときも含む)竹●房が破壊されるまでに追加で表示される文字数の期待値を\( x \)とすると

次の連立方程式が成り立つ。

\( a_1=\frac{1}{n}(1+a_1)+\frac{1}{n}(1+a_2)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( a_2=\frac{1}{n}(1+a_1)+\frac{1}{n}(1+a_3)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( \cdots \)

\( a_{n-2}=\frac{1}{n}(1+a_1)+\frac{1}{n}(1+a_{n-1})+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( a_{n-1}=\frac{1}{n}(1+a_1)+\frac{1}{n}(n)+\frac{n-2}{n}(1+x)\)

\( x=\frac{1}{n}(1+a_1)+\frac{n-2}{n}(1+x)+\frac{1}{n}(n+x) \)

この方程式を解けばよい。

ここで、

\( a_1-\frac{1}{n}(1+a_2)=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( a_2-\frac{1}{n}(1+a_3)=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

\( \cdots \)

\( a_{n-2}-\frac{1}{n}(1+a_{n-1})=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \)

であるから、\(1\leq k \leq n-2 \)の範囲で \(a_k-\frac{1}{n}(1+a_{k+1}) \)は一定値を取る。

よってこの値を\( C \)とすると、 \(a_k-\frac{1}{n}(1+a_{k+1})=C \)すなわち\(a_{k+1}-na_k=-nC-1 \)が成り立つ。ここで\(-nC-1=C'\)とすると、\(a_{k+1}-na_k=C'\)となるので、\(a_k\)はある定数\(A\)を用いて

\(a_k=An^k+\frac{C'}{1-n}\)

と表される。

 また、この式から\(a_1=An+\frac{-nC-1}{1-n}\)であるから、これを

\( C=\frac{1}{n}(1+a_1)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \) (∵\(C\)の定義)

に代入すると、

\( \begin{eqnarray} C&=&\frac{1}{n}\left(An+\frac{-n(C+1)}{1-n}\right)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \\ &=&\left(A-\frac{C+1}{1-n}\right)+\frac{n-3}{n}(1+x)+\frac{1}{n}(n+x) \end{eqnarray}\)

 また、\( a_{n-1}, x\)の式にも同様に代入すると、

\( An^{n - 1}+\frac{-nC-1}{1-n}=\left(A-\frac{C+1}{1-n}\right)+1+\frac{n-2}{n}(1+x) \)

\( x=\left(A-\frac{C+1}{1-n}\right)+\frac{n-2}{n}(1+x)+\frac{1}{n}(n+x) \)

となる。

これらの3式を\(A,C,x\)について解けばよい。

一旦分母を払って右辺を\(=0\)にする。

\( n(1-n)C-n(1-n)A+n(C+1)-(n-3)(1-n)(1+x)-(1-n)(n+x)=0 \)

\( An^n(1-n)+n(-nC-1)-n(1-n)A+n(C+1)-n(1-n)-(n-2)(1-n)(1+x)=0 \)

\( n(1-n)x-n(1-n)A+n(C+1)-(n-2)(1-n)(1+x)-(1-n)(n+x)=0 \)

あとはこれをグレブナー基底で解いて、

 \( A=-2+\frac{1}{n}, C=\frac{n^{n-1}(n-1)(2n-1)-1}{n}, x=n^{n-1}(2n-1) \)

を得る。

したがって、求める文字数は\(n^{n-1}(2n-1) \)文字である。

ゴドマチ数え上げ(1)

一般に、最初の2つの図形が合同の時は定義より後手の勝ちであるから、最初の2つの図形が合同でないときのみを考えればよい。

よって、1単位マッチ、2単位マッチは自明(どちらも後手必勝)であるから、3単位マッチ以上を考えればよい。

3単位マッチ

非合同なトリオミノの組は次のパターンしかない:

0110  0000

0010  0111

(ただし1の部分がブロックとする)

この場合、先手は次のxの部分を削除すれば勝利できる:

0110  0000

00x0  011x

よって非自明な3単位マッチは先手必勝である。

4単位マッチ

1単位以上削除して非合同な図形を作ると後手必勝となるから、先手必勝となるためにはどんな組に対しても1手で合同な図形ができなければならない。

T以外のテトロミノは1×2の長方形の領域を削除して残りを1×2の長方形の領域にできるので、T以外の非合同なテトロミノ2つが与えられれば先手必勝となる。

また、TとO,L,Sの場合は1マス削除して両方をL-トリオミノにすることができ、TとIの場合は1マス削除して両方をI-トリオミノにすることが出来るので先手必勝である。

よって非自明な4単位マッチはどんな場合も先手必勝である。

5単位マッチ

1単位以上削除して非合同な図形を作ると後手必勝となるから、先手必勝となるためにはどんな組に対しても1手で合同な図形ができなければならない。

W,I,X以外は1マス削除してL-テトロミノにすることができる。

以下、これらが含まれる場合を表の形で数え上げる。表の太字でない要素は削除してできる形を示す。-Trはトリオミノ、-Ttはテトロミノを表す。

	W	I	X
F	S-Tt	(不可能)	T-Tt
L	L-Tr	I-Tt	(不可能)
N	S-Tt	I-Tr	(不可能)
P	S-Tt	I-Tr	T-Tt
Y	L-Tr	I-Tt	T-Tt
Z	L-Tr	(不可能)	(不可能)
T	(不可能)	I-Tt	T-Tt
U	L-Tr	(不可能)	(不可能)
V	(不可能)	I-Tt	(不可能)
W	(合同)	(不可能)	(不可能)
I	(不可能)	(合同)	(不可能)
X	(不可能)	(不可能)	(合同)

ここで、(不可能)とあるのは1手で合同にできない、すなわち後手必勝な組み合わせを意味します。すなわち、上の表で(不可能)となっている組み合わせのときは後手必勝、それ以外の時は先手必勝である。

・・・といきたいところですが、実は今まで扱わなかったルールがあります。それは、「先手と後手が最初の形を1個ずつ選べる」ということです。すなわち、先手が任意の初期配置に対して勝てなくても、ある1つの形を固定したときにもう1つの形がどのようなものでも先手必勝なら、先手はその固定した形を最初に選ぶことが出来るので先手必勝になってしまいます。

5単位マッチの場合は、先手がPまたはY-ペントミノを選べば相手がどんなペントミノを選んでも先手必勝になるので、ゲーム全体も先手必勝となります。

フィボナッチ数グラフ

注意：この記事では、0は自然数に含まないものとします。

次の動画で、以下の問題が提起された：

www.nicovideo.jp

問題：

全ての自然数に対して、それぞれに対応する頂点がちょうど1個存在するような(無限の大きさを持つ)グラフを考える。このグラフの辺は、和がフィボナッチ数であるような2頂点の間にのみ存在する。このとき、このグラフが三角形を含まない(次数3の完全グラフ\(K_3\)を部分グラフに持たない)ことを証明せよ。

解答：

背理法で証明する。グラフが三角形を含むものと仮定し、その相異なる3頂点に対応する自然数をそれぞれ\( a,b,c \)とする。また、\(F_n\)で\(n\)番目のフィボナッチ数を表すものとする。また、\(F_1=F_2\)であるから、\(F_n\)は\(n\geq 2\)で考えればよい。このとき、\(F_n\)は単調増加となる。

まず、1つの頂点が1だと仮定すると、1と1以外の数を足してフィボナッチ数にするためには\(1+2=3\)しかないが、このとき残りの1つの頂点との和を考えると差が1のフィボナッチ数が必要であることが分かる。これは1と2,2と3しか存在しないが、どちらの場合も\(a,b,c\)が相異なることに矛盾する。したがって、頂点の1つが1となることはない。

次に、以下の補題を証明する：

【補題】\( F_m+F_n=F_l \)が成り立つとき、\(m\)と\(n\)の差は1である。

【証明】\(m\geq n\)として一般性を失わない。

このとき、\(F_l>F_m\)であるから\(l>m\)である。また、\(F_m\)より大きい最小のフィボナッチ数は\(F_{m+1}=F_m+F_{m- 1}\)であるから\(F_n\geq F_{m- 1}\)となる。

さらに、\(F_l\geq F_{m+2}\)とすると\(F_{m+2}=F_m+F_{m+1}\)であるから\(F_n\geq F_{m+1}\)が得られ、これは\(m\geq n\)に反するので

\(F_l=F_{m+1}\)である。したがって、\(n=m- 1,l=m+1\)となるので、\(m-n=1\)を得る。

ここから、3つの場合に分けて証明を行う。

(i) \(a,b,c\)の中にフィボナッチ数が2個以上含まれる場合

対称性より、\(a,b\)がフィボナッチ数で、 \(a=F_m, b=F_n \ (m>n) \)として一般性を失わない。

このとき、3つの整数\(s,t,u\)が存在し、

\( F_m+F_n=F_s \ \cdots(1) \)

\( F_m+c=F_t \ \cdots(2) \)

\( F_n+c=F_u \ \cdots(3) \)

となる。

まず、補題と(1)と\(m>n\)から、\(m=n+1, s=n+2\)がわかる。

次に、(2)-(3)より、

\( \begin{eqnarray} F_m-F_n&=&F_t-F_u \\F_{n+1}-F_n&=&F_t-F_u \\ F_{n-1}&=&F_t-F_u \\ F_{n-1}+F_u&=&F_t \end{eqnarray}\)

 となり、(3)より\(F_u>F_n\)であるから\(u\geq n+1\)を得る。しかし、これは補題と矛盾する。

(ii) \(a,b,c\)の中にフィボナッチ数が1個含まれる場合

対称性より、\(a\)がフィボナッチ数で、 \(a=F_m, b>c \)として一般性を失わない。また、\(b,c\)はフィボナッチ数ではない。

このとき、3つの整数\(s,t,u\)が存在し、

\( F_m+b=F_s \ \cdots(1) \)

\( F_m+c=F_t \ \cdots(2) \)

\( b+c=F_u \ \cdots(3) \)

となる。

このとき、(2)で\(t=m+1\)とすると\(c=F_{m- 1}\)、\(t=m+2\)とすると\(c=F_{m+1}\)となるから、( これらは\(c\)がフィボナッチ数でないことに矛盾するので ) \(t\geq m+3\)となる。同様にして、( \(b>c\)より ) \(s\geq m+4\)を得る。

また、(1)~(3)より\( F_s+F_t-2F_m=F_u \)であり、\(F_t\geq F_{m+3}, 2F_m<F_m+F_{m+1}=F_{m+2} \)から \(F_s<F_u\)を得る。

また、\(b>c\)より\(s>t\)であるから、\(F_s>F_t-2F_m\)である。よって、\(F_s<F_u<2F_s\)であり、これを満たすためには\(F_u=F_{s+1}, F_t-2F_m=F_{s-1}\)でなければならない。

 このとき、

\( \begin{eqnarray} F_{s-1}&<&2F_m+F_{s-1}=F_t \\ &=& F_m+F_m+F_{s-1} \\ &<& F_m+F_{m+1}+F_{s-1} \\ &=& F_{m+2}+F_{s-1} \\&\leq&F_{s-2}+F_{s-1}  \\ &=&F_{s} \end{eqnarray} \)

より、\(F_t=2F_m+F_{s-1}\)がフィボナッチ数であることに矛盾する。

(4行目から5行目への変形では\(s\geq m+4\)を用いた)

よって(ii)の場合でも示された。 

(iii) \(a,b,c\)の中にフィボナッチ数が0個含まれる場合

対称性より、\(a>b>c \)として一般性を失わない。また、\(a,b,c\)はフィボナッチ数ではない。

このとき、3つの整数\(s,t,u\)が存在し、

\( a+b=F_s \ \cdots(1) \)

\( b+c=F_t \ \cdots(2) \)

\( a+c=F_u \ \cdots(3) \)

このとき、

\( a=\frac{1}{2}(+F_s-F_t+F_u) \)

\( b=\frac{1}{2}(+F_s+F_t-F_u) \)

\( c=\frac{1}{2}(-F_s+F_t+F_u) \)

となる。ここで、\(a>b>c\)より、\(F_s>F_u>F_t\)である。また、\(s\geq t+3\)のとき、

\( F_t+F_u \leq F_{u-3}+F_{u} <F_{u-1}+F_{u}=F_{u+1}\leq F_s \)

となり、\(c<0\)となるので不適

よって\(s=t+2,u=t+1\)であるが、このとき

\( c=\frac{1}{2}(-F_{t+2}+F_{t+1}+F_u)=0 \)

となるので不適

よって矛盾が示せた

以上(i)~(iii)より、与えられたグラフには三角形は存在しない。

円板の慣性モーメント

問題：

半径\(R\)、質量\(M\)の円板の慣性モーメントを求めよ。ただし、回転軸は\(\mathbb{R^3}\)内の任意の直線をとりうるものとする。

解答：

求める慣性モーメントを\(I\)とする。

回転軸が中心を通らないとき、回転軸と中心との距離を\(d\)、回転軸を平行移動させて中心に移動させたときの慣性モーメントを\(I_G\)とすると、

\(I=I_G+Md^2\)

 の関係があるので、以下では回転軸は円板の中心を通るものとする。

また、円板と回転軸を適宜平行移動・回転させることにより、円板は\(xy\)平面上で原点を中心とする半径\(R\)の円、回転軸は\(xz\)平面内にあるものとしてよい。

このとき、\(x\)軸の正の方向と回転軸のうち\(z\geq0\)の部分がなす角を\(\theta (0\geq \theta < \pi) \)とする。

ここで、円板上の点\(P(x,y,0)\)とこの直線との距離を求める。直線上の点を\( Q(t\cos{\theta}, 0, t\sin{\theta}) \)とし、\(PQ\)が最小になる\(t\)を求めればよい。

このとき、\(\overrightarrow{PQ}\)は直線に垂直であるから、

\(\overrightarrow{PQ}\cdot\overrightarrow{OQ}=0\)

すなわち\(t\cos{\theta}(t\cos{\theta}-x)+t^2\sin^2{\theta}=0\)となる。

これを整理すると\(t^2-xt\cos{\theta}=0\)

よって\(t\neq0\)より\(t=x\cos{\theta}\)となる。

このとき\( Q(x\cos^2{\theta}, 0, x\sin{\theta}\cos{\theta}) \)であるから、

\( \begin{eqnarray} PQ&=& \sqrt{x^2(\cos^2{\theta}-1)^2+y^2+x^2\sin^2{\theta}\cos^2{\theta}} \\ &=& \sqrt{x^2(\cos^2{\theta}-1)^2+x^2(1-\cos^2{\theta})\cos^2{\theta}+y^2}\\ &=& \sqrt{x^2(1-\cos^2{\theta})+y^2}\\ &=& \sqrt{x^2\sin^2{\theta}+y^2} \end{eqnarray} \)

となる。

また、\( (x,y,0) \)周辺の微小部分(面積\(dS\) )の慣性モーメントは、

\( M\cdot\frac{dS}{\pi R^2}\left(\sqrt{x^2\sin^2{\theta}+y^2}\right)^2\)

\(=\frac{M}{\pi R^2}(x^2\sin^2{\theta}+y^2) dS \)

となる。

全体のモーメントを求めるには、これを円板全体で積分すればよい。実際に積分を行うと、

\( \begin{eqnarray} I&=&\int_{-R}^{R} \int_{-\sqrt{R^2-x^2}}^{-\sqrt{R^2-x^2}} \frac{M}{\pi R^2}(x^2\sin^2{\theta}+y^2) dy dx \\ &=& \frac{M}{\pi R^2} \int_{0}^{R} \int_{0}^{2\pi} r^2(\cos^2{\phi}\sin^2{\theta}+\sin^2{\phi})r d\phi dr \\ &=& \frac{M}{2\pi R^2} \int_{0}^{R} \int_{0}^{2\pi} r^3( (1+\cos{2\phi})\sin^2{\theta}+(1-\cos{2\phi})) d\phi dr \\ &=& \frac{M}{2\pi R^2} \int_{0}^{R} \int_{0}^{2\pi} r^3( (\sin^2{\theta}+1)+(\sin^2{\theta}-1)\cos{2\phi}) d\phi dr \\ &=& \frac{M}{2\pi R^2} \int_{0}^{R} 2r^3\pi(\sin^2{\theta}+1)dr \\ &=& \frac{M}{2\pi R^2}\cdot \pi(\sin^2{\theta}+1) \cdot \frac{R^4}{2} \\ &=&\frac{1}{4}MR^2(\sin^2{\theta}+1) \end {eqnarray}\)

となる。

なお、この式に\( \theta=\frac{\pi}{2} \)を代入すると\( I=\frac{1}{2}MR^2\)、\( \theta=0 \)を代入すると \( I=\frac{1}{4}MR^2\)となり、よく知られた結果と一致する。

よって、回転軸が円板の中心を通らない場合も考慮すると、回転軸と中心との距離を\(d\)、円板と回転軸がなす角を\(\theta\)とすると、その慣性モーメントは

\( \frac{1}{4}MR^2(\sin^2{\theta}+1)+Md^2 \)

となる。

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}のとき) \)である。