浅葱色の計算用紙

数学(広義)を扱っています。移転後サイトです。

57が合成数であることの証明

【問題】57は合成数であることを証明せよ。

 

【解答】57は2以上の整数なので、57は素数または合成数である。以下、57が合成数であるかどうかで場合分けする。

 

(i) 57が合成数の時

57は合成数なので、自明に57は合成数である。

 

(ii) 57が素数の時

まず、連続する3整数57,58,59について考える。

連続する3整数の積は6の倍数なので、57*58*59は6の倍数である。

仮定より、57,59はともに2とも3とも異なる素数であるから、57と59は2の倍数でも3の倍数でもない。

したがって、58は2の倍数かつ3の倍数、すなわち6の倍数である。

よって、60-58=2は6の倍数である。 (∵6の倍数同士の差は6の倍数)

2が6の倍数なので、6k=2となる整数kが存在する。

このkは0<k<1, 3k=1を満たす。

ここで、1以上の整数nを任意に取ると、n=n*1=n*(3k)=k*(3n)と表され、

0<k<1よりkは±1でも±nでもないので、kはnの非自明な約数である。

よって、nには非自明な約数が存在するので、nは合成数である。

とくにn=57とすると、57は合成数である。

 

以上(i)(ii)より、57が合成数であっても素数であっても57が合成数であることが示されたので、57は合成数である。 (Q.E.D.)

素数日の一覧

2018年10月19日について、次の事実が成り立つ:

19は素数

1019は素数

181019は素数

20181019は素数

 

そこで、日付xyzw年mn月de日であって、de,mnde,zwmnde,xyzwmndeが全て素数があるものがどれだけあるかを調べた。

 

すると、1900年から2099年までの200年間で、条件を満たす日付は次の185個であることがわかった:

1900-01-03
1900-08-11
1900-08-23
1903-03-07
1903-11-23
1905-05-03
1906-03-31
1908-01-07
1908-09-11
1908-10-19
1909-05-23
1909-11-29
1911-10-31
1912-08-11
1912-09-19
1914-06-17
1914-12-23
1915-09-07
1915-09-19
1920-01-31
1921-05-23
1921-08-11
1921-08-23
1924-06-07
1926-03-17
1926-10-31
1929-01-07
1929-03-17
1929-04-19
1930-03-31
1930-08-23
1932-10-31
1935-12-17
1935-12-29
1936-08-23
1936-12-13
1938-01-31
1938-12-23
1939-02-23
1941-03-17
1945-08-11
1947-03-17
1948-09-19
1948-11-23
1950-10-19
1950-11-03
1951-03-31
1951-06-13
1951-12-13
1953-09-11
1954-06-13
1956-01-13
1956-03-11
1956-05-03
1956-06-17
1956-09-29
1957-06-13
1959-07-19
1960-03-07
1962-09-29
1962-12-23
1963-03-07
1963-06-07
1963-08-23
1965-01-07
1965-10-19
1969-01-03
1969-11-29
1972-08-29
1972-11-29
1972-12-13
1974-10-31
1974-12-29
1977-12-17
1978-06-13
1980-03-11
1980-12-17
1981-02-23
1981-09-07
1983-03-11
1984-08-23
1984-12-31
1986-03-11
1986-03-17
1986-10-13
1986-10-31
1987-12-31
1989-01-07
1989-11-03
1990-06-07
1993-11-29
1993-12-13
1996-03-31
1998-05-03
1998-09-11
1999-03-07
1999-11-29
2000-01-07
2000-03-11
2000-05-03
2000-10-19
2000-10-31
2000-12-17
2001-02-23
2001-03-13
2003-12-23
2004-08-29
2004-12-13
2006-01-07
2007-08-23
2010-08-11
2010-09-07
2013-02-23
2013-08-29
2013-11-29
2015-01-31
2018-03-11
2018-10-19
2019-05-23
2019-06-13
2019-08-11
2019-08-23
2019-12-31
2021-01-31
2021-03-17
2021-09-29
2022-03-07
2024-12-29
2028-01-03
2028-02-29
2028-06-07
2028-08-11
2030-03-17
2030-07-19
2036-03-17
2037-09-19
2037-12-13
2039-01-13
2039-11-03
2040-03-07
2040-08-23
2042-05-03
2042-11-03
2045-01-13
2045-07-19
2046-06-19
2048-01-07
2048-05-03
2049-06-19
2052-01-03
2052-03-07
2054-12-17
2055-11-29
2055-12-31
2057-04-19
2058-09-19
2060-03-17
2061-05-23
2063-12-29
2064-03-07
2064-11-29
2066-06-17
2066-10-19
2070-01-03
2070-02-23
2070-03-07
2070-05-23
2072-03-11
2072-10-13
2072-12-23
2073-08-23
2075-01-31
2075-04-19
2075-11-03
2078-12-17
2079-06-07
2079-06-13
2085-03-31
2087-12-29
2091-01-03
2091-11-29
2093-01-13
2093-06-17
2094-06-07
2096-04-19

 

しかし、この中には2019年05月23日のように、年の下2桁、月、日の十の位のうち少なくとも1つに0が含まれるものがある。このような日付は2019年5月23日のように書いた場合に素数性が失われる(実際19523は素数ではない)。

年の下2桁、月、日の十の位が全て0でないものは1900年から2099年の範囲では43個あり、以下がそのすべてである:

1911-10-31
1914-12-23
1926-10-31
1932-10-31
1935-12-17
1935-12-29
1936-12-13
1938-12-23
1948-11-23
1950-10-19
1951-12-13
1962-12-23
1965-10-19
1969-11-29
1972-11-29
1972-12-13
1974-10-31
1974-12-29
1977-12-17
1980-12-17
1984-12-31
1986-10-13
1986-10-31
1987-12-31
1993-11-29
1993-12-13
1999-11-29
2013-11-29
2018-10-19
2019-12-31
2024-12-29
2037-12-13
2054-12-17
2055-11-29
2055-12-31
2063-12-29
2064-11-29
2066-10-19
2072-10-13
2072-12-23
2078-12-17
2087-12-29
2091-11-29

 

というわけで、2019年の年越しは素数大富豪で!(気が早い)

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

問題: [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 \)

となる。