朝日新聞パズルパーク2004年3月27日の問題

トーナメントで1位に負けた人を2位，準決勝で1位,2位に負けた人を3位,4位，準々決勝で1〜4位に負けた人を5位〜8位とする。

100名でトーナメントを行ったとき，AさんはBさんに勝ち，Bさんの順位がAさんの順位の7倍だった。

Aさん，Bさんの順位は幾つか。28人は一回戦不戦勝でした。

解答への考え方(ヒント)

決勝戦をレベル0，準決勝をレベル1，準々決勝をレベル2と考えると，N位の人にレベルLで負けた人の順位は 2^L + N になる。

以下に図を示す。

Aさんが N 位, Bさんが7N 位とすると，以下の式が成り立つ。

7N = 2^L + N

式を変形して

6N = 2^L

通分すると

3N = 2^(L-1)

2を何乗しても3の倍数にはならない。ということはこの式を満たすN,Lの組合せは存在しないことになる。

ありゃ?困った。

トーナメントに参加した人数が2の階乗の場合，上記式が成り立つが，2の階乗でない場合一回戦が不戦勝の人が存在する。実は1回戦で不戦勝があるのでそのことを考慮する必要がある。

不戦勝があると，N位に一回戦で負けた人の順位は

 2^L + N 

でなく，

 2^L + N - i      ( i >= 0 )

と考えることが出来る。

BさんはAさんに一回戦で負けている。AさんとBさんが2回戦以降で対戦したとするなら 7N = 2^L + N が成立しなければならないが，これを満たすN,Lは無いので，AさんはBさんと一回戦で対戦しAさんが勝っている。ということはBさんは64位以降100位以内ということになる。

for( n=0; n< 100; n++) {
    m = 7 * n;
    if( m > 64 && m <= 100) { 解候補 }
}

解速度

即