# 千葉大 融合理工学府 数学情報科学専攻 数学・情報数理学コース 専門科目（A0・A問題・B問題） 2022年度 院試 過去問 解答例・解説

> 千葉大 融合理工学府 数学情報科学専攻 数学・情報数理学コース 専門科目（A0・A問題・B問題） 2022年度の院試過去問、18項目の解説。大問1問の途中式・最終答を無料公開。解答PDFは6年分収録で3,200円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a/2022
- 解答・解説PDF: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a（税込3,200円、6年分を収録）
- 最終更新: 2026-11-14
- 公式の過去問: https://www.se.chiba-u.jp/admission/past/1st_dr/mi.html（2025年10月入学／2026年4月入学、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — A0 写像の像・逆像と濃度の比較

### 解説

**方針**

像と逆像の性質を確認する典型問題。$A\subset f^{-1}(f(A))$ と $f(f^{-1}(B))\subset B$（一般に等号は成立しない）の方向を念頭に置く。
(II) は Cantor の定理。論法は対角線論法であることを必ず明記する。

**典型ミス**

(a) で $\subset$ と $\supset$ のどちらが偽かを取り違える例が多い。一般的に成り立つ包含関係 $A_1\cup A_2\subset f^{-1}(f(A_1)\cup f(A_2))$ は**逆向き**であることに注意。
(d) で「単射の逆写像は像でしか定義できない」点を見落とすと議論が破綻する。

**試験で書くべきポイント**

(II)(2) は「もし全単射が存在したら」と背理法を立て、$D$ を定義し、$F(d)=D$ なる $d$ について $d\in D\Leftrightarrow d\notin D$ の矛盾を導出する流れを丁寧に書く。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第2問 — A1 双線形形式の Gram 行列と正定値性

### 解説

**方針**

Gram 行列 $A=((v_i,v_j))$ を扱う典型問題。座標表示 $v=\sum c_j v_j$ で $(v,w)=c^{\top}A d$ と表せることを最初に確認すれば見通しがよい。
正定値の判定はシルヴェスタの主小行列式判定法、対角化は Gram--Schmidt が定石。

**典型ミス**

(2) で「実対称ゆえ固有値は実」を言わずに正定値性だけで議論すると、固有ベクトルが複素のとき詰まる。
(4) で $w_i$ を求めるだけで $(w_i,w_j)$ の値を提示し忘れがち。対角成分まで書くこと。

**試験で書くべきポイント**

(1) は「$A$ の核 $\Rightarrow$ $(,)$ の右核」を双線形性 $(v_i,\sum c_j v_j)=\sum c_j a_{ij}$ で結びつける。
(3) は $n$ が整数であることを忘れず、$\sqrt 2<2$ より $n=2$ が最小と明記する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第3問 — A2 級数の収束 (隣接差・絶対収束・対数交代級数)

### 解説

**方針**

(1) は「等差級数の差」が $\delta$ 以上なので $a_n$ はおよそ等差列、$\sum 1/a_n^2$ は $\sum 1/n^2$ と比較可能。
(2) は $\ell^2$ ノルムと $1/n\in\ell^2$ の Cauchy--Schwarz が定石。
(3) は $H_n/(\log n)^2\sim 1/\log n\to 0$ で交代級数の Leibniz 判定。

**典型ミス**

(1) で「$a_n$ が正である」を仮定して比較してしまうと、初期に $a_1

**試験で書くべきポイント**

(2) は絶対収束を示すので $\sum |b_n|/n$ が有限であることを論じる。
$\sum b_n^2$ と $\sum 1/n^2$ の積（Cauchy--Schwarz）でひとことで処理。
(3) は調和数 $H_n$ を「$\log n+\gamma+O(1/n)$」と漸近展開しておくと、(i)(ii) の評価が見通せる。

### 解答

