\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{tikz}
\usepackage{hyperref}
\usepackage{youngtab}
\usepackage{ytableau}
\usepackage{mathdots}
\usetikzlibrary{cd}

\setlist[enumerate]{label = (\arabic*), ref = (\arabic*)}

\theoremstyle{definition}
\newtheorem{prob}{問題}[section]
\newtheorem*{ans}{解答}

\newcommand{\Star}{☆}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}

\title{数理空間・トポステーマ別問題集}
\author{}
\begin{document}
\maketitle
\begin{description}[style = multiline, leftmargin = 5mm]
\item[※] 2023年度より, 通年の新たな企画として, 各月でテーマを設定して, 一ヶ月間そのテーマに沿った問題を出題する, という試みを実施したいと思います. 
\item[※] この文書は, これまでトポスで出題されて盛り上がったり反応の良かった問題をテーマ別に分類し, さらに問題を追加し整理することで, 上記企画を長期的に体系化していくためのものです. 
\item[※] 一ヶ月のうち, 最初はそのテーマに関するベタな問題から始まり, 徐々に深く面白い問題を紹介していく, というイメージですが, とりあえずやってみるところから始めたいと思います（問題である必要は実はないかもしれません）. 
\item[※] 問題に記載された\Star の数の意図は以下の通りです\\
\begin{tabularx}{110mm}{Xl}
    （\Star ） \dotfill & 非常にベタな問題（1週目に出すイメージ）\\
    （\Star \Star ） \dotfill & 比較的ベタな問題（2週目に出すイメージ）\\
    （\Star \Star \Star ） \dotfill & ちょっと難しいor深いor面白い問題\\
    （\Star \Star \Star \Star ） \dotfill & 難しいor深いor面白い問題\\
    （\Star\Star\Star\Star\Star  ） \dotfill & 非常に難しいor深いor面白い問題\\
\end{tabularx} 
\item[※] 作成者：中澤俊彦, 安福智明, 神尾悠陽, 小泉淳之介，洞龍弥（←記入者はここに名前を追記してください）
\end{description}

\tableofcontents



\section{論理パズル}
\begin{prob}[\Star]
目の前に正直村と嘘つき村に通じる分かれ道があり，どちらの村人かわからない人が1人立っている．\\
正直村の住人は必ず本当のことを言い，嘘つき村の住人は嘘しか言わないとする．\\
あなたは正直村に行きたいとする．その人になんと尋ねれば正直村へ行けるだろうか．
\end{prob}
\begin{ans}
「あなたの村はどちらですか」
\end{ans}

\begin{prob}[\Star]
３人の思考力に自信のある生徒（Ａさん，Ｂさん，Ｃさん）が一列に並んでいます．
Aの後ろにB，その後ろにCが並び，全員前を向いています．
先生が後ろから３人に帽子を被せました．全員，自分の帽子の色はわかりませんが自分の前の人の帽子の色はわかります．
つまり，
ＢはＡの帽子の色が見えます．
ＣはＡとＢの帽子の色が見えます．

先生「君たちは今，赤か白，どちらかの色の帽子をかぶっています．少なくとも１人は赤い帽子です．これから１人１人に順に質問をします」

先生は生徒Ｃに尋ねました．
「自分の帽子の色がわかりますか？」
生徒Ｃ「わかりません」

先生は生徒Ｂに尋ねました．
「自分の帽子の色がわかりますか？」
生徒Ｂ「わかりません」

先生は生徒Ａに尋ねました．
「自分の帽子の色がわかりますか？」
生徒Ａ「わかりました」

さて，Ａの帽子の色は何色ですか？
\end{prob}
\begin{ans}
赤
\end{ans}


\begin{prob}[\Star\Star\Star]
ある島には$1000$人の住人が住んでいる．$100$人の目は青く，$900$人の目は黒い．この島の住人は自身の目の色を知ってしまったらその日のうちに島を出なくてはならない．さて，この島に一人の冒険家がやってきた．冒険家は，住人全員を広場に集め，全員に聞こえる声で「この島には青色の目の人がいるんですね」と(住人はとっくに知っている情報を)言った．さて，この後島の住人はどうなるか?
\end{prob}
\begin{ans}
    全員が100日目に島を出ていく．
\end{ans}

\begin{prob}
    「何か，主張をしてください．あなたの主張が正しければ一万円を，正しくなければ一万円ではない金額をあなたにプレゼントします．」と提案されました．この人から，確実に\emph{一億円}を得てください．
\end{prob}
\begin{ans}
次の主張をすると良い．
    主張:「あなたは，一万円でも一億円でもない金額を私にプレゼントする」
\end{ans}


\begin{prob}[\Star\Star\Star]
    $n$人の囚人が縦1列に並んでいる．囚人はそれぞれ赤または白の帽子を被っており，自分より前にいる人の帽子の色のみがわかる．囚人は後ろから順に「赤」または「白」と発言し，それが自分の帽子の色と一致していれば釈放される．「全員が釈放される確率」をなるべく高くするにはどうすればいいか？ただし，囚人は自分より後ろの人の発言が聞こえるが，それが合っているかどうかは知らされないとする．
\end{prob}

\begin{ans}
    %一番後ろの囚人は他の全ての囚人のうち赤い帽子を被っている人の数を数え，それが偶数なら赤，奇数なら白と答える．すると後ろから2番目以降の人は自分の帽子の色を確実に言い当てることができる．この戦略により全員が釈放される確率は$1/2$となり，これが最大である．
\end{ans}

\section{グラフ理論}
\begin{prob}[\Star ]
以下のグラフの中から，オイラーグラフ，準オイラーグラフを選べ．（安福）\\

(ア)
\begin{center}
\begin{tikzpicture}[auto]
\node[shape=circle, draw] (b) at (-1, 1) {};
\node[shape=circle, draw] (c) at (-1, -1) {};
\node[shape=circle, draw] (d) at (0, 0) {};
\node[shape=circle, draw] (e) at (1, 1) {};
\node[shape=circle, draw] (f) at (1, -1) {};

\draw[-] (b) to (c);
\draw[-] (b) to (d);
\draw[-] (b) to (e);
\draw[-] (c) to (d);
\draw[-] (c) to (f);
\draw[-] (d) to (e);
\draw[-] (d) to (f);
\draw[-] (e) to (f);
\end{tikzpicture}
\end{center}

(イ)
\begin{center}
\begin{tikzpicture}[auto]
\node[shape=circle, draw] (b) at (-1, 1) {};
\node[shape=circle, draw] (c) at (-1, -1) {};
\node[shape=circle, draw] (d) at (0, 0) {};
\node[shape=circle, draw] (e) at (1, 1) {};
\node[shape=circle, draw] (f) at (1, -1) {};
\node[shape=circle, draw] (g) at (2, 0) {};

\draw[-] (b) to (c);
\draw[-] (b) to (d);
\draw[-] (b) to (e);
\draw[-] (c) to (d);
\draw[-] (c) to (f);
\draw[-] (d) to (e);
\draw[-] (d) to (f);
\draw[-] (e) to (f);
\draw[-] (e) to (g);
\draw[-] (f) to (g);
\end{tikzpicture}
\end{center}

(ウ)
\begin{center}
\begin{tikzpicture}[auto]
\node[shape=circle, draw] (a) at (-2, 0) {};
\node[shape=circle, draw] (b) at (-1, 1) {};
\node[shape=circle, draw] (c) at (-1, -1) {};
\node[shape=circle, draw] (d) at (0, 0) {};
\node[shape=circle, draw] (e) at (1, 1) {};
\node[shape=circle, draw] (f) at (1, -1) {};
\node[shape=circle, draw] (g) at (2, 0) {};

\draw[-] (a) to (b);
\draw[-] (a) to (c);
\draw[-] (b) to (c);
\draw[-] (b) to (d);
\draw[-] (b) to (e);
\draw[-] (c) to (d);
\draw[-] (c) to (f);
\draw[-] (d) to (e);
\draw[-] (d) to (f);
\draw[-] (e) to (f);
\draw[-] (e) to (g);
\draw[-] (f) to (g);
\end{tikzpicture}
\end{center}
\end{prob}

\begin{prob}[\Star \Star \Star ]
長さ$n$のあらゆるビット列がちょうど一つだけ含まれるようなビット列が存在することを示せ. （トポスでの初出題：2020.10.11/出典：/関連・背景:de Bruijn sequence）
\end{prob}


\begin{prob}[\Star\Star\Star]
    \(4 n\)個の小石があり，それぞれの重さは\(1, 2, 3, \dotsc, 4 n\)である．
    各小石は\(n\)色のうちのいずれか1色で塗られており，各色で塗られている小石はちょうど\(4\)個ずつある．
    小石をうまく2つの山に分けることによって，次の2つの条件をともにみたすことができることを示せ．
   \begin{itemize}
        \item 各山に含まれる小石の重さの合計は等しい．
        \item 各色で塗られている小石は，各山にちょうど2個ずつある．
    \end{itemize}
    (出典：IMO 2020，問題3)
