2017年ヨーロッパ女子数学オリンピックの問題に学ぶ ～自然数を巧妙に塗り分けろ...

皆さんこんにちは。東進衛星予備校　金沢南校の北川と申します。年末年始の寒い時期ですが、体調を崩したり、雪に悩まされたりはしていないでしょうか。

今回は、ヨーロッパ女子数学オリンピックの問題から1問を選んで頭の体操をやってみましょう。こちらも、なるだけ行間を埋めながら解説することを心がけます。

今回の記事の難易度は少し高めです。難関大志望で、二次試験に数学を使う人であれば文理も学年も問わず読める内容ではないかと思います。よろしくお願いいたします。

目次

1. 今回の問題～一般的事実の整理～

2. 何色だと塗れないのか？

3. 何色あれば足りるのか？

4. まとめ

1.今回の問題～一般的事実の整理～

それでは、今回扱う問題について説明します。

（出典：https://www.imojp.org/overseas/egmo_statistics.html　2017年の問題pdfより）

やや複雑な問題文になっていますね。関数\(f:\mathbb{Z}_{>0}→\mathbb{Z}_{>0}\)という表記が見慣れない人もいるかもしれませんが、要するに定義域も値域も正の整数であるような関数ということです。整数を、何か別の整数に（一意に）変換するルールと言い換えてもいいでしょう。

本題に戻りましょう。この問題では自然数を、何色か使って塗り分けることを考えるようです。

そして、(i)で言っているのは「同じ色が塗られた数に対する制約」で、(ii)で言っているのは「(i)の制約を満たさない違う色同士の数がある」ということです。関数fは、制約をみたしつつも、ある程度はその制約をすり抜けるように返り値を設定しないといけないわけですね。

では解説を始めます。

\(k\)と\(f\)、2つのものに気を配らなくてはいけないのは大変です。そこでまず、\(f\)だけに注目し、「色の条件に関係なく関数\(f\)が満たす性質」を考察してみることにしましょう。

これ見よがしに注が振られている「正の整数\(m\)と\(n\)は相異なる必要はない」という一言がポイントです。こう書かれていると、「\(m=n\)の場合はどうなるのかな？」と自然に考えるものでしょう。

さて、任意の整数\(m\)は「自分自身と同じ色で塗られている」と考えられますから、必然的に(i)の条件が使えます。すると、以下のような式変形が可能です。

\(f(2m)=f(m+m)=f(m)+f(m)=2f(m)\)

また、これを繰り返し使うことで、\(f(4m)=4f(m)、f(8m)=8f(m)\)、……などの事実も分かります。

以上より、「\(f(2m)\)、\(f(4m)\)、\(f(8m)\)、……の値は、\(f(m)\)の値によって定まる」ということが分かります。言い換えれば、「\(f(m)\)の値を定めてしまえば、\(f(2m)\)、\(f(4m)\)、\(f(8m)\)、……の値も決まってしまう」というわけです。

\(m\)を2つの正の整数の和として表す方法は、\(m\)が大きくなるにつれて増えていきます。その中で、適当に関数の返り値を設定してしまうと簡単に矛盾が生じてしまう可能性があります（例えば、\(100=20+80=30+70\)ですが、もし、\(20\)と\(80\)、\(30\)と\(70\)が同じ色で塗られている場合、\(f(20)+f(80)=f(30)+f(70)\)が成り立つように関数の返り値を定めないと破綻してしまうわけです）。

ということで、実は(i)の条件というのは案外シビアに関数の返り値を決めてしまいます。

(ii)の条件についても考察してみましょう。

\(≠\)が入ったままだと考えにくいので、一旦否定を取ってみることにします。

そして、これは少し考えると以下の命題と同値であることが分かります。

証明は以下の通り。

そして、下の命題の否定が次の通りです。

否定の否定は普通、元の命題に戻りますから、これは元の(ii)の条件と同値な命題になっているはずです。こうした方が何だかすっきりして考えやすそうですね。

まとめると、以下の2つの事実が一般に成り立つことが分かりました。

・\(f(m)\)の値が定まっているとき、\(f(2m)\)、\(f(4m)\)、\(f(8m)\)、……の値も決まってしまう

・(ii)の条件は「正の整数mであって、\(f(m)≠mf(1)\)をみたすものが存在する」と読み替えて良い（以下でもそうします）。

以上をもとに、考察を深めていきましょう。

2.何色だと塗れないのか？

まず、当たり前のことから始めてみましょう。

1色で塗ることは可能かを考えてみることにします。深く考えるまでもなく、これは無理であることが明らかです。

一応ちゃんと説明しておくと、全ての自然数が同じ色で塗られているならば、（条件(i)より）任意の自然数\(m\),\(n\)に対して、\(f(m+n)=f(m)+f(n)\)が成立するということになります。

これは先ほど考察した条件(ii)の否定と全く同じですね。ある命題とその否定は、同時に1つしか成立しませんから、条件(ii)の否定がみたされることは、条件(ii)がみたされないことを意味します。

つまり、条件(i)がみたされる限り、条件(ii)はみたされないため、1色で2つの条件が両立するように塗ることはできません。

さて、ここからが本題です。

色を1色増やして、2色にしてみるとどうでしょうか？ ここで、「条件(i)がみたされるときに、条件(ii)が満たされていることがあり得るのか」を具体的な数で考えてみましょう。

例えば、条件(i)がみたされているという仮定の下、\(f(3)≠3f(1)\)であるとしてみます。何が起こるかを順に観察していきましょう。

まず、この仮定とは関係なく、無条件で\(f(2)=2f(1)\)であることが分かっています（第1項での考察から）。

\(f(2)=2f(1)\)から、もし1と2が同色で塗り分けられていると仮定すると、\(f(3)≠3f(1)\)という仮定に矛盾します。よって、1と2は違う色で塗り分けられています。

便宜上、以下では1が赤色で、2が青色で塗られているとします。

\(1\),\(2\),\(3\),\(4\),……

次に考えたいのは、3が何色で塗られているかです。

もし3が赤色で塗られているとします。すると、1と3は同色で塗られていることになりますから、\(f(4)=f(1)+f(3)\)が成り立ちます。一方で、\(f(4)=2f(2)=4f(1)\)ですから、\(4f(1)=f(1)+f(3)\)となり、これはやはり仮定に矛盾します。

よって、3は青色で塗られていることになります。

\(1\),\(2\),\(3\),\(4\),……

また、2と3が青色で塗られていますから、\(f(5)=2f(1)+f(3)\)です。

さて、次に4が何色で塗られているか考えてみましょう。

4が赤色で塗られていると仮定すると、\(f(5)=f(1)+f(4)=f(1)+4f(1)=5f(1)\)となりますが、これは今しがた確認した\(f(5)=2f(1)+f(3)\)と併せると、過程に矛盾します。

一方で、4が青色で塗られていると仮定すると、2と4はともに青色で塗られていることになりますから、\(f(6)=f(2)+f(4)=2f(1)+4f(1)=6f(1)\)ということになります。一方で、\(f(6)=2f(3)\)ですから、これもやはり仮定に矛盾します。

\(1\),\(2\),\(3\),\(4\),……

以上より、4を赤で塗っても青で塗っても\(f(3)≠3f(1)\)に矛盾してしまうことが分かりました。これは(i)と\(f(3)≠3f(1)\)が両立するという仮定の下で進めた議論でした。よって、ここで矛盾が起きたことにより、この2つの仮定が同時にみたされることはない、と結論付けられます。

さて、これは3という具体的な数値に限った話でしたが、同じことをより抽象的に行えるのではないでしょうか？

端的に、(i)と(ii)が両立していると仮定します。

つまり、(i)の条件下で、「正の整数\(m\)であって、\(f(m)≠mf(1)\)をみたすものが存在する」とします。このような条件を満たす\(m\)がいくつありうるかは分かりませんが、\(m\)が正の整数である以上、条件を満たすようなもののうち最小であるものが必ず存在します。

つまり、「正の整数\(m\)であって、\(1≤i≤m-1\)を満たす任意の正の整数\(i\)について\(f(i)=if(1)\)をみたし、かつ、\(f(m)≠mf(1)\)をみたすものが存在する」として議論を進めます。

\(m\)が偶数だとすると、\(\frac{m}{2}\)は\(m\)より小さい正の整数ですから、\(f(m)=(\frac{m}{2}+\frac{m}{2})=2f(\frac{m}{2})=mf(1)\)が明らかであり矛盾します。また、明らかに\(m≠1\)でありますから、\(m\)は\(3\)以上の奇数だとしてよいです。

先においた仮定から、「\(1\)と\(m-1\)」、「\(2\)と\(m-2\)」、「\(3\)と\(m-3\)」、……、「\(\frac{m-1}{2}\)と\(\frac{m+1}{2}\)」は、すべてお互いにそれぞれ違う色同士で塗られていると分かります（そうでなければ、\(f(m)=f(i)+f(m-i)=mf(1)\)が成立してしまいます）。これを事実①と呼ぶことにします。

