はじめに
※本記事は、2018/2/8にHatenaBlogに投稿した記事を移行したものです
前回に引き続き、数学オリンピック国内1次予選 ( JMO ) の解説です。オリジナルの問題、解答 ( 答えの数値だけ ) は、こちらに公開されています。
- 問1~問6 … その1
- 問7~問9 … その2
- 問10,11 … 今回
- 問12 … その4
問題と解説
問題文の詳細については、冒頭のリンクよりご参照ください。以下では要約した問題文で説明していきます。
問10
問題・答え
8人の選手で総当たり戦を行った際の勝敗の状況として、次の条件を満たすのは何通りか。ただし引き分けはないものとする。
- その8人でトーナメントを行った場合、トーナメントの組み方により優勝者となる可能性のある人は2人である。ただし前提として、トーナメントの各試合の勝敗が総当たり戦の時と同じだとする。
※トーナメントの試合の進め方の詳細がオリジナルの問題に記されていますが、世間一般的なトーナメント方式 ( 誰でも3連勝で優勝 ) と考えて問題ないと思いますので、ここでは割愛します。
答え: 344064通り
解説
まあなんというか、丁寧に条件を解きほぐしていくよりなさそうです。
まずは「優勝者となる可能性のある人は2人」ということなので、その2人をA,Bと名付け、AがBに勝つものとします。
ここで明確にしておきたいのはこの「可能性」の意味です。これはつまり、次の2つのことを指しています。
- 総当たり戦の勝敗状況のままA,Bを優勝させるトーナメントの組み方がある。
- 総当たり戦の勝敗状況のままでは、A,B以外が優勝となるトーナメントの組み方はない。( 必ずA,Bどちらかが優勝する )
後者の方が意識から抜けがちなので注意したいところです。
では、Aの勝敗状況から行きます。もしAが全勝するとどうなるでしょうか? …それはもちろん、誰もAを負かせないので、常にAが優勝です。これはBの優勝の可能性が消えてしまいますからN.G.ということになります。つまりAに勝つ人が存在する ことを意味します。AはBに勝つという前提ですから、それはB以外の人になるはずです。
続いて、ではそのAに勝つ人は複数でしょうか? しかしもし複数いて、そのうち2人をC1,C2 ( C1はC2に勝つ ) とすると、次のトーナメントを組んだ時、A,Bとも優勝できません。

つまり、Aに勝つ人は1人だけです。それをCと名付けておきます。またこれで、Aの勝敗はC以外に全勝と確定しました。
次に、新しく出てきたCの勝敗状況を考えてみます。CはAに勝ちますが、それ以外の人に対してはどうでしょうか。
さきほどと似たトーナメントを組んでみると分かります。もしCがA,B以外の誰か ( Dとします ) に勝つようだと、A,Bとも優勝できずN.G.です。

じゃあ、CがBに勝つのはどうかというと、今度は別のトーナメントでA,Bとも優勝できないパターンができます。

結局、CがA以外の誰かに勝つのはマズいということです。これで、Cの勝敗はA以外に全敗と確定しました。
残るは ( 多分 ) Bだけです。BはAに負けてCに勝ちます。ではそれ以外の人に対してはどうでしょうか。
ところが、もしBがA,C以外の誰か ( Dとします ) に負けるようだと、次のトーナメントでA,B仲良く1回戦敗退でN.G.です。