\end{prob}
\begin{ans}
    \(n\)個の色を頂点とし，\((1, 4 n), (2, 4 n - 1), \dotsc, (2 n, 2 n + 1)\)を辺とするグラフを作る．
    各頂点の次数は4なので，Euler閉路が各連結成分ごとにとれる．
    それぞれのEuler閉路が偶数番目に訪れる点と奇数番目に訪れる点で組分けをすればよい．
\end{ans}

\begin{prob}[\Star\Star\Star\Star]
    $n,m$ は正整数とする．正$n$角形の頂点に全部で$m$個の石が置 かれている状況を考える．操作とは，正$n$角形の ($n$個の) 頂点から一つを選び，その頂点においてある石を 全て取り，選んだ頂点の隣から反時計回りに石を一つずつ置いていくことを指す．
    \begin{enumerate}
        \item どんな石の配置からでも，全ての頂点に$m$個の石が置かれた配置へ有限回の操作で移れるか．
        \item どんな石の配置からどんな 石の配置へも有限回の操作で移れるか．
    \end{enumerate}
\end{prob}
\begin{ans}
(1)は，一つの頂点には触らず，他の頂点を連打するとわかる．(2)は，状態遷移の有向グラフが一筆書き可能なことを示す．グラフの連結性は(1)でわかっている！
\end{ans}

\begin{prob}[?]
正20面体の各辺を白か黒の2色で塗り分けた時に、ある頂点があって、その対となる頂点に同色の辺を通って辿り着けることを示せ。（トポスでの初出題：小泉さんにより2024.4.6に出題）
\end{prob}
\begin{ans}
\end{ans}

\section{組合せ論}
\begin{prob}[\Star ]
$3\times 3$の正方形の中に$10$個の点を打ったとき，ある$2$つの点の距離が$\sqrt{2}$以下になることを示せ．
\end{prob}
\begin{ans}
    $1\times 1$の正方形$9$個に分割し，鳩の巣原理を用いる．
\end{ans}

\begin{prob}[\Star \Star ]
「$600$以下の自然数からどの$N$個を選んでもその中に互いに素な$2$つの自然数の組が存在する」ような最小の自然数$N$を求めよ．（安福）（トポスでの初出題：2022.11.5）
\end{prob}

\begin{prob}[\Star \Star ]
「$600$以下の自然数からどの$N$個を選んでもその中に一方が他方を割り切る相異なる二つの自然数の組が存在する」ような最小の自然数$N$を求めよ．（トポスでの初出題：2022.11.5）
\end{prob}

\begin{prob}[\Star \Star \Star ]
「$600$以下の自然数からどの$N$個を選んでもその中に商が無限小数となるような相異なる二つの自然数の組が存在する」ような最小の自然数$N$を求めよ．（小泉）
\end{prob}

\begin{prob}[\Star \Star]
正の整数$k$に対し, 
$d(k)$を$k$の正の約数の個数とする. 
正の整数$n$に対し以下の等式を示せ. 
\[
d(1)+\cdots+d(n)=
\left \lfloor \frac{n}{1} \right \rfloor + \cdots + \left \lfloor \frac{n}{n} \right \rfloor
\]
\end{prob}

\begin{prob}[\Star \Star \Star]
星についてのあるハンドブックには$100$項目の性質が
示されており, 
各星はその性質を持っているか持っていないかのどちらかである. 
ふたつの星はそれらの性質が$50$項目以上同じであるとき, 
似ているとよばれる. 
$51$個の星が記載されているとき, 
ある$2$つの似ている星が存在することを示せ. 
(神田)
\end{prob}


\begin{prob}[\Star \Star \Star ]
赤石2個，青石2個，緑石4個を正八角形の頂点に配置する方法は何通りあるか？ただし，裏返したり，回転して一致するものは同じものものとみなす．（安福）
\end{prob}

\begin{ans}
コーシー・フロベニウスの定理より，
\begin{align*}
    |X/G|&=\displaystyle\frac{1}{|D_8|}(420+0+0+12+0+0+12\times4+12\times4)\\
    &=\displaystyle\frac{1}{16}\times528=33\ \ \ \ \ \text{よって，33通り．}
\end{align*}
\end{ans}

\begin{prob}[\Star \Star \Star \Star ]
\begin{enumerate}
    \item 白石と黒石が 3個ずつある. これらの石は積み重ねられるとする. 白石と黒石を積み重ねたり, 並べたりして置く方法（これを配置と呼ぶ）として取り得る配置の個数を求めよ. ただし, 二つの配置について, 一方の配置が他方の配置と,列数が同じであり, 列を入れ替えることにより二つの配置で各列の色の順番も同じようにできる場合,この二つの配置は同じ配置とみなす. また, そのようにできないときに違う配置とみなす.(正解：$131$)
    \item 上記の問題において, 白石$n$個, 黒石$m$個の時の配置の数を$a(n,m)$とする. $a(n,m)$を求める良い法法を求めよ (想定解：
\begin{align*}
\sum_{n,m \geq 0} a(n,m)x^ny^m=\prod_{a,b \geq 0,(a,b )\neq (0,0)}\left( \frac{1}{1-x^ay^b} \right)^{ \binom{a+b}{a}}
\end{align*}
により定まる$a(n,m)$
\end{enumerate}
\begin{ans}
この事実を発見した参加者の高校生（山田くん）による証明は次のようなものである. 
\begin{align*}
\frac{1}{1-x^ay^b}=1+x^ay^b+(x^ay^b)^2+(x^ay^b)^3+\cdots
\end{align*}
と展開した時, 各項$(x^ay^b)^k$は白石が$a$個, 黒石が$b$個からなる列（ただし, 白石と黒石の色の順番は一つ固定されているとする）$k$列からなる配置と対応づけることができる. 白石が$a$個, 黒石が$b$個からなる列について, 白石と黒石の色の順番は$\binom{a+b}{a}$通りあるから, $(1/(1-x^ay^b))^{\binom{a+b}{a}}$によりすべての列が白石が$a$個, 黒石が$b$個からなる配置がすべて生成できる. すべての配置はこれらの配置に一意的に分解できるからこれらを$a,b \geq 0,(a,b )\neq (0,0)$について掛け合わせれば, すべての配置がちょうど一通りずつ生成でき, それを$x^ny^m$についてまとめた係数は$a(n,m)$に一致する
\end{ans}
（トポスでの初出題：2019.6.8~29/出典：(1)は数学コンテストpurple commetより, (2)は加藤文元先生がそれを一般化/関連・背景:Macmahonの公式）
\end{prob}


\begin{prob}[\Star\Star\Star\Star]
    ジグソーパズルのピースが\(n\)種類ある(各ピースは1辺の長さが1の正方形の辺を少しだけ波打たせたものと考える)．
    それぞれの種類のピースは同じものが無限個あるとする．
    どんなに大きな有限サイズの正方形についても，それを覆うようにピースを配置できるとするとき，無限に広い平面全体を充填するようにピースを配置できることを示せ．
    言い換えると，無限に広い平面全体を充填できないならば，
    ある有限のサイズの正方形の時点で既に覆えないことを示せ．
    ただし，ピース同士を重ねてはいけないものとする．
    (出題：湯山， 背景:Wangのタイリング問題が\(\Pi^0_1\)であること)
\end{prob}
\begin{ans}
    ピースを平面に配置する方法は\(\Z^2\)から\(4 n\)への写像とみなせる．
    チコノフの定理から\((4 n)^{\Z^2}\)はコンパクト空間であり，「噛み合っているピースの配置」は閉集合であるので，有限交叉性からわかる．
\end{ans}
\begin{prob}[\Star\Star\Star\Star]
    無限グラフ$G$の任意の有限部分が$n$彩色可能なとき,グラフが$n$彩色可能なことを示せ．
\end{prob}
\begin{ans}
    
\end{ans}

\begin{prob}
    黒$n$枚，白$n$枚の合計$2n$枚のトランプで，ギャンブルをする．あなたは最初正の所持金(例えば，$1000$円)を持っている．トランプをシャッフルして伏せ，一枚づつめくっていく．めくるたびにあなたは所持金から一部($0$でも，全体でもいい)を賭け，色を当てることができれば所持金は倍になって帰ってくる．

    このギャンブルはプレイヤー有利にも程がある！実際，最後のカードの色は確実に当てられるのだから，最初の$2n-1$回$0$円を賭け続ければ，あなたは確実に所持金を$2$倍にすることができる．確実に所持金を$r$倍に増やせるような戦略が存在する$r$の最大値を求めよ．
\end{prob}
\begin{ans}
    $\dfrac{2^n}{\binom{2n}{n}}$
    (なぜランダムウォークと似ているのか？情報理論的な解釈はあるのか？)
\end{ans}


\begin{prob}[\Star \Star]
$n$個の集合のベン図を描け．（小泉）
\end{prob}

\begin{ans}
Gray符号．
\end{ans}


\begin{prob}[\Star \Star \Star ]\label{gray}
$n$を$1$以上の整数とし, $1$から$n$までの整数 のうちいくつかを要素とする集合が全通り描かれたカードがある(空集合と全体集合も含め, カードは全部で$2^n$枚ある). このカードの中から任意に1枚をとり, そこから残ったカードを一枚ずつ次のルールに従って上に重ねていく. \\
ルール：上に重ねることができるカードは, そこに描かれた集合が一番上のカードに描かれた集合に含まれるか, 含むかのいずれかである\\
このルールに従ってカードを重ねていった時に, 全てのカードを使い切るような重ね方が存在することを示せ. （トポスでの初出題：2020.5/出典：集合トランプでスピードをやっていた時に参加者の但見くんが気になり, 鈴木健太くんが証明を与えた/背景・関連：Gray符号）
\end{prob}


\begin{prob}[\Star \Star \Star \Star ]
    整数全体$\mathbb{Z}$を有限個（$2$個以上）の等差数列に分割するとき，それらの公差を小さい順に$a_1,a_2,\cdots,a_n$とすると，$a_1=a_2$が成り立つことを示せ．（Mirsky-Newmanの定理）（小泉）
\end{prob}

\begin{ans}
    $a_1,\cdots,a_n$の最小公倍数を$N$とすると，正$N$多角形の頂点全体が正$a_i$角形の頂点に分割されるので
    $$
        z^N-1=\prod_{i=1}^n(z^{a_i}-w_i)
    $$
    （ただし$w_i$は絶対値$1$の複素数）と表せる．$a_1<a_2$と仮定すると$z^{a_i}$の係数が$0$でなくなってしまう．
\end{ans}


\begin{prob}[\Star \Star \Star \Star ]
    平面上の格子点全てを$2$色で塗り分けるとき，同色の頂点のなす正方形（斜めはダメ）が存在することを示せ．（小泉）
\end{prob}

\begin{ans}
    van der Waerdenの定理と同じようにできる．参考：フィボナッチ・フリーク https://fibonacci-freak.hatenablog.com/entry/2017/08/04/170559
\end{ans}

\begin{prob}[\Star \Star \Star]
$1, 2, \dots ,100$を
ランダムに並べ替えて
$\sigma_1, \sigma_2, \ldots ,\sigma_{100}$
とする.
ひもを$100$本用意し,
各ひもの端点を
$(P_1, Q_1), \ldots ,(P_{100}, Q_{100})$
とする.
$1 \le i \le 100$について$P_i$と$Q_{\sigma_i}$を結ぶ.
このときできる輪っかの個数の期待値を求めよ.
\end{prob}


\section{離散幾何学}

\begin{prob}[\Star \Star \Star ]
$N$を正の奇数とする.  宇宙には星が$N$個あり, 
どの$2$つの星の距離も異なっている. 
それぞれの星は, 
自身の星から最も近い距離にある星を観測している. 
ある星が存在して, 
どの星からも観測されなていないことを示せ. 
(神田)

\end{prob}

\begin{prob}[\Star \Star ]
$X\subset \mathbb{R}^3$が$s$-距離集合であるとは, $s=\#\{d(x,y)|x\neq y\}$となることである. 

(1) 最大の大きさの$1$-距離集合は?
(2) $\#X=6$となる$2$-距離集合を, 相似を除いてすべて求めよ. 
\end{prob}

\begin{prob}[\Star \Star \Star \Star]
$n \geqq 3$ を正の整数とする. 
平面上に$n$個の異なる点があり, 
どの$2$点に対してもそれを結ぶ直線はその$2$点以外の点を含むという. 
このとき全ての点が一直線上にあることを示せ. 
(神田)
\end{prob}

\begin{prob}[\Star\Star\Star\Star\Star]
    囚人の散歩
    ネタ帳:素敵な数学小景33 の20番
    \url{https://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf}
\end{prob}


\begin{prob}[\Star \Star \Star \Star \Star ]
    平面上の面積$1$の凸図形$X$に対し，$X$に含まれる$3$角形の面積の最大値を$S(X)$とする．$S(X)\geq\dfrac{3\sqrt{3}}{4\pi}$を示せ．（補足：$X$が円の場合に等号が成立する）（小泉）
\end{prob}

\begin{ans}
    %$X$内の最も離れた$2$点$P,Q\in X$を取り，その中点を$M$とする．$M$から$120^\circ$間隔で放射状に$3$本の半直線を描き，$X$の周と交わる点を結んで$3$角形を作る．半直線の角度をランダムに選ぶとこの$3$角形の面積の期待値が$\dfrac{3\sqrt{3}}{4\pi}$以上になることが示せる．（参考：フィボナッチ・フリーク https://fibonacci-freak.hatenablog.com/entry/2017/12/06/233026）
    %（原論文：E. Sas, \emph{Über eine Extremumeigenschaft der Ellipsen}, Compositio Mathematica 6 (1939), 468-470.）
\end{ans}
\section{群論}

\begin{prob}[\Star ]
    同じ結果をもたらすあみだくじが2つあるとき，使われている横棒の本数の偶奇は必ず等しいことを示せ．
    (背景：置換の符号のwell-defined性)
\end{prob}

\begin{prob}[\Star\Star\Star ]
    白石が一つ置かれている状態から，以下の操作を繰り返す:
    \begin{quote}
        石同士の間(端でもよい)に白石をいれ，その後その石に隣あっている石の白黒を入れ替える.
    \end{quote}
    このとき，白石$n$個一列の状態にできるような$n$の条件は?
\end{prob}
\begin{ans}
    白石を$x+1\colon \mathbb{F}_3\to \mathbb{F}_3$に，黒石を$-x+1\colon \mathbb{F}_3\to \mathbb{F}_3$に対応させて定数項をみるとよい．
\end{ans}

\begin{prob}[\Star\Star\Star]
    群\(G\)とその元\(x \in G\)，部分群\(H \subseteq G\)について，
    \(x H x^{-1} \subsetneq H\)となることがあるか？
\end{prob}
\begin{ans}
    ある．
\end{ans}

\begin{prob}[\Star\Star\Star\Star]
    有限生成群\(G\)であって，どんな\(n\)についても\(\Z^n\)を部分群に持つものはあるか？
\end{prob}
\begin{ans}
    ある．
    例えばrestricted wreath product \(\Z \mathrel{\mathrm{wr}} \Z\)など．
\end{ans}

\begin{prob}[\Star \Star \Star ]
ルービックキューブに対する操作$A$であって, 条件「どんな状態のルービックキューブに対しても操作$A$を有限回繰り返せば全面揃えることができる」を満たすものは存在しないことを示せ. ただし操作$A$としては, ルービックキューブの事前に決まったいくつかの面を事前に決まった順番で事前に決まった角度回転させることのみを許し, その他の突飛な操作(ルービックキューブの破壊や交換, 確率的及び条件分岐を含む操作など)は考えないものとする. （トポスでの初出題：2020.9.24トポス模試/出典：洞さんがトポス模試で出題）
\end{prob}

\begin{prob}[\Star \Star \Star]
    $100$個のボール$1,2,\cdots,100$が横一列に並んでいる．「$4$つのボール$B_1,B_2,B_3,B_4$を選んで$B_i$の位置に$B_{i+1}$をうつす」という操作（巡回置換）を繰り返して，任意の並べかえを実現できるか？また，$4$つではなく$n$個ならどうか？（小泉）
\end{prob}

\begin{ans}
    %$(1\;4\;2\;3)$と$(1\;2\;3\;4)^2$を合成すると$(1\;2)$が作れる．同じ要領で任意の$2$元が交換できるので任意の置換が実現できる．
    %$4$つではなく$n$個にすると，$n$が偶数ならば全ての置換を作ることができ，$n$が奇数ならば全ての\emph{偶置換}を作ることができる．
\end{ans}

\section{環論・体論}
\begin{prob}
(1)正3角形を作図せよ．[\Star]\\
(2)正5角形を作図せよ．[\Star \Star]\\
(3)正7角形は作図できるか？[\Star \Star \Star \Star]\\
(4)折り紙で正7角形を作れ．[\Star \Star \Star \Star]\\
(5)正17角形は作図できることを示せ[\Star \Star \Star \Star]
\end{prob}
\begin{ans}
(1) 略\\
(2) 略\\
(3) 複素平面上で考える．複素平面上の0,1から始めて，実軸上で$\mathbb{Q}$は作図できる．更に，$\mathbb{Q}$の2次拡大体の元も作図できる．その2次拡大から出発して，更にその2次拡大体の元も作図できる．逆に作図できる点の集合はこの繰り返しで作られる点に限られる．一方，1の7乗根は$\mathbb{Q}$の2次拡大の繰り返しにより作れない（$\mathbb{Q}$に1の7乗根を付け加えた体$\mathbb{Q}(\zeta_7)$について$[\mathbb{Q}(\zeta_7):\mathbb{Q}]=6$のため）．よって正7角形は作図できない．\\
(4) tsujimotterさんのブログを参照：https://tsujimotter.hatenablog.com/entry/2014/07/07/234101 \\
(5) $[\mathbb{Q}(\zeta_{17}):\mathbb{Q}]=16$であり，作図できる．tsujimotterさんのブログを参照：
http://tsujimotter.info/2012/07/14/heptadecagon/ \\
この事実はガウスが19歳のある朝に発見したという逸話で有名．
\end{ans}




\section{組合せゲーム理論}

\begin{prob}[\Star \Star ][制限ニム]
２人のプレイヤーが次のようなゲームを行う．\\
$n$個の石からなる1つの山があり，交互に（あらかじめ定められた）$k$個までの石を取っていく．最後に石を取れなくなったプレイヤーの負けである．
このとき，次の問に答えよ．（安福）
\begin{enumerate}
    \item $k=3$のとき，後手必勝となる条件を求めよ．
    \item $k=m$のとき，後手必勝となる条件を求めよ．
\end{enumerate}
\end{prob}

\begin{ans}
\begin{enumerate}
    \item $k=3$のとき，$n \bmod 4\equiv 0$であるかつそのときに限り，後手必勝である．
    \item $k=m$のとき，$n \bmod (m+1)\equiv 0$であるかつそのときに限り，後手必勝である．
\end{enumerate}
\end{ans}

\begin{prob}[\Star ][ニム，石取りゲーム]
２人のプレイヤーが次のようなゲームを行う．\\
いくつかの石からなる$n$個の山があり，$2$人のプレイヤーは各手番で，一つの山を選び，好きなだけ（一個以上の）石を取る．交互に操作を行い，最後に操作ができなくなくなったプレイヤーの負けである．
このとき，次の問に答えよ．（安福）
\begin{enumerate}
    \item $n=2$のとき，ゲームの局面を$(x,y)$で表す．後手必勝となる条件を求めよ．
    \item $n=3$のとき，ゲームの局面を$(x,y,z)$で表す．後手必勝となる条件を求めよ．
    \item $m$山のとき，ゲームの局面を$(m_1,m_2,\ldots,m_n)$で表す．後手必勝となる条件を求めよ．
\end{enumerate}
（背景：2進数）
\end{prob}

\begin{ans}
繰り上がりなしの$2$進和を$\oplus$で表す．例えば，$3\oplus5=(011)_2\oplus(101)_2=(110)_2=6$である．
\begin{enumerate}
    \item $n=2$のとき，$x\oplus y=0$，すなわち$x=y$であるかつそのときに限り，後手必勝である．
    \item $n=3$のとき，$x\oplus y\oplus z=0$であるかつそのときに限り，後手必勝である．
    \item $m$山のとき，$m_1\oplus m_2\oplus\cdots\oplus m_n=0$であるかつそのときに限り，後手必勝である．
\end{enumerate}
\end{ans}

\begin{prob}[\Star \Star ][素数しりとり]
$2$以上の整数$N$について，$N$以下の素数のみを用いて($10$進数で)しりとりをすると，必ず先手必勝になることを示せ．
\end{prob}
\begin{ans}
    一の位が$2$である素数は$2$しかない．よって，仮に後手必勝であると仮定し，先手が$2$と言った時の後手戦略を$S$とすると，先手は($2$を言う代わりに)$S$を最初から実行すれば良い．
\end{ans}

\begin{prob}[\Star \Star ][ターニング・タートルズ]
２人のプレイヤーが次のようなゲームを行う．\\
いくつかの石からなる$n$個の山があり，$2$人のプレイヤーは各手番で，以下の2つの操作を続けて行う．交互に操作を行い，最後に操作ができなくなくなったプレイヤーの負けである．
\begin{itemize}
\item\ 表（白）のコインを一つ選び，そのコインをひっくり返して裏（黒）にする．
\item\ その後，選んだコインより，左側にあるコイン（表でも裏でも良い）を$1$枚ひっくり返して良い（ひっくり返さなくても良い）．

    %%%%%%%%%%%%%%%%%%%%
    \begin{center}
    \begin{ytableau}
    \none[\scalebox{0.75}{1}]&\none[\scalebox{0.75}{2}]&\none[\scalebox{0.75}{3}]&\none[\scalebox{0.75}{4}]&\none[\scalebox{0.75}{5}]&\none[\scalebox{0.75}{6}]&\none[\scalebox{0.75}{7}]\\
        \circ&\bullet&\circ&\circ&\circ&\bullet&\bullet \\
    \end{ytableau}
    \end{center}
    %%%%%%%%%%%%%%%%%%%%
    
    \end{itemize}
    
    なお，終了局面は次のようになる．
    %%%%%%%%%%%%%%%%%%%%
    \begin{center}
    \begin{ytableau}
        \none[\scalebox{0.75}{1}]&\none[\scalebox{0.75}{2}]&\none[\scalebox{0.75}{3}]&\none[\scalebox{0.75}{4}]&\none[\scalebox{0.75}{5}]&\none[\scalebox{0.75}{6}]&\none[\scalebox{0.75}{7}]\\
        \bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet \\
    \end{ytableau}
    \end{center}
    %%%%%%%%%%%%%%%%%%%%
このとき，後手必勝となる条件を求めよ．
\end{prob}

\begin{ans}
表のコインが置いてある位置の番号$f_i$によって，このゲーム（ターニング・タートルズ）の局面を$(f_1,f_2,\ldots,f_n)$と表す．例えば，
\begin{center}
    \begin{ytableau}
    \none[\scalebox{0.75}{1}]&\none[\scalebox{0.75}{2}]&\none[\scalebox{0.75}{3}]&\none[\scalebox{0.75}{4}]&\none[\scalebox{0.75}{5}]&\none[\scalebox{0.75}{6}]&\none[\scalebox{0.75}{7}]\\
        \circ&\bullet&\circ&\circ&\circ&\bullet&\bullet \\
    \end{ytableau}
    \end{center}
    のとき，$(1,3,4,5)$である．\\
    
  ターニング・タートルズの局面$(f_1,f_2,\ldots,f_n)$において，$f_1\oplus f_2\oplus\cdots\oplus f_n=0$であるかつそのときに限り，後手必勝である．
\end{ans}

\begin{prob}[\Star \Star ]
２人のプレイヤーが次のようなゲームを行う．\\
$m$個の石からなる1つの山があり，以下のルールで交互に山から1つ以上の石を取っていく．最後に石を取れなくなったプレイヤーの負けである．
\begin{enumerate}
    \item まず最初のプレイヤーは好きなだけ石を取る．ただし，全ての石を取ることはできない．
    \item 以降は，直前のプレイヤーが取った石の個数の2倍以下の範囲で，石を取ることができる．
\end{enumerate}
このゲームにおいて，後手必勝となる初期局面の石の数$m$をすべて求めよ．（安福）
（背景：ゼッケンドルフの定理）
\end{prob}

\begin{ans}
$i$番目のフィボナッチ数を$F_i$とすると，$m=F_i$のときかつそのときに限り，後手必勝となる．\\
なお，この事実は「任意の正整数は連続しない相異なる1以上のフィボナッチ数の和で一意に表すことができる」というゼッケンドルフの定理を用いて示すことができる．
\end{ans}

\begin{prob}[\Star \Star \Star ]
２人のプレイヤーが次のようなゲームを行う．\\
いくつかの石からなる$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}
（安福）（背景：$p$進付値）
\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}
    