- $a_1$ は固定値で、漸化式 $a_{n+1}\ge a_n+\delta$ を繰り返すと
$a_{n+1}\ge a_1+n\delta$。$a_n\to\infty$ で、十分大きい $n$ について $a_n>0$。
$a_n$ のうち負のものの個数は有限個（高々 $\lceil(-a_1)/\delta\rceil+1$ 個程度）なので、その有限項を除いた残りで議論すれば十分。
ある $N_0$ があって $n\ge N_0$ ならば $a_n\ge\delta(n-N_0)+a_{N_0}\ge \delta(n-N_0)$ (取り直して $a_{N_0}\ge 0$ としてよい)。
よって $n\ge N_0+1$ で

$$
a_n^2\ge \delta^2(n-N_0)^2,\quad \frac{1}{a_n^2}\le\frac{1}{\delta^2(n-N_0)^2}.
$$

$\sum_{n\ge N_0+1}\dfrac{1}{(n-N_0)^2}=\sum_{k=1}^{\infty}\dfrac{1}{k^2}
- Cauchy--Schwarz の不等式（数列版）より、有限和に対して

$$
\sum_{n=1}^{N}\frac{|b_n|}{n}=\sum_{n=1}^{N}|b_n|\cdot\frac{1}{n}
  \le \Bigl(\sum_{n=1}^{N}b_n^2\Bigr)^{1/2}\Bigl(\sum_{n=1}^{N}\frac{1}{n^2}\Bigr)^{1/2}.
$$

仮定より $\sum b_n^2$ は収束、また $\sum 1/n^2$ も収束。したがって右辺は $N$ について有界であり、
左辺は単調増加かつ有界、つまり $\sum_{n=1}^{\infty}\dfrac{|b_n|}{n}
- 部分和を $H_n=\sum_{k=1}^{n}\dfrac{1}{k}$ とおき、$c_n=\dfrac{H_n}{(\log n)^2}$ ($n\ge 2$) と書く。
示すべきは $\sum_{n=2}^{\infty}(-1)^n c_n$ の収束。
Leibniz の交代級数判定法を適用するために
(i) $c_n\to 0$、(ii) $c_n$ が（十分大きい $n$ で）単調減少、を示す。
**(i)** $H_n=\log n+\gamma+o(1)$ (Euler--Mascheroni)。よって
$c_n=\dfrac{\log n+\gamma+o(1)}{(\log n)^2}=\dfrac{1}{\log n}+\dfrac{\gamma+o(1)}{(\log n)^2}\to 0$ ($n\to\infty$)。
**(ii)** 単調減少性の検証。$g(x)=\dfrac{H(x)}{(\log x)^2}$ (連続版、$H(x)=\int_1^x\frac{1}{t}dt+\gamma+\cdots$ の近似 $\log x+\gamma$) を取れば
$g'(x)=\dfrac{1/x\cdot(\log x)^2-(\log x+\gamma)\cdot 2\log x/x}{(\log x)^4}
=\dfrac{\log x-2\log x-2\gamma}{x(\log x)^3}=\dfrac{-\log x-2\gamma}{x(\log x)^3}

### 最終答

(1) $a_n\ge a_1+(n-1)\delta$ より $|a_n|\to\infty$ かつ $|a_n|=O(n)$、$\sum 1/a_n^2\le\mathrm{const}\sum 1/n^2<\infty$。(2) Cauchy--Schwarz で $\sum |b_n|/n\le(\sum b_n^2)^{1/2}(\sum 1/n^2)^{1/2}<\infty$、絶対収束。(3) Leibniz の判定。$c_n=H_n/(\log n)^2$ は $n\to\infty$ で $0$ に単調減少。

## 第4問 — A3 位相空間の生成と区間のコンパクト性

### 解説

**方針**

(1) は「準開基 $\{1\},\{2,3\},\{3,4\}$ から生成される最小の位相」を反例の母体にする。
有限交わりと任意和で何が作れるかを書き出すのが定石。
(2) は「下方無限を含む集合のみが開」という変則位相を扱う。コンパクト性は端点 $1$ を覆えるかで分かれる。

**典型ミス**

(1)(iv) で「単射 $\Rightarrow$ 連続」と勘違いする例が多い。連続性は**逆像**が開かどうかであって写像の単射性とは無関係。
(2)(ii) で「$(0,1]$ は普通の位相で非コンパクト」と短絡する答案。位相が変わればコンパクト性も変わる。

