◆愛知県 Y.M.Ojisan さんからの解答。
【問題1】
【問題2】
3人ずつA,B,Cクラスに分け
(1) クラス内では3すくみ(つまり各人1勝)
(2) AはBから各人2勝、Cから各人3勝→全6勝中Cから3勝
(3) BはCから各人2勝 →全4勝中Cから2勝 & Cは全2勝中Cから1勝
が成立すればOK.実際成立した。
【問題3】 9人のみ
Cクラス内では3試合あり、勝ち数合計は3である。
よってCクラスの3人の勝ち数合計はその倍の6に限られる。
これを均等に分けるとしても最低Cクラスの人の勝ち数は2である。
よってA〜Bクラスの人の勝ち数は4か6(Cクラスは3人)でなければならない。
人数をNとするとき、トーナメント全体の勝ち数はNC2でありこの数には次の条件を満足しなければならない。
(1) 偶数である。
(2) 4(N−3)+6以上
(3) 6(N−3)+6以下
以上を満足するNは8と9だけである。
N=9は【問題1】で存在が確認されている。
N=8の場合、勝ち数28を振り分けるとAクラス1人、Bクラス4人及びCクラス3人でなければならない。
BクラスはCクラスに各人1敗:全体で4敗しなければならない。
一方、CクラスはAクラスには勝てないのでBクラスから丁度合計3勝しなければならず矛盾する。
よってN=8は不可能。
【P。S。】
勝ち数タイ時は得失点差とかトスで順位を決める場合は、次の【問題1】の解もある。\××○○○○○○
○\×○○×○○○
○○\×○×○○○
××○\×○×○○
×××○\○×○○
×○○××\○×○
×××○○×\○○
×××××○×\○
××××××××\
この場合、問題3の条件(2)は2(N−3)+6以上である。
そしてN=5が条件を満足するものとして加わる。
即ち Cクラス5人である。
しかしその解は存在しない。
またN=8の場合、新しいクラス分けが可能になる。
即ち Dクラス0勝を含めA3C5、A2B2C4、A1B5C1D1の3ケースが可能性ありになる。
しかしこれらに対応する解も存在しない。
従ってやはり9人のみである。
【P。S。ケース不可能証明1】
下位3チームは上位チームから必ず合計3個勝ちをえなければならない。
それはBまたはCクラスからのみである。
従って上位チームのクラス分けはAXB1C1かAXB3しかない。
(a)N=5のC5の上位はC2であり適合しない。
(b)N=8のA3C5の上位はA3C2であり適合しない。
(c)N=8のA2B2C4の上位はA2B2C1であり適合しない。
(d)N=8のA1B5C1D1の上位はA1B4であり適合しない。
なお、 (問題3解) N=8のA1B4C3の上位はA1B4であり適合しない。
【P。S。ケース不可能証明2】
一般に
(I) N=NA+NB+NC+ND
(II) N(N−1)/2=6NA+4NB+2NC
(III) NB+2(NC -3)=3 (下位C3ケース)
or NB +2(NC -1)=3 (下位B1C1D1ケース)
である非負整数NA,NB,NC,NDがあるかという問題にもなります。
(III)から
[NB=1 NC =4 ND=0],
[NB=3 NC=3 ND=0],
[NB=1 NC=2 ND=1],
[NB=3 NC=1 ND=1]
の4ケースが可能で
4NB+2NC=12、18、8、14≡0 or 2 mod 6 です。
すなわち(II)式より
N(N−1)/2≡0 or 2 mod 6でなければなりません。
よってN=5,8は成立しません。
一方N=9は候補です。
あるいは、(I)を代入すると
N(N−1)/2=6N−[18|18|16|16] に帰着され、
ここからN=4,9が得られます。
N=4はNA<0で不適当です。
よってN=9のみ。
◆東京都 明 さんからの解答
【問題1】\×○○×××××
○\××○××××
×○\××○×××
×○○\○○×××
○×○×\○○××
○○×××\○○×
○○○○××\○○
○○○○○××\○
○○○○○○××\
【問題2】
「全員がリーグ戦の最下位から3人までの選手との対戦で勝ち星のちょうど半数を得た」ことから「最下位から3人までの負け数」が全体の勝数の半分になる。
9人のリーグ戦のため、全体の勝数は 36
3人の総試合数は 24
したがって、最下位から3人までの総勝数を w とすると、
2・(24-w) = 36
よって w = 6
最下位3人の個々の勝数をできるだけ少なくするためには、最下位3人同士の戦いは3すくみ(各自一勝ずつ)が望ましい。
逆に1人が2勝してしまうと、その選手は題意より4勝していなければならず、 それより上位の6選手は5勝以上していなければならない。
各人の勝数は、最下位3選手からの勝数の倍であることから偶数でなくてはならない。
したがって上位6選手は、少なくとも6勝をあげていることになり、全体の勝数が36を越えてしまう。
したがって最下位3人の戦いは3すくみとならなくてはならない。
以上より最下位3選手の個々の勝数は2勝ずつとなる。
この条件で下位3選手の勝敗を決定する。
このとき下位選手が特定の上位選手から勝ちを取らないように配置する。
最下位3選手の勝敗を決めると、上位選手6人が最下位3選手から取る勝数が決まる。
後はこの勝数と同じ勝ちがとれるように、上位6人同士の勝敗を決定すればよい。
なお、最下位3選手については勝数が最下位選手同士の対戦の勝数の倍である制限を外すと、以下のような勝敗表が可能ですが、題意には合わないようです。\○×××××××
×\○○×××××
○×\×○○×××
○×○\○○×××
○○××\○○××
○○×××\○○×
○○○○××\○○
○○○○○××\○
○○○○○○××\
【問題3】
最下位3選手同士の試合を外して、最下位3選手と上位6選手と18試合の勝敗に注目すると、最下位から3人までの総勝数 w と全体の勝数との間で以下の関係が成り立つ。
2・(18-(w-3))+w = 36
(w から引かれる 3 は最下位同士の試合の勝数)
答えは【問題2】と同じく w = 6
(これが上記「最下位3選手については勝数が最下位選手同士の対戦の勝数の倍である制限を外す」ときの勝敗表が可能な理由の一つです。)
以上の考え方から、リーグ戦への参加人数を n とすると以下の二式が成立することになる。
2・(3・(n-1)-w) = n(n-1)/2 (1)
2・(3・(n-3)-(w-3))+w = n(n-1)/2 (2)
(2)-(1)より n にかかわらず
w = 6
(1)式に代入して
n(n-1)/2-12・(n-1)+24 = 0
よって n2-13n+36 = 0
n = 9 または 4
n = 4 のときは勝敗表が下記のようになり、上位選手が存在しない。\○×○
×\○○
○×\○
×××\
したがって最下位3選手を対象とする場合、 n = 9 のみが条件をみたせる。
最下位の選手を3選手から p 選手に拡張すると、(1),(2)式は次のように表現されます。
2・(p(n-1)-w) = n(n-1)/2 (1)
2・(p(n-p)-(w-p(p-1)/2))+w = n(n-1)/2 (2)
同じように(2)-(1)から w を求めると、
w = p(p-1)
(1)に代入して p について解くと
2p2-2np+n(n-1)/2 = 0
p = (n±貧)/2
p が整数となるためには n = k2 の形が必要であり、また最下位選手数が全体の半分以下であると考えると、
p = k(k-1)/2 (n = k2)
【問題1】は k = 3に対応している。
k = 4 とすると16選手のリーグ戦を扱うことになり、この時、「全員がリーグ戦の最下位から6人までの選手との対戦で勝ち星のちょうど半数を得る」という条件になります。
実際この時は以下の勝敗表が条件に合致します。
\○○○×× ○○○×××××××
×\○○○× ×××○○○××××
××\○○○ ××××××○○○×
×××\○○ ○××××××××○
○×××\○ ×○○×××××××
○○×××\ ×××○○×××××
×○○×○○ \○○○○×××××
×○○○×○ ×\○○○○××××
×○○○×○ ××\○○○○×××
○×○○○× ×××\○○○○××
○×○○○× ××××\○○○○×
○×○○○○ ○××××\○○○○
○○×○○○ ○○××××\○○○
○○×○○○ ○○○××××\○○
○○×○○○ ○○○○××××\○
○○○×○○ ○○○○○××××\
(最初の6選手が最下位グループです。)
n = k2 (k≧2) すべてで成立することは証明できていませんが、何とかなりそうな雰囲気です。
ちなみに n = 4 は最下位選手が1名の全敗で上の n = 4 の表のひっくり返しの形になります。
◆愛媛県 K5 さんからの解答
たとえば、\○○○××○○○
×\○○○×○○○
××\○○○○○○
×××\○○○○×
○×××\○○×○
○○×××\×○○
×××××○\×○
××××○×○\×
×××○×××○\
このような感じになります。
解き方は、全員がリーグ戦の最下位から3人までの選手との対戦で勝ち星のちょうど半数を得たわけだから全員勝ち数は偶数になり、また最高は6勝になる。
また、リーグ戦の表から全員の勝ち星の合計は36となるから、9人で組み合わせを考えると、6勝が3人、4勝が3人、2勝が3人となり、最下位から3人というのは、その3人全員が2勝ずつしていることになる。
そこに注目すると、その3人はお互いに1勝ずつして残りの1勝を、その3人以外の人からあげていることになる。
同様に考えて、4勝した3人は最下位の3人から2勝ずつし、上位3人は最下位3人に全勝していることになる。
このように考えて○×を当てはめていくと、あとは何通りもの組み合わせができる。
問題3は、最下位の3人から最高あげられる星数は、全員に勝ったときの3勝だから、何人参加しようが上位は最高6勝までしかできない。
また、問題文の条件から最下位の3人はお互いに1勝ずつしてリーグで2勝という形しかできない。
したがって、2勝3人、4勝、6勝を何人ずつするかという組み合わせになる。
10人、11人のときはリーグ戦の総勝ち数が奇数になり一人一人の勝ち数が偶数であるから、その組み合わせができない。12人のときは最下位3人が4勝して残り9人が6勝すれば勝ち数は一致するが、最下位3人がお互いから2勝ずつすることは不可能であるから12人も無理である。
したがって、まず最高9人であるといえる。
次に、8人のときは2勝3人、4勝4人、6勝1人、7人、6人は総勝ち数が奇数、5人のときは2勝3人で残り2人で4勝だから全員2勝ということになり、不可能。
それ以下はない。
8人のときは4勝が4人になるがそれでは2勝が3人でなくなり、結局これも不可能。
したがってこの問題では9人のみである。
◆大阪府 Non さんからの解答
【問題1】
\○×○○×○○○
×\○×○○○○○
○×\○×○○○○
×○×\○×○○×
××○×\○×○○
○××○×\○×○
××××○×\○×
×××××○×\○
×××○××○×\
【問題2】
9人を上位3人(Aグループ),中位3人(Bグループ),下位3人(Cグループ)に分け、
A-A 1勝1敗 A-B 2勝1敗 A-C 3勝0敗 (総勝ち星6、対C勝ち星3)
B-A 1勝2敗 B-B 1勝1敗 B-C 2勝1敗 (総勝ち星4、対C勝ち星2)
C-A 0勝3敗 C-B 1勝2敗 C-C 1勝1敗 (総勝ち星2、対C勝ち星1)
とすると条件を満たす。各グループ内では三つ巴の状態。
(条件を満たす形はこれだけではないが)
【問題3】
下位3人をCグループとよぶことにすると、勝ち星の数は、
・総勝ち星0(対C勝ち星0)
・総勝ち星2(対C勝ち星1)
・総勝ち星4(対C勝ち星2)
・総勝ち星6(対C勝ち星3)
の4つの可能性が考えられる。
Cグループ内対戦(総勝ち星数3)について考える。
もし総勝ち星0の選手がいたと仮定すると、
Cグループの構成は、
・総勝ち星0(グループ内勝ち星0)
・総勝ち星2(グループ内勝ち星1)...(A)
・総勝ち星4(グループ内勝ち星2)...(B)
の3人ということになり、他の選手はすべて
・総勝ち星6(対Cグループ勝ち星3)
ということになるが、そうするとCグループ選手はグループ外選手に全く勝てないことになり、(A)や(B)に矛盾する。
よって、総勝ち星0の選手はいない。
よって、Cグループの構成は、
・総勝ち星2(対C勝ち星1)
が3人ということになる。
このとき、Cグループ選手はそれぞれグループ外選手から1勝をあげていることになるが、その選手は重ならない。
(もし重なるとすればその相手はCグループ相手に高々1勝しかできないことになり矛盾)
よって、Cグループ選手に負けた選手
・総勝ち星4(対Cグループ勝ち星2)
が3人。
残りが、
・総勝ち星6(対Cグループ勝ち星3)
ということになる。
選手の総人数をn人とすれば、その内訳は、
・総勝ち星2 3人
・総勝ち星4 3人
・総勝ち星6 (n-6)人
となり、勝ち星の総数は、6+12+6(n-6)=6n-18だが、
総対戦数を考えると、勝ち星の総数はn(n-1)/2となるので
6n-18=n(n-1)/2を解いて、n=4,9
このうち条件に適するのは9人の時のみ。
◆東京都 じっさん さんからの解答
【問題1】\×○○○×○○○
○\×○×○○○○
×○\×○○○○○
××○\×○○○×
×○×○\×○×○
○×××○\×○○
×××××○\×○
××××○×○\×
×××○×××○\
【問題2】
A |B
|
−−+−
C |D
図のように対戦表の各領域にA〜Dと名前をつける。
Dは下位3人の中での対戦。全3戦。
D中には○が3個あり、最低1勝する人がいる。
題意から、C中の○の数とD中の○の数は同じ。
C中も○が3個となる。
対戦表の特性から、B中の×の数はC中の○の数と同じ3個となる。
B中の○の数は(n−3)×3−3=3n−12個となる。
題意から、A中の○の数とB中の○の数は同じ。
A中の○の数も3n−12個となる。
表の全体の○の数は、(B中の○の数+D中の丸の数)×2
なので(3n−12+3)×2=6n−18となる。
一方、n人のリーグ戦の対戦数は、
n×(n−1)÷2で、その数だけ対戦表に○が付くので、
n×(n−1)÷2=6n−18
とならなければならない。
これを解くと、
n×n−13n+36=0
(n−4)(n−9)=0
従って、n=4,9
ただしn=4の場合はB中の○の数が0となり、下位3人よりも上位1人の成績が低くなってしまうので題意を満たさない。
従って、9人以外は解が無い。
【問題3】
対戦者n人、下位k人で考える。(n>k≧1)
D中の○の数はk×(k−1)÷2
C中の○の数はk×(k−1)÷2
B中の○の数はk×(n−k)−k×(k−1)÷2
A中の○の数はk×(n−k)−k×(k−1)÷2
これらの合計は、2k×(n−k)
n人の対戦数と同じなので、
n×(n−1)÷2=2k×(n−k)
n×n−(4k+1)×n+4k×k=0
これを解くと、
n={4k+1±ルート(8k+1)}÷2
nは整数なので、8k+1は奇数の2乗でなければならない。
8k+1=(2j+1)×(2j+1)
(2j+1>0,jは整数)と置く。
k≧1に対し、j≧1となる。
これを解くと
k=j×(j+1)÷2となる。
jとj+1はどちらかが必ず偶数になるので、kは整数という条件を満たす。
また、このときnをjで表すと、
n={2j(j+1)+1±(2j+1)}÷2
これを解いて
n=(j+1)×(j+1)またはj×j
でいずれも平方数となる。
次に、k人が下位と確定するためには、下位k人の勝ち星(○の数)を平均化し小数点以下を切り上げた数が、 上位n−k人の誰の勝ち星よりも小さくなければならない。
全員、下位k人との対戦で勝ち星の半分を得ることから、下位k人との対戦での勝ち星の数で考えても条件は同じ。
下位k人の間での対戦数(=○の数)、即ちD中の○の数は、
k×(k−1)÷2
下位k人の平均は (k−1)÷2 となる。
これの小数点以下を切り上げた数は、
kが奇数のとき、 (k−1)÷2
kが偶数のとき、 k÷2である。
上位n−k人が全てこの数よりも最低1勝多く勝たなければならないので、B中の○の数は、以下の数字以上でなければならない。
kが奇数のとき、 (n−k)×{(k−1)÷2+1}
kが偶数のとき、 (n−k)×(k÷2+1)
B中の○の数はk×(n−k)−k×(k−1)÷2 なので、以下の不等式を満たす必要がある。
(1)kが奇数のとき
k×(n−k)−k×(k−1)÷2≧(n−k)×{(k−1)÷2+1}
2k×(n−k)−k×(k−1)≧(n−k)×(k+1)
(n−k)×(k−1)−k×(k−1)≧0
(k−1)×(n−2k)≧0
k≧1なので、k=1またはn≧2k
n>kなので、k=1のときn≧2となりn≧2kを満たすので、
まとめて n≧2k
n≧2×{j×(j+1)÷2}
n≧j×j+j
これはj×jよりも大きく、(j+1)×(j+1)よりも小さい。
従って、解はn=(j+1)×(j+1)だけであり、
またこの解はn≧2kの条件を満たす。
(2)kが偶数のとき
k×(n−k)−k×(k−1)÷2≧(n−k)×(k÷2+1)
2k×(n−k)−k×(k−1)≧(n−k)×(k+2)
(n−k)×(k−2)−k×(k−1)≧0
(k−2)×n−k(2k−3)≧0
(k−2)×n≧k(2k−3)
ここで、k=2のとき、0≧2 で条件を満たさない。
1≦k<2の偶数は無い。
k>2のとき、両辺をk−2で割って、
n≧k×(2k−3)÷(k−2)
k=j×(j+1)÷2を代入して、
n≧(j×j+j)÷2×(j×j+j−3)÷(j×j+j−4)×2
n≧(j×j+j)×{1+1÷(j×j+j−4)}
右辺の前半はj×jよりも大きく、後半は1よりも大きいので、
n=j×jの解は無い。
n=(j+1)×(j+1)の解についてはこれだけではわからない。
(j+1)×(j+1)−{(j×j+j)×(j×j+j−3)÷(j×j+j−4)}≧0
が成り立てばn=(j+1)×(j+1)は条件を満たすことになる。
(j+1)×(j+1)×(j×j+j−4)−j×(j+1)×(j×j+j−3)≧0
(j+1)×(j×j+j−4)−j×(j×j+j−3)≧0
j×j×j+2j×j−3j−4−j×j×j−j×j+3j≧0
j×j−4≧0
(j+2)×(j−2)≧0
j≧2
これを満たさないのはj=1の時だけであるが、
j=1の時はk=2×3÷2=1で奇数であるため、
kが偶数であれば必ずj≧2を満たすことになる。
従って、kが奇数でも偶数でも、n=j×jの解は無く、
n=(j+1)×(j+1)の解は条件を満たす。
結果として、
j=1,2, 3, 4, 5, 6,...に対し、
k=1,3, 6,10,15,21,...
n=4,9,16,25,36,49,...
が決まる。
上記以外の解は無い。
解答
【問題】
あるスポーツでは,n人の参加選手全員の総当りのリーグ戦で順位を決めています。
ただしこのスポーツには引き分けがないとします。
今回の対戦では、選手は全員がリーグ戦の最下位からk人までの選手との対戦で勝ち星のちょうど半数を得ました。
に解があるという条件で、nとkに当てはまる数字は以下の条件を満たす。
正の整数j(j=1,2,3,...)に対し、
k=j×(j+1)÷2
n=(j+1)×(j+1)
問題3はこれ以外に解は無いことは証明できましたが、この対戦表が必ず作れることは証明の
方法がわかりませんでした。
残念。
◆愛知県 迷子の雄猫 さんからの解答
\○○×○×○○○
×\×○○○○○○
×○\×○○○○○
○×○\×××○○
×××○\○○×○
○××○×\○○×
×××○××\○×
××××○××\○
×××××○○×\
下位3人以外を上位陣と定義する。
1人あたりの試合数をnとおく。
試合に参加した人は全て偶数個の勝ち星を上げたから、各個人の勝利数は6,4,2,0のいずれかである。
このゲームには引き分けがないので、
全員の勝数合計=全員の負数合計=1人あたりの試合数X人数÷2
上位(n−2)人が全て6勝(下位3人に3勝0敗)したと考えると、
(勝数−負数)の合計は、(n−2)(12−n)となる。
実際には下位3人同士では、3勝3敗となるから、下位3人は全員で、6勝したことになる。
つまり、上位陣は下位3人に、合計3敗している。
上位陣の(勝数−負数)の合計は、
(n−2)(12−n)−12となる。
これが下位三人の(負数−勝数)
つまり(3n−12)と等しいから、
(n−2)(12−n)−12=(3n−12)
これをといて、n2−11n+24=0
n=8またはn=3
試合数=(参加人数−1)より、考えられる人数は9人または4人
しかし、参加人数が4人であると、上位陣が一人しかいないので、上位陣一人は下位3人に、合計3敗、つまり全敗していることになる。
これでは2勝している下位3人より上位にはなれないので、考えられる人数は9人のみ。
=証明終わり=
9人しかありえないのにはおどろきました。
◆ 問題へもどる
◆ 今週の問題へ