※試験の設定は2025年度時点の情報であり、2026年度以降は変更の可能性があります。試験内容についてはエントリーされた方にお送りする情報をご確認ください。
こんにちは、シミュレーション & マイニング部の高橋と申します。昨年に引き続き、当社の入社試験問題を紹介する企画の第八回です。今年度はこの記事のみの予定です。
入社試験問題例
2025年度に出題した問題の中から、私が担当した高校数学の問題を紹介します。
問題.
各項が正整数の数列 $\{a_n\}_{n=1,2,\dots}$ が次の条件を満たしている：
$\begin{cases} a_1=1, \\ a_{2n}<6a_{n}, \\ 3a_{n}a_{2n+1}=(3a_{n}+1)a_{2n}. \end{cases}$
この設定のもと以下の問いに答えよ。
(1) $a_2, a_3, a_4, a_5$ を求めよ。答えのみでよい。
正整数上の単調増加関数 $f$ を次のように定める。
・正整数 $n$ の有限桁の2進展開 $b_{N_n}\cdots {b_{0}}_{(2)}\left(=\Sigma_{m=0}^{N_n}b_{m}2^m\right)$ は一意に定まる。
これを用いて $f(n)\coloneqq b_{N_n}\cdots {b_{0}}_{(3)}\left(=\Sigma_{m=0}^{N_n}b_{m}3^m\right)$ と定義する。
例えば $f(1)=f(1_{(2)})=1_{(3)}=1$ である。
(2) $a_n$ を $f$ を用いて表示せよ。
(3) 正整数の組 $(i, j)$ のうち $a_i + a_j=2025=3^4\cdot 5^2$ を満たすものを10進表記で全て求めよ。
(2025年度 株式会社NTTデータ数理システム 入社試験問題),
まずは問題の解答を示し、次に問題背景について見ていきましょう。
なお、この問題は漸化式・$N$進数の扱いに慣れている人向けの問題で、実際の試験では複数問のうち2問を選択して解けばよいので、これらが苦手だという方も心配ご無用です。
解答
(1)
$a_n$ が満たしている条件式に $n=1$ を代入する。
$3a_{3}=4a_{2}, \gcd (3,4)=1$ より $a_2$ は $3$ の倍数だが $a_2<6$ より $a_2=3$ となる他ない。
よって $a_2=3, a_3=4$.
$a_n$ が満たしている条件式に $n=2$ を代入する。
$9a_{5}=10a_{4}, \gcd (9,10)=1$ より $a_4$ は $9$ の倍数だが $a_4<18$ より $a_4=9$ となる他ない。
よって $a_4=9, a_5=10$.
(2)
$n=1,2,3,4,5$ で実験すれば $a_n=f(n)$ と推測できる。これを帰納的に示せばよい。
$3 a_n a_{2 n+1}=\left(3 a_n+1\right) a_{2 n}$ と $\operatorname{gcd}\left(3 a_n, 3 a_n+1\right)=\operatorname{gcd}\left(3 a_n, 1\right)=1$ より、$a_{2 n}$ は $3 a_n$ の倍数。
さらに $a_{2 n}<6 a_n$ なので $a_{2 n}=3 a_n$ となる他ない。
よって $\begin{cases} a_{2 n}=3 a_n, \\ a_{2 n+1}=3 a_n+1 \end{cases}$ が成立。
これを用いて $a_n=f(n)$ を示す。
$a_1=1=f(1)$ なので $n=1$ のとき $a_n=f(n)$ は成立。
正整数 $k$ について $a_k=f(k)$ の成立を仮定する。$k$ の2進展開を $b_{N_k}\cdots {b_{0}}_{(2)}$ と書くことにする。
$z \in\{0,1\}$ について次の関係式が従う：
[[\begin{align*} 3 f(k)+z&=3 f\left(b_{N_k}\cdots {b_{0}}_{(2)}\right)+z \\ &=10_{(3)} \cdot\left(b_{N_k}\cdots {b_{0}}_{(3)}\right)+z_{(3)} \\ &=b_{N_k}\cdots {b_{0}}z_{(3)} \\ &=f\left(b_{N_k}\cdots {b_{0}}z_{(2)}\right) \\ &=f\left(10_{(2)} \cdot\left(b_{N_k}\cdots {b_{0}}_{(2)}\right)+z_{(2)}\right) \\ &=f(2 k+z). \end{align*}]]
よって $\begin{cases} a_{2k}=3 f(k)=f(2k), \\ a_{2k+1}=3f(k)+1=f(2k+1) \end{cases}$ が成立。
任意の $n(\geq 2)$ に対しただ一つの正整数 $k_n(<n)$ が存在して $n$ が $2 k_n, 2 k_n+1$ のいずれか一方のみの形で表示できるため、任意の正整数 $n$ に対し $a_n=f(n)$ が帰納的に成立する。
(3)
$a_{i}, a_{j} (=f(i), f(j))$ を3進表示して考える。
これらの各桁は $0$ or $1$ であり、和において繰り上がりは生じないので、桁ごとに組み合わせを考えればよい。
$2025=3^4 \cdot 5^2=10000_{(3)} \cdot 221_{(3)}=2210000_{(3)}$ なので、求める組 $(i,j)$ は以下の関係を満たすもの：
[[\begin{align*} \left(f(i), f(j)\right)=\left(a_i, a_j\right)&=\left(1100000_{(3)}, 1110000_{(3)}\right),\left(1110000_{(3)}, 1100000_{(3)}\right)\\ &=\left(f\left(1100000_{(2)}\right), f\left(1110000_{(2)}\right)\right),\left(f\left(1110000_{(2)}\right), f\left(1100000_{(2)}\right)\right)\\ &=\left(f(96), f(112)\right),\left(f(112), f(96)\right). \end{align*}]]
$f$ の単調増加性より、求める組 $(i, j)$ は $(96,112),(112,96).$
問題背景
ここからは確率・統計に詳しい方向けの内容となりますが、ご興味のある方はぜひお読みください。
本問の $f$ はカントール分布（ルベーグ測度と互いに特異な分布の代表例）に従う確率変数の構成に用いられる関数をモチーフにしています。
以下に述べる関数 $\tilde{f}$ を $[0,1]$ 上の一様分布に従う確率変数 $U$ と合成した確率変数 $2\tilde{f}(U)$ はカントール分布に従います。（証明は省略します。考えてみてください。）
（関数 $\tilde{f}:[0,1]\rightarrow\mathbb{R}$ の定義）
$x\in[0,1]$ の二進展開を $b_{N_k}...b_{0}.b_{-1}..._{(2)}$ とする。
ただし、この二進展開としては有限桁で打ち切れるものを採用する。（例えば、$\frac{1}{2}$ の二進展開として、ここでは $0.011..._{(2)}$ ではなく $0.1_{(2)}$ を採用する）
そして、$\tilde{f}(x)\coloneqq b_{N_k}...b_{0}.b_{-1}..._{(3)}$ と定める。
本問の $f$ はこの $\tilde{f}$ の定義域を正整数に変更したものです。
この $f$ は、本問(2)の解答で示した通り $f(2n)=3f(n)$, $f(2n+1)=3f(n)+1$ という面白い性質を持つので、$f(n)$ を一般項に持つ数列を今回出題しました。
前述のカントール分布は、ルベーグ測度と互いに特異な分布です。
分布の特異性はあまり歓迎されず、様々な定理で分布が特異でないことが前提条件として課されます。
このような定理のひとつが、マルコフ連鎖のサンプル平均の収束定理です。
（この定理により、後述するMCMCによる数値積分の収束性が保証されます。）
以降、この収束定理の前提条件を満たさない場合でもサンプル平均が収束することはある、という具体例をカントール分布を用いて構成してみます。
（実は、自分はこの具体例の構成中にカントール分布に従う確率変数について考えたことで本問の出題に至った、という経緯があります。）
MCMCとは、所与の分布に収束するマルコフ連鎖を構成し、その分布からのサンプルを得るアルゴリズムです。よく知られている応用の一種が、このサンプルを用いた数値積分です。
MCMCによる数値積分の収束を保証する定理として以下のDoobの定理が知られています。
（Doobの定理）
確率空間 $(\Omega, \mathcal{F}, P)$ 上の確率変数列 $X_0, X_1, \dots$ が $\mathcal{X}$ を状態空間とするマルコフ連鎖であるとする。
マルコフカーネル $K$ を $K(x,\cdot)\coloneqq P(\cdot\mid X_0=x)$ と表記する。
以下の条件を仮定する：
・（条件1）$\mathcal{X}$ の任意の2点 $x, y$ において $K(x,\cdot)$ と $K(y,\cdot)$ が互いに特異でない
・（条件2）マルコフ連鎖の不変確率分布 $\Pi$ が存在する
このとき任意の $\Pi$-可積分関数 $g$ について以下の結果1,2が成立する。
・（結果1）
$K(x,\cdot)$ はエルゴード性を持つ。すなわち、全変動ノルム $\|\cdot\|_{\text{TV}}$ に関して以下が成立：
$\Pi(\{x\in\mathcal{X}|\lim_{n\to\infty}\|K^{n}(x,\cdot)-\Pi\|_{\text{TV}}=0\})=1$.
・（結果2）
結果1と大数の弱法則より以下が成立：
$\int_{\mathcal{X}} P\left(\left\{\omega\in\Omega\mid\lim_{M\to\infty}\frac{1}{M}\Sigma_{m=0}^{M-1}g(X_m(\omega))=\int_{\mathcal{X}} g(z)\Pi(dz)\right\}\mid X_{0}=x\right)\Pi(dx)=1$.
用語の詳しい定義や定理の証明は省略しますが、$K(x,\cdot), K(y,\cdot)$ が互いに特異でないことからこれらは共通部分を持ち、$n$ を大きくしていくと $K^{n}(x,\cdot), K^{n}(y,\cdot)$ の共通部分が大きくなっていき、最終的には（一意な）不変確率分布 $\Pi$ に一致する、というイメージの定理です。
この定理の結果2より、事後分布 $\Pi$ による積分 $\int_{\mathcal{X}} g(z)\Pi(dz)$ が目的値として与えられたとき、MCMCにより $\Pi$ を不変確率分布に持つような性質の良いマルコフ連鎖を構成して十分多くのサンプルを得れば、$g$ の数値積分 $\frac{1}{M}\Sigma_{m=0}^{M-1}g(X_m(\omega))$ により目的値を精度よく近似できるということが保証されます。
自分はこの定理を見たとき、条件を満たさないが結果は成立するようなマルコフ連鎖はないのかが気になりました。そこで、条件1を満たさないマルコフ連鎖を考えてみます。この構成にカントール分布を用います。
状態空間 $\mathcal{X}$ を閉区間 $[0,1]\subset\mathbb{R}$ とし、
マルコフカーネル $K$ を次のように定めます：$K(x,A)\coloneqq\mu_{C}(A)\mathbb{1}_{[0,\frac{1}{2})}(x)+U_{[0,1]}(A)\mathbb{1}_{[\frac{1}{2},1]}(x)$.
（ただし、$\mu_{C}$ はカントール分布、$U_{[0,1]}$ は $[0,1]$ 上の一様分布）
このとき、$K(0,\cdot)=\mu_{C}$ と $K(1,\cdot)=U_{[0,1]}$ は互いに特異で、条件1は満たされていません。
しかし、条件2や結果1は成り立ちます。まず、$K^{2}(x_{0},\cdot)$ は以下のように計算できます。
[[\begin{align*} K^{2}(x_{0},A)&=\int_{x_{1}\in\mathcal{X}}K(x_{1},A)K(x_{0},dx_{1})\\&=\int_{x_{1}\in\mathcal{X}}\left(\mu_{C}(A)\mathbb{1}_{[0,\frac{1}{2})}(x_{1})+U_{[0,1]}(A)\mathbb{1}_{[\frac{1}{2},1]}(x_{1})\right)K(x_{0},dx_{1})\\&=\mu_{C}(A)K\left(x_{0},[0,\frac{1}{2})\right)+U_{[0,1]}(A)K\left(x_{0},[\frac{1}{2},1]\right)\\&=\frac{1}{2}\mu_{C}(A)+\frac{1}{2}U_{[0,1]}(A).\end{align*}]]
上記の計算結果は初期値 $x_{0}$ に依存しません。（この部分には、計算の最後で用いたように、任意の $x_{0}\in\mathcal{X}$ について $K(x_{0},[0,\frac{1}{2}))=K(x_{0},[\frac{1}{2},1])=\frac{1}{2}$ が成立することが効いています。）
このため、任意の $n\geq 2$ について、$K^{n}(x_{0},\cdot)$ は同一のものだと帰納的に分かります。
よって、$\frac{1}{2}\mu_{C}+\frac{1}{2}U_{[0,1]}$ がこのマルコフ連鎖の一意な不変確率分布 $\Pi$ であり、条件2は満たされます。
このとき、任意の $n\geq 2, x\in\mathcal{X}$ について $K^{n}(x,\cdot)=\Pi$ であるため、結果1が成立します。
また、結果2は結果1が成立すれば成立するものであるため、結果2が成立します。
以上から、条件1は満たされていないものの条件2, 結果1,2は成立するマルコフ連鎖の例が構成できました。
この例では、定理のイメージで述べた現象（$n$ を大きくしていくと $K^{n}(x,\cdot), K^{n}(y,\cdot)$ の共通部分が大きくなっていき最終的には（一意な）不変確率分布 $\Pi$ に一致する）とは異なり、一度の更新で初期値に関係のない分布に到達しそれが不変確率分布となる、という半ば偶然に近い現象が見られるのが興味深いと感じます。
このように、実務でも用いられるMCMCによる数値積分がどのような条件下で目的値に収束するのかという興味から出発し、考察を発展させていく中で少し変わった高校数学の問題が得られるのは、それ自体興味深い事象と言えるのではないでしょうか。
応募者募集！
当社の筆記試験では、会社の雰囲気を伝える機会でもあると考え、標準的な知識で解ける面白い問題を出題しています。この記事を通して当社に興味を持っていただけた方は、ぜひ説明会にお越しください！
アカリク NTTデータ数理システム 求人情報ページ
