投稿者「totulens」のアーカイブ

JMO予選1990問12

$$a_1=1,a_{n+1}=a_n+\frac{1}{a_n} \ \ (n\ge1)$$

で定められた数列\(\{a_n\}\)に対し,\([a_{100}]\)の値を求めよ.

【思考・方針】

$$a_2=2,a_3=\frac{5}{2},a_4=\frac{29}{10}\cdots$$

と求めて手が止まった人も多いでしょう.

ざっくりとしたイメージも入りますが

\(\cdot\ a_n\)は単調増加

\(\cdot\ a_n\)が大きいほど,\(a_{n+1}\fallingdotseq a_n\)

\(\cdot\ \)もっと言えば,\(a_{n+1}\fallingdotseq a_n+\frac{1}{a_n}\)であるから,

\(a_n=5\)なら,

$$a_{n+1}=5+\frac{1}{5}$$

$$a_{n+2}\fallingdotseq5+\frac{1}{5}+\frac{1}{5}$$

$$a_{n+3}\fallingdotseq5+\frac{1}{5}+\frac{1}{5}+\frac{1}{5}$$

のようになっていく.すると

$$a_n\fallingdotseq1+\frac{1}{1}+\frac{1}{2}+\frac{1}{2}+\frac{1}{3}+\frac{1}{3}+\frac{1}{3}+\frac{1}{4}+\cdots (全部で項の数はn)$$

のように考えられる.

\(∴\ (1+2+\cdots+13=91より)\)\(a_{100}\fallingdotseq14+\frac{8}{14}\)から答えは\(14\)と予想できます!

このように,答えだけならある程度予想は実は出来るのですが,ちょっと怪しい(誤差がでて\(13\)や\(15\)でもおかしくなさそう)ですから,真面目に考えてみましょう.

\(a_1\)からスタートして「増えてく分」を足し合わせると,与えられた漸化式から\(a_n=a_1+\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_{n-1}}\)ですが,この\(a_1+\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_{n-1}}\)の部分を\(1+\frac{1}{1}+\frac{1}{2}+\frac{1}{2}+\frac{1}{3}+\frac{1}{3}+\cdots\)と近似したのが先程の考え方ですが,もうすこし真面目に評価できないか,つまり\(14\)以上\(15\)未満を示せないかと考えてもこのままではなかなか難しいわけです.そこで,近似の精度をあげるため,二乗してみます.

(与えられた式は確かに二乗したくなる式ではありますね.)

$$a_{n+1}^2=a_n^2+\frac{1}{a_n ^2}+2$$

\(∴\ \)この式の\(n\)に\(1\sim99\)を代入したものを足し合わせることで,先程と似た式,

\begin{eqnarray}a_{100}^2&=&a_1^2+\frac{1}{a_1 ^2}+\cdots+\frac{1}{a_{99}^2}+2\times99\\∴\ a_{100}^2&=&\frac{1}{a_1 ^2}+\cdots+\frac{1}{a_{99} ^2}+199\end{eqnarray}

が得られます.こうすれば,我々の予想\([a_{100}]=14\)を示すには

$$\frac{1}{a_1 ^2}+\cdots+\frac{1}{a_{99} ^2}
が26未満 $$

を示せば良いですが,これは先程と比較しても小さい数の和ですからなんとかなりそうです!

\(n\ge 2\)のとき,\(\frac{1}{a_n ^2}\le\frac{1}{a_2 ^2}=\frac{1}{4}\)を用いれば,

$$\frac{1}{a_1 ^2}+\cdots+\frac{1}{a_{99} ^2}\le1+98\times\frac{1}{4}=25.5<26$$

となり,なんとか,\(196\le a_{100}^2<225\)が示せましたから,答えは\(14\)とわかりました!

難しい道具は一切使っていませんが,かなりの難問と言っていいでしょう.それではもう1問,同じ漸化式にまつわる似たような問題を考えてみましょう.

今回は,日本の数学オリンピックの類題が海外の数学オリンピックで出題された例です.

Q.\(\ \ \)漸化式

$$a_{n+1}=a_n+\frac{1}{a_n} \ \ (n\ge0)$$

を満たす数列\(\{a_n\}\)に対し,初期値\(a_0\)がどんな正の実数であっても,\(a_{1996}>63\)を示せ.

(1996年南半球数学オリンピック問2)

下からの評価のみで良いこともあり,先ほどよりも2乗をしたくなるのではないのでしょうか?というわけで,先ほどの問題をみたあとなら簡単ですね.漸化式を2乗すると

$$a_{n+1}^2=a_n^2+\frac{1}{a_n ^2}+2$$

\(∴\ \)この式の\(n\)に\(0\sim1995\)を代入したものを足し合わせることで,

\begin{eqnarray}a_{1996}^2&=&a_0^2+\frac{1}{a_0 ^2}+\cdots+\frac{1}{a_{1995}^2}+2\times1996\\&\ge&3992>3969=63^2\end{eqnarray}

