手数が多い問題は解いてて楽しいので解説を書いて楽しさを共有していきたいと思います. (で集合の要素数を表します. 可能不可能とかは構成が可能か不可能かということです)
ISL2021N8
以下の条件を満たす正整数を全て求めよ:
ある整数係数多項式が存在して任意の正整数に対してをで割った余りが成立する.
ここではを回適用したものである.
なお, 以下をで割った余りをと書く.
まず問題を見たら多項式をネストさせていることに目が行きます. すると2019JMO春P9とか次の補題とかを思い出します.
Periodicity lemma(和訳は定着していないがせめて和訳するなら周期性補題)
を整数係数多項式とし, とすると. 特にとすれば.
この補題を使う問題はたまにあるが(
これとか
,
IMO2006P5とか
,
これ
,
これ
)とりあえずは忘れて条件を満たすを探してみよう. なんか取り得る値がで大体半減する関数を見つければ良い.
, 可能. それはそう.
, とか. はい.
, . はい. での値域がになるなーというお気持ちから思いつきそう.
, のアナロジーからとか. 後者を先に思いつくと迷走しそう(自分は迷走した).
...出来そうだし出来なさそう.
とりあえずのときはが回ってくれそうである. が行けてるのでは可能そう. ここでを考えてみる.
ここで何個かアイデアが浮かぶ. まず多項式に限らず一般の関数としてなら構成が存在しそうということ. 例えば倍して良い感じに桁を切り捨てとか(多少やりにくそう), もっとやりやすいのはで割って切り捨てであろう.
これは関数を有向グラフと見なすというイメージ化によっても認識しやすいと思う. なんか入次数の頂点を沢山作ってあげれば良さそう.
またの関数は全て多項式で表現出来る(これには気付かなくても構成出来るが). これは関数全体の集合の要素数が個で因数定理を考えると次以下の多項式は全て関数として異なるのでの多項式を関数としてみるとその個数は個あるためである.
ということで構成が可能であることが分かったが実際に構成してみる. 上の考察にあるようで割って切り捨てる関数を構成しよう. はしか取らず, の部分はフェル小とかで強引に作れそう. この辺からが構成出来ると思う.
ということでが冪か素数のときは可能であることが分かった. 次はが素冪でない場合を考えたい. というのも奇素数の冪で書ける数は冪が可能なのを考えても構成が可能そうだし, かといって今までの構成が回るわけでは無く, この問題で一番ややこしい部分になりそうであるため, また素冪で無いものがどうなるかによって方針が大きく変わるためである.(あとは素冪でないとき中国の剰余定理が使えそうというのもある)
素冪でない正整数の最大の特徴と言えば互いに素な以上の整数の積の形で書けることだろう. ということで, (は互いに素な以上の整数)と書けると仮定する.
中国の剰余定理からはとの組として考える事が出来る. ここで何かヤバいことが起こらないかと考えると(流石に不可能であることを予想している)となる辺りでなんかおかしいことになりそうである. だからのどちらかがになる. 対称性よりとする. するとあるがあってが成立する. するとの前後で関数ののとりうる値が半減してしまうのでのとりうる値は変化しない. よってこれ以降でとりうる値の個数は変化しない!!!これは矛盾である.
これを理解するのには関数のネストの値域のイメージとして(を集合, とすると)が成立することを持っておくと良いと思う. (これを使う問題はすぐには思い出せないけど無くはなかった気がする. A分野の集合と写像が出てくる問題にありそう)
ということでが素冪の時が残った. これが可能か不可能か.
実はこれは不可能である. 自分はの場合をプログラミングで全探索して確信を持った.(ずるい) まあ直感として構成するのは厳しそうという風にはなると思う. 例えばの関数は個あるが多項式で表現出来る関数は個より全然少ないのでそれに対して条件が厳しすぎるなという気分になるでしょう.
とりあえず状況設定を, (は奇素数, は以上の整数)とします. での多項式の特徴といえば()で同じものの値はで同じであるというものがあるでしょう. これはに対する大きな制約となっていそうです. もう少し踏み込んでのの値を固定したときの取り得る値の個数はどのように評価出来るのかを考えたい. つまり何個かの値を確定したとき残りの値にどれくらいの制約が付くのかを精密化しようというノリである. で, これはヘンゼルの補題 (雑に言うとでの因数分解を帰納的にに持ち上げるみたいな話) の考え方と酷似しているのでなんらかの議論ができそうである. としたときと書ける. そしてがわかる.(やっぱり微分便利(真面目にやると二項定理で示せる))だからならとりうる値は通り以下に, そうでないなら通り全てが取れるみたいな感じになることが分かる. (このように帰納的にに関する議論をすることは多いかも(すぐには例が出せないけど例えばJMOho2010P2とか
OMC60Fとか?
ISL1998N5とか?
))
結局の値を固定すると取り得る値は(動ける値の個数と比べて)元と変わらないか以下に減少する事が分かる.
前者後者どちらかになるかはの値別に決まるのでの場合を考えるのが都合が良さそうである. の類ごとに頂点を用意してでの値の行き先に辺を張った有向グラフを考えたい. ネストを繰り返し最後値が通りになるのだからこのグラフはこんな感じ
木みたいなやつ
になるはず. これをみると不動点が丁度一個ある, これの類をとでも表すとこの類のによるでの行き先はの増加に伴い常に個以下に減っていく(最後個になるまで).
だから全ての整数に対してが成立してしまえば後はオーダーで取り得る値は減っていくし, が成立するのだからが十分大きいところではは不可能という結論を得る.(なので)
この議論の評価を改善していきたい. まず出来る事は取りうる値の個数がになる場所をもっと精密に議論することだろう. というのも普通の状況を考えたら次の図のような感じで(黒い頂点に対応する類にを作用させると取りうる値の個数がになる)
イメージ
しかし極端なケースが問題である
極端なケース
左のケースなら早い段階(オーダー)で一点に潰れるのでそれを使えば良さそう. 右のケースならもっと黒の頂点があるはず. するとわかることとして結構早い段階(か定数ぐらいのオーダーで)で全部の類は(矢印を辿ると)黒頂点を通過するということである. そうすると全て黒頂点を通過した後取りうる値の個数は雑に評価しても個なのでと良い勝負が出来そう.
というわけで全ての類が黒頂点を通過した時をとして, 最後に通過した類の一つをとして表そう. (これはISLにおける文字の置き方と同じなのでそちらも参照されたい) まず, がオーダーで抑えられる事を言いたい. これはからに変わる際の類のせいで以上要素数が減少するので, と合わせて評価出来そう. 実際にはからの類の行き先を除いた集合の
での行き先がからの類の行き先を除いたものを含むことを使って
(の類の行き先の要素数), 結局が必要. だからは大体以下である事が必要なのではオーダーで抑えられた.
がオーダー(未満)で抑えられるということは上にあったグラフの行き先がまだ一点になっていない可能性が十分にあるのでそれを使った議論が出来そう. また, 二個上の段落の末尾の議論が回りそう(まだギリギリ厳しいか)という気分にもなるからそこら辺を精密に評価してみる. よっての評価をする.
回目の段階で個の類は一点に集まっているのでそれらの像は高々個. 残りの個の類も黒い頂点を少なくとも一回通るのでその元の要素は高々個. 従って. あれ, 普通に上で見つけたの評価と組み合わせたら評価回るじゃん.
, つまり.(?!!!!)
これはもうやるだけですね. より.これより.よって矛盾.
これにより求めるの条件はは冪または素数のとき.
勝利!
難しかった...手数多い...
グラフのイメージや帰納的にを考えたり, いろんな事を駆使しましたね. あと周期性補題結局使わなかった()