ということで、Bは他の人に負けるわけには行きません。これで、Bの勝敗はA以外に全勝と確定しました。
ここまで整理してみます。
- AはC以外に全勝
- BはA以外に全勝
- CはA以外に全敗
では、他の人の条件はどうでしょうか。他の人は、A,Bには負け、Cには勝つところまで確定しています。
しかし、実は他の人の勝敗がどうであれA,B,Cの条件だけで、AまたはBの優勝が確定しているのです。次のように場合分けして考えてみます。
- A,C が1回戦で当たるトーナメント
- Aは1回戦敗退
- Bは1回戦も含め、全試合Aと当たらないため全勝
- つまりBが優勝
- A,C が1回戦で当たらないトーナメント
- Cは1回戦敗退
- Aは1回戦も含め、全試合Cと当たらないため全勝
- つまりAが優勝
この通り、A,B,C以外の勝敗は優勝者に全く影響を与えません。ということで、これで十分、条件は全て出揃いました。
後は組み合わせの計算です。
- 8人中、A,B,Cの役回りが誰になるか 8P3=336通り
- 残り5人の勝敗、計5C2=10試合で、それぞれ勝ち負けどちらでも良いので、210=1024通り
- トータルで、336×1024=344064通り
ということで、344064通りが答えとなります。
問11
問題・答え
以下の条件を満たす正の整数nは幾つ存在するか。
-
nを7進法表記した ( ただし最上位の桁は0ではない ) 場合の桁数kが2以上であり、
- 7進法表記したnから、それぞれ1桁目~k−1桁目を取り除いてできるk−1個のk−1桁7進法表記の数の総和がnに等しい。
答え: 42
解説
ちょっと問題が掴み辛いので、例を挙げてみます。
例えば、十進法での4649は、7進法では5桁の 16361 です。実際、 4649=1×74+6×73+3×72+6×71+1×70 が成立していますから。
ここから、1~4桁目を取り除いてできる数、1636, 1631, 1661, 1361 これを7進法表記として足し算すると、7進法10252、あるいは十進法で2536です。
ただ、この合計は元の数とは異なりますから、問題の条件は満たさないということになります。
…直感的には、桁を1つ抜いてできる数は、( 7進法での1桁の増減は7倍分に相当するので ) ほぼ元の 1/7 の大きさと見ると、7個分合計してやっと元の数と同等、つまり元のnの桁数kは8 ( k−1=7 ) なんじゃないかと思えます。とは言っても、その前後の桁数 ( 6桁や9桁 ) でも条件を満たす数がある可能性もありますし、まずは大きさを大まかに見積もって桁数を確定させることを考えます。
では見積もりですが、nの上位2桁だけだと流石に粗そうな気がするので、上位3桁を使ってやってみます。…というとk=2のケースが置き去りになってしまいますが、2桁の数では明らかに条件を満たせないので ( 桁を抜いた数1個だけでは元の数より明らかに小さい )、特に問題はありません。
では、nの7進法での上位3桁をabc (1≤a≤6, 0≤b,c≤6)とします。そうすると、n自体の大きさは次のように見積もれます。
- 0≤7k−3n−(49a+7b+c)<1
次に、桁を抜いた数k−1個分の総和についてです。上から2番目の桁を抜いてできる数は7進法でac⋯ですが、それ以外の桁を抜いてできるk−2個は全てab⋯となります。そのため、この総和をSとすると、
- 0≤7k−3S−{7(k−1)a+(k−2)b+c}<k−1
では、n=Sの仮定のもと、両不等式を合成します。
0≤7k−3n−(49a+7b+c)<1⇔−1<(49a+7b+c)−7k−3n≤00≤7k−3S−{7(k−1)a+(k−2)b+c}<k−1と辺々足し合わせて−1<(49a+7b+c)−7k−3n+7k−3S−{7(k−1)a+(k−2)b+c}<k−1⇒−1<(49a+7b+c)−{7(k−1)a+(k−2)b+c}<k−1 ∵n=S⇔−1<7(8−k)a+(9−k)b<k−1⇔0<(8−k)(7a+b)+b+1<k
こうしてみると、7a+bの部分は7以上ですから、
-
kが小さい場合: k≤7であれば、不等式の中央部分が8以上なのに対し、右辺kが7以下で不適
-
kが大きい場合: k≥9であれば、不等式の中央部分が0以下 ( bは6以下であることに注意 ) なので、左側の不等号が成立せず不適
これで、桁数k=8が必要であると分かりました。なので、実際に桁の数字の条件を調べてみます。
実際に桁を抜いた数を並べて、7進法のまま総和Sを表現してみます。nを7進法で表記した場合の下位の桁から d1,d2,⋯d8 (0≤d1,⋯,d7≤6,1≤d8≤6) としています。そうすると、次の図のようにnの桁と共通部分があることが分かります。

この時、ちょっと工夫としてnの上位2桁を1つずらして ( 代わりに7倍するので大きさは同じ )、同じ桁同士で見比べられるようにしています。そうすると、共通部分を相殺することで、1種の7進法覆面算ができあがります。これを解いてあげれば良いということです。
そうして覆面算を解いていくわけですが…。この時、各桁で繰り上がりが発生し得ますから、それを次の図のように c2,c3,⋯,c6 とします。

そうすると次の条件が分かります。
- d2+5d1≡0 mod 7, c2=(d2+5d1)/7 (0≤c2≤5)
- 2d3+4d2+c2≡0 mod 7, c3=(2d3+4d2+c2)/7 (0≤c3≤5)
- 3d4+3d3+c3≡0 mod 7, c4=(3d4+3d3+c3)/7 (0≤c4≤5)
- 4d5+2d4+c4≡0 mod 7, c5=(4d5+2d4+c4)/7 (0≤c5≤5)
- 5d6+d5+c5≡0 mod 7, c6=(5d6+d5+c5)/7 (0≤c6≤5)
- d7=c6
mod 7 なのは7進法の筆算だから、なのと、繰り上がりが0~5の範囲に収まるのは6個の数の加算だからですね。…しかし、良く見ると結構規則正しい形をしています。そこで、次のようにまとめられそうです。
- (i−1)di+(7−i)di−1+ci−1≡0 mod 7, ci={(i−1)di+(7−i)di−1+ci−1}/7 (2≤i≤6)
- d7=c6
なお、便宜上繰り上がりの来ない1桁目用にc1=0として文字を合わせています。
さてそうすると、7というのは素数ですから、一般に剰余方程式ax≡1 mod 7というのはa≡0の場合、必ず解が1つに決まります ( なおこの解のことをa−1と書いたりします。例えば2×4≡1⇔2−1≡4 )。ということは、この条件、d1を決めればそのまま将棋倒し的にd7まで一意に決まる ( かつ必ず解がある ) と言えます。具体的には次の通りです。なお、計算上の便宜としてei=di−ci (e1=d1)を導入しています。
⇔⇔⇔⇔⇔ (i−1)di+(7−i)di−1+ci−1≡0 mod 7 (i−1)di≡(i−7)di−1+ei−1−di−1 mod 7 (i−1)di≡(i−1)di−1+ei−1 mod 7 di≡di−1+(i−1)−1⋅ei−1 mod 7 ci={(i−1)di+(7−i)di−1+ci−1}/7 di−ei={(i−1)di+(7−i)di−1+di−1−ei−1}/7 ei={(8−i)(di−di−1)+ei−1}/7 d7=d6−e6
ということで、d1=0,1,⋯,6の7通りそれぞれに対してd2,d3,⋯,d7が1通りずつ決まると分かりました。問題としては個数を求めれば良いので、各diの値を求める必要はないのですが、実際に計算してみると次のようになります。
-
d1=0(e1=0)の場合
trivialに d2=d3=d4=d5=d6=d7=0
-
d1=1(e1=1)の場合
- d2≡d1+1−1⋅e1⇒d2=2,e2={6×(d2−d1)+e1}/7=1
- d3≡d2+2−1⋅e2⇒d3=6,e3={5×(d3−d2)+e2}/7=3
- d4≡d3+3−1⋅e3⇒d4=0,e4={4×(d4−d3)+e3}/7=−3
- d5≡d4+4−1⋅e4⇒d5=1,e5={3×(d5−d4)+e4}/7=0
- d6≡d5+5−1⋅e5⇒d6=1,e6={2×(d6−d5)+e5}/7=0
- d7=d6−e6=1
-
d1=2(e1=2)の場合
- d2≡d1+1−1⋅e1⇒d2=4,e2={6×(d2−d1)+e1}/7=2
- d3≡d2+2−1⋅e2⇒d3=5,e3={5×(d3−d2)+e2}/7=1
- d4≡d3+3−1⋅e3⇒d4=3,e4={4×(d4−d3)+e3}/7=−1
- d5≡d4+4−1⋅e4⇒d5=1,e5={3×(d5−d4)+e4}/7=−1
- d6≡d5+5−1⋅e5⇒d6=5,e6={2×(d6−d5)+e5}/7=1
- d7=d6−e6=4
-
d1=3(e1=3)の場合
- d2≡d1+1−1⋅e1⇒d2=6,e2={6×(d2−d1)+e1}/7=3
- d3≡d2+2−1⋅e2⇒d3=4,e3={5×(d3−d2)+e2}/7=−1
- d4≡d3+3−1⋅e3⇒d4=6,e4={4×(d4−d3)+e3}/7=1
- d5≡d4+4−1⋅e4⇒d5=1,e5={3×(d5−d4)+e4}/7=−2
- d6≡d5+5−1⋅e5⇒d6=2,e6={2×(d6−d5)+e5}/7=0
- d7=d6−e6=2
-
d1=4(e1=4)の場合
- d2≡d1+1−1⋅e1⇒d2=1,e2={6×(d2−d1)+e1}/7=−2
- d3≡d2+2−1⋅e2⇒d3=0,e3={5×(d3−d2)+e2}/7=−1
- d4≡d3+3−1⋅e3⇒d4=2,e4={4×(d4−d3)+e3}/7=1
- d5≡d4+4−1⋅e4⇒d5=4,e5={3×(d5−d4)+e4}/7=1
- d6≡d5+5−1⋅e5⇒d6=0,e6={2×(d6−d5)+e5}/7=−1
- d7=d6−e6=1
-
d1=5(e1=5)の場合
- d2≡d1+1−1⋅e1⇒d2=3,e2={6×(d2−d1)+e1}/7=−1
- d3≡d2+2−1⋅e2⇒d3=6,e3={5×(d3−d2)+e2}/7=2
- d4≡d3+3−1⋅e3⇒d4=2,e4={4×(d4−d3)+e3}/7=−2
- d5≡d4+4−1⋅e4⇒d5=5,e5={3×(d5−d4)+e4}/7=1
- d6≡d5+5−1⋅e5⇒d6=1,e6={2×(d6−d5)+e5}/7=−1
- d7=d6−e6=2
-
d1=6(e1=6)の場合
- d2≡d1+1−1⋅e1⇒d2=5,e2={6×(d2−d1)+e1}/7=0
- d3≡d2+2−1⋅e2⇒d3=5,e3={5×(d3−d2)+e2}/7=0
- d4≡d3+3−1⋅e3⇒d4=5,e4={4×(d4−d3)+e3}/7=0
- d5≡d4+4−1⋅e4⇒d5=5,e5={3×(d5−d4)+e4}/7=0
- d6≡d5+5−1⋅e5⇒d6=5,e6={2×(d6−d5)+e5}/7=0
- d7=d6−e6=5
ということで、全部で7通り…あれ? 何か忘れてるような。そうです、条件を整理している中で消えてしまったd8がありました。これは消えてしまったということはどんな値を設定しても良いということを意味しますので、1~6の6通りがそれぞれの組に対して設定できるわけです。
ということで、これが本当に最後です。7×6=42で42個が答えとなります。
終わりに
いよいよ次で最後です。やはり最後までまとめて書くのはきつかった。
Discussion