数学オリンピック2018 1次予選解説 その4 ( 最後 )

はじめに

※本記事は、2018/2/9にHatenaBlogに投稿した記事を移行したものです
ここまで続けてきました、数学オリンピック国内1次予選 ( JMO ) の解説、いよいよ最後です。オリジナルの問題、解答 ( 答えの数値だけ ) は、こちらに公開されています。

• 問1～問6 … その1
• 問7～問9 … その2
• 問10,11 … その3
• 問12 … 今回

問題と解説

問題文の詳細については、冒頭のリンクよりご参照ください。以下では要約した問題文で説明していきます。

問12

問題・答え

次の条件を満たす整数列$a_1,a_2,\cdots$、正の整数$N$に対して、$N$の取り得る最大値を求めよ。

• $任意の正の整数m,nに対し、m,n\ge 30 かつ |n-m|\ge 2018 \Rightarrow a_{m+n}=a_m+n または a_{m+n}=a_n+m$
• $a_{N+1}-a_{N}\neq 1$

答え: 4065

解説

数列からのすり替え

流石最終問題、訳が分かりません。条件を提示されても、じゃあどんな数列を調べれば良いのか、皆目見当がつきません。
しかし、ちょっとしたことに気付けば、実はこの問題は数列の問題ではないことが分かります。

$a_{m+n}=a_m+n または a_{m+n}=a_n+m$ この条件、ちょっと変形してみましょう。

$$\begin{aligned} &~a_{m+n}=a_m+n または a_{m+n}=a_n+m \\ &\Leftrightarrow a_{m+n}-a_m=n または a_{m+n}-a_n=m \\ &\Leftrightarrow a_{m+n}-a_m=(m+n)-m または a_{m+n}-a_n=(m+n)-n \\ \end{aligned}$$

いや、単に差の形にしただけじゃないか? と思われるかも知れません。が、ここでおもむろに、正の整数同士の関係 $\equiv$ を独自に作って導入してみます。

• 正の整数$u,v$に対して、関係$\equiv$を$u\equiv v\Leftrightarrow a_u-a_v=u-v$と定義する。

そうすると、最初に挙げた条件は更に次のように変形できます。

$$\begin{aligned} &~a_{m+n}=a_m+n または a_{m+n}=a_n+m \\ &\Leftrightarrow a_{m+n}-a_m=(m+n)-m または a_{m+n}-a_n=(m+n)-n \\ &\Leftrightarrow m+n\equiv m または m+n\equiv n \end{aligned}$$

このように、数列の条件が関係の条件にすり替わりました。

ところで、関係$\equiv$ってなに? 合同式 $23\equiv 83~mod~10$ と同じモノなの? と、字面が紛らわしいと思われるかも知れませんが、全く別物です。が、敢えてこの表現にしたのは適切な記号が思いつかなかったからというのもありますがちゃんと意図があります。それは、この関係$\equiv$が同値関係の一種であると主張したいわけです。

実際、今回作った関係$\equiv$は同値関係の3要件を全て満たします。

• 反射律: $x\equiv x$
  $\because a_{x}-a_{x}=0=x-x$
• 対称律: $x\equiv y\Rightarrow y\equiv x$
  $\because a_{x}-a_{y}=x-y\Rightarrow a_{y}-a_{x}=-(a_{x}-a_{y})=-(x-y)=y-x$
• 推移律: $x\equiv yかつy\equiv z\Rightarrow x\equiv z$
  $\because a_{x}-a_{y}=x-y かつ a_{y}-a_{z}=y-z \Rightarrow a_{x}-a_{z}=(a_{x}-a_{y})+(a_{y}-a_{z})=(x-y)+(y-z)=x-z$

一般に同値関係というのは、お仲間グループを幾つか ( 無限の場合も含む ) 作って各要素をそのグループに割り当てる場合の、同じグループであることを示すものです。
つまり、この関係$\equiv$を導入することで、数列の実態がどうであるか、ではなく、正の整数をなんらかの仲間同士に分類するやり方に注力することができるという訳です。
※この関係$\equiv$に相当する数列$\{a_n\}$を構成できることは trivial ですから、もはや完全に数列のことは忘れてしまって良いです。

問題再考

それでは、問題を変形して見直してみましょう。

• 次の条件を満たす正の整数に対する同値関係$\equiv$・正の整数$N$に対して、$N$の取り得る最大値を求めよ。
  • $任意の正の整数 m,n に対し、m\ge 30 かつ n\ge m+2018\Rightarrow m+n\equiv m または m+n\equiv n$
  • $N+1\not\equiv N$

この第一の条件を見ると、$x\ge 2078$であれば$x-30\ge 30+2018$ですから、$x\equiv 30 または x\equiv x-30$ と、より小さい数に対しての$\equiv$の関係が潜んでいます。ということは、詳細は割愛しますが帰納法により次のことが分かります。

• $任意の x に対して x\ge 30\Rightarrow ある p ( 30\le p\le 2077 ) に対して x\equiv p$

