未分類」カテゴリーアーカイブ

JMO本選2019問1

答え\(\cdots (a,b,c)=(2,2,1)\)

【分析】

問1ということで絶対に落とせない問題ですね。このような問題は適当に数字を代入してみてどのような数だと方程式が成り立つのかを考察していきましょう。そのようにすると簡単に答えである\((a,b,c)=(2,2,1)\)は発見できますし、左辺は平方数なので\(b+3\)は\(2a+1\)以上であり、\(a\)が大きいと右辺が全然大きいという感覚もつかめるでしょうか。なので、今回は\(a\)を上から押さえて有限個だけ調べるという整数問題での定石で倒していきましょう。

【略解】

$$a^2+b+3=(b^2-c^2)^2\cdots☆$$

☆の左辺は平方数なので\((a+n)^2\)としますと

$$(a+n)^2=a^2+b+3\\ ∴b=2an+n^2-3$$

\(c\)が変化すると☆は右辺しか変化せず、右辺が最小となるのは\(c=b-1\)のときで

\begin{eqnarray}(b^2-c^2)^2&=&\left((2an+n^2-3)^2-(2an+n^2-4)^2\right)^2\\&=&(4an+n^2-7)^2\end{eqnarray}

これが最小なのですべての\(n\)に対して

$$4an+n^2-7>a+n\cdots ①$$

が成り立つような\(a\)は考える必要がないとわかります。さらに、

$$(①の左辺)-(①の右辺)=n^2+(4a-1)n-7-a$$

なので\(n=1\)で①が成り立てばすべての自然数\(n\)で①が成り立つとわかり、①に\(n=1\)を代入すると

\begin{eqnarray} 4a-6&>&a+1\\ 3a&>&7
\end{eqnarray}

なので\(a\)が3以上は考える必要がないとわかります。よって、あとは\(a=1,2\)のときを考えればよく、

\((i)a=1\)のとき

①に\(a=1\)を代入すると

$$n^2+3n-8>0$$

となり、この不等式を満たさないのは\(n=1\)のときのみでこのとき\(b=0\)となるので不適。

\((ii)a=2\)のとき

①に\(a=2\)を代入すると

$$n^2+7n-9>0$$

となり、この不等式を満たさないのは\(n=1\)のときのみ。このとき、\(b=2,c=1\)とすれば☆を満たす。

よって、☆を満たすのは\((a,b,c)=(2,2,1)\)のときのみ。

JJMO本選2019問4

答え\(\cdots 2n-2\)
【略解】
個人的には時間もかけずあっさり解けた問題で、問1よりも先に解けたくらいなのですが、出来は(恐らく)そこまでよくなかったらしいです。
ただし、答えの予想くらいは駒を実際に動かしていけばすぐにわかりますから、そのくらいは解答して部分点を狙うべきでしょう。
ちなみに、僕がこの問題を解けたのは、先日、SNSで

「将棋の銀の駒を端っこのマスに置く。銀の動きに沿って全てのマスを1回ずつ通ることは可能か。」

という問題を見て、解いたことがあるからかも知れません。
銀という駒は横に動けないという大きな特徴があります。そのため、上から順に1行目,2行目,…,9行目とすれば、奇数行目から偶数行目、偶数行目から奇数行目に動くしかありません。
しかし、奇数行目のマスは45マス、偶数行目のマスは36マスなので、どうやっても奇数行目のマスが余ってしまうのです。
この問題についてもほぼ同じアプローチで解決します。
縦、横それぞれに何回ずつの操作が最低でも必要かを考えましょう。

【略解】
(最小性)
斜め、縦のみの移動では奇数行目から偶数行目に、偶数行目から奇数行目にしか移動できないので、ます目全体で奇数行目のマスは偶数行目のマスより\(n\)個多いから、横の移動回数を下から押さえると、(奇数行目からスタートして)少なくとも\(n-1\)回は横に移動する必要がある。同様に、縦の移動も\(n-1\)回はする必要がある。

(実例)
また、左上からスタートし、1行目と2行目を斜め移動で交互に進み、右上についたら1つ下に移動して斜め移動で1行目と2行目を交互に進み、2行目の左端に来たら1つ下に移動する。
同じ要領で3行目と4行目、5行目と6行目、\(\cdots\)、\(n-2\)行目と\(n-1\)行目を通過し、\(n-1\)行目の左端に来たら、1個下に移動して、\(n\)行目はまっすぐ左から右へ横に移動しておけば、このとき、縦と横の移動は\(n-1\)回ずつ。

以上より求める最小値は\(2n-2\)

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\)が求める最小値。