4

ISL2021N8

379
0

手数が多い問題は解いてて楽しいので解説を書いて楽しさを共有していきたいと思います. (#Xで集合の要素数を表します. 可能不可能とかは構成が可能か不可能かということです)

ISL2021N8

以下の条件を満たす正整数nを全て求めよ:
ある整数係数多項式P(x)が存在して任意の正整数mに対して#{Pm(k)nで割った余り|kZ}=n2mが成立する.
ここでPmPm回適用したものである.
なお, 以下{Pm(k)nで割った余り|kZ}Pm(Z/nZ)と書く.

まず問題を見たら多項式をネストさせていることに目が行きます. すると2019JMO春P9とか次の補題とかを思い出します.

Periodicity lemma(和訳は定着していないがせめて和訳するなら周期性補題)

P(x)を整数係数多項式とし, a,bZ,abとするとab|P(a)P(b). 特にan=Pn(0)とすればan+mam(modan).

この補題を使う問題はたまにあるが( これとか , IMO2006P5とか , これ , これ )とりあえずは忘れて条件を満たすnを探してみよう. なんか取り得る値がmodnで大体半減する関数を見つければ良い.

n=1, 可能. それはそう.
n=2, P(x)=2x,x(x+1)とか. はい.
n=3, P(x)=x2+1. はい. modpx2の値域がp12になるなーというお気持ちから思いつきそう.
n=4, n=2のアナロジーからP(x)=2x,x(x+1)(x+2)とか. 後者を先に思いつくと迷走しそう(自分は迷走した).
n=5...出来そうだし出来なさそう.
とりあえずn=2mのときはP(x)=2xが回ってくれそうである. n=3が行けてるのでn=pは可能そう. ここでn=pを考えてみる.

ここで何個かアイデアが浮かぶ. まず多項式に限らず一般の関数としてなら構成が存在しそうということ. 例えば2倍して良い感じに桁を切り捨てとか(多少やりにくそう), もっとやりやすいのは2で割って切り捨てであろう.
これは関数を有向グラフと見なすというイメージ化によっても認識しやすいと思う. なんか入次数2の頂点を沢山作ってあげれば良さそう.
またmodpの関数は全て多項式で表現出来る(これには気付かなくても構成出来るが). これは関数全体の集合の要素数がpp個で因数定理を考えるとp1次以下の多項式は全て関数として異なるのでmodpの多項式を関数としてみるとその個数はpp個あるためである.
ということで構成が可能であることが分かったが実際に構成してみる. 上の考察にあるよう2で割って切り捨てる関数fを構成しよう. n2f(n)0,1しか取らず, 1の部分はフェル小とかで強引に作れそう. この辺からP(x)=p+12(n(n(n2)(n4)(np+1))p1)が構成出来ると思う.

ということでn2冪か素数のときは可能であることが分かった. 次はnが素冪でない場合を考えたい. というのも奇素数の冪で書ける数は2冪が可能なのを考えても構成が可能そうだし, かといって今までの構成が回るわけでは無く, この問題で一番ややこしい部分になりそうであるため, また素冪で無いものがどうなるかによって方針が大きく変わるためである.(あとは素冪でないとき中国の剰余定理が使えそうというのもある)

素冪でない正整数の最大の特徴と言えば互いに素な2以上の整数の積の形で書けることだろう. ということで, n=ab(a,bは互いに素な2以上の整数)と書けると仮定する.
中国の剰余定理からPm(k)modnPm(i)modaPm(j)modbの組として考える事が出来る. ここで何かヤバいことが起こらないかと考えると(流石に不可能であることを予想している)n2m=2となる辺りでなんかおかしいことになりそうである. #Pm(Z/aZ)#Pm(Z/bZ)=2だから#Pm(Z/aZ),#Pm(Z/bZ)のどちらかが1になる. 対称性より#Pm(Z/aZ)=1とする. するとあるt<mがあって#Pt(Z/aZ)2,#Pt+1(Z/aZ)=1が成立する. するとt,t+1の前後で関数のmodaのとりうる値が半減してしまうのでmodbのとりうる値は変化しない. よってこれ以降modbでとりうる値の個数は変化しない!!!これは矛盾である.
これを理解するのには関数のネストの値域のイメージとして(Xを集合, f:XXとすると)Xf(X)f2(X)f3(X)...が成立することを持っておくと良いと思う. (これを使う問題はすぐには思い出せないけど無くはなかった気がする. A分野の集合と写像が出てくる問題にありそう)

ということでnが素冪の時が残った. これが可能か不可能か.
実はこれは不可能である. 自分はn=9の場合をプログラミングで全探索して確信を持った.(ずるい) まあ直感として構成するのは厳しそうという風にはなると思う. 例えばmodp2の関数はp2p2個あるが多項式で表現出来る関数はp2p(p1)個より全然少ないのでそれに対して条件が厳しすぎるなという気分になるでしょう.

とりあえず状況設定を, n=pt(pは奇素数, t2以上の整数)とします. modptでの多項式の特徴といえばmodps(s<t)で同じものの値はmodpsで同じであるというものがあるでしょう. これはPに対する大きな制約となっていそうです. もう少し踏み込んでkmodpsの値を固定したときP(k)modptの取り得る値の個数はどのように評価出来るのかを考えたい. つまり何個かの値を確定したとき残りの値にどれくらいの制約が付くのかを精密化しようというノリである. で, これはヘンゼルの補題 (雑に言うとmodpでの因数分解を帰納的にmodpNに持ち上げるみたいな話) の考え方と酷似しているのでなんらかの議論ができそうである. ka(modps)としたときk=a+bpsと書ける. そしてP(k)=P(a+bps)P(a)+bpsP(a)(modps+1)がわかる.(やっぱり微分便利(真面目にやると二項定理で示せる))だからP(a)0(modp)ならとりうる値はpts1通り以下に, そうでないならpts通り全てが取れるみたいな感じになることが分かる. (このように帰納的にpNに関する議論をすることは多いかも(すぐには例が出せないけど例えばJMOho2010P2とか OMC60Fとか? ISL1998N5とか? ))
結局modpsの値を固定すると取り得る値は(動ける値の個数と比べて)元と変わらないか1p以下に減少する事が分かる.
前者後者どちらかになるかはmodpの値別に決まるのでs=1の場合を考えるのが都合が良さそうである. modpの類ごとに頂点を用意してPでの値の行き先に辺を張った有向グラフを考えたい. ネストを繰り返し最後値が1通りになるのだからこのグラフはこんな感じ
木みたいなやつ 木みたいなやつ
になるはず. これをみると不動点が丁度一個ある, これの類をnα(modp)とでも表すとこの類のPmによるmodptでの行き先はmの増加に伴い常に1p個以下に減っていく(最後1個になるまで).
だから全ての整数kに対してPm(k)αmodpが成立してしまえば後は1pオーダーで取り得る値は減っていくし, mpが成立するのだからtが十分大きいところではn=ptは不可能という結論を得る.(2<pなので)

この議論の評価を改善していきたい. まず出来る事は取りうる値の個数が1pになる場所をもっと精密に議論することだろう. というのも普通の状況を考えたら次の図のような感じで(黒い頂点に対応する類にPを作用させると取りうる値の個数が1pになる)
イメージ イメージ
しかし極端なケースが問題である
極端なケース 極端なケース
左のケースなら早い段階(logオーダー)で一点に潰れるのでそれを使えば良さそう. 右のケースならもっと黒の頂点があるはず. するとわかることとして結構早い段階(logか定数ぐらいのオーダーで)で全部の類は(矢印を辿ると)黒頂点を通過するということである. そうすると全て黒頂点を通過した後取りうる値の個数は雑に評価してもpt1個なのでpt2mと良い勝負が出来そう.

というわけで全ての類が黒頂点を通過した時をmとして, 最後に通過した類の一つをkr(modp)として表そう. (これはISLにおける文字の置き方と同じなのでそちらも参照されたい) まず, mlogオーダーで抑えられる事を言いたい. これはa=#Pm1(Z/ptZ)からb=#Pm(Z/ptZ)に変わる際rの類のせいで(p1)pt2以上要素数が減少するので, a2b,baと合わせて評価出来そう. 実際にはPm1(Z/ptZ)からrの類の行き先を除いた集合の
Pでの行き先がPm(Z/ptZ)からrの類の行き先を除いたものを含むことを使って
a2b=2(b(rの類の行き先の要素数)+pt2)2(apt1+pt2), 結局2pt2(p1)a=n2m12bが必要. だから2mは大体p以下である事が必要なのでmlogオーダーで抑えられた.

mlogオーダー(p未満)で抑えられるということは上にあったグラフの行き先がまだ一点になっていない可能性が十分にあるのでそれを使った議論が出来そう. また, 二個上の段落の末尾の議論が回りそう(まだギリギリ厳しいか)という気分にもなるからそこら辺を精密に評価してみる. よって#Pm(Z/ptZ)の評価をする.

m1回目の段階でm個の類は一点に集まっているのでそれらの像は高々pt2個. 残りのpm個の類も黒い頂点を少なくとも一回通るのでその元の要素は高々(pm)pt2個. 従ってb=#Pm(Z/ptZ)(pm+1)pt2. あれ, 普通に上で見つけたa,bの評価と組み合わせたら評価回るじゃん.
pt2(p1)(pm+1)pt2, つまりm2.(?!!!!)
これはもうやるだけですね. m2よりpt4bpt2(p1).これよりp=2.よって矛盾.

これにより求めるnの条件はn2冪または素数のとき.

勝利!

難しかった...手数多い...

グラフのイメージや帰納的にpnを考えたり, いろんな事を駆使しましたね. あと周期性補題結局使わなかった()

投稿日:2022722
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

整数が好きです

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中