\end{ans}

\begin{prob}[\Star \Star \Star \Star ][レイリーの定理]
$a,b$を正の実数とするとき，次の2条件が同値であることを示せ．
\begin{enumerate}
    \item $a,b$はともに正の無理数で，$\frac{1}{a}+\frac{1}{b}=1$を満たす．
    \item 任意の正整数は
    \begin{center}
        $I:=\{\lfloor a\rfloor,\lfloor b\rfloor,\lfloor 2a \rfloor,\lfloor 2b \rfloor,\ldots,\lfloor na\rfloor,\lfloor nb\rfloor,\ldots\}$
    \end{center}
    の中にちょうど一回だけ必ず現れる．
    \end{enumerate}

\end{prob}

\begin{prob}[\Star \Star \Star \Star ][ワイトホフ]
２人のプレイヤーが次のようなゲームを行う．\\
いくつかの石からなる2つの山があり，$(m,n)$とする．$2$人のプレイヤーは各手番で，次のどちらかの手を打つ．
\begin{itemize}
\item 一つの山から好きなだけ石を取る（ただし1個以上）．\\
（すなわち，$(m,n)\rightarrow(m-a,n)$ or $(m,n)\rightarrow(m,n-b)$）
\item\ 二つの山から同時に同じ数だけ石を取る．\\
（すなわち，$(m,n)\rightarrow(m-c,n-c)$ ）
\end{itemize}
このとき，後手必勝となる条件を求めよ．（背景：レイリーの定理）
\end{prob}

\begin{ans}
$(m,n)$をワイトホフの局面とする．

$|n-m|=k$とすると, ワイトホフの後手必勝局面は次で与えられる．
\begin{center}
$(\lfloor k\Phi \rfloor,\lfloor k\Phi \rfloor +k)$ or $(\lfloor k\Phi \rfloor +k,\lfloor k\Phi \rfloor)$
\end{center}
ただし，$\Phi$ 黄金比である．すなわち， $\Phi=\frac{1+\sqrt{5}}{2}$．
\end{ans}

