■

[小ネタ] \mathbb{N}\times \mathbb{N} \to \mathbb{N}の逆関数を求める

　久々の投稿ではあるが，めっちゃ小ネタである．実は仕事のソフトを書いていてこの問題にぶつかった．

　\mathbb{N}\times \mathbb{N}の濃度が\mathbb{N}の濃度に等しいということの証明として，対応を具体的に (n,m) \mapsto k=(n+m+1)(n+m)/2 + mと与えることができる．(0,0)\to(1,0)\to(0,0)\to(2,0)\to(1,1)\to(0,2)\cdotsという具合に\mathbb{N}\times \mathbb{N}の作る平面を斜めに切るように数える，よく知られたものである．さて，問題はプログラムでループ変数を\mathbb{N}にして，\mathbb{N}\times \mathbb{N}の方を求める，つまり逆関数が欲しいと思ったのである．ところが意外にもこの対応の逆関数を陽に表した公式が Webで見つからないのである．頼みの綱のstack overflowにも『全単射なんだから逆対応の存在は明らか』みたいなのしかなくて困ったが，一つだけ手がかりとして，『 \sqrt(2k)\simeq n+m』というのが見つかった．このヒントは，確かに2k=(n+m+1)(n+m)+2mをにらむと見えては来るが，数値で計算してみると，\sqrt(2k)を切り上げたり切り捨てたりしても合ってはいない．いろいろ試行錯誤の挙句，次のような公式を得た．


n+m = \lceil \sqrt(2k+2) +1/2 \rceil-2


ここに\lceil x \rceilはxを切り上げて整数化する記号である．

ちょっと試してみよう．
(0,0)のときk=0で，\sqrt(2k+2)+1/2 \fallingdotseq 1.91.切り上げて2なので 0.
(1,0)のときk=1で，\sqrt(2k+2)+1/2)=2.5.切り上げて3なので 1.
(0,1)のときk=2で，\sqrt(2k+2)+1/2)\fallingdotseq 2.94.切り上げて3なので 1.
(2,0)のときk=3で，\sqrt(2k+2)+1/2)\fallingdotseq 3.32.切り上げて4なので 2.
(1,1)のときk=4で，\sqrt(2k+2)+1/2)\fallingdotseq 3.56.切り上げて4なので 2.
(0,2)のときk=5で，\sqrt(2k+2)+1/2)\fallingdotseq 3.96.切り上げて4なので 2.

とかなりきわどいもののイケている．もっと先の方を適当にやってみると，
(20,31)のときk=1357で，\sqrt(2k+2)+1/2)\fallingdotseq 52.61.切り上げて53なので 53-2=51=20+31 とこれも正しい．

n+mがわかると m=k-(n+m)(n+m+1)/2なので逆関数は求まったことになる．


さて，上の公式を証明しよう．
n+m+2 = \sqrt(2k+2) +1/2 + \alphaと置く．\sqrt(2k+2) +1/2の切り上げがn+m+2に等しいということは，0 \le \alpha < 1であることと同値である．まず，0 \le \alphaを示す. もし, \alpha < 0ならn+m+2 < \sqrt(2k+2) +1/2で，
n+m+3/2 < \sqrt(2k+2)
\Rightarrow (n+m+3/2)^2 < 2k+2 = (n+m+1)(n+m)+2m+2
\Rightarrow (n+m)^2+ 3(n+m)+(3/2)^2 < (n+m)^2+ (n+m) +2m+2
\Rightarrow 2n+(3/2)^2 < 2
\Rightarrow 2n < -1/4 は矛盾である．よって0 \le \alpha.
同様に 1 \ge \alphaなら，1 \ge n+m+2 - (\sqrt(2k+2) +1/2).

1 \ge n+m+2 - (\sqrt(2k+2) +1/2)
\Rightarrow 1+(\sqrt(2k+2) +1/2) \ge n+m+2
\Rightarrow \sqrt(2k+2) \ge n+m+1/2
\Rightarrow 2k+2=(n+m+1)(n+m)+2m+2 < (n+m+1/2)^2
\Rightarrow (n+m)^2+(n+m)+2m+2 < (n+m)^2+(n+m)+(1/2)^2
\Rightarrow 2m+2 < (1/2)^2
\Rightarrow 2m < -3/4 は矛盾．よって \alpha < 1 □