平成２９年7月9日
[流れ星]
第348回数学的な応募解答
＜解答募集期間：6月１1日〜７月９日＞
［サッカーのリーグ戦］
あるサッカーの大会に、いくつかのチームが参加した。各参加チームは他チームとちょうど1回ずつ試合をした。各試合では、勝つと３点、引き分けると１点、負けると０点の得点を与えられる。すべての試合が終了したとき、あるチームは他のどのチームより高い得点を獲得したにもかかわらず、他のどのチームよりの勝利した試合数が少なかった。
このようなことが起こりうる参加チームの最小値を求めよ。
＜出典：数学オリンピックへの道 組合せ論の精選102問（朝倉書店）＞
NO1「スモークマン」 06/17 19時49分 受信
更新 7/9
(勝)-(分け)-(負) の数で表す...
a-(m-a)-0・・・得点=3a+m-a=m+2a
残りがみな、以下のように近似的になりうる…
そのチームの得点=3(a-1)+1=3a-2<m+2a=4a-3 がなりててばいい…
1<a
so…
2-(m-2)・・・得点=3*2+m-2=m+4
3-1-3・・・m=7
このとき、
3*3+1=10<7+4=11 で成り立つ ^^
so…
so…
実際に…
3-1-3
3-1-3
3-1-3
3-1-3
3-1-3
3-0-4
3-04
と可能…なはず ^^
NO2「早起きのおじさん」 06/18 11時26分 受信
「早起きのおじさん」 06/20 10時58分 受信
「早起きのおじさん」 06/22 17時18分 受信
更新 7/9
|
特定の1チーム（A）とnチーム（B1，B2，･･･，Bn）の計n＋1チームのリーグ戦を考えます。 |
||||||||||||||||||
|
全チームの成績が同じところから考え始めます。 |
||||||||||||||||||
|
全チームｎ引き分けとします。 |
||||||||||||||||||
|
参加チーム数は、ｎ＋1です。 |
||||||||||||||||||
|
勝ちは○、負けは×、引分は△で表します。 |
||||||||||||||||||
|
１．考え初め |
||||||||||||||||||
|
|
A |
B1 |
B2 |
B3 |
･･･ |
Bn |
勝ち |
負け |
引分 |
得点 |
||||||||
|
A |
|
△ |
△ |
△ |
･･･ |
△ |
0 |
0 |
n |
ｎ |
||||||||
|
B1 |
△ |
|
△ |
△ |
･･･ |
△ |
0 |
0 |
n |
ｎ |
||||||||
|
B2 |
△ |
△ |
|
△ |
･･･ |
△ |
0 |
0 |
n |
ｎ |
||||||||
|
B3 |
△ |
△ |
△ |
|
･･･ |
△ |
0 |
0 |
n |
ｎ |
||||||||
|
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
|
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
||||||||
|
Bn |
△ |
△ |
△ |
△ |
△ |
|
0 |
0 |
n |
ｎ |
||||||||
|
網掛けの部分のnチームのリーグ戦を考えます。 |
||||||||||||||||||
|
どのチームも1勝したとします。 |
||||||||||||||||||
|
１つの引き分けが勝ちになり、１つの引き分けが負けになります。 |
||||||||||||||||||
|
2点減り、3点増えるのでどのチームも１勝すればどのチームも得点が1増えます。 |
||||||||||||||||||
|
特定の1チームは、1勝すると引き分けが１つ減るので、2点増えることになります。 |
||||||||||||||||||
|
２．nチームのリーグ戦でどのチームも3勝（3敗）した場合 |
||||||||||||||||||
|
|
A |
B1 |
B2 |
B3 |
B4 |
B5 |
･･･ |
Bn |
勝ち |
負け |
引分 |
得点 |
||||||
|
A |
|
△ |
△ |
△ |
△ |
△ |
･･･ |
△ |
0 |
0 |
n |
ｎ |
||||||
|
B1 |
△ |
|
○ |
○ |
○ |
× |
･･･ |
× |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
B2 |
△ |
× |
|
○ |
○ |
○ |
･･･ |
× |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
B3 |
△ |
× |
× |
|
○ |
○ |
･･･ |
× |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
B4 |
△ |
× |
× |
× |
|
○ |
･･･ |
○ |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
B5 |
△ |
○ |
× |
× |
× |
|
･･･ |
○ |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
|
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
||||||
|
Bn |
△ |
○ |
○ |
○ |
× |
× |
･･･ |
|
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
特定のチームが2勝すると得点が4増えます。 |
||||||||||||||||||
|
３．Aが2勝した場合 |
||||||||||||||||||
|
|
A |
B1 |
B2 |
B3 |
B4 |
B5 |
･･･ |
Bn |
勝ち |
負け |
引分 |
得点 |
||||||
|
A |
|
○ |
○ |
△ |
△ |
△ |
･･･ |
△ |
2 |
0 |
nー2 |
ｎ＋4 |
||||||
|
B1 |
× |
|
○ |
○ |
○ |
× |
･･･ |
× |
3 |
4 |
nー7 |
ｎ＋2 |
||||||
|
B2 |
× |
× |
|
○ |
○ |
○ |
･･･ |
× |
3 |
4 |
nー7 |
ｎ＋2 |
||||||
|
B3 |
△ |
× |
× |
|
○ |
○ |
･･･ |
× |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
B4 |
△ |
× |
× |
× |
|
○ |
･･･ |
○ |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
B5 |
△ |
○ |
× |
× |
× |
|
･･･ |
○ |
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
|
･･･ |
･･･ |
･･･ |
･･･ |
･･･ |
||||||
|
Bn |
△ |
○ |
○ |
○ |
× |
× |
･･･ |
|
3 |
3 |
nー6 |
ｎ＋3 |
||||||
|
この結果特定のチームは、他のどのチームより得点が高くかつ勝利した試合数が少なくなります。 |
||||||||||||||||||
|
引き分けの数ｎー7＝0とすると、ｎ＝7。 |
||||||||||||||||||
|
よって参加チームの最小数は、n＋1＝7＋0＋1＝8です。 |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
NO3「二度漬け白菜」 06/24 12時24分 受信
更新 7/9
(答)このようなことが起こりうる参加チーム数の最小値は 8．
(証明)
題意を満たすような「あるチーム」が存在したとして，
そのチームを A とする．
このサッカー大会に参加したチームの総数を n (n≧2)とし，
Aが勝利した試合数を k とする．
この大会においては，1試合につき，対戦する両チームに加算
される得点は，両チーム合わせて2点以上．
従ってこの大会で加算された総得点数は，
2*C(n,2)=2*(n*(n-1)/2)=n*(n-1) 以上．------(★)
いま，もしAが獲得した得点が n-1 以下だとすると，A以外の
チームはどのチームも n-2 点以下しか獲得していないから，
この大会で加算された総得点数は (n-1)+(n-1)*(n-2)=(n-1)^2
以下となり(★)に反する．
よって，Aが獲得した得点は n 以上．------(★★)
もし，k=0だとすると，Aは全ての試合で引き分け
もしくは 負け
ということになり， Aの得点は，1*(n-1)=n-1 以下となる．
これは(★★)に反する．
したがって k≧1 である．
Aが獲得した得点のうち，勝利による得点はちょうど 3*k 点．
A以外のチームは，どのチームも勝利によって少なくとも
3*(k+1)=3*k+3 点を獲得している．
Aの獲得した点は 3*k+3 より大でなければならないから，
Aと引き分けているチームが少なくとも1つある．
Aと引き分けているチームの一つをBとすると，
Bは勝利と引き分けにより，少なくとも 3*(k+1)+1
=3*k+4 点を獲得していることになる．
よって，Aの得点は 3*k+5 点以上でなければならない．
つまり，Aは5試合以上で引き分けていることになる．
このとき，チームA および Aが勝利したk個のチーム および
Aと引き分けた少なくとも5個のチーム
が存在することになる．
よって，n≧1+k+5=k+6≧7 となる．
n=7と仮定してみる．
このとき k=1 であり，Aと引き分けたチームはちょうど5チーム
となる．A以外のチームはどのチームも2勝以上していることになる
が，Aの得点がちょうど8点であることを考慮すれば，A以外のチーム
はどのチームもちょうど2勝していることになる．
さらにA以外のチームはどのチームも引き分けは 1 試合以下である．
よって，A以外のチームはどのチームも3試合以上負けていることに
なる．このとき，
この大会で勝ったチームののべ数は 1+2*6=13であり，
この大会で負けたチームののべ数は 3*6=18 以上
ということになるが，これは矛盾．
(勝ったチームののべ数と負けたチームののべ数は等しいはずである．)
よって，n≧8 である．
n=8のとき，題意を満たすような勝敗表が存在することを以下に示す．
正整数 a，b に対し，aをbで割った余りを mod(a,b) で表す．
参加する8チームを，
A，B[1]，B[2]，B[3]，B[4]，B[5]，B[6]，B[7]
とする．
A は B[1]，B[2] に勝利し，B[3]，B[4]，B[5]，B[6]，B[7]
に引き分けるものとする．
また，1≦i≦7なるすべてのiに対し，
B[i] は B[1+mod(i,7)]，B[1+mod(i+1,7)]，B[1+mod(i+2,7)] に勝利し，
B[1+mod(i+3,7)]，B[1+mod(i+4,7)]，B[1+mod(i+5,7)] に負けるものと
する．このように勝敗を決めれば，これは問題文の条件をみたすような
勝敗表であることがわかる．
(この勝敗表においては，
Aの成績は2勝0敗5分けで，Aの得点は11点．
B[1]とB[2]の成績は3勝4敗0分けで，得点は9点．
残りのチームの成績は3勝3敗1分けで，得点は10点．)
以上より，題意を満たすようなことが起こり得る参加チーム数の最小値
は 8 である．(証明終)
「102 combinatorial problems 」というキーワードで検索すれば，
今回出題されている問題の，問題文と解答例を閲覧することができますね．
例えば次のページがヒットしました．
(どうやら一定期間が経過すると，削除されるようです．)
https://mathematicalolympiads.files.wordpress.com/2012/08/102-combinatorial-problems.pdf
NO4「にいばりZ12」 07/09 01時36分 受信 更新 7/9
|
参加チーム数をｎ |
|||||
|
引き分けの試合数をｍとすると |
|||||
|
試合数は、ｎC2＝ｎ（ｎ-1）/2 |
|||||
|
勝敗のつく試合数は |
|||||
|
ｎ（ｎ-1）/2-ｍ |
|||||
|
全チームの得点合計 |
|||||
|
下図リーグ表の水色と緑に入る点数の合計となります |
|||||
|
水色に勝ち（3点）が入ると対角の緑には負け（0点）が入り、引き分けの場合両方に1点が入るので |
|||||
|
3（ｎ（ｎ-1）/2-ｍ）+2ｍ＝3ｎ（ｎ-1）/2-ｍ |
|||||
|
得点の平均は、 |
|||||
|
（3ｎ（ｎ-1）/2-ｍ）/ｎ＝3（ｎ-1）/2-ｍ/ｎ |
|||||
|
平均の最大値はｍ＝0の時で |
|
||||
|
3（ｎ-1）/2 |
点 |
|
|||
|
どのチームよりも高い得点を獲得するには平均を上回らなければなりません |
|||||
|
また、どのチームよりも勝ち数が少ないという事は、他のチームは少なくとも1勝以上をあげているという事になります。 |
|||||
|
今、a1チームに注目します。（ｎを充分に大きくとります） |
|||||
|
全て引き分けた場合（勝ち数0）得点はｎ-1点となります |
|||||
|
また、引き分けの試合数ｎ（ｎ-1）/2≧ｍ≧ｎ-1となります |
|||||
|
よって得点の平均の最小値は、ｍが最大の時に取るので |
|||||
|
3（ｎ-1）/2-ｍ/ｎにｎ（ｎ-1）/2＝ｍを代入し |
|||||
|
ｎ-1となります。（これはすべてのチームが他のチームと引き分けたケースです） |
|||||
|
a1チームの得点がｎ-1点で他のチームがすべて同じ得点であってもその得点はｎ-1点であり |
|||||
|
他のチームより高いとは言えません |
|||||
|
よって、a1チームの全て引き分けは有りません。 |
|||||
|
同様の理由で、1勝以上はあげなければなりません（引き分けと負けだけの組み合わせはない） |
|||||
|
上記の理由で、a1チーム以外のチームはa1チームより勝ち数が多くなければならないので2勝以上挙げなければならない事が解ります。 |
|
また、a1チームはｎ-1得点以上であれば負けもありうるが勝ち数を最小にすることを考えると負けは考えられない。 |
|
a1チームは引き分けで得点を稼ぐほかありません |
|
a1チームが１勝ｎ-2分け（勝ち以外はすべて分け） 得点3+n-2+0=n+1点 チーム数1 |
|
a1チームに負けたチームは、2勝ｎ-3負け 得点6+0+0=6点 チーム数1 |
|
それ以外のチームは2勝1分けｎ-2負け
得点6+1+0=7点
チーム数n-2 |
|
参加チームnが最小7の時上式が条件を満たします |
|
上記の計算式にn=7を代入すると |
|
8n-7＝49 |
|
ところが、チームの総得点は前述したとおり |
|
3ｎ（ｎ-1）/2-ｍ |
|
なので |
|
ｎ=7、m=n-2＝5で |
|
3・7（7-1）/2-5＝58 |
|
で結果はｏｕｔとなります |
|
そこで |
|
a1チームが１勝ｎ-2分け（勝ち以外はすべて分け） |
|
a1チームに負けたチームは、2勝ｎ-3負け |
|
それ以外のチームは2勝1分けｎ-2負け |
|
の条件で方程式を解いてみます |
|
8n-7＝3ｎ（ｎ-1）/2-（ｎ-2） |
|
9n-9＝3ｎ（ｎ-1）/2 |
|
ｎ（ｎ-1）＝6n-6 |
|
n2-7n+6＝0 |
|
n＝1,6となりｏｕｔ |
|
a1チームが2勝ｎ-3分け（勝ち以外はすべて分け）
得点6+n-3+0=n+3点 チーム数 1 |
|
a1チームに負けたチームは、3勝ｎ-4負け
得点9+0+0=9点 チーム数
2 |
|
それ以外のチームは3勝1分けｎ-5負け
得点9+1+0=10点
チーム数 n-3 |
|
の条件で方程式を解いてみます
総得点は n+3+18+10(n-3)=11n-9 |
|
11n-9＝3ｎ（ｎ-1）/2-（ｎ-3） |
|
12n-12＝3ｎ（ｎ-1）/2 |
|
8n-8＝ｎ2-n |
|
ｎ2-9n+8＝0 |
|
n=2,8 |
でa1チームは8チームあれば他のどのチームより高得点で勝ち数がどのチームより少ないという条件を満たします。
よって最小値は8チーム・・・・回答
|
|
対戦相手 |
|||||||||||||
|
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
得点計 |
得点 |
勝ちの |
勝ち回数 |
|||
|
得点 |
a1 |
|
3 |
3 |
1 |
1 |
1 |
1 |
1 |
11 |
1 |
2 |
8 |
|
|
a2 |
0 |
|
3 |
3 |
3 |
0 |
0 |
0 |
9 |
7 |
3 |
1 |
||
|
a3 |
0 |
0 |
|
0 |
3 |
3 |
0 |
3 |
9 |
7 |
3 |
1 |
||
|
a4 |
1 |
0 |
3 |
|
0 |
0 |
3 |
3 |
10 |
2 |
3 |
1 |
||
|
a5 |
1 |
0 |
0 |
3 |
|
0 |
3 |
3 |
10 |
2 |
3 |
1 |
||
|
a6 |
1 |
3 |
3 |
0 |
3 |
|
0 |
0 |
10 |
2 |
3 |
1 |
||
|
a7 |
1 |
3 |
3 |
0 |
0 |
3 |
|
0 |
10 |
2 |
3 |
1 |
||
|
a8 |
1 |
3 |
0 |
0 |
0 |
3 |
3 |
|
10 |
2 |
3 |
1 |
||
＜水の流れ：実は今までずっと応募いただいていた「uchinyan」様ですが、現在のところ届いていません。体調を崩されたと思われます。皆さん、季節がら体調管理にご留意ください」
