NF杯2023(N) - 余談　f(x,y)がwell-definedであることの証明

ここの解説では, $f(x,y)$ がwell-definedであることの証明を行います.

$f(x,y)$の定義は,「～～～を満たす最小の正の整数$k$」と書かれています. ここで,「～～～を満たす正の整数$k$」が1つでも存在することが言えれば,well-definedであることが言えます.

つまり,

$$X=\lbrace k\in\mathbb{Z}_{\gt 0} ; \exists N,\forall n\geq N, s.t. a_{n+k}\equiv a_{n}\pmod{p}\rbrace$$

という集合に対して,

$$f(x,y):=\min X$$

としているわけですが,

$X$が空集合でなかったら$X$は(正の整数からなる集合なので)最小値の存在が保証されるわけです.

逆に言えば,$X$が空集合だったらまずいので,$X$が空集合でないことを証明すればよいことになります.

というわけで証明

集合$A$を以下で定めます.

$$A=\lbrace (a,b);0\leq a,b\leq p-1\rbrace$$

このとき,$|A|=p^2\lt \infty$となります.

$\lbrace (a_n\mod{p} ,a_{n+1}\mod{p})\rbrace_{n=0,1,\ldots}$

という列を考えると,各項は全て$A$の元となります.

よって,

$$(a_0,a_1),(a_1,a_2),\ldots,(a_{p^2},a_{p^2+1})$$

の$p^2+1$個の組を考えると,鳩の巣論法によって,一致するペアが存在することが言えます.

つまり,ある$0\leq i\lt j\leq p^2$という整数$i,j$が存在して,

$$(a_i,a_{i+1}) \equiv (a_j,a_{j+1}) \Leftrightarrow a_i\equiv a_j \land a_{i+1}\equiv a_{j+1}$$

となります.このとき,数列$\lbrace a\rbrace$は三項間漸化式で定義されるので,2項さえ一致していればそれ以降はずっと同じです.

よって,

$$a_{i+2}\equiv a_{j+2} \land a_{i+3}\equiv a_{j+3}\land a_{i+4}\equiv a_{j+4}\land \cdots$$

となります.

このとき,$N=i$とすれば,$n\geq N$なる任意の整数$n$について

$$a_{n+(j-i)}\equiv a_{n}\pmod{p}$$

が成立します.

よって,$(j-i)\in X$となるため,$X$が空でないことが言えました.

余談の余談

周期の定義をこのようにしていますが,実は$0\leq x\lt p,1\leq y\lt p$の条件ならば$N=0$としても問題ないです.つまり,周期の定義を

「任意の非負整数$n$に対して,$a_{n+k}\equiv a_n$が恒等的に成り立つような最小の正の整数$k$」

としても問題ないわけです. つまり,この問題で問われている状況の範囲内では,正直どっちでもいいのですが,この定義にすると$y=0$のときに問題が発生します.

$y=0,x\neq 0$ならば,$a_n$は

$$0,1,x,x^2,x^3,\ldots$$

となります.$a_n=0$となるような$n$は1個しか無いので周期が定義できません.

特に,$x=0$かつ$y=0$だと

$$0,1,0,0,0,\ldots$$

となると,こっちもうまく周期が定義できなくなってしまいます.

ちなみに,問題で採用している,「ある正整数$N$が存在し～」だと,$y=0$の場合でも問題なく周期を定義することができます.

実はこの問題の原案はシグマを取る範囲が$1\leq y\lt p$ではなく$0\leq y\lt p$でした.さらに,周期の定義も「ある正整数$N$が存在し～」ではないものでした.もしこのままだと$y=0$の場合に$f(x,y)$を定義できなくなるため,問題不備になってしまいます.

有志コン作問のメンバーに上記の点を指摘されたとき,「とりあえず周期の定義を変えれば問題不備はなくなる」と思ったため現在のような周期の定義に変えたのですが,その上で特性方程式の解に0がある場合の例外処理があまり好きじゃないと思ったため,$y=0$の場合を省くことにしたわけです.

結果,より広い場合でも適用できるような定義だけが残ったという裏話でした.