ある関数の存在　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「ａｔ」さんからの出題です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２５年１１月２４日付け）

　気が向いたら、次の問題を考えてみてください。

【問題】　Nを正の整数全体の集合とします。NからNへの関数 Ｆ：N → N で、Nの任意の要

　　　　素 ｎ に対して、　Ｆ(Ｆ(ｎ)) ＝ ｎ²　となるようなものが存在することを証明してください。


（コメント）　すべての自然数 ｎ に対して、Ｆ(ｎ) ＝ ｍ　、Ｆ(ｍ) ＝ ｎ²　となるようなものが存
　　　　　　在するとは面白いですね！

　上記の性質を持つ関数 Ｆ が存在したとして、例えば、Ｆ(１)＝ｋ　とすると、Ｆ(ｋ)＝１²＝１
このとき、Ｆ（Ｆ(ｋ)）＝Ｆ(１)＝ｋ　で、ｋ²＝ｋ　となるｋは、０と１しかない。

　Ｆ(２)＝ｍ　とすると、Ｆ(ｍ)＝２²＝４　なので、Ｆ（Ｆ(ｍ)）＝Ｆ(４)＝ｍ²　となる。

　同様にして、　Ｆ(１６)＝ｍ⁴ 、　・・・・・・・・・・・・・・・・

　このような形で、順次値を定めていけばいいのだろうか？


　空舟さんが考察されました。（平成２５年１１月２６日付け）

　次のように構成できました。

　２以上の平方数でない整数を順番に並べた数列を {Y_k} とする。すなわち、

　Y₁=2　、Y₂=3　、Y₃=5　、・・・・

　数列 {Y_k} を使って、関数 Ｇ：N×N　→　(２以上の整数全体の集合) を次のように定義する。

　　Ｇ(ａ，ｂ) = (Y_a)^(２^b-1)

　関数 Ｇを使って、Ｆ(ｎ) を次のように定義すれば良いと考えました。

　　ｎ = １ のとき、　 Ｆ(ｎ) = １

　　ｎ≧２ のとき、Ｇ(ａ，ｂ) = ｎ となる (ａ，ｂ)∈N×N を唯一とることができる(★)ので、

　　　ａ が奇数のとき、　Ｆ(ｎ) = Ｇ(ａ＋１，ｂ)

　　　ａ が偶数のとき、　Ｆ(ｎ) = Ｇ(ａ−１，ｂ＋１)

例　Ｇ(１，１) = (Y₁)^(２⁰) = 2^(２⁰) = 2
　　Ｇ(１，２) = (Y₁)^(２¹) = 2^２ = 4
　　Ｇ(１，３) = (Y₁)^(２²) = 2^４ = 16
　　　　・・・・・・・・・・・・・・・・・・・・・

　　Ｇ(２，１) = (Y₂)^(２⁰) = 3^(２⁰) = 3
　　Ｇ(２，２) = (Y₂)^(２¹) = 3^２ = 9
　　Ｇ(２，３) = (Y₂)^(２²) = 3^４ = 81
　　　　・・・・・・・・・・・・・・・・・・・・・

　　Ｇ(３，１) = (Y₃)^(２⁰) = 5^(２⁰) = 5
　　Ｇ(３，２) = (Y₃)^(２¹) = 5^２ = 25
　　Ｇ(２，３) = (Y₃)^(２²) = 5^４ = 625
　　　　・・・・・・・・・・・・・・・・・・・・・