\begin{prob}[\Star\Star\Star\Star\Star ]
Grundy数の問題
\end{prob}

\begin{prob}[\Star\Star\Star\Star\Star ]
佐藤・ウェルターゲームの問題
\end{prob}

\section{整数論}

\begin{prob}[\Star]
正多面体に対し，その頂点・辺・面の個数から1を引くとすべて （素数）であり，そのうちの2つの和，3つの和から1を引いたものも，すべて（素数）か （素数の2乗）である．これを確かめよ．（出典：橋本義武『正多面体と素数』）
\end{prob}


\begin{prob}[\Star]
正多面体に対し，その頂点・辺・面の個数から1を引くとすべて （素数）であり，そのうちの2つの和，3つの和から1を引いたものも，すべて（素数）か （素数の2乗）である．これを確かめよ．（出典：橋本義武『正多面体と素数』）
\end{prob}
\begin{ans}
正多面体の頂点，辺，面の個数の表は以下の通り．
\vskip\baselineskip
\noindent
\begin{tabular}{|r|r|r|r||r|r|r|}
\hline
     & $V$ & $E$ & $F$ & $V-1$ & $E-1$ & $F-1$ \\ \hline
正4面体 & 4   & 6  & 4  & 3   & 5  & 3  \\ \hline
正6面体 & 8   & 12  & 6 & 7   & 11  & 5  \\ \hline
正8面体 &  6  & 12  & 8  &  5  & 11  & 7  \\ \hline
正12面体 &  20  & 30  & 12 &  19  & 29  & 11  \\ \hline
正20面体 &  12  & 30  & 20  &  11  & 29  & 19  \\ \hline
\end{tabular}
\vskip\baselineskip
\noindent
\begin{tabular}{|r|r|r|r|r||r|r|r|r|}
\hline
     & $V+E$ & $E+F$ & $V+F$ & $V+E+F$ & $V+E-1$ & $E+F-1$ & $V+F-1$ & $V+E+F-1$ \\ \hline
正4面体 & 10   & 10  & 8 & 14 & 9   & 9  & 7 & 13 \\ \hline
正6面体 & 20   & 18  & 14 & 26 & 19   & 17  & 13 & 25 \\ \hline
正8面体 &  18  & 20  & 14 & 26 &  17  & 19  & 13 & 25 \\ \hline
正12面体 &  50  & 42  & 32 & 62 &  49  & 41  & 31 & 61 \\ \hline
正20面体 &  42  & 50  & 32 & 62 &  41  & 49  & 31 & 61 \\ \hline
\end{tabular}
\end{ans}

\begin{prob}[\Star \Star \Star]
$n$を2以上の整数としたとき
\begin{align*}
1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}
\end{align*}
は整数にはならないことを示せ．
（タイシンガー，1915）
\end{prob}
\begin{ans}

\end{ans}


\begin{prob}[\Star \Star \Star ]
$p$を5以上の素数としたとき
\begin{align*}
1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}
\end{align*}
の分子は$p^2$で割り切れることを示せ.
（トポスでの初出題：2020.12.12/出典：ウォルステンホルムの定理/背景・関連：ウォルステンホルムの定理・有限体 ）
\end{prob}
\begin{ans}
\begin{align*}
S=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}
\end{align*}
とおくと
\begin{align*}
2S &=\sum_{k=1}^{p-1}\left(\frac{1}{k}+\frac{1}{p-k}\right)\\
&=\sum_{k=1}^{p-1}\frac{p}{k(p-k)}
\end{align*}
より, $S$は$p$で割れる. そこで$2S/p$を考えると
\begin{align*}
2S/p &=\sum_{k=1}^{p-1}\frac{1}{k(p-k)}\\
& = -\sum_{k=1}^{p-1}\frac{1}{k^2} \pmod{p}\\
& \equiv -\sum_{k=1}^{p-1}k^2 \pmod{p}\\
& = -\frac{(p-1)p(2p-1)}{6}
\end{align*}
であり, $p$が5以上の素数であることからこれも$p$で割れる. 
以上より$S$は$p^2$で割り切れる. 
\end{ans}

\begin{prob}[\Star \Star \Star \Star ]
$F_n$をフィボナッチ数列とする．$F_p =\pm 1 \pmod p$を示せ．($p\neq 5$の時)
   また，いつ$1$になり，いつ$-1$になるか求めよ．
\end{prob}
\begin{ans}
   $p\pmod 5$が$1,4$のとき$1$となり，$2,3$のとき$-1$となる．
   $F_n$の一般式と相互法則を使えばできる．
\end{ans}

\begin{prob}[\Star \Star]
    $\displaystyle\sum_{m=1}^\infty\sum_{n=1}^{m-1}\dfrac{1}{m^2n}=\sum_{m=1}^\infty \dfrac{1}{m^3}$を示せ．（小泉）（背景：多重ゼータ値）
\end{prob}

\begin{ans}
    左辺と右辺を足すと$\displaystyle\sum_{m=1}^\infty\sum_{n=1}^m \dfrac{1}{m^2n}=\sum_{m=1}^\infty\dfrac{1}{m^2}\left(\sum_{n=1}^\infty \dfrac{1}{n}-\dfrac{1}{m+n}\right)=\sum_{m=1}^\infty\sum_{n=1}^\infty \dfrac{1}{mn(m+n)}$となる．和の中身を$\left(\dfrac{1}{m}+\dfrac{1}{n}\right)\dfrac{1}{(m+n)^2}$と書き直すと左辺の$2$倍が出てくる．
\end{ans}

\begin{prob}[\Star \Star \Star]
    $\tan\theta = \sqrt{2}$となる角度$\theta$は度数法で無理数であることを示せ．（小泉）
\end{prob}

\begin{ans}
    $(1+\sqrt{2}i)^n$の虚部が$n>0$のとき$0$にならないことを示せばよい．この虚部を$a_n\sqrt{2}$とすると，$a_0=0,\;a_1=1$および$a_{n+2}=2a_{n+1}-3a_n$が成り立つ．
    mod $3$で見ると$a_n\neq 0\;(n>0)$がわかる．
\end{ans}

\begin{prob}[\Star \Star \Star \Star ]
    $x^3+20x=y^2$を満たす整数の組$(x,y)$を全て求めよ．（小泉）
\end{prob}

\begin{ans}
    
\end{ans}

\begin{prob}[\Star \Star \Star \Star ]
    正整数$n$に対し，$n$以外の正の約数の$2$乗和が$3n$であるとき，$n$を\emph{$F$完全数}と呼ぶ．
    例えば$10,65,20737$は$F$完全数である：
    \begin{align*}
    3\cdot 10 &= 1^2+2^2+5^2,\\
    3\cdot 65 &= 1^2+5^2+13^2,\\
    3\cdot 20737 &= 1^2+89^2+233^2.
    \end{align*}
    上の式の右辺にはフィボナッチ数ばかり出てくる（$2,5,13,89,233$）．なぜか？（小泉）
\end{prob}

\begin{ans}
    
\end{ans}


\section{行列・線形代数学}

\begin{prob}[\Star ]
$\begin{pmatrix}
2 &-1 \\
-1 & 2
\end{pmatrix},
\begin{pmatrix}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{pmatrix}$
の行列式を求めなさい．(東田)
\end{prob}



\begin{prob}[\Star \Star]
$A$を$n\times n $行列とした時，そのトレース$\mathsf{tr} A$を，
$$\mathsf{tr} A = \sum^n_{i=1} A_{ii} = A_{11}+\dots+A_{nn}$$
と定める．\\
以下，$A,B,C $を$n \times n$行列とする．\\
(1) $\mathsf{tr}(AB-BA)$ を求めなさい．\\
(2) $\mathsf{tr}(ABC-BCA)$ を求めなさい．(ヒント:結合律)\\
(3) $\mathsf{tr}(ABC-BAC)$ が$0$にならないような$A,B,C$の組は存在するか？(ヒント：$n=2$の時から考えると良い．また分配法則に気をつけよ．)

($n=2$とすれば$\Star$問題)(東田)
\end{prob}

\begin{prob}[\Star \Star]
$A,B$を$n\times n$行列とする．\\
$$AB=A+B$$
が成り立つとき，
$$AB=BA$$
は常に成立するか．
\end{prob}

\begin{prob}[\Star \Star \Star]
次の$n \times n $行列，
$A _n=
\begin{pmatrix}
2 & -1 & 0 & \cdots & \cdots & 0 \\
-1 & 2 & -1 & 0 & \cdots & 0 \\
0 & -1 & 2 & \ddots & \ddots & \vdots \\
\vdots & 0 & \ddots & \ddots & -1 & 0 \\
\vdots & \vdots & \ddots & -1 & 2 & -1\ \\
0 & 0 & \cdots & 0 & -1 & 2
\end{pmatrix}$
について考えなさい．\\
(1) 行列式を求めなさい．\\
(2) 固有値を全て求めなさい．
\end{prob}

