数学オリンピック1次予選問題解いてみました ( その2 )
はじめに
今年度 ( 2016年1月 ) のJMO ( 日本数学オリンピック ) の1次予選問題を解いた、その説明の続きです。
目次
- 問1 … その1にあります
- 問2 … その1にあります
- 問3 … その3にあります
- 問4 … その1にあります
- 問5 … その3にあります
- 問6 … 今回の記事にあります
- 問7 … 今回の記事にあります
- 問8 … その4にあります
- 問9 … 今回の記事にあります
- 問10 … その4にあります
- 問11 … そのうち書きます
- 問12 … ぐぬぬ
解説
例によって、問題文は適宜改変してますので、オリジナルについては冒頭のリンクからご覧ください。
問6
問題
次のような問題です。
- 1~200の整数の内、半数 ( 100個 ) の合計から残りの合計を引き、平方した数を計算する。
- 半数の選び方全てに対する、その「平方した数」の平均を求めよ。
解説
答えは670000です。
いや、いきなり1~200と言われても想像つきませんね。小さい数で試しに考えていきましょう。さしあたり1~4で。これであれば半数 ( 2個 ) の選び方も6通りで済みます。
$$
\begin{eqnarray}
(+1+2-3-4)^2=&+&1^2+2^2+3^2+4^2 \\
&+&2(+1\cdot 2-1\cdot 3-1\cdot 4-2\cdot 3-2\cdot 4+3\cdot 4) \\
(+1-2+3-4)^2=&+&1^2+2^2+3^2+4^2 \\
&+&2(-1\cdot 2+1\cdot 3-1\cdot 4-2\cdot 3+2\cdot 4-3\cdot 4) \\
(+1-2-3+4)^2=&+&1^2+2^2+3^2+4^2 \\
&+&2(-1\cdot 2-1\cdot 3+1\cdot 4+2\cdot 3-2\cdot 4-3\cdot 4) \\
(-1+2+3-4)^2=&+&1^2+2^2+3^2+4^2 \\
&+&2(-1\cdot 2-1\cdot 3+1\cdot 4+2\cdot 3-2\cdot 4-3\cdot 4) \\
(-1+2-3+4)^2=&+&1^2+2^2+3^2+4^2 \\
&+&2(-1\cdot 2+1\cdot 3-1\cdot 4-2\cdot 3+2\cdot 4-3\cdot 4) \\
(-1-2+3+4)^2=&+&1^2+2^2+3^2+4^2 \\
&+&2(+1\cdot 2-1\cdot 3-1\cdot 4-2\cdot 3-2\cdot 4+3\cdot 4) \\
\end{eqnarray}
$$
はい。地道な平方の展開です。ただし、こういう組み合わせの時にはちゃんと規則性が見えるように書き方を工夫しておくと見通しが良くなります。
見て気づくのは、どの平方に関しても同じ項 ( 符号が違うことはあるにしても ) が現れる、ということです。
そして、個々の数の立場は同等である以上、符号が + になる数、- になる数というのも、全体の合計では揃っているはずです。実際これを合計して平均を出すと、次のようになります。
$$
(合計)=6(1^2+2^2+3^2+4^2)-2\cdot 2(1\cdot 2+1\cdot 3+1\cdot 4+2\cdot 3+2\cdot 4+3\cdot 4) \\
(平均)=(1^2+2^2+3^2+4^2)-\frac{1}{3}\cdot 2(1\cdot 2+1\cdot 3+1\cdot 4+2\cdot 3+2\cdot 4+3\cdot 4)
$$
殊に1~4の平方和がそのまま平均に現れますね。そうすると問題になるのは+,-が入り乱れる積の項の部分、+の項と-の項が何回ずつ現れるのか。また各項の合計が実際どのような値になるのか、です。
では n に一般化してみましょう。「半数」をいちいち分数で書くのが面倒なので、$n=2m$としておきます。そうすると、
- $(+1+2\cdots)^2$ や $(-1-2\cdots)^2$ のように符号が揃って $2(+1\cdot 2\cdots)$ と積の項が+になる数
残り$n-2$種から、半数の残り$m-2$個を選択する ${}_{n-2}C_{m-2}$の倍、$2{}_{n-2}C_{m-2}$個
※+の半数を選ぶのと-の半数を選ぶのは符号が裏返しで等価であることに注意 - $(+1-2\cdots)^2$ や $(-1+2\cdots)^2$ のように符号が揃わず $2(-1\cdot 2\cdots)$ と積の項が-になる数
残り$n-2$種から、半数の残り$m -1$個 ( +になってるのは1個だから ) を選択する ${}_{n-2}C_{m -1}$の倍、$2{}_{n-2}C_{m -1}$個
よって、
$$
\begin{eqnarray}
(平均)&=&(1^2+2^2+\cdots +n^2)+\Bigl(\frac{2{}_{n-2}C_{m-2}}{{}_nC_m}-\frac{2{}_{n-2}C_{m -1}}{{}_nC_m}\Bigr)\cdot 2(1\cdot 2+1\cdot 3+\cdots +(n-1)n) \\
&=&(1^2+2^2+\cdots +n^2)+\Bigl(\frac{2m(m -1)}{n(n-1)}-\frac{2m(n-m)}{n(n-1)}\Bigr)\cdot 2(1\cdot 2+1\cdot 3+\cdots +(n-1)n) \\
&=&(1^2+2^2+\cdots +n^2)+\frac{2m(2m-n-1)}{n(n-1)}\cdot 2(1\cdot 2+1\cdot 3+\cdots +(n-1)n) \\
&=&(1^2+2^2+\cdots +n^2)-\frac{1}{n-1}\cdot 2(1\cdot 2+1\cdot 3+\cdots +(n-1)n)\,\,\,\,(\because n=2m) \\
\end{eqnarray}
$$
C 同士の分数の約分は…慣れてない人にはキツいのかな。数式が多くなると書くのが大変見通しが悪そうなので省いてますが。
ともあれ、大分すっきりしました。後は平方和と積の和を整理します。
$$
(1+2+\cdots +n)^2=(1^2+2^2+\cdots +n^2)+2(1\cdot 2+1\cdot 3+\cdots +(n-1)n) \\
\Rightarrow 2(1\cdot 2+1\cdot 3+\cdots +(n-1)n)=(1+2+\cdots +n)^2-(1^2+2^2+\cdots +n^2) \\
(1+2+\cdots +n)=\frac{1}{2}n(n+1) \\
(1^2+2^2+\cdots +n^2)=\frac{1}{6}n(n+1)(2n+1)
$$
これらを組み合わせて仕上げです。
$$
\begin{eqnarray}
(平均)&=&(1^2+2^2+\cdots +n^2)-\frac{1}{n-1}\cdot 2(1\cdot 2+1\cdot 3+\cdots +(n-1)n) \\
&=&(1^2+2^2+\cdots +n^2)-\frac{1}{n-1}\Bigl((1+2+\cdots +n)^2-(1^2+2^2+\cdots +n^2)\Bigr) \\
&=&\frac{n}{n-1}(1^2+2^2+\cdots +n^2)-\frac{1}{n-1}(1+2+\cdots +n)^2 \\
&=&\frac{n^2(n+1)(2n+1)}{6(n-1)}-\frac{n^2(n+1)^2}{4(n-1)} \\
&=&\frac{n^2(n+1)\Bigl( 2(2n+1)-3(n+1) )\Bigr)}{12(n-1)} \\
&=&\frac{1}{12}n^2(n+1)
\end{eqnarray}
$$
最終形はかなり簡単な形になりました。結局$n=200$の時の値$\frac{200^2\cdot 201}{12}$を計算して終わりです。
…ちょっと計算をまとめるのに体力が要るかもしれませんが、やることは割と一本道ではないでしょうか。
問7
問題
- 「実数」a,b,c,dが次の条件を満たす時、$a^2+b^2+c^2+d^2$の最小値を求めよ
$$ \left\{\begin{array}. (a+b)(c+d)=2 \\ (a+c)(b+d)=3 \\ (a+d)(b+c)=4 \\ \end{array}\right. $$
解説
答えは7です。
…いやもうね。見た瞬間途方にくれます。どうすりゃいいんだと。こんなのご都合主義的な何かがないと解けないんじゃないかと。
しかしここで逆に考えてみます。解けるんであれば、むしろそういう何かが用意されてるんじゃないの、と。目的の式がいかにも対称式であること、条件の式全てに$a+b+c+d$を分割した数の積が現れていることから、対称性を活かした整理をすれば道が拓けると信じて進めてみます。
まず、中間的な変数を導入します。 $$ \begin{eqnarray} p=a&+&b \\ q=a&\,& &+&c \\ r=a&\,& &\,& &+&d \\ s=a&+&b&+&c&+&d \\ \end{eqnarray} $$ ここからb,c,dを消すように辺々足し引きすると、$p+q+r-s=2a$ という条件も分かります。ここから改めてb,c,dを置き換えていくのですが、まあそれは後にして、問題の条件を次のように書き換えます。 $$ \begin{eqnarray} p(s-p)=2 \\ q(s-q)=3 \\ r(s-r)=4 \\ \end{eqnarray} $$ こうして見ると非常に良く似た形ですね。…こういう時は和を取っておきたくなりませんかね。辺々足して整理して、次の形も出しておきます。 $$ p^2+q^2+r^2=s(p+q+r)-9 $$ 続いて、a,b,c,dを置き換えていきます。$p+q+r-s=2a$から更に整理すると、 $$ \begin{eqnarray} a=\frac{1}{2}(+p+q+r-s) &\Rightarrow& a^2=\frac{1}{4}\Bigl((p^2+q^2+r^2)+2(+pq+q r+rp)+2s(-p-q-r)+s^2\Bigr) \\ b=\frac{1}{2}(+p-q-r+s) &\Rightarrow& b^2=\frac{1}{4}\Bigl((p^2+q^2+r^2)+2(-pq+q r-rp)+2s(+p-q-r)+s^2\Bigr) \\ c=\frac{1}{2}(-p+q-r+s) &\Rightarrow& c^2=\frac{1}{4}\Bigl((p^2+q^2+r^2)+2(-pq-q r+rp)+2s(-p+q-r)+s^2\Bigr) \\ d=\frac{1}{2}(-p-q+r+s) &\Rightarrow& d^2=\frac{1}{4}\Bigl((p^2+q^2+r^2)+2(+pq-q r-rp)+2s(-p-q+r)+s^2\Bigr) \\ \end{eqnarray} $$ …sだけ特別扱いにするの、作為的ですね。ええその通りです。理由は合計した時に分かります。 $$ \begin{eqnarray} a^2+b^2+c^2+d^2&=&\frac{1}{4}\Bigl(4(p^2+q^2+r^2)+2s(-2p-2q-2r)+4s^2\Bigr) \\ &=&(p^2+q^2+r^2)-s(p+q+r)+s^2 \\ &=&s^2-9\,\,\,\,(\because p^2+q^2+r^2=s(p+q+r)-9 ) \end{eqnarray} $$ はい、p,q,rが綺麗さっぱり消えました。これをご都合主義と言わずして…という感じですね。
ここに来るとa,b,c,dが「実数」となっている理由に気づきます。そう、2次方程式の解の存在です。最も厳しい条件は、$r(s-r)=4$ という「rに関する2次方程式」の条件から$s^2\geq 4^2$ですから、答えは$4^2-9$と計算できるわけです。
解いてしまうと、難しいんだか簡単なんだか判断に悩む問題です。
問9
問題
以下の条件を全て満たす整数$(a,b)$の組の個数を求めよ
- $1\leq a,b\leq 2016$
- $a$は$b+1$の倍数
- $2016-a$は$b$の倍数
解説
答えは1980です。
…問題文を見ただけでは何とも掴みにくいところです。なので、条件を数式にしてみます。
$$
\begin{eqnarray}
a &=&n(b+1)\,\,\,&(& b\geq 1,nは整数,n\geq 1 ) \\
2016-a&=&mb &(& b\geq 1,mは整数,m\geq 1 ) \\
\end{eqnarray}
$$
実は a の大きさの条件は ( 書いていませんが ) これで吸収できてしまっていることに注意してください。
そして何となく辺々足してaを消去してみます。
$$
\begin{eqnarray}
2016&=&b(n+m)+n\,\,\,( b\ge 1,n\geq 1, m\geq 1 ) \\
\Leftrightarrow 2016&=&db+n\,\,\,( d=n+m, n\geq 1, d\gt n )
\end{eqnarray}
$$
…あれ? と、ここでティンと来たら解決です。
$$
2016\div d=b\ldots n\,\,\,( b\geq 1, d\gt n\geq 1 )
$$
そう、実はこの形、余り付きの割り算に他ならないのです。除数 d を定めれば、b,n,m ひいては a も一意に定まります。必要な条件はこれだけ。
- d は2016を割り切らない
- 商が 1 以上になる ( $d\leq 2016$ )
つまり、この問題は「2016の約数を数えよ」の逆バージョン、「2016の約数でない数を数えよ」と同じわけです。約数の数は ( 計算は省略しても良いよね?? ) 36個ありますので、2016から引いて答えが出ます。
続き
ここまで、絵を描くのが面倒でない数式でゴリっと行ける問題を駆け足で見てきました。こんだけ解ければ6問で、合格ラインに足りるかどうか…? というところじゃないでしょうかね。