東京工業大学 情報理工学院 数理・計算科学系 2017年8月実施 午前 問C

标签：

• institute-of-science-tokyo
• Binomial-Coefficient

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

以下の図に示すような $n \times m$ の格子を考える．ただし $n \geq m \geq 1$ とする．

ここで，点 $(0, 0)$ から点 $(n, m)$ まで，条件 1 を満たすように隣接する点の間を移動する経路全体の集合を $\mathcal{P}(n, m)$ とする．

• 条件 1: 経路上の全ての点に関して，その右または上の隣接点へのみ移動可能．

有限集合 A に対して |A| は A の濃度 (要素数) を表すものとする．

(1) $|\mathcal{P}(n,m)|$ を求めよ．

$\mathcal{P}(n,m)$ に含まれる経路で，条件 2 を満たす経路全体の集合を $\mathcal{B}(n, m) \subseteq \mathcal{P}(n, m)$ とする．

• 条件 2: ある $a \in \{1, . . . , m\}$ に対して，経路上に点 $(a, a)$ が存在する．すなわち，経路は上図に示した • 印の点を少なくとも 1 つ経由する．

集合 $\mathcal{B}(n,m)$ を $\mathcal{B}_{(0,1)}(n,m) \subseteq \mathcal{B}(n,m)$ と $\mathcal{B}_{(1,0)} \subseteq \mathcal{B}(n,m)$ に分割する．

• $\mathcal{B}_{(0,1)}(n,m): \mathcal{B}(n,m)$ に含まれる経路で，点 $(0, 1)$ を通る経路全体の集合．
• $\mathcal{B}_{(1,0)}(n,m): \mathcal{B}(n,m)$ に含まれる経路で，点 $(1, 0)$ を通る経路全体の集合．

(2) $|\mathcal{B}_{(0,1)}(n,m)|$ を求めよ．

(3) $|\mathcal{B}_{(1,0)}(n,m)|$ を求めよ．

(4) $r(n,m) = \frac{|\mathcal{G}(n,m)|}{|\mathcal{P}(n,m)|}$ を求めよ．ただし $\mathcal{G}(n,m) = \mathcal{P}(n,m) \setminus \mathcal{B}(n,m)$． また $n = 15, m = 10$ として $r(15, 10)$ を求めよ．

题目描述

考虑题面图示的 $n\times m$ 方格，其中 $n\geq m\geq1$。令 $\mathcal P(n,m)$ 为所有从 $(0,0)$ 走到 $(n,m)$ 且满足条件 1 的格路径集合。

• 条件 1： 在路径上的每一点，只能移动到其右侧或上侧的相邻点。

对有限集合 $A$，以 $|A|$ 表示其元素个数。

1. 求 $|\mathcal P(n,m)|$。

在 $\mathcal P(n,m)$ 中，令 $\mathcal B(n,m)$ 为满足条件 2 的路径集合。

• 条件 2： 存在某个 $a\in\{1,\ldots,m\}$，使路径经过点 $(a,a)$；也就是说，路径至少经过题面图中一个以黑点标出的正对角点。

再把 $\mathcal B(n,m)$ 分为以下两个子集：

• $\mathcal B_{(0,1)}(n,m)$：$\mathcal B(n,m)$ 中经过点 $(0,1)$ 的全部路径；
• $\mathcal B_{(1,0)}(n,m)$：$\mathcal B(n,m)$ 中经过点 $(1,0)$ 的全部路径。

2. 求 $|\mathcal B_{(0,1)}(n,m)|$。

3. 求 $|\mathcal B_{(1,0)}(n,m)|$。

4. 定义

   $$\mathcal G(n,m)=\mathcal P(n,m)\setminus\mathcal B(n,m), \qquad r(n,m)=\frac{|\mathcal G(n,m)|}{|\mathcal P(n,m)|}.$$

   求 $r(n,m)$ 的表达式，并进一步计算 $n=15,m=10$ 时的 $r(15,10)$。

Kai

(1)

右へ $n$ 回、上へ $m$ 回の移動の順序を選ぶので、

$$\boxed{|\mathcal P(n,m)|=\binom{n+m}{m}}.$$

(2)

$(0,1)$ では $y-x=1$、終点では $y-x=m-n\leq0$ である。よって、最初に上へ進む経路は必ず正の対角点を通る。残りの移動の並べ方から、

$$\boxed{|\mathcal B_{(0,1)}(n,m)|=\binom{n+m-1}{m-1}}.$$

(3)

$(1,0)$ を通る悪い経路を、原点から最初に到達する対角点まで $y=x$ に関して反転する。これにより、$(0,1)$ を通る経路との全単射を得る。したがって、

$$\boxed{|\mathcal B_{(1,0)}(n,m)|=\binom{n+m-1}{m-1}}.$$

(4)

(2)、(3) の集合は互いに素で $\mathcal B$ を分割するので、

$$\boxed{r(n,m)=1-\frac{2\binom{n+m-1}{m-1}}{\binom{n+m}{m}} =\frac{n-m}{n+m}},\qquad \boxed{r(15,10)=\frac15}.$$