京大特色入試, コインの問題を解く先週あたり, 京大の特色入試の問題 (理学部) が超難問だと話題になっていました. 確かに大学受験でこの問題を解けと言われたらかなり難しく,「五輪級」(数学オリンピック本選あたりかな?) というのも納得です. 既にこの問題を解いている人はいます. 問1については実際の手順を示すことで解答としているようですが, ここではn=7, k=3の場合について一般的に解きたいと思います. 一般的に解くことで, 示す手順が最小の手順だということも証明します. 記法 問1の表になってるコインのうち, 一番上にあるものから時計回りにc1, c2,…, c7と名前を付けます. (「コイン (coin)」のcを使いました.) コインが表の状態を0, 裏の状態を1で表します. さっきの名前を変数名として使って「コインc1が表であること」を「c1の値が0であること」で,「コインc1が裏であること」を「c2の値が1で
