C - Divide and Divide 解説
by 
rsk0315
公式解説で省略されている部分の証明
まず、いくつかの補題を示しておきます。
\(\gdef\floor#1{\lfloor#1\rfloor}\) \(\gdef\ceil#1{\lceil#1\rceil}\) \(\gdef\qed{\square}\)
Lemma 1: 実数 \(x\) と正整数 \(n\) に対して、\(\floor{\floor{x}/n} = \floor{x/n}\) および \(\ceil{\ceil{x}/n} = \ceil{x/n}\) が成り立つ。
Proof
$\floor{\floor{x}/n} = \floor{x/n}$ について示す。 $\floor{x}=x$ のときは自明なので、以下 $\floor{x}\lt x$ とする。このとき、$\floor{x}/n\lt x/n$ より $\floor{\floor{x}/n}\le \floor{x/n}$ が成り立つ。
背理法による。$\floor{\floor{x}/n}\lt \floor{x/n}$ と仮定すると、ある実数 $y$ が存在して $\floor{x}\lt y\le x$ かつ $y/n = \floor{x/n}$ が成り立つ。また、$y = \floor{x/n}\cdot n$ より $y$ は整数となる。 これは、$\floor{x}$ が $x$ 以下の最大の整数であることに矛盾する。$\qed$
$\ceil{\ceil{x}/n} = \ceil{x/n}$ についても同様にして示せる。
Corollary 2: 実数 \(a\) と、整数 \(m\), \(n\) (\(m\ne 0\), \(n\gt 0\)) に対して \(\floor{\floor{a/m}/n} = \floor{a/mn}\) が成り立つ。
Proof
$x = a/m$ として lemma 1 から従う。$\qed$Lemma 3: 実数 \(x\) に対して、\(\ceil{x}-\floor{x} \in \{0, 1\}\) が成り立つ。
Proof
$x$ が整数のとき、$\ceil{x}=\floor{x}$ より $\ceil{x}-\floor{x}=0$ となる。$x$ が整数でないとき、$\ceil{x}=\floor{x}+1$ より $\ceil{x}-\floor{x}=1$ となる。$\qed$
Lemma 4: 実数 \(x\) と整数 \(n\) に対して \(\floor{x}\le n\le\ceil{x}\) のとき、\(n\in\{\floor{x}, \ceil{x}\}\) が成り立つ。
Proof
背理法による。 $\floor{x}\lt y\lt\ceil{x}$ なる整数 $y$ が存在したとすると、$y-\floor{x}\ge 1$ かつ $\ceil{x}-y\ge 1$ より $\ceil{x}-\floor{x}\ge 2$ となる。これは lemma 3 に矛盾する。$\qed$
上記を用いて、所望の命題を示すことができます。
Claim 5: 正整数 \(N\) に対して、\(N \gets \floor{N/2}\) か \(N \gets \ceil{N/2}\) のいずれかを任意の順で \(k\) 回 (\(k\ge 0\)) 行うことで得られる整数は、\(\floor{N/2^k}\) または \(\ceil{N/2^k}\) である。
Proof
数学的帰納法で示す。 まず、$k=0$ のとき、$N = \floor{N/2^0} = \ceil{N/2^0}$ より成り立つ。 $k$ で成り立つとして $k+1$ で成り立つことを示す。$k$ 回行って得られた値が $\floor{N/2^k}$ のとき、 $$\floor{N/2^{k+1}} = \floor{\floor{N/2^k}/2} \le \ceil{\floor{N/2^k}/2} \le \ceil{\ceil{N/2^k}/2} = \ceil{N/2^{k+1}}$$ なので、lemma 4 より従う。$\ceil{N/2^k}$ だった場合も同様にして従う。 よって、任意の $k\ge 0$ に対して成り立つ。$\qed$\(N\) や \(\floor{N/2^k}\) や \(\ceil{N/2^k}\) について、2 進法での表示を観察してみると、何らかのよいイメージを得られるかもしれません。
また、corollary 2 はしばしば AtCoder でも出題されるので、覚えておくとよいでしょう。(e.g. ABC 141 D, ABC 132 F)
投稿日時:
最終更新: