[過去ﾛｸﾞ] 有限数列上の変換について [無断転載禁止]©2ch.net (84ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

71: ◆tAo.kQ2STk 2016/01/26(火)12:01 ID:C203oPVR(1)調 AAS
ふと思いついたんで書いてみる。チラ裏失礼。

y=C(x)に対し、その定義域が0からN-1までの整数であり、又、値域が0からN-1までの整数であり、かつ全単射であると仮定する。

定理 1
Cによるm回の写像をC^m(・)とする時、全ての整数i<Nについて、ある整数m>0が存在し、i = C^m(i)が成り立つ。
直感としては、任意の全単射の整数関数及び任意の整数に対して長さmのループが存在する。
この時、D(i)=C^{m-1}(i)によりDを表現できる。

証明 1
背理法により、ループが存在しないと仮定する。つまり、ある整数iが存在し、全てのmについて、i \neq C^m(i)
鳩の巣の原理より、m>Nについて、系列C^m(i)には重複が存在する筈である。
つまり、C^{m+n}(i) = C^{m+n+h}(i)となるような整数n, hが存在する。
両辺にD^{m+n}を合成すると
i = C^h(i)
よって、全てのmについてi \neq C^m(i)が成り立つような整数iは存在しない。

定理 2
任意のCについて、全てのiに対して最小の整数mを計算した時、その値の集合MのサイズはO(√N)で押さえられる

証明 2
明らかに、あるループ長m_jに対して、そのループ長であるようなループの個数k_jが存在し、
N = \sum_j m_jk_j
M = \{m_1, m_2, ..., m_{M.size}\}
が成り立つ。今各ループ長及び個数に対してm_j = j, k_j = 1を仮定すると、
N \simeq (M.size)^2 / 2
となる。

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.013s