東京大学 工学系研究科 2018年度 数学 第6問

标签：

• Tokyo-University
• Fibonacci-Recurrence
• Markov-Chain

Author

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

Description

問題

$n$ 人の子供が一列に並んでいる。$m$ 個の飴を先頭から順に1人につき $1$ 個または $2$ 個ずつ配り、最後の子供まで配るか、飴がなくなった時点で終了する。$n,m$ は正の整数とする。

I. $n=m=4$ のとき、配り方の総数を求めよ。

II. $m\ge2n$ のとき、配り方の総数を求めよ。

III. $n\ge m$ のとき、配り方の総数を $X_m$ とする。$X_m$ の漸化式を求めよ。

IV. 漸化式を用いて $X_m$ を求めよ。

V. 子供の人数が飴の個数より多いとする。最後に $2$ 個配って終了する配り方の割合を $P(m)$ とする。$\lim_{m\to\infty}P(m)$ を求めよ。

VI. $m\ge2n$ とする。最初の子供は $1$ 個または $2$ 個をそれぞれ確率 $1/2$ で受け取る。前の子供が $1$ 個受け取ったとき、次の子供が $1,2$ 個受け取る確率はともに $1/2$、前の子供が $2$ 個受け取ったときは、それぞれ $3/4,1/4$ とする。$n$ 番目の子供が $2$ 個受け取る確率を求めよ。

题目描述

$n$ 个孩子排成一列，现有 $m$ 颗糖，从队首开始依次给每人 $1$ 或 $2$ 颗，直到队列结束或糖分完；$n,m$ 为正整数。

I. 当 $n=m=4$ 时，求分配方式数。

II. 当 $m\ge2n$ 时，求分配方式数。

III. 当 $n\ge m$ 时，以 $X_m$ 表示分配方式数，求递推关系。

IV. 利用递推关系求 $X_m$。

V. 当孩子数多于糖数时，令 $P(m)$ 为最后一次分出 $2$ 颗糖的方式数占全部方式数的比例。求 $\lim_{m\to\infty}P(m)$。

VI. 当 $m\ge2n$ 时，首人以相同概率得到 $1$ 或 $2$ 颗。前一人得到 $1$ 颗时，下一人得到 $1,2$ 颗的概率均为 $1/2$；前一人得到 $2$ 颗时，下一人得到 $1,2$ 颗的概率分别为 $3/4,1/4$。求第 $n$ 人得到 $2$ 颗的概率。

Kai

I.

$(1,1,1,1)$、$(1,1,2,0)$、$(1,2,1,0)$、$(2,1,1,0)$、$(2,2,0,0)$ の $\boxed{5}$ 通りである。

II.

各子供に $1$ 個または $2$ 個を独立に選んで配れるので、$\boxed{2^n}$ 通りである。

III–IV.

最初の子供に $1$ 個配る場合と $2$ 個配る場合に分けると

$$X_m=X_{m-1}+X_{m-2}\quad(m\ge2),\qquad X_0=X_1=1.$$

$\varphi=(1+\sqrt5)/2$、$\psi=(1-\sqrt5)/2$ とおけば

$$\boxed{X_m=\frac{\varphi^{m+1}-\psi^{m+1}}{\sqrt5}}.$$

V.

最後の2個を除く操作により、$m-2$ 個の飴の配り方と一対一に対応する。したがって $P(m)=X_{m-2}/X_m$（$m\ge2$）であり、

$$\boxed{\lim_{m\to\infty}P(m)=\varphi^{-2}=\frac{3-\sqrt5}{2}}.$$

VI.

$n$ 番目の子供が2個受け取る確率を $a_n$ とおく。全確率の公式より

$$a_{n+1}=\frac12(1-a_n)+\frac14a_n,\qquad a_1=\frac12.$$

$a_{n+1}-2/5=-(a_n-2/5)/4$ なので、

$$\boxed{a_n=\frac25+\frac1{10}\left(-\frac14\right)^{n-1}}.$$