つまり、この$\equiv$によって、30～2077のどれと仲間であるか、30以上の整数全体を有限のグループに分割できることを意味します。
※もちろん30～2077が全てバラバラのグループを構成するとは限りません。

更に一歩進めると、無限にある正の整数を有限のグループに分割していることから、次のことも分かります。

• $無限個の x と\equivの関係にある c ( 30\le c\le 2077 ) が存在する$
  正確には、$ある c ( 30\le c\le 2077 ) が存在し、任意の m に対して x\ge m かつ x\equiv c となる x が存在する$

といったところで、第二の条件に視線を移します。

$N+1\not\equiv N$ しかも、そのような$N$の最大値を求めさせるというのが問題の要求です。これは実は非常に強い主張を含んでいます。つまり、

• $ある c ( c\not\equiv N_{max} ) に対して、N_{max}より大きい x は全て x\equiv c になるはずだ$

と、ある程度大きくなると正の整数は全て同じグループに所属することになる、という主張です。で、そのグループに属さない最後の整数を見つけてみせろ、と。…本当なのでしょうか? ですが、そのあたりを突っ込んで検証していくことが、この問題の突破口になりそうです。

問題攻略前半

ということで、ここから本格的な攻略になります。

まずは同じグループに属する数を作り出す方法はないか? と探してみます。

そうすると、目に着くのは $m+n\equiv m もしくは m+n\equiv n$ という条件です ( いや、これしかないんですが )。ということは、もし$m\equiv n$であれば「もしくは」の選択を無力化して $m+n\equiv m\equiv n$ と状況を確定させることができます。
更にここから発展させて、次のように帰納的に幾つも同じグループの数も作れるはずです。

• $p\ge 30 かつ x\ge p+2018 かつ x\equiv p \Rightarrow 任意の j ( j\ge 0 ) に対して x+jp\equiv p$ ( 証明は割愛 )

つまり、$p$ずつ足していくことで、飛び飛びに同じグループの値を作れるということです。

では続いて、今度は2次元的に同じグループの数を広げられないでしょうか?
単純には $x\equiv x$ から $x+x\equiv x$ とできると嬉しいのですが…。これはできません。2つの数に2018以上の差がないからです。
しかし、先ほどの結果を活かして$p$ずつ飛び飛びに増やし、それで2018の差を作りさえすれば、今度は$+x$による広がりも作れるのではないでしょうか?

つまりこういうことです。

• $p\ge 30 かつ x\ge p+2018 かつ x\equiv p \Rightarrow u=\lceil \frac{2018}{p} \rceil, 任意のi,j ( i\ge 1, j\ge u ) に対して ix+jp\equiv p$

$j$部分は先ほどと同じ話ですから、$i$部分に帰納法を適用することで示すことができます。実際、 $(ix+jp)-x=(i-1)x+jp\ge up \ge 2018$ ですから、 $ix+jp\equiv p\Rightarrow (ix+jp)+x\equiv p \Leftrightarrow (i+1)x+jp$ となっていて、 $i\rightarrow i+1$ の推移の部分に問題はありません。

…ここで魔法を使います。

• $p\ge 30 かつ x\ge p+2018 かつ x\equiv p かつ q\ge 30 かつ y\ge q+2018 かつ y\equiv q なる p,x,q,y に対して$
• $u=\lceil \frac{2018}{p}\rceil, v=\lceil \frac{2018}{q}\rceil とした時 u,v\ge 1 であり、$
• $任意の i,j ( i\ge 1, j\ge u ) に対して ix+jp\equiv p が成立するため、yx+uvqp\equiv p~ ~\because y\ge 1, uvq\ge u$
• $任意の i,j ( i\ge 1, j\ge v ) に対して iy+jq\equiv q が成立するため、xy+uvpq\equiv q~ ~\because x\ge 1, uvp\ge v$
• $\therefore p\equiv yx+uvqp=xy+uvpq\equiv q すなわち x\equiv p\equiv q\equiv y$

なんと、2018以上の差がある同一グループの$(x,p),(y,q)$の存在を仮定するだけで、それらグループが実は同じであることまで分かってしまいました。イメージとしては、2組のペアからできる2次元の広がりにどうしても衝突が生じるので、別グループではいられない、というところでしょうか。

しかも思い出してみると、30以上の整数は、30～2077のいずれかと同一グループにある上、無限個の整数を含むグループもあるのでした。すなわち、

• $x\ge 30\Rightarrow ある p ( 30\le p\le 2077 ) が存在し、x\equiv p$
• $ある c ( 30\le c \le 2077 ) が存在し、任意の m に対して、x\ge m かつ x\equiv c となる x が存在する$

この2番目の条件の$c$に対して、$y\ge c+2018 かつ x\equiv c となる y が存在する$ はずです。ということは、片側のグループの条件は既に出来上がっているため、

• $p\ge 30 かつ x\ge p+2018 かつ x\equiv p\Rightarrow x\equiv p\equiv c$

また、

• $x\ge 2077+2018\Rightarrow ある p ( 30\le p \le 2077 ) が存在し、x\equiv p$
  $そのような x,p に関しては x\ge p+2018 なので x\equiv p\equiv c$

