FANDOM


GoucherのT関数とは、組合せ論に起因する、急成長する関数である。[1]名前の通り、Adam Goucherにより考案された。

C8問題とその変形編集

数学オリンピックにはたくさんの問題が投稿される。良い問題がショートリストに乗り、とくによい問題6つが本選に使用される。しかし、ショートリストどまりになる問題も少なからずある。次の問題は、2009年にオーストリアから投稿された問題である(これはC8問題と呼ばれ、組合せ論の問題の中で最も難しいもの):

整数n≧2に対し、次のような操作を施して得られる関数h(n)を定義する。但し、nの最も右の桁をrとする。
  • r=0なら、h(n)=n/10である。つまり、右端の連続するゼロを取り除く。
  • それ以外、rが非ゼロなら、次のような操作をする。Rを、nのr以上の桁をすべて含む右側の部分をRとおく。残りの部分はLとする。h(n)を、LにR-1を2回繰り返して連結したものとする。例えば、n=17151345543なら、r=3、L=17151、R=345543で、R-1=345542、h(n)=17151345542345542である。
全ての整数n≧2に対し、h関数を有限回施すことで、その値を1にすることが出来ることを証明せよ。

例えば、2 → 11 → 1010 → 101 → 1000 → 100 → 10 → 1となる。

この問題は非自明である。さらに、この問題をより難しくした変形を考えることが出来る。h関数ではR-1を2回繰り返していたが、この変種ではc回繰り返す。ここで、cは2から始まり、関数を施すごとに1ずつ増えてゆく数である。例えば、2回目の変形ではR-1を3回、3回目ならR-1を4回…繰り返す。n=2の時の例はこうである:

2 → 11 → 101010 → 10101 → 10100000 → 1010000 → 101000 → 10100 → 1010 → 101 → 1000000 → 100000 → 10000 → 1000 → 100 → 10 → 1

C8問題でもそう呼ばれていたが、nを「数」と考えず、10進数の繋がった文字列と考えるべきである。文字列であると制限する必要はないので、代わりにそれらを正の整数の列であるとする。例えば、{1, 0, 1, 0, 1}は10101と表される。

文字列を順序数へ対応させる関数gを考えよう。g("0")=1とする。g("3420001107000")=ω^g(“231″) + 1 + 1 + 1 + ω^g(“00″) + 1 + ω^g(“6″) + 1 + 1 + 1とする。特に言えば、数を非ゼロ整数に分解し、その桁から1づつ引き、それを基数に対応させ、べき乗の乗数をω問い、すべて足し合わせる操作である。これを再帰的に対応させる。

連続するゼロを消去することはそれをすべて1に替えることで実現できる。もう一つの操作は、 ω^nを(ω^(n−1)).cと置き換えるものである。ここで、cは上記と同じである。c < ωであるため、この列は減少していく。

\(\epsilon_0\)より小さい順序数は整列集合であるため、そこには無限減少列は存在しない。よって、この列は必ず有限回の操作で1に達する。Q.E.D.

この操作で1に達するまでの長さはとても長い。その時間の長さをT(n)とおく。T(1)=0、T(2)=16、そしてT(3)はとても大きくなる。最初のほうの列を示すと、3 → 22 → 212121 → 212120212120212120212120 → 21212021212021212021212 → 212120212120212120212111111 → 212120212120212120212111110212111110212111110212111110212111110212111110 → …

この_T関数は急増加関数で\(f_{\epsilon_0}(x)\)ほどである。C8問題の物を用いれば\(f_4(x)\)ほどとなる。似たような関数(グッドスタインの定理を参照)はn=12の時にグラハム数を超える。

変形の問題C8'は、国際数学オリンピックには難しすぎて出題されないだろう。ペアノ公理では証明できない。

出典編集

  1. http://cp4space.wordpress.com/2012/12/15/fast-growing-1/

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki