偽コインのパズル

知識のあり方について議論する上でよい題材なのでまとめる

探し方(つまりアルゴリズム)の工夫で効率が10倍以上変わることと、偽コインが複数あるかもしれないと途端に難しくなることを解説(デバッグの文脈での講義なので早く気づくことが大事と言う話)

「N枚のコインの中にM枚の偽コインがあって、偽コインは(少し重い|重いか軽いかわからない)」という問題の問題ごとの最小手数のパターンが急に気になってきた(なぜそれを連休初日ではなく連休終わりに気になるのか…)

2020-08-11

問題のいろいろなバリエーション

複数個ある場合の解法を発見

2021-04-25

→10枚中2枚の時最悪4手で確定できることが分かったので、10年前の僕が解けなかった「80枚中1〜3枚」にチャレンジしよう

→「80枚に重いコインが2枚」でも僕にとってまだ難しかった

N,N,Mに分けて比較した場合の次の状態

傾いた場合2,0,0 か1,0,1

傾かない場合1,1,0か0,0,2