より,\(a_0>0\)と漸化式を繰り返し用いて\(a_{1996}>0\)を加味すれば,\(a_{1996}>63\)が示せますね!

先ほどよりも不等式評価につまらずにすむあたり,解きやすくなっていますね.ただし,日本の方は答えだけでよかった分,どちらの方が難しいかは微妙なところな気もしますが.

JMO予選1990問10

\(x,y,z\)を正の数とする。\(x+y+z=1\)のとき、\(\frac{1}{x}+\frac{4}{y}+\frac{9}{z}\)の最小値を求めよ。

【思考・方針】

多変数関数の最大・最小は順像法や逆像法など、様々な方針がありますが、数学オリンピックではむしろ特殊な不等式の利用がメインでしょう。

JMOの本選やIMOなどでは様々な特殊な不等式を使うはめになりますが、いきなりいろんな道具を使いこなすのは難しいうえ、覚えるのも大変なので、まずは特に有名な

\(\cdot\ \)相加相乗平均の不等式

\(\cdot\ \)コーシーシュワルツの不等式

を何変数であっても使いこなせるようにしておくのがよいでしょう。

知ってても使えるようになるには、多少の慣れが必要ですが、逆に言えば、ある程度、経験すれば出来るようになります。今回は、コーシーシュワルツの不等式の利用です。(まだ思い付いてない人はそれをヒントに考えてみましょう。)

3変数コーシーシュワルツの不等式

\begin{eqnarray}(a^2+b^2+c^2)(p^2+q^2+r^2)\ge(ap+bq+cr)^2\end{eqnarray}

において、\(a=\sqrt{x},b=\sqrt{y},c=\sqrt{z},p=\frac{1}{\sqrt{x}},q=\frac{2}{\sqrt{y}},r=\frac{3}{\sqrt{z}}\)を考えましょう。

すると、

\begin{eqnarray}(x+y+z)\left(\frac{1}{x}+\frac{4}{y}+\frac{9}{z}\right)\ge(1+2+3)^2\end{eqnarray}

より、\(\frac{1}{x}+\frac{4}{y}+\frac{9}{z}\ge36\)となりますから、等号が成立する

\begin{eqnarray}\frac{a}{p}=\frac{b}{q}=\frac{c}{r}\Leftrightarrow x=\frac{y}{2}=\frac{z}{3}\Leftrightarrow x=\frac{1}{6},y=\frac{1}{3},z=\frac{1}{2}\end{eqnarray}

のとき、\(\frac{1}{x}+\frac{4}{y}+\frac{9}{z}\)は最小値36をとる。

\((x,y,z)\)と\((\frac{1}{x},\frac{4}{y},\frac{9}{z})\)の「内積が定数」のような形の時にコーシーシュワルツの不等式が活躍します。また、他のよくあるパターンとして、「ルート型」も見ておきましょう。東大入試に挑戦です。

Q.\(\ \ \)任意の正の実数\(x,y\)に対し、

\begin{eqnarray}\sqrt{x}+\sqrt{y}\le k \sqrt{2x+y}\cdots①\end{eqnarray}

となるような正の実数$k$の範囲を求めよ。

(東大理系1995問1)

【略解】

もちろん入試問題ですし、微分などをごりごり使って倒すのもよい作戦だとは思いますが、ここではコーシーシュワルツの不等式を使った解法を紹介しましょう。①の両辺は正ですから、

\begin{eqnarray}①\Leftrightarrow k^2(2x+y)\ge(\sqrt{x}+\sqrt{y})^2\cdots②\end{eqnarray}

です。少し、近付きましたね。

さて、コーシーシュワルツの不等式を使うことを強く意識すると、

\begin{eqnarray}\left(\frac{1}{2}+1\right)(2x+y)\ge(\sqrt{x}+\sqrt{y})^2\end{eqnarray}

という不等式が作れます。

\begin{eqnarray}∴\frac{3}{2}(2x+y)\ge(\sqrt{x}+\sqrt{y})^2\cdots③\end{eqnarray}

となり、\(\frac{1}{2}:1=2x:y\)(例えば\(x=1,y=4\)など)のときに③の等号が成立してしまうことも加味すれば、②をみたす\(k\)の条件は\(k^2\ge\frac{3}{2}\)

となり、求める条件は\(k\ge\frac{\sqrt{6}}{2}\)となりますね!

このように、コーシーシュワルツの不等式などの特殊な不等式を利用する問題は、様々な経験をし、使えそうな時に「使えそうだな」と思う嗅覚が必要なうえ、用いる有名不等式を強く意識して不等式を作る必要があります。慣れないと難しいですが、その分、解けたときの達成感が味わえる分野の1つです。

JMO予選1990問9

正の整数\(n\)に対し,

$$a_n=n^2+50, \ d_n={\rm{gcd}}(a_n,a_{n+1})$$

とする.\(n\)が正の整数全体を動くとき,\(d_n\)の最大値を求めよ.ここで,\({\rm{gcd}}(a,b)\)で\(a\)と\(b\)の最大公約数を表す.