**試験で書くべきポイント**

(1) は「$\mathcal{O}$ として最小のものを取る」と一文添えて、反例位相の構成を明示する。
(2)(i) は $\widetilde{\mathcal{U}}$ を構成的に列挙し、(ii) は端点 $1$ を含めるには $a>1$ なる $(-\infty,a)$ が必要、その単一被覆で済むことを明記する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第5問 — A4 順序統計量の分布と共分散

### 解説

**方針**

順序統計量の基本: $F_Y(y)=1-(1-F)^n,\ F_Z(z)=F^n$。同時密度は $n=3$ で
$f_{Y,Z}(y,z)=6(z-y)$ ($0

**典型ミス**

(2) で $f_Y$ と $f_Z$ を取り違える、あるいは符号忘れ。$f_Y(y)$ は $y$ が小さいほど大きい（$=3(1-y)^2$）、$f_Z$ は $z$ が大きいほど大きい（$=3z^2$）。
(4) で $Y,Z$ を独立と勘違いして $\mathrm{Cov}=0$ と書く例。$Y\le Z$ なので独立ではない。

**試験で書くべきポイント**

(3) は $(s-r)^3$ の形で $0<r<s<1$ の範囲を明示する。
(4) は同時密度 $6(z-y)$ を導出してから $E[YZ]$ の積分を計算する流れで論理を明確化する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第6問 — A5 Pascal による全順列生成プログラム

### 解説

**方針**

$q(i)$ を「$p[1..i]$ を全部並び替えて $q(0)$ を呼び出す再帰関数」と読み解くのが本筋。
ループ内の「交換 $\to$ 再帰 $\to$ 元に戻す」が再帰的並び替えアルゴリズム（Heap 法）の典型。

**典型ミス**

(1) で出力順を勘違いする。for k:=i downto 1 なので、$k$ は大きい方から小さい方へ動くこと、また $k=i$ のときは交換しても変化しない（$p[i]$ と $p[i]$ の交換）ことに注意。
(2) で「すべての並び替えが出る」だけで終わらせず、**重複なく**と $p$ が元に戻ることを帰納法で示す。

**試験で書くべきポイント**

帰納法仮定 $P(m)$ を「$q(m)$ は $p[1..m]$ のすべての並び替えを生成し、終了時 $p$ を元に戻す」と二条件で書く。
基本ステップ $m=0$、帰納ステップで「ループ内の各 $k$ で $p[m]$ に位置 $k$ の元が来る $\to$ 残りを $q(m-1)$ で全並び替え $\to$ 元に戻す」を明確に書く。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第7問 — B1 置換群と対角群、Sylow 部分群

### 解説

**方針**

$H_1$ は $S_3$ の置換行列実現、$H_2$ は $(\mathbb{Z}/3)^3$ の対角埋め込み。$H$ は半直積 $H_2\rtimes S_3$。
正規性は「置換による共役で対角成分が並び替わるだけ」で示せる。
Sylow 3 部分群は $H_2$ と「$3$ 巡回 $(1\,2\,3)$」を組み合わせる。

**典型ミス**

(2) で $\omega$ が原始 $3$ 乗根である（位数 $3$）ことを使い忘れて $|H_2|$ を間違える。
(5) で $|H|=162$ の Sylow 3 部分群の位数を $27$ と誤る（$162=2\cdot 81$ ゆえ $81$）。

**試験で書くべきポイント**

(3) は具体的に $\sigma D(a,b,c)\sigma^{-1}=D(a_{\sigma^{-1}(1)},\dots)$ を書き、$H_2$ に留まることを明示。
(5) は $81=3^4$ と $H_2$ (位数 $27$) を見て、追加の $3$ を「3 巡回置換」から取る、という発想を述べる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第8問 — B2 唯一の素イデアルを持つ環の冪零イデアル

### 解説

**方針**

冪零イデアル $N$ は任意の可換環で素イデアルの共通部分（$\sqrt{(0)}$）に等しい。
本問は素イデアルが一つのため $N=\mathfrak{p}$ と直結する。
(2) は局所環の判定（極大が一つ $\Leftrightarrow$ 局所環）と単元判定の組合せ。

**典型ミス**

(1) で $(x+y)^{m+n}$ の二項展開を使わず適当に処理する。
(3) で $\mathfrak{p}\subset N$ の証明を「素ゆえ $x^n=0\Rightarrow x\in\mathfrak{p}$」と取り違える（これは逆方向）。
正しくは $x\in\mathfrak{p}$ のときに $x^n=0$ を導く必要があり、$S=\{x^n\}$ の局所化と素イデアルの存在性で示す。

**試験で書くべきポイント**

(2) は「素 $\Rightarrow$ 極大」の理由（$\mathfrak{p}$ は唯一だから）と「局所環の単元判定」を段階的に書く。
(3) は $\sqrt{(0)}=\bigcap\mathfrak{q}$ の事実を引用し、$R$ の素イデアルが $\mathfrak{p}$ のみであることに帰着する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第9問 — B3 Monge グラフの Gauss 曲率と Gauss 写像

### 解説

**方針**

Monge グラフの曲率公式 $K=(f_{xx}f_{yy}-f_{xy}^2)/(1+f_x^2+f_y^2)^2$ は記憶しておく。
原点では $f_x=f_y=0$ なので $K(0)=f_{xx}(0)f_{yy}(0)-f_{xy}(0)^2$ と簡潔。
Gauss 写像 $e=n\circ p$ について、$de=-S\circ dp$（Weingarten）と $\det S=K$ は基本。

**典型ミス**

(1) で $K$ を「$\det dn/\det dp$」と書いて、$p_x\times p_y$ の向きを混同し符号間違いをする。
$n$ の向きを $z$ 成分が正と固定していることを忘れない。

**試験で書くべきポイント**

(3) は $2$ 次元線形変換でのベクトル積の挙動 $S(u)\times S(v)=\det S\cdot(u\times v)$ を理由とともに書く。
原点で第一基本形式が単位行列に近いことから、(2) の計算が単純化されることに触れると論理が明快。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第10問 — B4 ホップ絡み目補空間とホモロジー

### 解説

**方針**

$S^3$ 内の Hopf 絡み目補空間が torus にホモトピー同値という基本事実を、半径補正による強変形レトラクトで具体的に示す。
$(4)$ は $N$ が $K$ 上にあることに気づくのが鍵。Alexander 双対性または「開ソリッドトーラス $-$ 一点」の幾何的考察で計算可能。

**典型ミス**

(1)(2) で「$z\ne 0$ かつ $w\ne 0$」の条件を使い忘れる。
ホモトピーが well-defined であるために分母が零でないことを確認すること。
(4) で $N$ が $K$ 上にあることを見落とすと、$J\cup\{N\}$ を「絡み目に点を付け足す」と誤解する。

**試験で書くべきポイント**

(1)(2) の強変形レトラクトは、目的の部分集合上で恒等となる連続族 $F_t$ を明示する。
(4) は $J\cup\{N\}\simeq S^1\sqcup\{*\}$ を確認した後 Alexander 双対 $\tilde H_q(S^3-X)\cong\tilde H^{2-q}(X)$ を引用するのが最短。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第11問 — B5 半円弧上の複素積分と実積分

### 解説

**方針**

$\sin x/x$ の Dirichlet 積分を求める古典的な複素積分問題。
半円輪郭で $e^{iz}/z$ を積分し、(1) で小円積分、(2) で大円積分の処理を確立してから (3) で組み立てる。

**典型ミス**

(2) で Jordan の不等式 $\sin\theta\ge 2\theta/\pi$ を使わず、$|e^{ire^{i\theta}}|\le 1$ で済ませて $\pi$ になり $\to 0$ を示せない例が多い。
$\sin\theta$ の下からの線形近似を必ず使う。

**試験で書くべきポイント**

(3) で $e^{iz}/z$ の輪郭が「閉曲線で内部に特異点なし」（$z=0$ は除外する小半円があるため）と明記する。
$\int_{-R}^{-\varepsilon}e^{ix}/x dx$ を $-\int_\varepsilon^R e^{-ix}/x dx$ に置換する計算を丁寧に書く。
最終的に $\sin x/x$ が偶関数より $2\int_0^\infty$ として $\pi/2$ を得る論理を示す。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第12問 — B6 線形 ODE の解、軌道の同値関係と相図

### 解説

**方針**

$2\times 2$ 線形系の固有値・固有ベクトル分解。
鞍点（$\lambda_1>0>\lambda_2$）では安定多様体・不安定多様体の $4$ つの半直線と、$4$ 象限の一般軌道があり、計 $9$ 個の同値類。

**典型ミス**

(2) で「軌跡同士が交わらない」事実（解の一意性）を使わずに同値関係を示そうとして詰まる。
線形 ODE では大域解が一意で、軌跡同士は disjoint または完全一致のいずれか。

**試験で書くべきポイント**

(3) は鞍点の相図を「$v_1$ の方向に発散、$v_2$ の方向に収束」と図示し、安定・不安定多様体の $4$ 半直線と原点・$4$ 象限の一般軌道で計 $9$ 個の同値類があることを明示する。
代表系は各クラスから一点ずつ取ればよい。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第13問 — B7 数列空間のノルム性、完備性と双対表現

### 解説

**方針**

(2) $\ell^1$ の完備性は古典的: 各点極限を取って Fatou の補題で評価する。
(3) 有限台空間 $Y$ 上の有界線形汎関数（$\sup$ ノルムで評価）を、$\ell^1$ ベクトル $g$ で双対的に表現する。
これは $(c_0)^*=\ell^1$ の特殊な場合（$Y$ は $c_0$ の稠密部分空間）。

**典型ミス**

(2) で「各点極限が $\ell^1$ に属する」だけ示してノルム収束を示し忘れる。
(3) で $g$ の $\ell^1$ 性を有限和の **選択的符号付き合成** $f=\sum\alpha_j e_{n_j}$ で示す技巧を見落とす。
任意有限部分和の上界 $\le 1$ を強調する。

**試験で書くべきポイント**

(3) では $\Phi$ の有界性条件 $|\Phi(f)|\le\|f\|_\infty$（$\ell^\infty$ ノルム）を使うので、$\sup_n|f(n)|$ と書く。
$g\in\ell^1$ を、有限部分和に対する $\Phi$ の値で評価して下から押さえる手法は典型的。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第14問 — B8 i.i.d. ランダムウォーク、停止時刻と Wald の等式

### 解説

**方針**

有界増分の i.i.d. ランダムウォークの基本問題。
(1)(2) は条件付き期待値の独立性公理から自動。
(4) は $\mu\ne 0$ と大数の強法則がポイント、ドリフトがあるので必ず境界を越える。
(5) は Wald の等式（$E(T)

**典型ミス**

(4) で $\mu=0$ のケースの扱いを混乱しがち。本問は $\mu\ne 0$ を仮定しているのでドリフト $\to$ 必ず無限へ。
(5) で「$T

**試験で書くべきポイント**

(5) は $T\wedge n$ で停止し、$n\to\infty$ の極限を取って収束定理を使う流れ。
増分が有界 ($|X|\le C$) なので $|S_{T\wedge n}|\le M+C$ で一様有界、有界収束定理が使えると明示する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第15問 — B9 ベルヌーイ分布の最尤推定と Fisher 情報量

### 解説

**方針**

ベルヌーイの最尤推定の標準問題。
$\widehat p=\bar X$ は不偏・一致・有効すべての性質を持つ理想的な推定量。
Fisher 情報量は $I_1(p)=1/[p(1-p)]$ を覚えておく（または導出 $\log f$ の二階微分の期待値で計算）。

**典型ミス**

(5) の符号: $I(p)=-E[\partial^2\log f/\partial p^2]$ で**マイナス**を忘れない。
あるいは $I(p)=E[(\partial\log f/\partial p)^2]$ と書いて計算しても同じ。

**試験で書くべきポイント**

(6) では「分散 $=$ CRB $\Rightarrow$ 有効」の論理を明示する。
ベルヌーイの場合、$\bar X$ はちょうど効率 $1$ で達成する典型例（指数分布族の MLE は一般に有効）。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第16問 — B10 有限体の原始元によるグラフ

### 解説

**方針**

有限体の原始元の特定が肝。
$\mathbb{Z}/11\mathbb{Z}$ では $(\mathbb{Z}/11)^\times\cong\mathbb{Z}/10$、原始元は $\varphi(10)=4$ 個。
$\mathbb{F}_2[X]/(X^4+X+1)$ は $\mathbb{F}_{16}$ で原始元は $\varphi(15)=8$ 個。

**典型ミス**

原始元を「$0$ や $1$ でない元」と勘違いする例。
**原始元は乗法群の生成元**（位数最大の元）であり、定義は乗法群の位数に等しい位数を持つ元。

**試験で書くべきポイント**

原始元を一つ見つけてから $\gcd(k, n)=1$ の指数すべてで列挙するのが定石。
$11$ では $2$ を、$\mathbb{F}_{16}$ では $\alpha=X\bmod(X^4+X+1)$ を最初の原始元として取る。
グラフの図は頂点を円形に並べて辺を矢印で結べばよい。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第17問 — B11 NFA、ポンピング補題、shuffle 言語の非正則性

### 解説

**方針**

NFA は最小限の状態で構成。受容状態の選び方で $\epsilon$ や $a^n$ の扱いを工夫する。
ポンピング補題の典型適用: $a^p b^p$ を取って $y$ が $a$ のみとなる分解で矛盾を出す。
shuffle 操作は正則性を保たないことの古典的反例 $(ab)^*\to\{a^nb^n\}$ 風（$\mathrm{shuffle}((ab)^*)$ は $a,b$ 同数語）。

**典型ミス**

(1) で $\epsilon\in L_1$ を含めるかどうかの確認。$n=m=0$ で $\epsilon=a^0(ab)^0$ なので $\epsilon\in L_1$、$q_0$ も受容状態にする。
(3) で「shuffle が正則性を保つ」と勘違い。$\#_a=\#_b$ の制約は文脈自由（$a^nb^n$ と同様）であり正則ではない。

**試験で書くべきポイント**

(1) は状態遷移を表で書くか、状態と矢印で図示。状態 $3$ で十分。
(2)(3) は「$|xy|\le p$ より $y$ は $a$ のみ」を明示し、$i=0$ で矛盾を導く流れ。
(3) は具体的な $L=(ab)^*$ を選び、$\mathrm{shuffle}(L)$ が $\{a,b\}$ の同数語と一致することを示す。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

## 第18問 — B12 Scheme によるリスト生成、再帰の停止性

### 解説

**方針**

s1 の意味を「x 以降の整数のうち v に含まれないものを $n$ 個並べる」と読み解くのが鍵。
s2 はこれを直接的に再帰で実現する形。
停止性は「$n$ は単調非増加で、$n$ が変わらない再帰は x が v 内に居るときのみ、x は単調増加」がポイント。

**典型ミス**

(1) で (s0 (+ 4 3) 1) の長さを $4$ と勘違い（正しくは $7$）。
(2) で「x$\in v$ のとき $n$ を減らす」と書いてしまう答案。$n$ はそのまま、x だけ進める。

**試験で書くべきポイント**

(3) は構造帰納で「$n=0$ は基底、$n\ge 1$ で x$\in v$ と x$\notin v$ のケース分け」。
(4) は「$n$ を減らす再帰の回数は $n$ 自身に上から押さえられ、$n$ を減らさない再帰の連続回数は $|v|$ に押さえられる」点を述べる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a

---

出典: 院試hub（https://inshihub.com/exam-solutions/chiba-university/graduate-school-of-science-and-engineering/mathematics-informatics-specialized-a/2022）。引用するときはWeb版のURLを示してください。