\begin{prob}[\Star \Star \Star]
(1)$D=
\begin{pmatrix}
\ddots & \ddots & \ddots & \ddots & \ddots \\
\ddots & 0 & 1 & 0 & \ddots \\

\end{pmatrix}$
\end{prob}
    
ネタ帳:素敵な数学小景33 \url{https://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf}%憧憬になっていたので変更しました

\begin{prob}[\Star \Star ]
次の行列式を計算せよ．ただし，因数分解した形で答えよ．（安福）\\

(1)
$
\left|
\begin{array}{ccc}
1 & 1 & 1\\
x & y & z\\
x^2 & y^2 & z^2
\end{array}
\right|
$
\\\\\\

(2)
$
\left|
\begin{array}{cccc}
1 & 1 & 1 & 1\\
x & y & z & w\\
x^2 & y^2 & z^2 & w^2\\
x^3 & y^3 & z^3 & w^3\\
\end{array}
\right|
$
\\\\\\

(3)
$
\left|
\begin{array}{ccccc}
1 & 1 & \cdots & 1\\
x_1 & x_2 & \cdots & x_n\\
x_1^2 & x_2^2 & \cdots & x_n^2\\
\cdots & \cdots & \cdots & \cdots\\
x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1}\\
\end{array}
\right|
$
\end{prob}

\begin{ans}
(1)
$
\left|
\begin{array}{ccc}
1 & 1 & 1\\
x & y & z\\
x^2 & y^2 & z^2
\end{array}
\right|
=
(z-y)(z-x)(y-x)
$
\\\\\\

(2)
$
\left|
\begin{array}{cccc}
1 & 1 & 1 & 1\\
x & y & z & w\\
x^2 & y^2 & z^2 & w^2\\
x^3 & y^3 & z^3 & w^3\\
\end{array}
\right|
=
(w-z)(w-y)(w-x)(z-y)(z-x)(y-x)
$
\\\\\\

(3)
$
\left|
\begin{array}{ccccc}
1 & 1 & \cdots & 1\\
x_1 & x_2 & \cdots & x_n\\
x_1^2 & x_2^2 & \cdots & x_n^2\\
\cdots & \cdots & \cdots & \cdots\\
x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1}\\
\end{array}
\right|
=
\displaystyle\prod_{i<j}^{} (x_j-x_i)
$
\end{ans}

\begin{prob}[\Star \Star]
ライツアウトの問題（トポスでげんがくさんが出してたやつ）
\end{prob}

\begin{prob}[\Star \Star \Star \Star ]
$n$がフィボナッチ数であることと, $5n^2 \pm 4$の少なくとも一方が平方数であることは同値であることを示せ. （トポスでの初出題：2020.2.8）
\end{prob}
\begin{ans}
   
\end{ans}




\section{代数幾何学}
\begin{prob}[\Star \Star ]
曲線$y=x^3-x$上に相異なる$9$個の点$A,B,C,A',B',C',A'',B'',C''$がある．$(A,B,C)$, $(A',B',C')$, $(A'',B'',C'')$, $(A,A',A'')$, $(B,B',B'')$がそれぞれ同一直線上にあるとき，$(C,C',C'')$も同一直線上にあることを示せ．（小泉）
\end{prob}
\begin{ans}
    %解と係数の関係より，$y=x^3-x$上の$3$点$P,Q,R$が同一直線上にあることは、それらの$x$座標の和が$0$であることと同値である．このことから容易に示せる．
\end{ans}

\begin{prob}[\Star \Star \Star ]
放物線$y=x^2$上に相異なる$4$点$A,B,C,D$がこの順に並んでいる．$A,B,C,D$が同一円周上にあるならば，直線$AB,CD$の傾きの和は$0$であることを示せ．（小泉）
\end{prob}

\begin{ans}
    %$A,B,C,D$を通る円の方程式を$x^2+y^2+ax+by+c=0$とする．$A,B,C,D$はこの式と$y=x^2$を同時に満たすので，これらの点の$x$座標は$4$次方程式
    %$$
    %    x^4+(1+b)x^2+ax+c=0
    %$$
    %の解となる．$A,B,C,D$の$x$座標を$a,b,c,d$とすると，解と係数の関係より$a+b+c+d=0$である．一般に点$(p,p^2),(q,q^2)$を通る直線の傾きが$p+q$であることから求める結論を得る．
\end{ans}





\section{帰納法}
\begin{prob}[\Star ]
$1+2+ \cdots +n$が$\dfrac{n(n+1)}{2}$に等しいことを数学的帰納法で示せ．（中澤）
\end{prob}
\begin{ans}
$n=1$の時は明らかに正しい．$n$まで正しいとした時$n+1$では
\begin{align*}
1+2+ \cdots +n+(n+1) &= \frac{n(n+1)}{2} + (n+1) \\
&= (n+1)( \frac{n}{2} + 1 )\\
&=\frac{(n+1)(n+2)}{2}
\end{align*}
となるためよい．
\end{ans}

\begin{prob}[\Star]
平面が有限個の直線($1$点で交わる$3$直線があってもよい)によって
いくつかの領域に分けられている. 
領域をうまく青と黄で塗り分けることで, 
隣り合う領域は異なる色に出来ることを示せ. 
ただし, 
$1$点のみを共有する$2$つの領域は隣り合っているとみなさない. 
(神田)
\end{prob}

\begin{prob}[\Star\Star ]
    \(0\)以上の整数全体の集合を\(\omega = \{0, 1, 2, \dotsc\}\)とする．
    \(\omega \times \omega\)から\(\omega\)への関数
    \[
        J(x, y) = \frac{(x + y)(x + y + 1)}{2} + y
    \]
    が全単射であることを示せ．
    (背景：Cantorのpairing function)
\end{prob}

\begin{prob}[\Star\Star \Star]
$C$をカントール集合とする時，$S=\{ x+y \mid x,y \in C  \}$
はどのような集合か？
\end{prob}
\begin{ans}
$S=[0,2]$となる．
\end{ans}





\section{トポロジー}
\begin{prob}[\Star ]
正多面体（正4面体，正6面体，正8面体，正12面体，正20面体）の頂点の個数と辺の個数と面の個数を数えて表にし，それぞれの正多面体の（頂点の個数）$-$（辺の個数）$+$（面の個数）を計算せよ．（中澤）
\end{prob}
\begin{ans}
正4面体：$4-6+4=2$，
正6面体：$8-12+6=2$，
正8面体：$6-12+8=2$，
正12面体：$20-30+12=2$，
正20面体：$12-30+20=2$．
\end{ans}

\begin{prob}[\Star \Star \Star]
(1)額縁の紐を$2$本の釘に引っかける. 
うまく引っかけることで, 
どちらの釘がとれても額縁が落ちるようにせよ. 
(2)$n$本の釘で同じことが出来るか. 

(最小の「巻き回数」を求めたい(未解決))
(神田)
\end{prob}

\begin{prob}[\Star \Star \Star \Star]
$[0,1]^2$内の$(0,0)$,$(1,1)$を結ぶ曲線$C_1$と，
$(1,0)$,$(0,1)$を結ぶ曲線$C_2$は必ず交わることを示せ
(ちゃんと書くと，連続写像$f_1,f_2:[0,1]\to [0,1]^2$が
$f_1(0)=(0,0),f_1(1)=(1,1)$,
$f_2(0)=(0,1),f_1(1)=(1,0)$を満たすとき，$f_1(t)=f_2(s)$となる
$t,s\in \R$の存在を示せ)
\end{prob}
\begin{ans}
背理法を用いる．
$\phi:[0,1]^2\to R^2\setminus \{(0,0)\},(t,s)\to f_1(t)-f_2(s)$と置く．
$[0,1]^2$の周の0に対する回転数は$1$だが，これを$(0.5,0.5)$に縮めると一点になり矛盾
\end{ans}

\begin{prob}[\Star \Star \Star \Star]
正$20$面体の辺を白と黒の$2$色で塗り分ける．どのように塗り分けても，ある頂点から反対側の頂点まで同色の辺のみを通って行く道が存在することを示せ．（小泉）
\end{prob}
\begin{ans}
\end{ans}

\begin{prob}[\Star \Star \Star]
トーラスに$7$次完全グラフが埋め込めることを示せ（洞)
\end{prob}
\begin{ans}
$I=(2-\omega)\subset \mathbb{Z}[\omega] \subset \mathbb{C}$なる格子を考えると，
$\mathbb{F}_{7}\cong \mathbb{Z}[\omega]/I \hookrightarrow \mathbb{C}/I$.

(トポスでの初出題: 2024.4/13)
\end{ans}

\section{極限}
\begin{prob}[\Star \Star \Star]
    $x>0$に対し，$x,x^x,x^{x^x},\dots$の極限を$x^{x^{x^{\iddots}}}$と書く．以下の$2$つの問題を考える：
    \begin{enumerate}
        \item $x^{x^{x^{\iddots}}}=2$となる$x$は何か？
        \item $x^{x^{x^{\iddots}}}=4$となる$x$は何か？
    \end{enumerate}
    (1)は$x^{x^{x^{\iddots}}}=x^{(x^{x^{\iddots}})}=x^2=2$より$x=\sqrt{2}$となるように思える．(2)も同様に$x^4=4$より$x=\sqrt{2}$となるように思える．しかしそうすると$\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\iddots}}}$は$2$でもあり$4$でもあることになってしまう．どこが間違っているか？
