偽コインのパズル

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

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

https://www.facebook.com/1129148772/posts/10222591132543559?d=n&sfns=mo

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

• 問題のいろいろなバリエーション
• 複数個ある場合の解法を発見

2021-04-25 https://www.facebook.com/nishiohirokazu/posts/10224642622509526 10枚中2枚が重い偽コイン →10枚中2枚の時最悪4手で確定できることが分かったので、10年前の僕が解けなかった「80枚中1〜3枚」にチャレンジしよう →「80枚に重いコインが2枚」でも僕にとってまだ難しかった

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

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

10枚中1〜2枚が重い偽コイン 10枚中3枚が重い偽コイン