4枚7〜8桁の素数の別の覚え方
昨日の記事は83_kinokinoさんによる「家族で楽しむ素数大富豪」でした。
kinokomemo.hatenablog.com身近にプレイヤーがいると、強くなりやすいですね。私はこの記事から機械学習を連想しました。
このブログは、(皆さん既に覚えていると思いますが)4枚7～8桁の素数を覚えようという企画です。
(注意:この覚え方はプログラマー向けです。)
(エラー:覚え方を考えることを一部諦めました。)
まず、覚える対象を確認しておきましょう。以下に示すのが4枚7～8桁の素数の一覧です。
1TQJ 1JTK 1JQJ 1JQK 1QTJ 1KJK 2TJJ 2TQK 2TKK 2JKJ 2QTJ 2KTK 3TKJ 3JTK 3JKK 3KJK 3KKJ 4TTJ 4TKK 4JQK 4QTJ 4QJJ 4QJK 4QQK 4QKJ 4KKK 5TQJ 5JTJ 5QJK 5QQJ 5KTK 5KJJ 5KQJ 6TJJ 6TQK 6TKJ 6JTJ 6JTK 6KKJ 7TKK 7JQK 8JTJ 8QTJ 8QTK 8KJJ 9QQK 9KTJ TKQJ TKKJ JJKJ JKJJ QJKJ QJKK QQQJ QKJK KTQJ KJTK KJQJ
多いですね。覚えにくいですね。というわけで、最上位カードの値で整理しましょう。
1:TQJ JTK JQJ JQK QTJ KJK
2:TJJ TQK TKK JKJ QTJ KTK
3:TKJ JTK JKK KJK KKJ
4:TTJ TKK JQK QTJ QJJ QJK QQK QKJ KKK
5:TQJ JTJ QJK QQJ KTK KJJ KQJ
6:TJJ TQK TKJ JTJ JTK KKJ
7:TKK JQK
8:JTJ QTJ QTK KJJ
9:QQK KTJ
T:KQJ KKJ
J:JKJ KJJ
Q:JKJ JKK QQJ KJK
K:TQJ JTK JQJ
少しは見やすくなりましたが、まだ覚えにくいですね。もう少し情報を圧縮しましょう。そのために、以下のようなことを行います。
TQJ→[各カードの値から10を引く]→021→[それぞれ2bitの2進数にする]→001001→[2桁16進数にする]→09
JTK→[各カードの値から10を引く]→103→[それぞれ2bitの2進数にする]→010011→[2桁16進数にする]→13
...
16進数の値をカード列に戻すためには、この逆の操作を行えばよいです。
09→[2進数にする]→001001→[2bitごとに十進数にする]→021→[10を足す]→TQJ
13→[2進数にする]→010011→[2bitごとに十進数にする]→103→[10を足す]→JTK
さて、上の4枚7～8桁の素数一覧にこの変換を行ってみましょう。
1:09 13 19 1b 21 37
2:05 0b 0f 1d 21 33
3:0d 13 1f 37 3d
4:01 0f 1b 21 25 27 2b 2d 3f
5:09 11 27 29 33 35 39
6:05 0b 0d 11 13 3d
7:0f 1b
8:11 21 23 35
9:2b 31
T:39 3d
J:1d 35
Q:1d 1f 29 37
K:09 13 19
だいぶ覚えやすくなりましたね。あとはこれにストーリーを付けていきます。
(ナレーター: 今日は1213日に一度の「クイック遺産」というオンラインイベントの前日。その準備段階を少し覗いてみましょう。)
1:クイック遺産イブに意味などない！ (9 19 13 1b 21 37)
前日ではなく、当日に初めて盛り上がりたい人もいます。
2:F5 PID 33 21 (05 0b 0f 1d 33 21)
クイック遺産のシステムを修正するため、F5キーを押します。システムのプロセスID(PID、単項イデアル整域ではない)は3321です。
3:DIFferentiatED LEET (0d if 3d 13 37)
「微分されたLEET」という意味です。LEETは英語圏のネットスラングです。
4: 1F/B/571DB/F (01 0f 1b 21 25 27 2b 2d 3f)
IF/B/来ないDB/F。ここどうしろと！？
5: 肉、ササミコックミク。いいぶな。(29 33 35 09 39 11 27)
リアルフードも使われるようです。
6:誤算だ。11~19の素数を十六進数で(05 3D 0B 0D 11 13)
十進と十六進を間違えるというトラブルもあるようです。
7:"Fib"onacci
フィボナッチ数も参加するようです。
8:1から上がって下がって駆け上がる(11 23 21 35)
数字の並びが覚えやすいですね(突然のメタ)。
9:2B31 (2b 31)
どうしろと！？
(ナレーター: 当日になりました。)
T: 3Dミク (3d 39)
今回はVRからの参加者もいるようです。
J: 巫女「ID」
IDの提示が求められたので、
Q: ID: 291F37
提示しました。「憎い文な」とでも覚えておけばよいでしょう。
K:クイック遺産 (9 19 13)
そしてイベントが始まりました。
おまけ2:
見やすいように表にしました。
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 1 | 9 | 39b | 1 | 7 |
| 2 | 5bf | d | 1 | 3 |
| 3 | d | 3f | 7d | |
| 4 | 1f | b | 157bd | f |
| 5 | 9 | 1 | 79 | 359 |
| 6 | 5bd | 13 | d | |
| 7 | f | b | ||
| 8 | 1 | 13 | 5 | |
| 9 | b | 1 | ||
| T | 9d | |||
| J | d | 5 | ||
| Q | df | 9 | 7 | |
| K | 9 | 39 |
4の行にある157bdが目立ちますね。
おまけ3:
5枚9~10桁も同じ方法でエンコードしてみました。それぞれの16進数2桁の数が1つの素数を表しています。
1:11 27 29 2f 33 4d 57 5f 7b 83 87 99 9b ab ad b3 c3 c9 cb dd
2:17 1d 35 43 47 4d 4f 53 6b 6d 73 83 95 a7 b3 d3 d9 eb ef
3:0f 25 2d 33 37 4f 6d 7f a3 cd df
4:0b 27 51 5f 6b 77 7d 89 93 99 a1 a5 a7 b1 b7 ed f5
5:13 19 3d 43 5b 61 6d 77 79 97 a1 bf d3 d9 e5
6:0d 19 37 3d 75 85 97 b5 bb eb f1
7:09 17 21 4d 59 75 89 9f c3 c9 cf fb
8:0d 11 35 3b 47 49 53 59 61 7f 85 91 9b ad d7 dd
9:01 21 25 4f 6f 7f 9d af b5 cf
T:15 2f 4b 5f 7b 7d 81 8f a7 b3 d5 db e7 ef
J:1f 3b 3d 4d 5b 67 77 79 8b 9d a9 d7 e5 fb fd
Q:13 1f 27 39 63 73 75 bb bd c3 cd cf e7 ed f9 ff
K:09 17 1d 59 5f 65 6f 75 83 8f 95 ad b1 b7 b9 bd d1 e1 ed
多い！
おまけ5:
35の後に絵札を4枚付けると35億素数になります。このような素数を同様のエンコードで列挙してみました。
35:49 4f 55 6b a7 a9 ad bf fb
「35+絵札4枚」のパターンの素数が9個あることがわかりますね。
ちなみに、以下の素数大富豪 Advent Calendar 2018の2日目記事にある素数表では6枚出し35億素数は5個書かれていますが、これらは上からそれぞれfb, ad, a9, 55, 49に対応しています。素数表にない4個の素数のうち、4f以外は上位互換が存在するので載せていないのも理解できるのですが、なぜ4f(3511101313)が省略されているかがわかりません。執筆者は素数大富豪大会の優勝者なので、何らかの理由はあると思いますが...
おまけ7:
35+絵札4枚は35の次の桁が1なので35億素数の中でも非常に弱い素数です。相手に3599999933(最大35億素数大富豪素数)を出されたら、絵札4枚では対抗できません。ではどうすればよいでしょうか?答えは単純です。36億素数を覚えておけばよいのです。なぜなら、任意の35億素数は36億よりも小さいからです。
では実際に、「36+絵札4枚」を列挙してみましょう。
36:31 39 3d 51 55 85 87 b5 bb d5 f3
11種類あります。35億と36億で共通している部分が55(3X11111111, X=5,6)のみというのは面白い事実です(少なくとも筆者は執筆時に初めて知りました)!
トリビア: 3X11111111が素数となるXはX=5,6,9,Jで全てです。3JJJJJが素数であるということも非常に興味深いですね。ちなみに、569, 569Jはどちらも素数です。
明日の記事はm_2seiさんによる「1年前の話をします（すみません）」です。明日は12月13日すなわち素数大富豪の日なので、素数大富豪の今後の発展につながる素晴らしい記事を期待しています(実際はそうではないようですが)!
57が合成数であることの証明
【問題】57は合成数であることを証明せよ。
【解答】57は2以上の整数なので、57は素数または合成数である。以下、57が合成数であるかどうかで場合分けする。
(i) 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は自然数に含まないものとします。
次の動画で、以下の問題が提起された：
問題：
全ての自然数に対して、それぞれに対応する頂点がちょうど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)より、与えられたグラフには三角形は存在しない。
