7.5 g:\N^2\ni (x,y)\mapsto\frac12(x+y-2)(x+y-1)+y\in\Nが全単射であることを示せ
7.5 $ g:\N^2\ni (x,y)\mapsto\frac12(x+y-2)(x+y-1)+y\in\Nが全単射であることを示せ
調べるのめんどいな……takker.icon
どちらかというと7.6以降をやりたいので、飛ばそうかな
文字定数を具体化して挙動を調べる
$ g((1,1))=0+1=1
$ g((1,2))=\frac12(1+2-2)(1+2-1)+2=\frac12\cdot1\cdot2+2=3
$ g((1,3))=\frac12(1+3-2)(1+3-1)+3=\frac12\cdot2\cdot3+3=6
$ g((1,4))=\frac12(1+4-2)(1+4-1)+4=\frac12\cdot3\cdot4+4=10
$ g((2,1))=\frac12(2+1-2)(2+1-1)+1=\frac12\cdot1\cdot2+1=2
$ g((3,1))=\frac12(3+1-2)(3+1-1)+1=\frac12\cdot2\cdot3+1=4
$ g((4,1))=\frac12(4+1-2)(4+1-1)+1=\frac12\cdot3\cdot4+1=7
$ g((2,2))=\frac12(2+2-2)(2+2-1)+2=\frac12\cdot2\cdot3+2=5
放物線が動く
表にしよtakker.icon
table:g
x\y 1 2 3 4 5
1 1 3 6 10
2 2 5
3 4
4 7
5
！！！！！takker.icon
そういうこと！nishio.icon
いやこれ面白い問題だなnishio.icon
$ \Nの話をしてるので放物線と考えるのは微妙かな…
$ t=x+yとする、$ h(t):=\frac12(x+y-2)(x+y-1) = \frac12(t-2)(t-1) = \frac12t^2 - \frac32t + 1
$ tが奇数の時$ t^2も奇数なので、$ h(t) \in \Nが言える
$ tを固定したまま$ y\in\Nを動かせるので$ g(x, y)は$ tを固定したまま任意の整数になれる
この発想なかった。見習いたいtakker.icon
よって任意の整数$ nに対して$ g(x, y) = nであるような$ (x, y)が存在する(全射性)
あってるかな？takker.icon
$ x=t-y\in\Nだから$ 0<y< tが拘束条件
$ \{z\in\N|h(t)<z<h(t)+t\}が動く範囲か
$ \bigcup_{t\ge2\land t\in\N}\{z\in\N|h(t)<z<h(t)+t\}=\Nであれば全射性を示せる
えっ、単射じゃなくない？なんか勘違いしてる？？
$ \Zではなく$ \Nが変域の点？takker.icon
あっ、それだnishio.icon
上の具体例列挙を見ると、第一項は三角数なので、値の間隔から一意であることを言うのか
本当に全単射なのかな、端が少し重なったりしそう…
あー、て言うか上の列挙で答え出てるじゃん、並び順がわかりにくいだけ
三角数じゃん！！！！！(激遅気づき) / そういうこと！
一般化すると
$ {\rm Tri}(t) = \frac12t(t+1)とする。(1, 3, 6, ...)
$ g(x, y) = {\rm Tri}(x+y-2) + y
任意の自然数$ n > 0について$ {\rm Tri}(z) < nである最大の$ zを$ g'(n)とすると
$ y=n - {\rm Tri}(g'(n)), \quad x = g'(n)-2 - y
こんな感じ(手抜き)
1つのパラメタで2次元の点を掃けるのは面白いtakker.icon
$ \Rでは成立しない……と思ったけどペアノ曲線があったな 気になり始めたので、こんどやろうtakker.icon
nishio.icon
$ f: \N^2\ni (x,y)\mapsto (a+b, a) (1\le a < a+b, 1\le b)
は全単射
$ f': (a+b, a) \mapsto {\rm Tri}(a+b)+a
は全単射
(多分微妙に-1とか足りない)
$ g = f' \circ fなので全単射
って感じなんだろうな