【思考・方針】

下手なことをせず,\(a_n,a_{n+1}\)は\(n\)の式で表せます.あとは最大公約数を求めるときの基本方針の1つである互除法を使えば解決です.

\begin{eqnarray} {\rm{gcd}}(a_n,a_{n+1}) &=&{\rm{gcd}}(n^2+50,n^2+2n+51)\cdots①\\ &=&{\rm{gcd}}(n^2+50,2n+1)\cdots②\\ &=&{\rm{gcd}}(4n^2+200,2n+1)\cdots③\\ &=&{\rm{gcd}}(201,2n+1)\cdots④ \end{eqnarray}

と計算できますね.

①は一般項から,②,③は互除法です.

③に式変形をするところで戸惑うかもしれませんが,これは,②で互除法を使おうとすると分数式が出てしまうので,\(2n+1\)が奇数であるから,\(n^2+50\)を\(4\)倍しても最大公約数は代わらないことを利用した式変形です.

ここまでくれば,\(d_n={\rm{gcd}}(201,2n+1)\)の最大値は\(201\ (2n+1\)が\(201\)の倍数のとき)とわかります.実際に

\begin{eqnarray}a_{100}&=&10050=201\times50\\ a_{101}&=&10251=201\times51 \end{eqnarray}

と計算して確かめておくとよいでしょう.文字の絡んだ互除法になれたい人は以下の類題でも考えてみてください.記念すべき第1回IMOの第1問です.

Q.\(\ \ \)任意の正の整数に対し,\(\frac{21n+4}{14n+3}\)は既約分数であることを示せ.

(IMO1959問1)

【略解】

\(21n+4\)と\(14n+3\)の最大公約数が\(1\)であることを確かめればいいですね.互除法を使うと

\begin{eqnarray}{\rm{gcd}}(21n+4,14n+3)={\rm{gcd}}(7n+1,14n+3)={\rm{gcd}}(7n+1,1)=1 \end{eqnarray}

となりますから,これで無事,示せました!

ちなみに,互除法を使うとこんな簡単に示せてしまう問題で互除法を使っていいのか!という人は,

\begin{eqnarray} -2(21n+4)+3(14n+3)=1\cdots①\end{eqnarray}

であり,もし,\({\rm{gcd}}(21n+4,14n+3)=d\ge 2\)とすると,\(21n+4,14n+3\)は両方\(d\)の倍数なので①の左辺は\(d\)の倍数となるが,①の右辺は\(d\)の倍数でないというふうに説明した方がいいかもしれません.

記念すべき第1回IMOの最初の1問は今と比べ物にならないくらい簡単なのですね.

JMO予選1990問8

正の整数\(n\)に対して定義された関数\(f\)は

$$ f(n) = \begin{cases} n-3 & (n\ge 1000のとき) \\ f(f(n+7)) & (n<1000のとき) \end{cases} $$

満たす.\(f(90)\)を求めよ.

【思考・方針】

関数方程式の問題の基本は,「様々な値を代入」です.(これをしない関数方程式の問題なんて存在しないといっても過言ではないでしょう.)

もちろん,\(n\)が\(1000\)以上のときの\(f(n)\)の値は簡単で,

\( f(1006)=1003\)

\(f(1005)=1002\)

\(f(1004)=1001\)

\(f(1003)=1000\)

\(f(1002)=999\)

\(f(1001)=998\)

\(f(1000)=997\)

はすぐわかるでしょう.また,\(n\)が\(1000\)未満のときの\(f(n)\)の値は上から決まり,

\(f(999)=f(f(1006))=f(1003)=1000\)

\(f(998)=f(f(1005))=f(1002)=999\)

\(f(997)=f(f(1004))=f(1001)=998\)

\(f(996)=f(f(1003))=f(1000)=997\)

\(f(995)=f(f(1002))=f(999)=1000\)

\(f(994)=f(f(1001))=f(998)=999\)

\(f(993)=f(f(1000))=f(997)=998\)

\(f(992)=f(f(999))=f(1000)=997\)

\(f(991)=f(f(998))=f(999)=1000\)

\(f(990)=f(f(997))=f(998)=999\)

\(f(989)=f(f(996))=f(997)=998\)

\(f(988)=f(f(995))=f(1000)=997\)

\(f(987)=f(f(994))=f(999)=1000\)

ここまでくればもうわかるでしょう.(実験はこのくらい徹底的にやりましょう.)「1000,999,998,997」の繰り返しになっていますね.

というわけで\(f(90)=999\)が答えです.

なぜこの規則が成り立つかは帰納法により,(真面目に書くのは面倒ですが,簡単に)確認できますから,各自確認してみてください.「読者への演習問題とする.」ってやつです.

ところで,僕は今紹介した方針で解きましたが,もう一人のこのHPのライターさんは

