\documentclass[dvipdfmx,autodetect-engine]{jsarticle} \usepackage[utf8]{inputenc} \usepackage{color,enumitem} \usepackage{amsmath,amssymb} \usepackage{amscd,tikz-cd} \usepackage{mathrsfs} \usepackage{amsthm} \usepackage{mathtools} \usepackage{tabularx} \usepackage{centernot} \usepackage{ascmac} \usepackage{enumitem} \usepackage{url} \setlist[enumerate]{label = (\arabic*), ref = (\arabic*)} \theoremstyle{definition} \newtheorem{prob}{問題} \newtheorem{ans}{解答} \title{Math Power記念\\数理空間トポス模試解答} \author{} \begin{document} \maketitle \begin{prob}[☆]\label{fib} $0$以上の整数$n$に対し、数列$F_n$を次のように定める。 \begin{align*} F_{0}=0, \quad F_{1}=1, \quad F_{n+2}=F_{n+1}+F_{n} \end{align*} このとき、座標平面上の点列 \begin{align*} \left(\frac{F_{2 n}}{F_{2 n+1}}, \frac{1}{F_{2 n+1}}\right) \end{align*} は全て同一円周上にあることを示し、その円の方程式を求めよ。 \end{prob} %出典：https://arxiv.org/pdf/2003.00852.pdf \begin{ans} 最初の$3$点$(0,1),(1/2,1/2),(3/5,1/5)$を通る円の式を求めると、$F_n$が \begin{align*} \left(\frac{F_{2n}}{F_{2n+1}}+\frac{1}{2}\right)^{2}+\left(\frac{1}{F_{2n+1}}\right)^{2}=\frac{5}{4} \end{align*} を満たすことを示せば良いことになる。この式を整理すると、 \begin{align*} F_{2n+1}^2-F_{2n} F_{2n+1}=F_{2n}^2+1 \end{align*} となる。左辺をさらに整理して \begin{align*} F_{2n-1}F_{2n+1}=F_{2n}^2+1 \end{align*} を示せばよいが、より一般に$m$を$1$以上の整数として \begin{align*} F_{m-1}F_{m+1}=F_{m}^2+(-1)^{m} \end{align*} が成り立つことを帰納法により示す。 $m=1$の時は$0 \cdot 1 = 1^2 - 1$より成り立ち、 \begin{align*} F_{m-1}F_{m+1}=F_{m}^2+(-1)^{m} \end{align*} が成り立つとしたとき、 \begin{align*} F_{m}F_{m+2}&=F_{m}(F_{m}+F_{m+1})\\ &=F_{m}^2+F_{m}F_{m+1}\\ &=F_{m-1}F_{m+1} -(-1)^m +F_{m}F_{m+1}\\ &=F_{m+1}(F_{m-1}+F_{m}) + (-1)^{m+1} \\ &=F_{m+1}^2 + (-1)^{m+1}\\ \end{align*} となる（帰納法終わり）。以上により、 \begin{align*} \left(\frac{F_{2 n}}{F_{2 n+1}}, \frac{1}{F_{2 n+1}}\right) \end{align*} は全て \begin{align*} \left(x+\frac{1}{2}\right)^{2}+y^{2}=\frac{5}{4} \end{align*} の円周上に乗る。 \end{ans} 背景：この円はいわゆるフォードの円と関連がある。詳しくは次のリンクを参照→ \url{https://arxiv.org/pdf/2003.00852.pdf} \begin{prob}[☆]\label{tan} 以下の2つの問いに答えよ。 \begin{enumerate} \item すべての実数$u$について$\displaystyle \tan\left(\int_0^u \frac{dx}{x^2 + 1}\right) = u$が成り立つことを示せ。 \item $\dfrac{1}{\sqrt{13}}$と$\tan\dfrac{1}{\sqrt{14}}$はどちらが大きいか。 \end{enumerate} \end{prob} \begin{ans} \ \begin{enumerate} \item\label{tan-guide} $x = \tan t$と置換して積分すればよい（容易なので詳細は省略する）。 \item $\tan\dfrac{1}{\sqrt{14}} < \dfrac{1}{\sqrt{13}}$を示す。 $\displaystyle I = \int_0^{1 / \sqrt{13}} \frac{dx}{x^2 + 1}$とおくと\ref{tan-guide}より$\tan I = \dfrac{1}{\sqrt{13}}$である。 $\tan$は区間$\left(-\dfrac{\pi}{2}, \dfrac{\pi}{2}\right)$において単調増加だから$\displaystyle I > \dfrac{1}{\sqrt{14}}$を示せばよいことになる。 $f(x) = \dfrac{1}{x^2 + 1}$とおくと$f''(x) = \dfrac{6 x^2 - 2}{(x^2 + 1)^3}$なので、$0 < x < \dfrac{1}{\sqrt{3}}$において$f(x)$は上に凸である。 すなわち、2点$(0, f(0)), \left(\dfrac{1}{\sqrt{13}}, f\left(\dfrac{1}{\sqrt{13}}\right)\right)$を結ぶ線分は$y = f(x)$のグラフよりも下にある。 よって4点$(0, 1), (0, 0), \left(\dfrac{1}{\sqrt{13}}, 0\right), \left(\dfrac{1}{\sqrt{13}}, \dfrac{13}{14}\right)$を頂点とする台形の面積を$S$とおけば \[ I > S = \left(1 + \frac{13}{14}\right) \times \frac{1 / \sqrt{13}}{2} = \frac{27}{28 \sqrt{13}} > \frac{1}{\sqrt{14}} \qquad (\because 13 \times 28^2 < 14 \times 27^2) \] を得る（下図参照）。 \[ \begin{tikzpicture}[domain = -0.2:1, scale = 5] \fill[color = gray!20] (0, 1) -- (0, 0) -- ({1/sqrt(13)}, 0) -- ({1/sqrt(13)}, 13/14) -- cycle; \draw[-latex] (-0.2, 0) -- (1.2, 0) node[right] {$x$}; \draw[-latex] (0, 0) -- (0, 1.2) node[above] {$y$}; \draw ({1/sqrt(13)}, 0) -- ({1/sqrt(13)}, 13/14); \draw plot (\x, {1/(\x*\x + 1)}) node[above right] {$y = \dfrac{1}{x^2 + 1}$}; \draw (0, 1) -- ({1/sqrt(13)}, 13/14); \fill (0, 0) circle (0.1mm) node[below] {$(0, 0)$} (0, 1) circle (0.1mm) node[above left] {$(0, 1)$} ({1/sqrt(13)}, 0) circle (0.1mm) node[below] {$\left(\dfrac{1}{\sqrt{13}}, 0\right)$} ({1/sqrt(13)}, 13/14) circle (0.1mm) node[above right] {$\left(\dfrac{1}{\sqrt{13}}, \dfrac{13}{14}\right)$}; \node at ({0.5/sqrt(13)}, 0.5) {$S$}; \end{tikzpicture} \] \end{enumerate} \end{ans} \begin{prob}[☆]\label{gray} $n$を$1$以上の整数とし、$1$から$n$までの整数 のうちいくつかを要素とする集合が全通り描かれたカードがある(空集合と全体集合も含め、カードは全部で$2^n$枚ある)。このカードの中から任意に1枚をとり、そこから残ったカードを一枚ずつ次のルールに従って上に重ねていく。\\ ルール：上に重ねることができるカードは、そこに描かれた集合が一番上のカードに描かれた集合に含まれるか、含むかのいずれかである\\ このルールに従ってカードを重ねていった時に、全てのカードを使い切るような重ね方が存在することを示せ。 \end{prob} \begin{ans} もし空集合が描かれたカードから初めて全てのカードを使い切る並べ方があれば、任意のカードAから始めても全てのカードを使い切る並べ方を構成できる。実際、空集合からスタートする重ね方の中で、Aが描かれたところから出発して最後まで行ったら、空集合から再開（どの集合にも含まれるので上に重ねることが可能）してAの手前のカードまで重ねていける。 従って1枚目は空集合が描かれたカードだとして良い。 以下、帰納法で示す。 $n=1$の時は明らか。 $n$の時に並べる方法が存在したとする。このときの部分集合たちの並びを$a_1,a_2,\cdots,a_{2^n-1},a_{2^n}$とする。この時に$n+1$の時の並べ方として、$a_1(=\emptyset ),a_2,\cdots,a_{2^n-1},a_{2^n},a_{2^n} \cup \{n+1\},a_{2^n-1} \cup \{n+1\},\cdots,a_{2} \cup \{n+1\},a_{1} \cup \{n+1\}$が取れる。よって$n+1$の場合も示せた。 背景：この構成方法はグレイコードと呼ばれる符号の構成と同じである。 \end{ans} \begin{prob}[☆☆]\label{dice} $n$個のサイコロをふり、出た目の二乗の和が$7$の倍数となる確率を求めよ。 \end{prob} \begin{ans} サイコロをn回ふり、2乗和を7で割った余りが$i$になる確率を$a_{n,i}$と置く。以下、添え字は7を法として考える。この時、漸化式$a_{n+1,i}=\sum_{j=1}^{6} a_{n,i-j^2} $ が成立する。また$\zeta_7$を1の原始7乗根とし、$b_{n,i}=\sum_{i=0}^6 a_{n_i}\zeta_7^i $と置くと、漸化式より$b_{n+1,i}=\frac{1}{7}b_{n,i}\sum_{j=0}^6 \zeta_7^{ij^2}$が成立する。 ここで、$A= 2\zeta_7+ 2\zeta_7^4+ \zeta_7^2,B= 2\zeta_7^3+ 2\zeta_7^5+ \zeta_7^6 $とおくと、$A+B=-2,AB=8$。よって、解と係数の関係より、$A,B=-1\pm\sqrt{-7}$。ゆえに、$p_n=a_{n,0}=\frac{1}{7}\sum_{j=0}^6 b_{n,j}=\frac{1}{7}(1^n+3(A/6)^n+3(B/6)^n)= (6^n+3(\sqrt{-7}-1)^n+3(-\sqrt{-7}-1)^n)/(7\times6^n) $\\ 最初に$b_{n,i}$を考え、それを足し合わせて$p_n$を求めるのが離散フーリエ展開の具体例、A,Bを求めるのはガウス和として知られている。 \end{ans} \begin{prob}[☆☆]\label{Rubik} ルービックキューブに対する操作$A$であって、条件「どんな状態のルービックキューブに対しても操作$A$を有限回繰り返せば全面揃えることができる」を満たすものは存在しないことを示せ。ただし操作$A$としては、ルービックキューブの事前に決まったいくつかの面を事前に決まった順番で事前に決まった角度回転させることのみを許し、その他の突飛な操作(ルービックキューブの破壊や交換、確率的及び条件分岐を含む操作など)は考えないものとする。 \end{prob} \begin{ans} 問題文が曖昧なので、想定解を書いておく。 背理法で示す。もし条件を満たす操作$A$が存在したと仮定すると、他のどんな操作も$A$を有限回繰り返したものとして実現できるはずである。(ここで厳密に言えば、複数の操作は操作前のルービックキューブの状態が同じなら操作後の状態も同じであるときに同一視されている。)なぜなら、他のどんな操作$B$に対しても、$B$の逆再生の操作$B^{-1}$を既に揃っているルービックキューブに対して行い、その後$A$を有限回繰り返せば再びルービックキューブは揃うからである。 であれば、ルービックキューブへの操作は全て$A$の有限回の繰り返しになり、特にどんな二つの操作$X,Y$も「可換」になる。つまり、$X$をしてから$Y$をするという操作と、$Y$をしてから$X$をするという操作は(既に言及した同一視のもとで)同じ操作になる。しかし、実際には可換でない操作が存在する(例えば、辺を共有する二つの面について、$90$度回転操作を考えるとこれらは可換でない)ので、矛盾が導かれた。 背景: (良い性質を持った)操作のもつ代数的な構造、群が背景にある。ルービックキューブに対する操作の為す群、ルービックキューブ群に関する群論的な証明は以下のようになる。条件を満たす操作$A$が存在すれば、ルービックキューブ群は$A$を生成元に持つ巡回群になり、特にアーベル群になる。しかし、ルービックキューブ群は非可換なので矛盾である。 \end{ans} \begin{prob}[☆☆]\label{TM} 次の数列の極限値を求めよ。 \begin{align*} \frac{1}{2}, \frac{\left(\frac{1}{2}\right)}{\left(\frac{3}{4}\right)}, \frac{\left(\frac{\left(\frac{1}{2}\right)}{\left(\frac{3}{4}\right)}\right)}{\left(\frac{\left(\frac{5}{6}\right)}{\left(\frac{7}{8}\right)}\right)}, \ldots \end{align*} \end{prob} %出典：https://sites.math.washington.edu/~morrow/336_12/papers/christopher.pdf \begin{ans} （収束性の議論は省略）極限の式を \begin{align*} D=\prod_{n=0}^{\infty}\left(\frac{2 n+1}{2 n+2}\right)^{(-1)^{T_{n}}} \end{align*} と置く。この$T_n$は次のような数列として取れることを確かめる。\\ ・$T_n$は$\{0,1\}$のいずれかである。\\ ・$T_0=0$\\ ・$T_{2n+1} \neq T_n$、$T_{2n} = T_n$\\ ここで$E$を \begin{align*} E=\prod_{n=1}^{\infty}\left(\frac{2 n}{2 n+1}\right)^{(-1)^{T_{n}}} \end{align*} とすると \begin{align*} DE &=\frac{1}{2} \prod_{n=1}^{\infty}\left(\frac{n}{n+1}\right)^{(-1)^{T_{n}}} \\ &=\frac{1}{2} \prod_{n=0}^{\infty}\left(\frac{2 n+1}{2 n+2}\right)^{(-1)^{T_{2 n+1}}} \prod_{n=1}^{\infty}\left(\frac{2 n}{2 n+1}\right)^{(-1)^{T_{2n}}}\\ &=\frac{1}{2} D^{-1}E \end{align*} となり、 \begin{align*} D=\sqrt{\frac{1}{2}} \end{align*} が求める極限値となる。 背景：ここに現れた数列$T_n$はThue-Morse数列と呼ばれるもので、興味深い性質を持つ。詳しくは次のリンクを参照 \url{https://sites.math.washington.edu/~morrow/336_12/papers/christopher.pdf} \end{ans} \begin{prob}[☆☆☆]\label{DeleteNim} ２人のプレイヤーが次のようなゲームを行う。\\ いくつかの石からなる$n$個の山があり、$2$人のプレイヤーは各手番で、以下の2つの操作を続けて行う。交互に操作を行い、最後に操作ができなくなくなったプレイヤーの負けである。 \begin{itemize} \item 1つの山を選び、その山を削除する。 \item 残りの$n-1$山のうち、1つの山を選んで（空でない） 2つの山に分割する。 \end{itemize} このとき、次の問に答えよ。 \begin{enumerate} \item $n=2$のとき、ゲームの局面を$(x,y)$で表す。後手必勝となる$(x,y)$をすべて求めよ。 \item $n=3$のとき、ゲームの局面を$(x,y,z)$で表す。後手必勝となる$(x,y,z)$をすべて求めよ。 \end{enumerate} \end{prob} \begin{ans} \begin{enumerate} \item $n=2$のとき、$x$と$y$がともに奇数であるときかつそのときに限り、後手必勝となる。 \item $n=3$のとき、$v_2(x)=v_2(y)=v_2(z)$であるときかつそのときに限り、後手必勝となる（ただし、$v_2(n)$は非負整数$n$の$2$進付値である）。\\ \end{enumerate} 背景：$p$進付値\\ 非負整数全体を$\mathbb{Z}_{\geq 0}$とおく。一般に$p$進付値の定義は以下である。\\ $p$を素数とする。$n\in \mathbb{Z}_{\geq 0}$の$p$進付値$v_p(n)$は \[v_p(n)=\left \{ \begin{array}{cc} {\rm max}\{l \in \mathbb{Z}_{\geq 0} : p^l \mid n\} & (n\neq 0) \\ \infty & (n=0). \end{array}\right. \] である。言い換えると、$n$の$p$進付値とは、$n$を$p$で割ることができる回数の最大数のことである。\\ なお、2進付値について、以下の性質が知られている。\\ 「正整数全体を$\mathbb{Z}_{>0}$とおく。 $z\in\mathbb{Z}_{>0}$かつ$v_2(z)\geq 1$であるとき、任意の非負整数$k0}$が存在する。」\\ 例えば、これを満たす$x,y$の例として、$x=z-2^k$, $y=2^k$があげられる。\\ この性質を用いることによって、(2)の事実を示すことができる。\\ {\bf 参考文献}\\ このゲームは(Single-) Delete Nimと呼ばれている組合せゲームである。 2山の場合、すなわち(1)の場合について初めに必勝判定を行ったのは\cite{VDN}である。また、2山の場合のこのゲームをDelete Nimと呼び（異なる他のルールのゲームを呼ぶ場合もあるが、いずれもゲームとしては同型である）、Delete Nimの局面におけるGrundy数という重要な値について調べた論文としては\cite{AS}がある。また、3山の場合、すなわち(2)の場合について必勝判定を行ったのは\cite{Sa}である。ちなみに4山の場合についての結果は\cite{Shi}にある。なお、5山以上の場合の必勝判定については2022年9月現在未解決である。 \begingroup \renewcommand{\section}[2]{} \begin{thebibliography}{9} \bibitem{VDN} Z. Stankova and T. Rike, editors：A Decade of the Berkeley Math Circle, American Mathematical Society, 159 (2008). \bibitem{AS} T. Abuku and K. Suetsugu：Delete Nim, Journal of Mathematics, Tokushima University {\bf 55}, 75-81 (2021). \bibitem{Sa} 坂井公：数学でピザを切り分ける！パズルの国のアリス4、日経サイエンス社、59-63 (2021). \bibitem{Shi} 篠田正人：Delete Nimの一般化と勝敗判定、情報処理学会研究報告、Vol.2022-GI-47、No.5、1-8 (2022). \end{thebibliography} \endgroup \end{ans} \begin{prob}[☆☆☆]\label{WQO} $\{a_n\}$を、各項$a_n$が正の有理数であるような数列とする（$n = 1, 2, 3, \dotsc$）。 さらに、どの正の整数$m, n$についても、$m < n$のとき$\dfrac{a_n}{a_m}$は整数でないとする。 このとき正の整数の狭義単調増加列$n(1) < n(2) < n(3) < \dotsb$であって、次の2条件のいずれか一方をみたすものが存在することを示せ。 \begin{enumerate} \item すべての正の整数$k$について、$\dfrac{a_{n(k)}}{a_{n(k + 1)}}$は$2$以上の整数である。 \item 相異なるすべての正の整数$k, l$について、$\dfrac{a_{n(k)}}{a_{n(l)}}, \dfrac{a_{n(l)}}{a_{n(k)}}$はどちらも整数でない。 \end{enumerate} \end{prob} \begin{ans} 2つの正の有理数$q, r$について、その比$\dfrac{r}{q}$が整数であるという関係を記号$q \unlhd r$で表すことにする（これはこの解説だけで使う記号である）。 また$q \unlhd r$でないことを$q \centernot\unlhd r$と書き、$q \unlhd r$かつ$r \centernot\unlhd q$であることを$q \lhd r$と書くことにする。 関係$\unlhd$は次の2条件をみたす（この2条件をみたす関係は一般に擬順序（quasi-order）または前順序（preorder）と呼ばれる）。 \begin{description} \item[（反射律）] すべての正の有理数$q$について$q \unlhd q$が成り立つ。 \item[（推移律）] 正の有理数$q, r, s$について$q \unlhd r$かつ$r \unlhd s$であるとき、$q \unlhd s$が成り立つ。 \end{description} 記号$\unlhd$を用いて問題文を書き直すと、以下を示せばよいことになる。 \begin{quote} $m < n$ならば$a_m \centernot\unlhd a_n$であるとき、$n(1) < n(2) < n(3) < \dotsb$をうまく選ぶことで、 \begin{enumerate} \item $k < l$ならば$a_{n(k)} \rhd a_{n(l)}$、 \item $k \neq l$ならば$a_{n(k)} \centernot\unlhd a_{n(l)}$かつ$a_{n(l)} \centernot\unlhd a_{n(k)}$ \end{enumerate} のいずれかが成り立つ。 \end{quote} 証明には次の無限グラフに関するラムゼー（Ramsey）の定理を用いる（証明は省略する）。 \begin{itembox}[l]{定理} $X$を無限集合とする。 $X$の相異なる2つの要素$x, y$からなる非順序対$\{x, y\}$全体の集合を$[X]^2 = \{\, \{x, y\} \mid x, y \in X, x \neq y \,\}$で表す（すなわち、$[X]^2$は「集合の集合」である）。 $[X]^2$の各要素にそれぞれ白か黒のどちらか一方の色を塗る。 このとき$X$無限部分集合$M$であって、$[M]^2$のすべての要素が同じ色で塗られているようなものが存在する。 \end{itembox} \noindent $X$として正の整数全体の集合をとり、非順序対$\{m, n\} \in [X]^2$（ただし$m < n$とする）が$a_m \rhd a_n$をみたすなら白で、$a_m \centernot\unlhd a_n$かつ$a_n \centernot\unlhd a_m$をみたすなら黒で塗る（問題の仮定から、必ず白または黒のちょうど一方が塗られることに注意せよ）。 このときラムゼーの定理から$X$の無限部分集合$M$がとれるので、$M$の要素を小さい順に並べて$n(1) < n(2) < n(3) < \dotsb$とすれば問題の条件をみたす。 背景：擬順序が整列擬順序（well-quasi-order; WQO）であることの2つの定義「どんな無限列も広義増加部分列を含む」と「無限狭義減少列も無限反鎖も持たない」が同値であることを、正の有理数全体の集合$\mathbb{Q}_{> 0}$上の半順序$\unlhd$について確かめる問題である。 整列擬順序の概念はクラスカル（Kruskal）の木定理やグラフマイナー定理などで用いられ、組合せ論をはじめとする諸分野において重要な役割を果たしている。 \end{ans} \begin{prob}[☆☆☆☆]（顧問の加藤文元先生からの出題） 以下の問に答えよ。 \begin{enumerate} \item 2つの生成元$x,y$と基本関係式 $xy^2=y^3x, yx^3=x^2y$ で定まる群を求めよ。 \item 2つの生成元$x,y$と基本関係式 $xyx^{-2}yx=1, y^3=1$ で定まる群の位数を求めよ。 \end{enumerate} \end{prob} \begin{ans} 引き続き挑戦者求む！ \end{ans} \end{document}