OMC194(C) - a_2=501 を求める別の方法（鳩の巣原理）

　$a_1, \cdots, a_{1000}$ が相異なるためには，$\lceil a_1 \rceil \cdots \lceil a_{999}\rceil$ が相異なることが必要条件である．そこで，漸化式を次のように変形する：
$$\lceil a_{n+1} \rceil = \left\lceil \dfrac{k}{10^5}\lceil a_n \rceil+1 \right\rceil=\left\lceil \dfrac{k}{10^5}\lceil a_n \rceil \right\rceil +1 \leq \left\lceil \lceil a_n \rceil \right\rceil +1= \lceil a_n \rceil +1\ \cdots(※)$$ 　ここで $\lceil a_2 \rceil \leq 500$ と仮定すると，次のいずれかを満たす：
(i) $\lceil a_1 \rceil \cdots \lceil a_{501} \rceil$ はいずれも $500$ 以下の自然数であり，鳩の巣原理より，$\lceil a_x \rceil = \lceil a_y \rceil$ となるものが存在する．
(ii) $\lceil a_3 \rceil \cdots \lceil a_{501} \rceil$ のいずれかが $500$ より大きい自然数である．このとき，式 $(※)$ より，$\lceil a_x \rceil = 500$ となるものが存在する．
どちらの条件を満たしても，$a_1, \cdots, a_{1000}$ が相異なるという条件に反するため，$\lceil a_2 \rceil \gt 500$ でなければならない．すなわち $\lceil a_2 \rceil = 501$．

　次に，$\lceil a_n \rceil \lt \lceil a_{n+1} \rceil$ と仮定する．このとき漸化式より $a_{n+1} \lt a_{n+2}$ である．一方，式 $(※)$ より， $$\lceil a_{n+1} \rceil \leq \lceil a_{n+2} \rceil \leq \lceil a_{n+1} \rceil+1$$ となる．従って，$a_1, \cdots, a_{1000}$ が相異なるための必要十分条件は，$n=1, \cdots,999$ の範囲で $\lceil a_n \rceil=n+499$ を満たすことである．
　ここで，次の連立不等式を考える：$\lceil a_N \rceil \lt \lceil a_{N+1} \rceil$，$a_{N+1} = \dfrac{k}{10^5}\lceil a_N \rceil+1$．この不等式が $1 \leq N \leq 998$ で成り立つような $k$ を求めればよい．
　$\lceil a_N \rceil \lt \lceil a_{N+1} \rceil \iff \lceil a_N \rceil \lt a_{N+1}$ を用いれば，次の解を得る： $$k \gt \dfrac{\lceil a_N \rceil -1}{\lceil a_N \rceil}× 10^5$$ 　$a_N$ が大きくなるほど右辺も大きくなるので，$N=998$ を代入して $k \geq 99934$ を得る．