つまり、4095以上の整数は全て$c$ と同一グループに所属することが分かりました。「ある程度大きくなると正の整数は全て同じグループに所属することになる」という問題に込められた主張は正しかったわけです。

問題攻略後半

前半で分かったことを整理します。

• $ある c ( 30\le c\le 2077 ) が存在し、p\ge 30 かつ x\ge p+2018 かつ x\equiv p\Rightarrow x\equiv p\equiv c$
• $4095以上の任意の整数 x は、前項 c に対して x\equiv c$

そして問題で求められているのは、この$c$と同一グループでない$N$の取り得る最大値でした。そうすると、4095の一歩手前の4094で良いのだろうか? と考えるわけですが。まだ、いろいろ検証しなければなりません。

何故かというと、例えば $x\ge 2078\Rightarrow x\equiv 30 または x\equiv x-30$ なんて話もあったわけで、$4094\equiv 30 または 4094\equiv 4064$ と$\equiv$の関係が下に伝染していくからです。これがどこかで$c$に到達してしまうようでは、答えとして不適切となってしまいます。

ここで良く見ると、「または」の選択肢の内、小さい数字の方は実は選べません。もし $4094\equiv 30$ となると、$4094\ge 30+2018$ ですから、即 $4094\equiv 30\equiv c$ となってしまうからです。
しかもこれは30だけに留まる話ではありません。 $4094\equiv 30 または 4094\equiv 4064,~4094\equiv 31 または 4094\equiv 4063,\cdots 4094\equiv 1038 または 4094\equiv 3056$ と「または」の選択肢は多数あるのです。そして全ての選択肢で小さい数字は除外しなければなりません。

つまり、4094が答えであるならば、$4094\equiv 4064\equiv 4063\equiv\cdots\equiv 3056$ が必要です。

しかもまだまだ伝染は止まりません。

• $4094\equiv 4064\equiv 4034\equiv 4033\equiv\cdots\equiv 3041$
• $4094\equiv 4062\equiv \cdots \equiv 3040$
• …
• $4094\equiv 3056\equiv \cdots \equiv 2037$

どこまで行けば止まるのでしょうか? それは、 $4094\equiv 2078\equiv 2048$ と、2048まで来れば、です。しかしそうすると、 $4094\equiv 2048$ に対して $4094\ge 2048+2018$ となってしまうため、結局は$c$と同一グループになってしまいます。つまりは、4094は答えとして不適切だったということです。

それならば、4094より若干小さいところはどうだろうとなるのですが、結局は同じ理屈で2048まで伝染しますから、$2048+2018=4066$ 以上では$c$と同一グループになることを免れません。…ということで、4065なら今度こそ答えとして適切ではないかと期待します。

では、「4065が$c$と同じグループに所属しない最大の数」となるよう、$\equiv$を構成できるでしょうか? trivialに組んでみます。なお、30未満については元々なんの条件もないので割愛します。

• 2048以上4065以下の整数はお互いに$\equiv$の関係にある。
• $c=30$ とし、前項以外の整数、すなわち 30以上2047以下の整数、および4066以上の整数は全て$c$と$\equiv$の関係にある
• 前2項の所属するグループは異なる

そうすると、2048～4065 からは差が2018以上の組み合わせが取れませんから、$m\equiv n\Rightarrow m+n\equiv m\equiv n$ でこれ以上同一グループの数が導出されることはありません。つまり、自分たちだけで閉じたグループが作れています。また、4066以上の数は「または」の選択をちゃんと30～2047、4066～以上のどちらかから取ることができるため、異なるグループとして存在できます。

ということで、ウラが取れたのでめでたく4065が答えとなりました。

補足

ということで、解説のボリュームがエラいことになってしまいましたが…。お気付きの方もいらっしゃると思いますが、実は答えを出すだけなら、ここまでしなくても構わなかったりします。

というのは、上の解説では「ある程度大きくなると正の整数は全て同じグループに所属することになる」が本当かどうか検証しているわけですが、これは問題の前提だとすれば、後半部分の考察だけで済むわけです。具体的には次の通りです。

• 問題で「最大値」が求められている、つまり「上限」があるのが前提だ
• → その上限を超えると、正の整数は全て同じグループに所属すると判断できる
• 一方、2018以上の差を持った同一グループのペアからは、少なくとも飛び飛びに同一グループの数が無限に作れる
• → もしそれが「全て同じグループ」と異なると「無限に作れる」が「上限」があることと矛盾する
• → ということは、答えは2018の差を持った2数のないグループに所属するはずだ

でも、放っておくと気持ち悪い部分もあったので、この解説では検証するところから始めているのです。

終わりに

ということで、全12問解説してきました。特に後ろの方になればなるほど、考えをまとめるのが難しくなりますね。ともあれ、導出過程を書く必要がないとは言え、そう長くない制限時間で本番に臨む現役の方は大変だなあ、と、改めて思った次第です。ただ、もう現役ではない人も含めて、じっくり考えて解くことでも、なかなか良い頭の体操になるのではないでしょうか。というところで終わりにしたいと思います。