\begin{eqnarray} f(90)&=&f(f(97))=f(f(f(101)))=\cdots\\ &=&f(f(f(\cdots f(1000)\cdots))) (fが131個) \end{eqnarray}

として,\(f\)が1つつく度に\(f(f(f(\cdots f(1000)\cdots)))\)は

$$1000\rightarrow997\rightarrow998\rightarrow999\rightarrow1000\rightarrow997\cdots$$

のよう,繰り返しになるので,答えは999とかっこよく求めていました!

こちらの方が,説明がしやすいですね.

ちなみに,この問題にかなり酷似した(というか単なる数値が変わっただけの)問題が昔のAIME(アメリカの数学のコンテスト,日本で言うJMO予選のようなものです)に出題されています.

Q.\(\ \ \)正の整数\(n\)に対して定義された関数\(f\)は

$$ f(n) = \begin{cases} n-3 & (n\ge 1000のとき) \\ f(f(n+5)) & (n<1000のとき) \end{cases}$$

満たす.\(f(84)\)を求めよ.

(AIME1984年問7)

全く同じ問題ですから,答えのみの紹介としておきます.\(n\)が\(1000\)未満のときの\(f(n)\)の値は\(n\)が偶数のとき\(997,n\)が奇数のとき\(998\)となり,答えは\(997\)です.もちろん,できますね?

(1990年はJMO予選のようなものが始まった年ですから,このように外国の数学コンテストと似た問題が出題されましたが,近年ではさすがにここまで似た問題が出ることは恐らく無いでしょう.)

JMO予選1990問7

\( A=4^{27}+4^{500}+4^{n}\) が平方数となる最大の自然数\(n\)を求めよ.

【思考\(\cdot\)方針】

平方数の問題で意識すべきは,

\(\cdot\ mod\ 3,mod\ 4\)を考えてみる

の他に,

\(\cdot \ \)平方数同士をかけても平方数

\(\cdot\ \)割りきれるなら,平方数を平方数でわっても平方数

といった「当たり前」や,

\(\cdot\ \)隣り合う平方数同士の差は(\(3,5,7,9,\cdots\)のよう)どんどん大きくなっていく

\(\cdot\ \)隣り合う平方数の間に平方数はない

などの不等式的な見方も重要です.今回はこのような考え方が活躍する問題です.

まず,「最大の自然数\(n\)」なんてそもそも存在するの?と思った人もいるかもしれませんが,これは不等式的に見れば明らかです.\(4^n=(2^n)^2\)は平方数ですから,それに定数\(4^{27}+4^{500}\)を加えても平方数となるには,あまりに\(n\)が大きすぎると,次の平方数\((2^n+1)^2\)にすらたどり着かなくなってしまいます.

(逆に,\(n\)が小さすぎても,\(4^{500}\)の次の平方数に\(A\)が満たないことになりますね.)

\(A\)は偶数ですから,\((2^n+1)^2\)にはならないので,少なくとも\(A\)は\((2^n+2)^2\)以上じゃなければなりません.もしも,\(A\)が\((2^n+2)^2\)に一致すれば答えな気もしますが,残念ながら

$$4^{27}+4^{500}=2^{n+2}+4$$

となり,\(n\)が求まりません.

ここで,\(4^{27}\)が\(4\)だったらなぁ\(\cdots\)と思うわけですが,じゃあ\(4\)にしてしまいましょう.

先ほども言ったよう,\(n\)はある程度は大きい.少なくとも\(27\)よりは大きそうですから,\(n\ge27\)範囲で答えを探ると,\(A\)を\(4^{26}\)でわった,\(4+4^{474}+4^{n-26}\)も平方数のはずです.そしてこれが平方数なのは,少なくとも,\(4^{n-26}=(2^{n-26})^2\)の次の偶数の平方数\((2^{n-26}+2)^2\)以上のとき.

\begin{eqnarray}&∴&4+4^{474}+4^{n-26}\ge(2^{n-26}+2)^2\\ &\Leftrightarrow&4^{474}\ge2^{n-24}\\ &\Leftrightarrow&2^{948}\ge2^{n-24}\\ &\Leftrightarrow&948\ge n-24\Leftrightarrow n\le972\end{eqnarray}

となり,\(n\)が上から押さえられ,しかも,等号が成り立つとき,

$$A=4^{27}+4^{500}+4^{n} =4^{26}(4+4^{474}+4^{n-26})=4^{26}(2^{946}+2)^2$$

となり,平方数となるとわかりましたから,求める\(n\)は\(972\)ですね!

答えだけでなく,真面目な不等式の論証も同時にやったので,少し複雑でしたが,もう1問,似たような考え方が鍵となる問題をみてみましょう.難問です.

Q.\(\ \ 2n^2+1,3n^2+1,6n^2+1\)が全て平方数となる自然数\(n\)は存在しないことを示せ.

(JMO本選2004年問1)

【略解】

難問でしたがいかがでしょうか.このような自然数\(n\)が存在したとします.全て平方数ということはかけても平方数です.しかし,6次式と平方数は相性が微妙なので,さらに\(n^2\)をかけて,8次式にしてしまいましょう.