　Ｆ(１) = １　のとき、　Ｆ(Ｆ(１)） = １²
　ｎ＝２ のとき、Ｇ(１，１) = 2　より、ａ＝１（奇数）から、　Ｆ(２) = Ｇ(２，１) = ３
　ｎ＝３ のとき、Ｇ(２，１) = 3　より、ａ＝２（偶数）から、　Ｆ(３) = Ｇ(１，２) = ４
　このとき、　Ｆ(Ｆ(２)） = Ｆ(３) = ４ = 2²
　　　　・・・・・・・・・・・・・・・・・・・・・

　上記の具体的な計算から、Ｆ(ｎ)が、条件を満たすことが理解できる。

　空舟さんによれば、Y_k の項を２つずつペアにして、２乗したものを横に並べてZ字状の挙動
をさせるイメージとのことです。

　Ｆ(2) = 3　、Ｆ(2²) = 3²　、Ｆ(2^(2^k)) = 3^(2^k)　、・・・

　Ｆ(3) = 2²　、Ｆ(3²) = 2⁴　、Ｆ3^(2^k)) = 2^(2^k+1)　、・・・

　Ｆ(5) = 6　、Ｆ(5²) = 6²　、Ｆ(5^(2^k)) = 6^(2^k)　、・・・

　Ｆ(6) = 5²　、Ｆ(6²) = 5⁴　、Ｆ(6^(2^k)) = 5^(2^k+1)　、・・・


(★)　ｎ≧２ のとき、Ｇ(ａ，ｂ) = ｎ となる (ａ，ｂ)∈N×N を唯一とることができる。

　Ｇ(ａ，ｂ) が全単射であることを示します。（ほとんど直感的だと思います）

Ｇの全射性：（★で、(ａ，ｂ)をとることができることの説明）

（証明）　２以上の整数Mに対して、m₁ = M とおく。m_k が平方数ならば、　m_k+1=√m_k とおく。

　　　　これを繰り返すと、２以上の範囲で単調減少の挙動なので、m_b が平方数ではないよ
　　　うなb∈Nが存在する。

　　　　数列{Y_k}の定義より、m_b = Y_a となる ａ∈N をとれる。そうやって得たａ、ｂに対して、
　　　Ｇ(ａ，ｂ） = M が成り立つ。　　（証終）

Ｇの単射性：(★での(ａ，ｂ)が唯一であることの説明)

（証明）　Ｇ(ａ，ｂ) = Ｇ(ｃ，ｄ)と仮定する。b≦dと仮定する。両辺の√を(b-1)回とる操作により、
　　　　　Ｇ(ａ，１) = Ｇ(ｃ，ｄ−ｂ＋１) が得られる。
　　　　　辺の値が平方数かどうかの情報より、ｄ = ｂ が要求され、そうすると、Y_a = Y_c とな
　　　　　るので、ａ = ｃ が要求される。　　（証終）


　ａｔ さんからのコメントです。（平成２５年１１月２７日付け）

　空舟さん、この問題を考えていただきありがとうございます。上記のように、Ｆ(ｎ)を定義す
れば、確かに Ｆ(Ｆ(ｎ)=ｎ² となりますね。

　本問は、「Mathematical Excalibur」に掲載されています。本問の問題文と解法は次のファ
イルにあります。(Page 3  Problem 281 を見てください)

　ここでは、2つの解法が紹介されてあります。
　　solution 1. は空舟さんの解法と同じです。
　　solution 2. は g(g(n))=2*n を満たすような関数gを利用する解法です。


　ＧＡＩ さんからのコメントです。（平成２５年１１月２８日付け）

　イメージが掴みにくかったので、具体的に、F：N--->N　の動きを調べてみました。

F(1)=1　、F(2)=3　、F(3)=4　、F(4)=9　、F(5)=6　、F(6)=25　、F(7)=8　、F(8)=49　、F(9)=16
F(10)=11　、F(11)=100　、F(12)=13　、F(13)=144　、F(14)=15　、F(15)=196　、F(16)=81
F(17)=18　、F(18)=289　、F(19)=20　、F(20)=361　、F(21)=22　、F(22)=441　、F(23)=24
F(24)=529　、F(25)=36　、F(26)=27　、F(27)=676　、F(28)=29　、F(29)=784　、F(30)=31
F(31)=900　、F(32)=33　、F(33)=1024　、F(34)=35　、F(35)=1156　、F(36)=625　、F(37)=38
F(38)=1369　、F(39)=40　、F(40)=1521　、F(41)=42　、F(42)=1681　、F(43)=44　、F(44)=1849
F(45)=46　、F(46)=2025　、F(47)=48　、F(48)=2209　、F(49)=64　、F(50)=51　、F(51)=2500
F(52)=53　、F(53)=2704　、F(54)=55　、F(55)=2916　、F(56)=57　、F(57)=3136　、F(58)=59
F(59)=3364　、F(60)=61　、F(61)=3600　、F(62)=63　、F(63)=3844　、F(64)=2401　、F(65)=66
F(66)=4225　、F(67)=68　、F(68)=4489　、F(69)=70　、F(70)=4761　、F(71)=72　、F(72)=5041
F(73)=74　、F(74)=5329　、F(75)=76　、F(76)=5625　、F(77)=78　、F(78)=5929　、F(79)=80
F(80)=6241　、F(81)=256　、F(82)=83　、F(83)=6724　、F(84)=85　、F(85)=7056　、F(86)=87
F(87)=7396　、F(88)=89　、F(89)=7744　、F(90)=91　、F(91)=8100　、F(92)=93　、F(93)=8464
F(94)=95　、F(95)=8836　、F(96)=97　、F(97)=9216　、F(98)=99　、F(99)=9604　、F(100)=121
････

　これでいいですかね？

　また、atさんが紹介されたサイトで、g：N-->N　g(g(n))=2n を構成してみたら、次のような対
応になりました。ちなみに奇素数ｐを3としています。

g(1)=6　、g(2)=12　、g(3)=1　、g(4)=24　、g(5)=30　、g(6)=2　、g(7)=42　、g(8)=48　、g(9)=54
g(10)=60　、g(11)=66　、g(12)=4　、g(13)=78　、g(14)=84　、g(15)=5　、g(16)=96　、g(17)=102
g(18)=108　、g(19)=114　、g(20)=120　、g(21)=7　、g(22)=132　、g(23)=138　、g(24)=8
g(25)=150　、g(26)=156　、g(27)=9　、g(28)=168　、g(29)=174　、g(30)=10　、g(31)=186
g(32)=192　、g(33)=11　、g(34)=204　、g(35)=210　、g(36)=216　、g(37)=222　、g(38)=228
g(39)=13　、g(40)=240　、g(41)=246　、g(42)=14　、g(43)=258　、g(44)=264　、g(45)=270
g(46)=276　、g(47)=282　、g(48)=16　、g(49)=294　、g(50)=300　、g(51)=17　、g(52)=312
g(53)=318　、g(54)=18　、g(55)=330　、g(56)=336　、g(57)=19　、g(58)=348　、g(59)=354
g(60)=20　、g(61)=366　、g(62)=372　、g(63)=378　、g(64)=384　、g(65)=390　、g(66)=22
g(67)=402　、g(68)=408　、g(69)=23　、g(70)=420　、g(71)=426　、g(72)=432　、g(73)=438
g(74)=444　、g(75)=25　、g(76)=456　、g(77)=462　、g(78)=26　、g(79)=474　、g(80)=480
g(81)=486　、g(82)=492　、g(83)=498　、g(84)=28　、g(85)=510　、g(86)=516　、g(87)=29
g(88)=528　、g(89)=534　、g(90)=540　、g(91)=546　、g(92)=552　、g(93)=31　、g(94)=564
g(95)=570　、g(96)=32　、g(97)=582　、g(98)=588　、g(99)=594　、g(100)=600
　　……
　　……
g(102)=34　、g(108)=36　、g(114)=38　、g(120)=40　、g(132)=44　、g(138)=46　、g(150)=50
g(156)=52　、g(168)=56　、g(174)=58　、g(186)=62　、g(192)=64　、g(204)=68　、g(210)=70
g(216)=72　、g(222)=74　、g(228)=76　、g(240)=80　、g(246)=82　、g(258)=86　、g(264)=88
g(270)=90　、g(276)=92　、g(282)=94　、g(294)=98　、g(300)=100　、g(312)=104　、g(318)=106
g(330)=110　、g(336)=112　、g(348)=116　、g(354)=118　、g(366)=122　、g(372)=124
g(378)=126　、g(384)=128　、g(390)=130　、g(402)=134　、g(408)=136　、g(420)=140
g(426)=142　、g(432)=144　、g(438)=146　、g(444)=148　、g(456)=152　、g(462)=154
g(474)=158　、g(480)=160　、g(486)=162　、g(492)=164　、g(498)=166　、g(510)=170
g(516)=172　、g(528)=176　、g(534)=178　、g(540)=180　、g(546)=182　、g(552)=184
g(564)=188　、g(570)=190　、g(582)=194　、g(588)=196　、g(594)=198　、g(600)=200


　ａｔ さんからのコメントです。（平成２５年１１月３０日付け）

　私も、Ｆ(ｎ)の値を調べてみました。Maximaを利用して調べた結果、Ｆ(1)〜Ｆ(10000)の値は
表のようになりました。