東京大学 工学系研究科 2011年8月実施 数学 第6問

标签：

• Tokyo-University
• Absorbing-Random-Walk
• Ramsey-Theory

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

I. 粒子は原点から出発し、各ステップで独立に、等確率 $1/3$ で $-1,0,+1$ だけ数直線上を移動する。

1. $n$ ステップ後の位置の平均と分散を求めよ。
2. 正の整数 $L$ に対し、粒子は $\pm L$ に達すると運動を終了する。整数位置 $-L<k<L$ から終了までの期待ステップ数を $e(k)$ とする。$e(k-1),e(k),e(k+1)$ の差分方程式を示せ。
3. 解が $k$ の二次式であることと $e(-L)=e(L)=0$ を用いて、$e(k)$ を求めよ。

II. 完全グラフ $K_n$ の辺に二通りのラベルを付け、それぞれ実線と点線で表す。

1. 同じラベルの三辺を持つ $K_3$ を含まない $K_5$ のラベル付けを示せ。
2. $K_6$ を用いて「六人集まれば、互いに知り合っている三人組か、互いに見知らぬ三人組が必ず存在する」ことを証明せよ。知人関係は双方向とする。
3. 実線の $K_3$ と点線の $K_4$ のどちらも含まない $K_8$ のラベル付けを示せ。

题目描述

I. 粒子从数轴原点出发，每一步独立地以概率 $1/3$ 分别移动 $-1,0,+1$。

1. 求 $n$ 步后位置的均值与方差。
2. 给定正整数 $L$，粒子到达 $\pm L$ 即停止。令 $e(k)$ 为从整数位置 $-L<k<L$ 出发到停止的期望步数，建立 $e(k-1),e(k),e(k+1)$ 的差分方程。
3. 已知解为 $k$ 的二次式，利用 $e(-L)=e(L)=0$ 求 $e(k)$。

II. 完全图 $K_n$ 的每条边涂为两种标签，分别画为实线和虚线。

1. 给出 $K_5$ 的一种标记，使其不含三条边同一标签的 $K_3$。
2. 利用 $K_6$ 证明：任意六个人中，必有三人互相认识，或三人互不认识。认识为双向关系。
3. 给出 $K_8$ 的一种标记，使其既不含全为实线的 $K_3$，也不含全为虚线的 $K_4$。

Kai

I

各増分 $X_j$ の期待値は $0$、分散は $2/3$ である。独立性より、

$$\boxed{\mathbb E\sum_{j=1}^nX_j=0,\qquad \operatorname{Var}\sum_{j=1}^nX_j=\frac{2n}3}.$$

最初の一歩で場合分けすると、

$$e(k)=1+\frac{e(k-1)+e(k)+e(k+1)}3, \quad\Longrightarrow\quad \boxed{e(k+1)-2e(k)+e(k-1)=-3}.$$

$e(k)=Ak^2+Bk+C$ とおくと $2A=-3$ であり、境界条件を用いて、

$$\boxed{e(k)=\frac32(L^2-k^2)}.$$

II

1

頂点を順に $0,1,2,3,4$ とし、五角形の辺を実線、五本の対角線を点線とする。 各ラベルの辺はそれぞれ五角形を構成し、三角形を含まない。

2

頂点 $v$ を一つ取る。五本の隣接辺のうち少なくとも三本は同じラベルである。$a,b,c$ への三辺を実線としてよい。 $a,b,c$ 間に実線があれば $v$ と実線三角形を作る。なければ三辺すべてが点線である。 ラベルを交換しても同様であり、命題が示された。

3

頂点を法 $8$ で番号付けし、差が $\pm1$ または $4$ の辺を実線、残りを点線とする。すなわち八角形の辺と四本の対径線を実線とする。 各頂点の三つの実線隣接頂点間には実線がないので、実線三角形は存在しない。

点線の $K_4$ があれば、その四頂点は八角形上で互いに隣接してはならない。 可能なのは $\{0,2,4,6\}$ と $\{1,3,5,7\}$ だけだが、どちらも実線の対径辺を含み、矛盾する。