\begin{eqnarray}&&n^2(2n^2+1)(3n^2+1)(6n^2+1)\\ &=&(6n^4+5n^2+1)(6n^4+n^2)\cdots① \end{eqnarray}

これが平方数となるかどうかですが,これは隣り合う平方数で挟めそうです!

\begin{eqnarray}①&=&36n^8+36n^6+11n^4+n^2\\ (6n^4+3n^2)^2&=&36n^8+36n^6+9n^4\cdots②\\ (6n^4+3n^2+1)^2&=&36n^8+36n^6+15n^4+6n^2+1\cdots③ \end{eqnarray}

より,①は隣り合う平方数②,③の間にあるので,平方数でなくなってしまいました!

よって,条件を満たす自然数$n$は確かに存在しませんね!

やってること自体は簡単だけど思いつくのは難しい.数学オリンピックらしい1問ですね.僕は強くこの問題が印象に残っているのですが,皆さんの「印象に残る1問」に追加されたら嬉しいです.

JMO予選1990問4

\(3\)人の力士\(A,B,C\)が「巴戦」をする.すなわち,まず,\(A,B\)の二人が\(1\)回戦目を行い,\(2\)回戦目以降は前の戦いで勝った人と前の戦いで戦わなかった人が戦う.\(2\)連勝した力士を優勝とする.\(7\)回戦行った上で,\(2\)連勝した力士がいなかった場合は優勝者なしとする.どの力士も各々の戦いで勝つ確率は\(1/2\)として,\(1\)回戦目で負けた力士が優勝する確率を求めよ.

【思考・方針】

大学入試にもよく出題される「巴戦」です.一度この手の問題を経験したことがある,もしくは,日頃から巴戦に親しんでいれば,パターンが実はほぼないことを知っているので楽勝ですし,知らない人も,樹形図を試しに書いてみれば,全然枝分かれしない様子がわかるでしょう.

簡単のため,\(1\)回戦目は\(A\)が勝ったとしましょう.すると

2回戦\(A\)vs\(C\)→\(A\)優勝or\(C\)が勝ち,続行

3回戦\(C\)vs\(B\)→\(C\)優勝or\(B\)が勝ち,続行

4回戦\(B\)vs\(A\)→\(B\)優勝or\(A\)が勝ち,続行

5回戦\(A\)vs\(C\)→\(A\)優勝or\(C\)が勝ち,続行

6回戦\(C\)vs\(B\)→\(C\)優勝or\(B\)が勝ち,続行

7回戦\(A\)vs\(B\)→\(B\)優勝or\(A\)が勝つ

のよう,試合のパターンや各々が優勝するタイミングというのは限られています.

∴\(\ B\)が優勝する確率は\(4\)回戦目で優勝する確率と\(7\)回戦目で優勝する確率を足し合わせ,

\begin{eqnarray}\left(\frac{1}{2}\right)^3+\left(\frac{1}{2}\right)^6=\frac{9}{64}\end{eqnarray}

です.\(A\)が\(1\)回戦目で負けた場合も同様ですから,\(1\)回戦目で負けた力士が優勝する確率は,

\begin{eqnarray}\frac{9}{64}\times2=\frac{9}{32}\end{eqnarray}

ですね!

むしろ気になるのは次のような疑問でしょうか.

Q.\(\ \ \)今の問題に対し,\(7\)回戦目でおしまいにせず,誰かが優勝するまで勝負を続けるとき,最初に戦う力士と最初に戦わない力士はどちらが有利か?

【略解】

\(n\)回やって勝負がつかない確率は\(\left(\frac{1}{2}\right)^{n-1}\)ですから,\(n\to\infty\)とすると\(0\)となるので,優勝者が決まらない確率は\(0\)と見なせます.

\(1\)回戦目で戦わなかった\(C\)が優勝する確率は,\(1\)回戦目のみはどちらが勝ってもいいことに注意して,無限等比級数の公式より,

\begin{eqnarray}&&(3回戦目で優勝が決まる確率)+(6回戦目で優勝が決まる確率)+\cdots\\ &=&\left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^5+\left(\frac{1}{2}\right)^8+\cdots=\left(\frac{1}{4}\right)÷\left(1-\frac{1}{8}\right)=\frac{2}{7}\end{eqnarray}

となります!そして,\(A\)と\(B\)の条件の対等性から,\(A\)が優勝する確率も\(B\)が優勝する確率も同じですから,\(\left(1-\frac{2}{7}\right)÷2=\frac{5}{14}\)となりますね.

これにより,\(A,B,C\)の優勝する確率の比は\(5:5:4\)となりました!\(C\)さんは若干不利なのですね.

ちなみに,\(A\)が\(B\)に勝った状態で次の試合を迎えるとき,\(A,B,C\)の優勝確率はそれぞれ,

