No.027 C

$2x$ か $2x+1$ にするということは, 左に1ビットシフトして, 末尾のビットをセットするかどうかということである.

すなわち, 高橋君の操作後は必ず $2k$ ビットになり, 青木君の操作後は必ず $2k+1$ ビットになる.

$N$ が $2k$ ビットであるとき, 高橋君はなるべく $2k$ ビットになる数値を少なくするようにして, 青木君はなるべく $2k$ ビットになる数値を大きくするようにするのが正しい戦略である. このとき, $2k$ ビットの数値は $101010 \cdots_{(2)}$ となる.

$N \geq 101010 \cdots_{(2)}$ であれば高橋君は $N$ 以下の $2k$ ビットの数値を作れるので, $2k+1$ ビットの数値を作らされる青木君の負けである. そうでないときは高橋君の負けである.

同様に $N$ が $2k+1$ ビットであるとき, 青木君が勝つためには $N \geq 1101010 \cdots_{(2)}$ であることが条件になる.