代表選考合宿 2022
問題 4

$\lfloor a_i/i\rfloor\geq 1$ なる整数 $1\leq i\leq n$ が $k$ 個存在するとし，それらを小さい順に $c_1,c_2,\dots,c_k$ とする．また，$\lfloor a_{c_i}/c_i\rfloor=b_i$ とする．このとき，以下が成り立つ．

$$a_{c_i}\leq (b_i+1)c_i-1,\quad c_1=1,\quad a_{c_k}=n$$

また，$i=1,2,\dots,k-1$ に対して $c_{i+1}\leq a_{c_i}+1$ が成り立つので，

$$a_{c_{i+1}}+1\leq (b_{i+1}+1)(a_{c_i}+1)$$

これを繰り返し用いれば

$$n+1=a_{c_k}+1\leq (b_1+1)(b_2+1)\cdots(b_k+1)$$

が従う．よって本問は

$$(b_1+1)(b_2+1)\cdots(b_k+1)\geq n+1$$

を満たす正整数 $b_1,b_2,\dots,b_k$ に対する

$$b_1+b_2+\cdots+b_k$$

の値の最小値を求める問題に帰着され，これは $\log_2 \lfloor n+1\rfloor$ である．