\begin{eqnarray}&&\left(\frac{1}{2}\right)^1+\left(\frac{1}{2}\right)^4+\left(\frac{1}{2}\right)^7+\cdots\\ &=&\left(\frac{1}{2}\right)÷\left(1-\frac{1}{8}\right)\\ &=&\frac{4}{7}\\ &&\left(\frac{1}{2}\right)^3+\left(\frac{1}{2}\right)^6+\left(\frac{1}{2}\right)^9+\cdots\\ &=&\left(\frac{1}{8}\right)÷\left(1-\frac{1}{8}\right)\\ &=&\frac{1}{7}\\ &&\left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^5+\left(\frac{1}{2}\right)^8+\cdots\\ &=&\left(\frac{1}{4}\right)÷\left(1-\frac{1}{8}\right)=\frac{2}{7}\end{eqnarray}

となりますね.つまり,巴戦では,

  • 直前の勝負に対して勝った人,戦わなかった人,負けた人の優勝確率の比は\(4:2:1\)
  • \(1\)回戦目で戦わない人は若干不利

ということがわかります.

皆さんも,巴戦をやるときは意地でも\(1\)回戦目に出場するようにしましょうね!

JMO予選1990問3

\(A^2\)の下三桁が\(0\)でない全て同じ数になるという.そのような自然数\(A\)のうち,最小のものを求めよ.

【思考・方針】

皆さん気づきました?\(\ \)僕は,「\(144\)も\(1444\)も平方数」というのを耳にしたことがあったので,どうせ,\(\sqrt{1444}=38\)が答えだろうと思った結果,こんな解答になりました.

\(111,222,\cdots,999\)は\(37\)の倍数だが\(37^2\)の倍数ではないので,平方数でない.

\(1111=11\times101\)は平方数でない.

また,\(\ \)(調べれば簡単にわかるよう,)\(\ \)一の位が\(2,3\)の平方数はありませんから,\(1222,1333\)でない.そして,\(1444=38^2\)より\(38\)が答え.

しかし,まさかこんなに早く平方数が登場するなんて思わなかった!という人もいるでしょうから,他の視点から答えを探っていきましょう.

上の解答にもあったよう,平方数の一の位は限られるので,

$$A^2の下3桁は111,444,555,666,999\cdots①$$

にしぼられます.さらに,整数問題では\(mod\)を考える,特に

$$『平方数を3や4で割った余りは0か1』$$

は平方数の問題の定石です.(知らなかった人は確かめてみましょう.)

今回は\(mod\ 4\)で考えれば,(4で割った余りは下二桁で見抜けますから)\(\ \)①の中で\(4\)で割った余りが\(0\)か\(1\)のものを考えれば,\(A^2\)の下三桁は\(444\)で確定です.

候補は\(1/10\)に絞り込めましたから,\(1444,2444\cdots\)の中から平方数を探すと,いきなり\(1444=38^2\)がみつかってしまうというわけです.

ここまで来ると,次のような疑問が出てきます.

Q.\(\ \ \)下四桁が\(0\)以外のぞろ目であるような平方数は存在するか.

【略解】

上の議論により,下三桁の時点で\(4\)のぞろ目しかありえません.下手に\(mod\)とか考えず,まずは素朴に文字でおいてみましょう.下四桁が\(4444\)の平方数が存在する,つまり,

$$n^2=10000a+4444\cdots①\ \ (n,aは自然数)$$

とします.

すると,\(n\)は偶数ですから,自然数\(m\)を用いて\(n=2m\)と表せ,これを①に代入すると,\(m^2=2500a+1111\)となりますが,これは下二桁が\(11\)の平方数,つまり\(4\)で割った余りが\(3\)の平方数が存在することとなり矛盾です.

∴\(\ \)下四桁が\(0\)以外のぞろ目となる平方数は存在しないことが示せました!

皆さんもお友達に,「\(144,1444\)は平方数だから\(14444\)も平方数なんだ!」とか言ってる人がいたら,注意してあげてくださいね.

JMO予選1990問2

\begin{eqnarray}x^2+25x+52=3\sqrt{x^2+25x+80}\cdots①\end{eqnarray}

の全ての実数解の積を求めよ。

【思考・方針】

①はルートのついた方程式ですから両辺2乗してルートを消しましょう。しかし、それだと大変な4次方程式になってしまいそうですが、\(x^2+25x\)をひとかたまりだと思えば実質2次方程式です。そうすれば方程式が解けそうですから解いてしまいましょう。

簡単のため、\(x^2+25x+52\)をひとかたまりとみて、\(t\)とおきます。①を2乗すると、

\begin{eqnarray}&&t^2=9(t+28)\\ &\Leftrightarrow& t^2-9t-9\times28=0\\ &\Leftrightarrow&(t-21)(t+12)=0\\ &\Leftrightarrow&t=21,-12 \end{eqnarray}

が得られます。ここで、ルートのついた方程式について注意が必要なのは、2乗したら同値変形が崩れる(余計なものまで出てきてしまう)ということです。ルートの同値変形の基本

