床関数・天井関数と関係式

POINT

• 床関数・天井関数の定義
• 競技プログラミングでよく使われる関係式の導出

分数のところの関係式が競技プログラミング（AtCoder，蟻本など）のコードでよく使われています．検索しても欲しい記事が出てこないので，自分で考えました．

床関数

床関数$\lfloor x \rfloor$は，$x$以下の最大の整数，つまり

\begin{aligned}
\mathbb{R}\ni x
\mapsto \lfloor x \rfloor := \max \{n\in\mathbb{Z}\mid n \leq x\}
\end{aligned}

で定義されます．これは，実数の小数点以下を切り捨てることに相当します．

まさに，実数$x$を整数ごとに敷かれた床まで落とすイメージです．

天井関数

天井関数$\lceil x \rceil$は，$x$以上の最小の整数，つまり

\begin{aligned}
\mathbb{R}\ni x
\mapsto \lceil x \rceil := \min \{n\in\mathbb{Z}\mid n \geq x\}
\end{aligned}

で定義されます．これは，実数の小数点以下を切り上げることに相当します．

こちらは，実数$x$を整数ごとにある天井にぶつけるイメージです．

関係式

我流の議論になっています．参考になるものがあれば教えて下さい．
（特に，分数の場合の関係式については，もっと見通しの良い方法がありそうだと感じています）

「x未満」の最大の整数

$x$未満の最大の整数を表す方法を考えます．

場合分けをして考えると，

1. $x$が整数のとき：$x-1=\lceil x -1 \rceil$
2. $x$が整数でないとき：$\lfloor x \rfloor=\lceil x -1 \rceil $

です．

よって，次で与えられます．

$x$未満の最大の整数

\begin{aligned}
\lceil x -1 \rceil
\end{aligned}

「xを超える」の最小の整数

同様に，$x$を超えるの最小の整数について考えます．

場合分けすると

1. $x$が整数のとき：$x+1 = \lfloor x+1 \rfloor$
2. $x$が整数でないとき：$\lceil x \rceil = \lfloor x+1 \rfloor$

です．

よって，次で与えられます．

$x$を超えるの最小の整数

\begin{aligned}
\lfloor x+1 \rfloor
\end{aligned}

分数（x=a/b）の場合の表現

$x$が分数で表される場合は，プログラミングでよく使われる他の表現があります．

以下では，分数$x=a/b$を考えて，$a\div b$の商を$a/\!/b$，剰余を$a \% b$と表します（*1）．つまり，

\begin{aligned}
a = b\cdot a/\!/b + a \% b
\end{aligned}

です．

剰余$a\% b$に着目するのがポイントです．これまでは$x$が整数かどうかに着目してきましたが，ここでは，$a\% b=0$が$a/b$が整数であることと同値であるためです．

床関数

\begin{aligned}
\lfloor a/b \rfloor
&=a/\!/b
\end{aligned}

【説明】
床関数の定義と，

\begin{aligned}
a/b = a/\!/b + (a \% b)/b
\end{aligned}

において，$a/\!/b$が整数で，$(a \% b)/b < 1$が小数であることによりわかります．//

天井関数

\begin{aligned}
\lceil a/b \rceil
&=
\begin{cases}
\, a/\!/b & (a \% b = 0) \\
\, a/\!/b + 1 & (a \% b \neq 0)
\end{cases} \\
&= \bigl(a + (b-1) \bigr)/\!/b
\end{aligned}

【説明】
1つ目の等号は，天井関数の定義からわかります．
2つ目の等式は，剰余で場合分けすれば

1. $a \% b = 0$の場合：$a \% b + (b-1)=b-1 < b$なので，$[a + (b-1)] /\!/ b = a/\!/b$，
2. $a \% b = 1,2,...,b-1$の場合：$b \leq a \% b + (b-1) < 2b$なので，$[a + (b-1)] /\!/ b = a/\!/b + 1$，

となることからわかります．//

---

2つ目の等式では，剰余に何か（$\alpha$とする）を加え，

1. 剰余ゼロの場合の商は変えず（つまり$a \% b + \alpha < b$）に，
2. 剰余がゼロでない場合の商を$+1$する（つまり$b \leq a \% b + \alpha < 2b$）