一方で、\(f(m+1)=f(\frac{m+1}{2}+\frac{m+1}{2})=2f(\frac{m+1}{2})=(m+1)f(1)\)であり、これと同じ要領で\(f(m+3)=(m+3)f(1)、……、f(2m-2)=(2m-2)f(1)\)が分かります。

この事実から、「\(1\)と\(m\)」、「\(3\)と\(m\)」、「\(5\)と\(m\)」、……、「\(m-2\)と\(m\)」がそれぞれ違う色同士で塗られていることも明らかです（そうでなければ、\((m+i)f(1)=f(m+i)=f(m)+f(i)=f(m)+if(1)\)が成立してしまいます）。これを事実②と呼ぶことにします。

さて、事実②から、「\(1\)と\(m\)」は違う色です。便宜上\(1\)が赤色で、\(m\)が青色で塗られているとしましょう。すると、事実②より、\(3\)、\(5\)、\(7\)、……、\(m-2\)はすべて赤色で塗られていることになります。

加えて、事実①より、「\(1\)と\(m-1\)」は違う色でしたから、\(m-1\)は青色で塗られていることが確定します。このまま進めていけば、\(2\)、\(4\)、\(6\)、……、\(m-1\)はすべて青色で塗られていることになります。

つまり、\(m\)未満の奇数はすべて赤色に、偶数はすべて青色に塗られており、\(m\)は青色で塗られています。

\(1\),\(2\),\(3\),\(4\),\(5\),\(6\),…,\(m-2\),\(m-1\),\(m\),…

さあ、いよいよ大詰めです。\(m+1\)は何色で塗られているかを考えてみましょう。

▶\(m+1\)が赤色で塗られていると仮定する

この時、\(1\)と\(m+1\)が同色で、\(f(m+1)=(m+1)f(1)\)であることが分かっているので、\(f(m+2)=f(1)+f(m+1)=(m+2)f(1)\)です。

一方で、\(m\)と\(2\)も同色であるので、\(f(m+2)=f(m)+f(2)=f(m)+2f(1)\)です。

この2つの式から、\((m+2)f(1) =f(m)+2f(1)\)を得られ、これは仮定に矛盾します。

▶\(m+1\)が青色で塗られていると仮定する

この時、\(m-1\)と\(m+1\)が同色であり、先ほどの議論と仮定からの\(f(m+1)\)と\(f(m-1)\)の値が分かっているので、\(f(2m)=f(m+1)+f(m-1)=(m+1)f(1)+(m-1)f(1)=2mf(1)\)を得る。

一方で、\(f(2m)=f(m+m)=2f(m)\)も分かります。

この2つの式から、\(2mf(1)=2f(m)\)を得られ、これは仮定に矛盾します。

よってこのとき、\(m+1\)を赤色で塗っても青色で塗っても矛盾します。

これは条件(i)と条件(ii)が両立すると仮定した上で進めた議論によって得られた矛盾です。つまり、条件(i)と条件(ii)は両立しえないと分かりました。

よって、2つの条件を両立させるような関数\(f\)と、2色での彩色は同時に行うことができない。端的に、「2色で塗ることはできない」と分かりました。

3.何色あれば足りるのか？

ここまでできてしまえば、実はこの後はウィニングランです。

「3色で塗るとき、条件を両立させるような関数\(f\)を見つけられるか？」を考えてみます。

先ほどの2色での議論は、「赤色でない」ことと「青色である」ことが同値であることに依拠している部分があります。3色使えるのであれば、この部分の論理を打ち崩せることになります。こうなれば、\(f\)が存在する可能性も充分にありそうです。

では、3色で実際に塗れるかを考えましょう。塗れる、という前提のもとに立って色々とごちゃごちゃしてみると、すぐに具体例が見つかります。早速見てみましょう。

便宜上、塗り分けに使う3色を赤色、青色、緑色とし、\(\mathbb{Z}_{>0}\)の部分集合\(A,B,C\)を以下の通り定めます。

\(A=\{3k+1 ┤| k≥0 ∩k∈\mathbb{Z}\}、B=\{3k+2 ┤| k≥0 ∩k∈\mathbb{Z}\}、C=\{3k+3 ┤| k≥0 ∩k∈\mathbb{Z}\}\)

\(A\)と\(B\)と\(C\)の和集合は\(\mathbb{Z}_{>0}\)になり、\(A\)、\(B\)、\(C\)のどの2つも共通部分を持ちませんから、任意の正の整数は\(A\)、\(B\)、\(C\)のいずれか1つの集合にのみ属します。