\begin{eqnarray}A=\sqrt{B}\Leftrightarrow A^2=BかつA\ge 0\end{eqnarray}

を意識すると実は\(t\ge 0\)という条件を付け加える必要があるので、\(t=21\)となります。よって①の解は

\begin{eqnarray}x^2+25x+52=21\Leftrightarrow x^2+25x+31=0\end{eqnarray}

の解であり、(判別式)\(=25^2-4\times31>0\)からこれは異なる2つの実数解を持つので求める実数解の積は解と係数の関係より、\(31\)となりますね。

これは比較的、大学受験的な問題ですし落としたくないですね。もう少し数学オリンピックぽさのあるルートのついた方程式の難問を見てみましょう。

Q.

\begin{eqnarray}x+\sqrt{x(x+1)}+\sqrt{x(x+2)}+\sqrt{(x+1)(x+2)}=2\cdots①\end{eqnarray}

を満たす正の実数\(x\)を求めよ。(JJMO予選2015問7)

【略解】

問7という問題が解けるかどうかは予選通過出来るか否かに大きく関わってくることが多い問題です。みなさんは解けましたでしょうか。

まず、気づかなければならないことは、ルートがたくさんついているので、対称性(?)をよくするために\(x=\sqrt{x}\sqrt{x}\)とみると、

\begin{eqnarray}①\Leftrightarrow(\sqrt{x}+\sqrt{x+1})(\sqrt{x}+\sqrt{x+2})=2\end{eqnarray}

のよう、因数分解できるということです。ここに気付くのが第一段階でしょう。ここからはルートの個数を減らしていくことを考えます。

有理化の要領で両辺に\(\sqrt{x+2}-\sqrt{x}\)をかけることにより、

\begin{eqnarray}2(\sqrt{x}+\sqrt{x+1})=2(\sqrt{x+2}-\sqrt{x})\end{eqnarray}

となり、整理すると

\begin{eqnarray}2\sqrt{x}=\sqrt{x+2}-\sqrt{x+1}\end{eqnarray}

となりますから、両辺2乗すればルートが1個に減らせます!

\begin{eqnarray}&&4x=x+2+x+1-2\sqrt{x+1}\sqrt{x+2}\\ &\Leftrightarrow&3-2x=2\sqrt{x+1}\sqrt{x+2}\end{eqnarray}

さらに両辺を2乗すれば、

\begin{eqnarray}&&4x^2-12x+9=4(x+1)(x+2)\\ &\Leftrightarrow&24x=1\Leftrightarrow x=\frac{1}{24}\end{eqnarray}

となりますね!途中で2乗してしまったことや計算ミスをしてないかの確認などの意味を込めて代入して確かめておくと、

\begin{eqnarray}\frac{1}{24}+\frac{5}{24}+\frac{7}{24}+\frac{35}{24}=2\end{eqnarray}

のように、\(x=\frac{1}{24}\)が解となっていることが確認できます。

なんにせよ、因数分解さえできれば、ルートを消していくという単純作業で解けてしまいました!

このようなA分野(代数)の問題は競技数学の中では比較的、勉強量が点数に結び付きやすい分野かもしれませんね。

JMO1990問1

\(N\)を\(1990\)桁の\(9\)の倍数とする.\(N\)の各桁の和を\(N_1,N_1\)の各桁の和を\(N_2,N_2\)の各桁の和を\(N_3\)とする.\(N_3\)を求めよ.

【思考・方針】

整数問題において,

  • \(\ mod\ \)を考える
  • 不等式的に範囲を考える

といったことは基本中の基本ですが今回は両方とも使います.まず,各桁の和といえば\(\ mod\ 9\ \)を考えるのは定石ですし,各桁の和をとる時点でだいぶ数が小さくなりますから,答えはそう大きくはない\(\ \)(というか,大きすぎると困る)\(\ \)と考えられますね.どちらも発想としては出やすいのではないのでしょうか.

STEP1\( \ \ mod\ 9\ \)で考える

各桁の和を取る操作は\(mod\ 9\)の世界では不変(つまり,元の数を\(9\)で割った余りと各桁の和を\(9\)で割った余りは等しい)なので,\(N\)が\(9\)の倍数であるから\(N_1\)も\(N_2\)も\(N_3\)も全て\(9\)の倍数です.

STEP2\( \ \ \)範囲を上から押さえる

\(N\)の各桁の和が最大となるのは\(9\)が\(1990\)個続くときでその時の各桁の和は

$$9\times 1990=17910\ \ \ \ \ ∴\ N_1\le17910$$

です.ということは,\(N_2\)はどんなに大きくても\(\ \)(\(N_1=9999\)のときを考えて)\(9\times4=36\)\(\ \)以下

さらに\(N_2\)は\(9\)の倍数でしたから,\(N_2=9,18,27,36\)にしぼりこめますが,いずれにしろ\(N_3=9\)となりますね!