\end{prob}

\begin{prob}[\Star \Star \Star \Star \Star]
    \[
    \lim_{n \to \infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}
    \]
    を求めよ. 
\end{prob}


\section{三角関数}
\begin{prob}[\Star \Star \Star ]
次の値を求めよ.
\begin{enumerate}
    \item $\sin(\pi/5)/\sin(2\pi/5)$を求めよ.(正解：$=(1+√5)/2$)
    \item $\sin(\pi/13)\sin(3\pi/13)\sin(4\pi/13)/\sin(2\pi/13)\sin(5\pi/13)\sin(6\pi/13)$を求めよ. (正解：$(-3+√13)/2$)
\end{enumerate}
（トポスでの初出題：2018.6.30/出典：おそらくRogers-Ramanujan連分数との関連で中澤が出題/背景・関連：類数公式, Rogers-Ramanujan連分数 ）
\end{prob}

\begin{prob}[\Star \Star \Star] 
\,
    \begin{enumerate}
    \item
        $2$次元空間内で長さ$1$の棒を壁にたてかけるとき, 
        棒の中心の描く軌跡はどうなるか？
        すなわち$xy$平面上に長さ$1$の線分を 
        線分全体が$\mathbb{R}_{\ge0} \times \mathbb{R}_{\ge0}$に
        含まれるように配置するとき, 
        線分の中点が存在しうる範囲(の境界)を求めよ. 
    \item
        $3$次元空間内で半径$1$の円板を部屋の隅にたてかけるとき, 
        円板の中心の描く軌跡はどうなるか？
        すなわち$xyz$空間上に半径$1$の(厚みのない)円板を 
        円板全体が$\mathbb{R}_{\ge0} \times \mathbb{R}_{\ge0} \times \mathbb{R}_{\ge0}$に
        含まれるように配置するとき, 
        円板の中心が存在しうる範囲(の境界)を求めよ. 
    \item
        $n$次元で同様の問題を考えるとどうなるか？
    \end{enumerate}
\end{prob}

\section{微積分}

\begin{prob}[\Star \Star]
    $1$以上の自然数$n$について
    \[
    \lim_{n \to \infty}e^{-n}\sum_{k=0}^{n}\frac{n^k}{k!}
    \]
    を求めよ.
\end{prob}

\begin{prob}[\Star \Star]
    $1$以上の自然数$n$について
    \[
    \int_0^{\frac{\pi}{2}} \frac{(\sin{x}-1)^n}{(\sin{x}+1)^n} dx
    \]
    を求めよ.
\end{prob}

\begin{prob}[？]
    \[
    \sum_{0 < m \leq n <N}\frac{1}{(N-m)n(n-x)}+ \sum_{0 < m < n <N}\frac{1}{n(n-x)(m-x)}=\sum_{0 < m <N}\frac{1}{n^2(n-x)}
    \]（出典：おそらく参加者の渡邉大貴さん）
\end{prob}


\begin{prob}[\Star \Star]
    $I_m=\displaystyle\int_0^{\frac{\pi}{2}} \sin^m \theta d\theta$
    とする．\\
    \begin{enumerate}
    \item $I_m=m(I_{m-1}-I_{m+1})$を示せ．\\
    \item $\lim_{m \to \infty} \sqrt{m}I_m$を求めよ．\\
    \item $I_{2m-1} < \displaystyle\int_0^{\infty} \exp{-mt^2}dt  < I_{2m-2}$を示せ．\\
    \item $\displaystyle\int_{-\infty}^{\infty} \exp(-t^2)dt= \int_0^{\infty} \exp(-mt^2)dt$を用いて、$\displaystyle\int_{-\infty}^{\infty} \exp(-t^2)dt$を求めよ．（出典：wikipedia）（中澤）
    \end{enumerate}
\end{prob}

\begin{prob}[\Star \Star \Star \Star ]
\begin{align*}
\int_{0}^{\infty}\frac{\cos(x)}{1+x^2}dx     
\end{align*}
を求めよ.（トポスでの初出題：2022.11.26/出典：湯澤くんの問題を神田さんが修正/背景・関連：複素解析, Fourier変換 ）
\end{prob}

\begin{prob}[\Star \Star \Star]
    次の値を求めよ
    \[ \lim_{n\to \infty} \frac{1}{n^2}\sum_{k=1}^{n} {n \% k}\]
    ここで，$n \% k$は$n$を$k$で割ったあまりである．
\end{prob}
\begin{ans}
    $n \% k$を床関数で表現し，区分求積する．
\end{ans}

\begin{prob}[\Star \Star]
    (1)$\displaystyle \int_0^{\log 2}x(2-3x)e^xdx$の値を求めよ． (2) (1)を用いて$\log 2>\dfrac{2}{3}$を示せ．（小泉）
\end{prob}
\begin{ans}
    (1) $-6(\log 2)^2+16\log 2-8$. (2) $t=\log 2\leq \dfrac{2}{3}$と仮定すると，(1)の被積分関数は積分区間内で正の値を取るので，(1)の答えは正でなければならない．一方，(1)の答えは$-6t^2+16t-8=-(3t-2)(2t-4)$であり，これは$t\leq \dfrac{2}{3}$において$0$以下なので矛盾する．
\end{ans}




\section{初等幾何}
\begin{prob}[\Star \Star]
(1)正方形$ABCD$において，辺$BD$上に点$P$をとり，$AP$と$BD$の交点を$Q$とする．この時，$AQ:QP=AB:BP$となることを示せ．\\
(2)折り紙を3等分せよ．\\
(3)折り紙を5等分せよ．\\
(4)折り紙を7等分せよ．
\end{prob}
\begin{ans}
(1)三角形$ADQ$と三角形$PQB$が相似であることから， $AQ:QP=AD:BP=AB:BP$となる．\\
(2)(1)より$P$を$BC$の中点に取れば，$AQ:QP=2:1$．よって辺$DC$が点$Q$上に来るように平行に折り返せばよい．\\
(3)$P$を$AB:BP=4:1$となるように取れば良い．\\
(4)$P$を$AB:BP=4:3$となるように取れば良い．\\
\end{ans}

\begin{prob} [\Star \Star \Star]
三角形$ABC$の内部に点$D$があり,
直線$AD$と$BC$は垂直に交わっている.
$\angle BAD= 60^{\circ}$,
$\angle CAD= 40^{\circ}$,
$\angle ACD= 30^{\circ}$,
$\angle DCB= 20^{\circ}$のとき,
$\angle ADB$を求めよ.
\end{prob}

\begin{prob}[\Star \Star \Star \Star \Star]
\textbf{理不尽な定規}とは, 
以下のように平面上に線分を書き込む道具である. 
\[
\text{距離が$1$以下の異なる$2$点を選ぶと, 
その$2$点を通る長さ$1$以上$2$以下の線分がランダムに描かれる}
\]
平面上の任意の$2$点に対し, 
理不尽な定規を複数回用いることでそれらを結ぶ線分を作図できることを示せ. 
(神田)
\end{prob}

\begin{prob}[\Star]
    平面上に$2$つの円$C_1$と$C_2$と点$P$がある. 
    円$C_1$上に点$P_1$, 
    円$C_2$上に点$P_2$をとることで三角形$PP_1P_2$を正三角形にしたい. 
    $P_1$と$P_2$をどのように作図すればよいか？
    ただしこのような点の存在はわかっているものとする. 
\end{prob}






\section{確率論}
\begin{prob}[\Star]
    \(1/n\)の確率で当たりが出るガチャを\(n\)回引いたとき，少なくとも1回当たりが出る確率\(P_n\)はいくらか．
    また，\(\lim_{n \to \infty} P_n\)を求めよ．
\end{prob}
\begin{prob}[\Star \Star \Star ]
2次元ランダムウォークの再帰確率を求めよ.（トポスでの初出題：2019.10.26/出典：おそらく湯山さんの出した問題がトポス内で発展/背景・関連：母関数 ）
\end{prob}
\begin{prob}[\Star \Star \Star \Star ]\label{coupon}
$n$種類の異なるクーポンがあるとき, 各種類のクーポンを1回以上引くまでに, 何回クーポンを引けば良いか?期待値を求めよ（クーポンコレクター問題）
\end{prob}
\begin{prob}[\Star \Star \Star \Star \Star]
問題\ref{coupon}の答えを$E_n$とする．$\lfloor E_n\rfloor$回以下で各種類のクーポンを1回以上引ける確率を$P_n$とするとき，$\lim_{n\to \infty}P_n$を求めよ．（小泉）
\end{prob}
\begin{ans}
$e^{-e^{-\gamma}}=0.57037\cdots$.
\end{ans}




\section{母関数}

