天秤の問題 その7

では、天秤を3回使って見つけることのできる最大の個数はいくつでしょうか。
「13個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を3回だけ使って見つけるにはどうしたらよいか。」
解答：
1. 13個のうち8個を選んで4個ずつを左右に乗せる。つりあわなかった場合は2aへ、つりあえば2cへ。
2a. 軽かった4個を左右に2個ずつ、重かった4個から1個ずつの合計3個ずつを両側に載せる。つり合わなかった場合は3aへ、つりあえば3bへ。
2c. 左に3個だけ残し、右側を最初に載せなかった5つのうち3個に変える。つり合わなかった場合は3cへ、つりあえば3dへ。
3a. 1回目に重かったコイン4個のうち、載せなかった2個を左右に1個ずつ載せて、重かったほうが偽コイン。
3b. 重かった方から、1回目に重かった2個を左右に1個ずつ載せて、重かったほうが偽コイン。つり合えば、軽かった方に乗っていた、1回目に軽かった1個が偽コイン
3c. 新たに載せた3個に偽コインがあることがわかり、それが軽いか重いかもわかるので、1回でわかる。
3d. 左に1個だけ残し、右側を今までのせたことのない2つのうち1個に変える。つり合わなかった場合は新しく載せたコインが偽コイン、つりあえば最後の1個が偽コイン。
かなり複雑になりますが、解けます。

天秤の問題 その6

3個では少ないならこれはどうでしょうか。
「4個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を2回だけ使って見つけるにはどうしたらよいか。」
解答：4つのうち2個を選んで1個ずつを左右に乗せる。つり合わなかった場合は、一方のコインを残っているコインと入れ替えて、つり合わなければ残したコインが偽コイン、つり合えば変えたコインが偽コインとわかります。
最初につり合ったときも、一方のコインを残っているコインと入れ替える。つり合わなければ最後の１個がが偽コイン、つり合わなければ今新たに載せたコインが偽コインとわかる。
4個は大丈夫です。うまくできました。

天秤の問題 その5

では問題を変えてみましょう。
「3個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を2回だけ使って見つけるにはどうしたらよいか。」
解答：3つのうち2個を選んで1個ずつを左右に乗せれば、つり合えば残りの1個が偽コインとわかる。つり合わなかった場合は、一方のコインを残っているコインと入れ替えて、つり合わなければ、残したコインが偽コイン、つり合えば変えたコインが偽コインとわかります。
1回が2回に変われば解があります。ただし、ここでは最初につり合えば2回目は必要ありません。ということは、3個というのは2回という条件では少なすぎることがわかります。

天秤の問題 その4

では問題をすこし複雑にしてみます。偽コインが重さがわかっていないとしたらどうでしょうか。コインが2個では重さが違うことはわかりますが、どちらが偽物かはわかりませんので、問題は3個以上に限られます。
「3個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を1回だけ使って見つけるにはどうしたらよいか。」
解答：不可能
最初に1個ずつ載せてつり合えば最後の1個が偽コインとわかりますが、つり合わなかったときには軽い方が偽コインか重い方が偽コインか判定できないためです。最後の1個は重いか軽いかはわからなくてもいいのですが、2個に関しては、偽コインが重いか軽いかがわからなければいけなくなります。ですから、全体では5通りの組み合わせがあるので、3通りしか分けられない天秤1回ではわからないわけです。

天秤の問題 その3

その2の先を考えます。一般的に
「3^n個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤をn回だけ使って見つけるにはどうしたらよいか。」
解答：3^n個を3^(n-1)個の3つのグループに分けれて、二つを天秤に乗せれば、つり合わなければ軽いグループに、つり合えば残りのグループに偽コインが含まれることになります。これを繰り返せば、n回で偽コインは見つかることになります。
となります。逆に言えば、
「いくつかのコインの中に見ただけではわからないが、1つだけ軽い偽コインがある。天秤をn回使って偽コインを見つけることができる最大の個数は3^n個」
ということができます。

天秤の問題 その2

その1で、天秤の状態が「右が軽い」「左が軽い」「つり合う」の3通りしか無いから、天秤を1回だけ使うという条件では、最大3つまでしか判別できないという話を書きました。ということは天秤を2回使えば、3×3=9通りの判別ができるはずから、9個までが2回で判別できる可能性はあります。
「9個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を1回だけ使って見つけるにはどうしたらよいか。」
解答：9個のうち6個を選んで3個ずつを左右に乗せれる。一方が軽ければその3個の中に偽コインがあり、つり合えば残りの3個の中に偽コインがあるとわかる。あとはその1と同様に、考えればよい。
無事に判別できそうです。

天秤の問題 その1

さて、まず簡単なよく知られた問題から。
「3個のコインがある。見ただけではわからないが、1つだけ軽い偽コインがある。これを天秤を1回だけ使って見つけるにはどうしたらよいか。」
解答：3つのうち2個を選んで1個ずつを左右に乗せれば、一方が軽ければそれが偽コイン、つり合えば残りの1個が偽コインとわかるわけです。

ここで重要なのは、天秤の状態が「右が軽い」「左が軽い」「つり合う」の3通りしか無いから、天秤を1回だけ使うという条件では、最大3つまでしか判別できないという点です。これを考えれば、4個のうち1つだけ軽い偽コインが含まれるときには、考えうる可能性が4通りあるわけですから、絶対に天秤を使う回数が1回では判別は不可能となるわけです。
これを頭に入れて、問題を複雑にしていきます。

レイトン教授と不思議な町

レイトン教授と不思議な町。Nintendo DS用のソフト。パズルのゲームである（公式サイトへ）。
結構面白いネタもある。この中から、アルゴリズムに関係する問題を少々抜粋して、それに手を加えて遊んでみたいと思っている。

Rserve

行動計量学会岡山地域部会第22回研究会(くわしくはここ)で発表があったが、結構面白かった。気になったのはRServeで、JavaでRを扱うものらしい。気になったので調べてみた。
公式のページはここ。なんか面白そうなので、今年のゼミでやってみましょうか。

再開します

なんとなく、めんどくさくなって放置プレー状態でしたが、ひとまず、１年半ぶりに再開する気になりました。
一応、ここは大学関連のものや統計やアルゴリズムといった関連のものについて書く予定です。その他の内容については、それぞれのブログで公開中で、中断無く続いています。