\(A\)に属する正の整数を赤色で、\(B\)に属する正の整数を青色で、\(C\)に属する正の整数を緑色で塗ることにします。

\(1\),\(2\),\(3\),\(4\),\(5\),\(6\),\(7\),\(8\),\(9\),\(10\),\(11\),\(12\),……

また、正の整数\(n\)に対して、関数\(f\)を以下の通り定義します。

\begin{equation}
f(n)= \left\{
\begin{aligned}
n ( n \in A \cup B)\\
2024n( n \in C)
\end{aligned}
\right\}
\end{equation}

このとき、2つの条件(i)、(ii)が両立していることを確認します。

▶条件(i)について

・\(A\)に属する2つの（相異なるとは限らない）整数は、非負整数\(k,l\)を用いてそれぞれ,\(3k+1\)、\(3l+1\)と表すことができます。

この2数の和は,\(3(k+l)+2\)となり、必ず\(B\)に属する整数になります。

このとき、以下の2つの式が成り立ちます。

\(f(3k+1)+f(3l+1)=3k+1+3l+1=3(k+l)+2\)

\(f((3k+1)+(3l+1))=f(3(k+l)+2)=3(k+l)+2\)

よって、確かに\(A\)に属する正の整数＝赤色で塗られた整数に対しては条件(i)をみたしていると言えます。

・同様に\(B\)に属する2つの整数の和は、\(A\)に属する整数になりますから、上記とほぼ同じようにして青色で塗られた整数も条件(i)をみたしていることが確認できます。

・\(C\)に属する2つの（相異なるとは限らない）整数は、非負整数\(k,l\)を用いてそれぞれ,\(3k\)、\(3l\)と表すことができます。

この2数の和は\(3(k+l)\)となり、必ず再び\(C\)に属する整数になります。

この時、以下の2つの式が成り立ちます。

\(f(3k)+f(3l)=2024×3k+2024×3l=2024×3(k+l)\)

\(f(3k+3l)=f(3(k+l))=2024×3(k+l)\)

よって、\(C\)に属する正の整数＝緑色で塗られた整数についても確かに条件(i)をみたしていると言えます。

以上より、このときすべての正の整数が条件(i)をみたしていることがわかります。

▶条件(ii)について

明らかに、\(f(1)+f(2)=3\)、\(f(1+2)=f(3)=2024×3\)ですから、\(f(1)+f(2)≠f(1+2)\)です。1つでも存在すればいいので、これで大丈夫です。

以上より、3色で塗り分ける方法と、条件(i)、(ii)をみたす関数fが存在することが分かりました。

よって、この問題の答えは\(k=3\)です。

4.まとめ

お疲れ様でした。

この問題は、振り返ってみるとそれほど難しい問題という訳でもありません。恐らく競技数学に慣れた人であれば、それほど労せずに解くことができる問題でしょう。

ですが、例えば競技数学を始めたての人などにとっては、挑みがいのある問題だったのではないでしょうか。しかも、その難しさは知識不足に起因しなかったのではないでしょうか（特に、この問題で使用した知識はすべて（原理的には）数I・Aの範囲内で収まっていますから、（原理的には）高1生でも解けることになります）。

この問題の難しさは、見慣れない条件設定（色を塗る、関数を見つける）や、問題文自体が複雑であること、そして使う考え方も複雑であることに由来すると言えます。特に考え方の複雑さについては、2色のときは抽象的な議論で「条件を両立する関数が存在しない」ことを示す必要があるのに対し、3色のときは「条件を両立する関数を具体的に構成する」ことが近道になっているのが罠です。具体と抽象の行き来にはそれなりのトレーニングが必要ですから、一筋縄ではいかないポイントの1つでしょう。

さらには、解答を作るプロセスの中に背理法が何度も使用されるところも厄介です。今、自分がどういう仮定の下に何をしようとしているのか分からなくなり、迷子になることも多そうです。アリアドネの糸ではないですが、迷ったら自分がたどったプロセスを逆にたどって、分かるところまで戻ってきたいものですね。

とはいえ、考え方を除けば使う知識は難しくありませんから、論理の使い方を確認するうえでは良い問題だと言えます。数学を得意にしたいという生徒であれば、学年問わず挑戦する価値のある問題です。

今年も多くの方に記事を読んでいただきました。この場を借りて感謝を申し上げます。

来年も原則1カ月に1度のペースで、数学の問題についての解説記事や、その他教育情報について掲載してまいります。どうぞよろしくお願いいたします。