$\alpha$はあるか，という問題を考え，$\alpha = b-1$とすればよい，という答えを得たわけです．

$\alpha$を整数に限らなければ，$\alpha = b-0.8$など，多数の表現が可能です．

---

【応用】
正整数$b$の倍数で，正整数$a$以上のもののうち最小のものを求めてみます．つまり，$b$を何倍すれば始めて$a$以上となるか，ということです．答えを$xb$とすれば，

\begin{aligned}
x &= \min\{n\in\mathbb{Z}\mid nb\geq a \} \\
&= \min\{n\in\mathbb{Z}\mid n\geq a/b \} \\
&=\lceil a/b \rceil
\end{aligned}

より，答えは以下で与えられます．

$\min\{ xb \mid xb \geq a,\; a,b,x\text{：正整数} \}$

\begin{aligned}
\lceil a/b \rceil \cdot b
= \bigl(a + (b-1) \bigr)/\!/b \cdot b
\end{aligned}

あるいは，

\begin{aligned}
a/b \leq \lceil a/b \rceil
\end{aligned}

から

\begin{aligned}
a= a/b\cdot b \leq \lceil a/b \rceil \cdot b
\end{aligned}

であり，$a/b$と$\lceil a/b \rceil $の間には整数が存在しないことからも，簡単にわかります（こちらの方がわかりやすく，早いかも）．

「x=a/b未満」の最大の整数

\begin{aligned}
\lceil a/b -1\rceil
&=
\begin{cases}
\, a/\!/b - 1 & (a \% b = 0) \\
\, a/\!/b= \lfloor a/b \rfloor & (a \% b \neq 0)
\end{cases} \\
&= (a-1)/\!/b
=\lfloor (a-1)/b \rfloor
\end{aligned}

【説明】
これまで示していないのは2行目の等式だけです．剰余で場合分けすれば

1. $a \% b = 0$の場合：$-b\leq a \% b -1 = -1 < 0$なので，$(a-1)/\!/b = a/\!/b - 1 $，
2. $a \% b = 1,2,...,b-1$の場合：$0\leq a \% b -1 < b$なので，$(a-1)/\!/b = a/\!/b$，

となることからわかります．//

---

2つ目の等式では，剰余に何か（$\alpha$とする）を加え，

1. 剰余ゼロの場合の商を$-1$し（つまり$-b\leq a \% b + \alpha < 0$），
2. 剰余がゼロでない場合の商を変えない（つまり$0 \leq a \% b + \alpha < b$）

$\alpha$はあるか，という問題を考え，$\alpha = -1$とすればよい，という答えを得たわけです．

$\alpha$を整数に限らなければ，$\alpha = -0.3$など，多数の表現が可能です．

「x=a/bを超える」の最小の整数

\begin{aligned}
\lfloor a/b+1 \rfloor
&=(a+b) /\!/ b
\end{aligned}

【説明】
床関数で示した関係式から示されます．//

x以下で最大の「pで割ってr余る数」

$\lfloor (x-r) /p\rfloor \cdot p + r$で与えられます．

この結果から，

• $x$以下で最大の$p$の倍数$=\lfloor x/p\rfloor \cdot p$
• $x$以下で最大の偶数$=\lfloor x /2 \rfloor \cdot 2$
• $x$以下で最大の奇数$=\lfloor (x-1) /2 \rfloor \cdot 2 + 1$

などがわかります．
【証明】
求めるものは

\begin{aligned}
p\cdot \max\{q\in \mathbb{Z} \mid pq + r \leq x\} +r
\end{aligned}

で表される．ここで，

\begin{aligned}
&\max\{q\in \mathbb{Z} \mid pq + r \leq x\} \\
&=\max\{q\in \mathbb{Z} \mid q \leq (x-r)/p \} \\
&=\lfloor (x-r) /p\rfloor
\end{aligned}

なので，示された．//

参考記事

床関数と天井関数 - Wikipedia

*1:代数では通常$a=bq + r\,(0\leq r< |b|)$と表します．本記事ではプログラミングに使うことを念頭に置くので，それに沿った記号を使うことにします．また，$a\% b=0$のことを代数では$b \mid a$と表記し，$a\% b\neq 0$のことを代数では$b \nmid a$と表記します．