IMO(国際数学オリンピック)にも類題が昔に出ておりますから,そちらでもう一度確認してみましょう.少し先程よりも手間はかかるもののすぐに解けるのではないでしょうか.

Q.\(\ N=4444^{4444}\)の各桁の和を\(A\),\(A\)の各桁の和を\(B\),\(B\)の各桁の和を\(C\)とする.\(C\)を求めよ.

(IMO1975年問4)

(注)\(4\)が並んだ不吉な問題だなと思いましたが,冷静に考えたら,開催国のブルガリアには\(4\)が不吉という文化はないのではということに気が付きました.

【略解】

まずは\(\ mod\ 9\ \)を調べましょう.先ほどの議論同様,\(N,A,B,C\)の\(9\)でわった余りは全て等しいです.

$$4444\equiv16\equiv-2\ \ (mod\ 9)$$

より,

$$4444^3\equiv(-2)^3\equiv-8\equiv1\ \ (mod\ 9)$$

ですから,

$$N\equiv4444^{1481\times3+1}\equiv(4444^3)^{1481}\times4444\equiv1^{1481}\times{(-2)}\equiv7\ \ (mod\ 9)$$

より,\(N,A,B,C\)を\(9\)でわった余りは\(7\)ですね.

次に不等式評価です.結構大雑把にしてしまいましょう.

\(N<10000^{4444}\)より,\(N\)は\(4444\times4=17776\)桁以下ですから,\(A\le9\times17776<180000\)ですから,\(8B\le45\)(\(←99999\)の各桁の和)

\(∴\ C\le12\)(←\(39\)の各桁の和)となり,\(C\)の\(9\)で割った余りは\(7\)ですから,\(C=7\)と確定します!

ここまで似た問題が出題されることは稀ですが,似たような考え方の問題というのはいろいろあったりするので,大昔のIMOの問題は比較的解きやすいものも多いですし,挑んでみるのも良いかもしれませんね.

JMO2019本選問2

答え\(\cdots n(n+1)\)

【分析】

まず、「問題を正しく読めたか」というのが勝負の分かれ目なのではないでしょうか。僕自身も数回読み直してから理解しました。この問題のややこしいポイントは「数字を書き込むたびに点数が入る」ということでしょう。つまり、\(3\times 3\)で具体例を挙げると(書き込む数字は1以上9以下ですが \(mod \ 3\)にしか興味がないので\(0,1,2\)を3つずつ書き込むことにします。)

のような感じで点が入り、この場合であれば\(2+2+2+0+1+1+1+1+2=12\)点というわけです。このように最後の書き込まれている数字を見ても書き込む順番が分からなければ点数はわからないわけです。しかし、実は最後に書き込まれている数字を見るとうまい順番で書き込んでも〇〇点しか入らないというふうに上からおさえることができます。たとえばこの例の3行目は\((1,2,0)\)なわけですがこれらはどのような順番で書き込んでも3行目では2点しか入らないというのは明らかですよね?

【略解】

\(mod \ n\)にしか興味はないので\(n\times n\)のマスに\(1\)以上\(n-1\)以下の整数を\(n\)個ずつ書き込むことを考える。

ゲームが終了した時点での数字の書き込みに注目すると\(m\)行目で入る点数は最大でも

$$(m行目にある0の個数)+\left[\frac{(m行目にある0以外の数の個数)}{2}\right]\ 点\cdots ☆$$

である。(∵\(\ \)0は始めに書き込めばそれぞれ1点になり、0以外の数は他の数と足して0を作らないと点が入らないので足して0になるペアができるときが最大)ここで、[a]でaの整数部分を表すことにした。

☆を各行各列に関して和を取ると書き込まれている数字においての点数の上限を与えることができ、

\begin{eqnarray}&&\sum_{m=1}^n\left\{
(m行目にある0の個数)+\left[\frac{
(m行目にある0以外の数の個数) }{2}\right] \right\} \\
&&+\sum_{m=1}^n\left\{
(m列目にある0の個数)+\left[\frac{
(m列目にある0以外の数の個数) }{2}\right] \right\}\\ =&&
\sum_{m=1}^n\left\{
(m行目にある0の個数)+
(m列目にある0の個数) \right\} \\
&&+\sum_{m=1}^n\left\{
\left[\frac{
(m行目にある0以外の数の個数) }{2}\right] +\left[\frac{(
m列目にある0以外の数の個数 )}{2}\right] \right\}\\ \le&& 2n+
\sum_{m=1}^n\left\{
\frac{(
m行目にある0以外の数の個数 )}{2} +\frac{(
m列目にある0以外の数の個数 )}{2} \right\}\\ =&&2n+(n^2-n)=n(n+1) \end{eqnarray}

となる。(∵\(\ \)1つの数字は行と列で2回点数に関与する。)

よって、\(n\times n\)マスでの点数は\(n(n+1)\)以下ということが分かり、\(n(n+1)\)点のものは簡単に作れる。(省略)

(上の例のように数字を書き込むとできます。)