JJMO本選2019問2

答え\(\cdots n=24\)
【分析】
今年の本選で最も簡単な1問。絶対に落とせません。円形に並べるといった条件を見落としてしまったり、1とnが違う色で塗られていることを忘れたりといったケアレスミスに注意しましょう。
まず、どの色の総和も同じなので1~nの合計n(n+1)/2は10の倍数です。この時点で

\begin{eqnarray}
n(n+1)が4の倍数⇔n≡0,-1(mod\ 4)\\
n(n+1)が5の倍数⇔n≡0,-1(mod\ 5)\\
(∵n,n+1は互いに素)\end{eqnarray}
より、\(n≡0,4,15,19(mod\ 20)\)に絞れます。
小さい順に調べると、\(n=4,15,19,20\)のときは無理だとすぐわかるので、\(n=24\)で考えてみると、\(n=24\)で不可能であることを示すのは難しそうなので、作れるかなと期待しつつ実例を探してみると答えが見つかります。
このような組み合わせ論の最小性の証明では、
①条件を満たすこと(実例探し)
②最小性の証明(それより小さいときは不可能であることの証明)
の2つを意識しましょう。どちらが欠けても許されません。
逆に、①と②のどちらかだけでも出来ていれば、部分点が狙えますから、わからなくてもこの手の問題は①と②のどちらかで部分点を取りにいきましょう。

【略解】
①\(n=24\)のとき$$
24,4,2\\
23,6,1\\
22,8\\
21,9\\
20,10\\
19,11\\
18,7,5\\
17,13\\
16,14\\
15,12,3$$
の同じ行に書かれた数に同じ色、違う行に書かれた数に違う色を塗れば、どの色の総和も30かつ隣り合うボールが違う色で塗られており、条件を満たす例となっている。

②最小性の証明
先ほど示したよう、\(n≡0,4,15,19(mod\ 20)\)のときに限られ、

・\(n=4\)のとき
総和が0の色が存在し、条件を満たさない。

・\(n=15\)のとき
1~15の総和は120なので、どの色についても総和は12となるはずだが、
15に塗られた色は12を超えるので条件を満たさない。
・\(n=19\)のとき
1~19の総和は190なので、どの色についても総和は19となるはずだが、
19と同じ色で塗るのは他になく、残り18個を9色で塗り分けたいが、どのボールも18以下なので残り9色はどの色も2つ以上で塗られる必要があるが、ボールが18個しか残ってないので、残り9色は2個ずつに使われる。
すると、10と同じ色で塗られたものが9となり、隣り合うボールを同じ色で塗ることになり、不合理。

・\(n=20\)のとき
1~20の総和は210なので、どの色についても総和は21となるはずだが、20に塗られた色について、1を同じ色で塗るしかなく、隣り合うボールを同じ色で塗ることになり、不合理

①②より\(n=24\)が求める最小値。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です