\begin{prob}[\Star \Star \Star \Star]
組体操のピラミッドにおける負荷は，以下の図のようになる
% $1\leq k \leq n$について，$a_{n,k}$をピラミッドにおける上から$n$段目の左から$k$番目の人の負荷を表す．$a_{1,1}$は$0$で，$a_{2,1}=a_{2,2}=0$
\[
\begin{tikzcd}[column sep= tiny]
&&&0\ar[rd]\ar[ld]&&&\\
&&\frac{1}{2}\ar[rd]\ar[ld]&&\frac{1}{2}\ar[rd]\ar[ld]&&\\
&\frac{3}{4}\ar[rd]\ar[ld]&&\frac{6}{4}\ar[rd]\ar[ld]&&\frac{3}{4}\ar[rd]\ar[ld]&\\
\frac{7}{8}&&\frac{17}{8}&&\frac{17}{8}&&\frac{7}{8}\\
\end{tikzcd}
\]
このとき，奇素数$p$について$p$行目の数(の分子)は$p$で割り切れることを示せ．
    (出典: エレガント)
\end{prob}
\begin{ans}
    $n$行目の負荷を$a_1,a_2,\dots,a_n$とし，$\mathbb{Z}[\frac{1}{2}]$係数多項式$L_n$を
    $$
    L_n = a_1x^{n-1}+a_2x^{n-2}+\dots+a_n
    $$
    により定める．例えば
    \begin{itemize}
        \item $L_{1} = 0$,
        \item $L_{2} = \frac{1}{2}x +\frac{1}{2}$,
        \item $L_{3} = \frac{3}{4}x^2 +\frac{6}{4}x + \frac{3}{4}$,
        \item $L_{4} = \frac{7}{8}x^3 +\frac{17}{8}x^2 + \frac{17}{8}x + \frac{7}{8}$
    \end{itemize}
    である．
    すると，$n-i$行目の人からの$L_n$への寄与は$\left(\frac{x+1}{2}\right)^i(x^{n-i-1}+x^{n-i-2}+\dots+x+1)$と表せるので
    \begin{align*}
        L_n=\sum_{i=1}^{n-1} \left(\frac{x+1}{2}\right)^i\cdot\frac{x^{n-i}-1}{x-1}
    \end{align*}
    と記述できる．
    等比数列の和の公式を使うと
     \begin{align*}
        (x-1)L_n&{}=x^n\sum_{i=1}^{n-1} \left(\frac{x+1}{2x}\right)^i-\sum_{i=1}^{n-1}\left(\frac{x+1}{2}\right)^i\\
        &{}=\frac{2x^{n+1}}{1-x}\left(\left(\frac{x+1}{2x}\right)^n-\frac{x+1}{2x}\right)-\frac{2}{x-1}\left(\left(\frac{x+1}{2}\right)^n- \frac{x+1}{2}\right)\\
        &{}=\frac{2}{1-x}\left(\frac{x(x+1)^n}{2^n}-\frac{x^n(x+1)}{2}+\frac{(x+1)^n}{2^n}-\frac{x+1}{2}\right)\\
        &{}=\frac{2(x+1)}{1-x}\left(\frac{(x+1)^n}{2^n}-\frac{x^n+1}{2}\right)
    \end{align*}
    と計算できる．$n$が奇素数$p$であるとき，$(x+1)^p\equiv x^p+1\pmod p$および$2^p\equiv 2\pmod p$が成り立つので，右辺はmod $p$で$0$となる．
\end{ans}


\begin{prob}[\Star \Star \Star ]
$m$ を $2 \leq m \leq 9$ をみたす自然数とする.  $xy$ 平面上の点のうち,  $x$ 座標と $y$ 座標がともに整数のものを格子点という.  $x$ 座標と $y$ 座標がともに $-1,0,1$ のいずれかである 9 個の格子点を考える. これらの格子点から異なる $m$ 個の格子点を選ぶ. 選ばれた $m$ 個の格子点のうち, どの異なる2点の中点も格子点とならないような $m$ 個の格子点を選ぶ選び方の総数を $a_m$ とおく.  $a_m\;(2 \leq m \leq 9)$ を求めよ. （トポスでの初出題：2022.11.12/出典：［2016 神戸大・理（後）］）
\end{prob}
\begin{ans}
2個の格子点の中点が格子点であることと, その2点の$x$座標と$y$座標が$\mod 2$で等しいことは同値. 問題文にある9個の格子点をこれにより分類すると, $(0,0)$と$(1,0),(-1,0)$と$(0,1),(0,-1)$と$(1,1),(-1,1),(1,-1),(-1,-1)$の4つの同値類に分類され, 同値類の位数はそれぞれ$1,2,2,4$である. $m$個の点について, どの異なる2点の中点も格子点とならないことと, それぞれの点が全て別の同値類に所属していることが同値であることから, 
\begin{align*}
(1+x)(1+2x)(1+2x)(1+4x)=1+9x+28x^2+36x^3+16x^4
\end{align*}
の$m$次の係数が求める$a_m$である. 
\end{ans}

\begin{prob}[\Star \Star \Star ]
    $1,2,\cdots, 100$と書かれた$100$個のボールを$1,2,3,4,5,6$と書かれた$6$個の箱に偶数個ずつ入れる方法はいくつあるか？（小泉）
\end{prob}

\begin{ans}
    指数型母関数（species）を考えると$\left(\dfrac{e^x+e^{-x}}{2}\right)^6$の展開係数を求める問題になる．二項定理で展開する．
\end{ans}

\begin{prob}[\Star\Star\Star]
    $F_n$をフィボナッチ数($F_0=0, F_1=1, F_2=1, \dots$)とするとき，
    \[
    \sum_{n=0}^{\infty} \frac{{F_n}^2}{3^n}
    \]
    を求めよ．
\end{prob}
\begin{ans}
    初出:9/21 hsjoisさん．母関数を用いると，$1.5$であることがわかる．
\end{ans}





\section{不等式}
\begin{prob}[\Star \Star ]
正の実数$a,b,c$について, 
\[
\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}
\geqq \frac{3}{2}
\]
を示せ. 
また等号成立条件も求めよ. 
(神田)
\end{prob}

\begin{prob}[\Star \Star ]
\[
sym (a(a+b)(a+b+c))^{-1}=abc^{-1}
\]
を示せ. 
(神尾)
\end{prob}



\begin{prob}[\Star \Star \Star ]
$a_{mn}=a_{m} + a_{n}$を満たす実数列$(a_1,a_2,\cdots)$を全て求めよ．
\end{prob}
\begin{ans}
   $a_{p}$（$p$は素数）について値を決めればいい．漸近的な評価をすると，$\log$の定数倍になる．（背景: シャノンエントロピー）
\end{ans}





\section{社会と数学}
\begin{prob}[\Star]
三角関数が社会で使われている例を調べよう
\end{prob}
\begin{ans}
信号処理の分野，音声処理，音響工学，振動工学，通信工学，制御工学，電気工学
\end{ans}

\begin{prob}[\Star]
googleやyahooの検索ページに行って，URLバーの南京錠マークをクリックし，証明書→詳細な情報とクリックして，何の暗号が使われているかを確かめよう．
\end{prob}
\begin{ans}
RSA暗号や楕円曲線暗号が使われている．
\end{ans}

\begin{prob}[\Star]
数学以外の分野や実社会において，行列を応用している例を一つ挙げ，その内容について簡単に説明せよ．（安福）
\end{prob}

\begin{ans}
（解答例）

ポートフォリオ（金融商品の組み合わせ）選択への応用

ページランク（Googleにおいて検索語に対する適切な結果を得るために用いられている，ウェブページの重要度を決定するアルゴリズム）の話

画像処理の話

コンピューター工学

ゲームの描画処理や3Dモデルへの応用

AmazonやYoutubeなどで用いられている推薦システムのアルゴリズムの話

半導体の話

人工知能や機械学習の話

物理学，力学，量子力学

人口減少社会の解析

CT（コンピュータ断層撮影）の話
\end{ans}

\begin{prob}[\Star]
数学以外の分野や実社会において，グラフ理論を応用している例を一つ挙げ，その内容について簡単に説明せよ．（安福）
\end{prob}

\begin{ans}
（解答例）

オイラーグラフを用いた，道路清掃者や除雪車の巡回の話

深さ優先探索と強連結を用いた美術館と博物館の順路決めや立体駐車場の道路システムの話

ダイクストラ法をカーナビに用いている話

ネットワーク最適化の話

研修医の病院配属やドナーと患者の割り当て（Gale-shapleyのアルゴリズム）

基盤回路やハードディスクの制御基板など（平面グラフ）
\end{ans}

\begin{prob}[\Star\Star\Star]
    数学以外の分野や実社会において，数学基礎論を応用している例を一つ挙げ，その内容について簡単に説明せよ．
\end{prob}
\begin{ans}
    例: 実閉体(RCF)の理論における量化記号消去(QE)のアルゴリズム(CAD)が，東ロボくんが数学のテストを解くために用いられた．
\end{ans}


\end{document}