■

うにょーん

http://f-layer.hp.infoseek.co.jp/（＠12/15）
それじゃおいらの答えを。思考をなぞる形で。
「ｎ回」の答えになるので要注意。

  1. 類似のオーソドックスな問題で「X個の玉の中にひとつだけ偽物（軽い）がある、ｎ回天秤使ってどれか求めよ」というのがある。この問いの答えは「1/3と1/3を比較して解の範囲を1/3にしていく」というもので既知。
  2. 今回の問題では重いか軽いかわからず情報量が少ないので、この１の問題以下の効率で切り出すことが出来るはずである。
  3. 軽いか重いかわからないなら、最初の一回で全部比べて、異端分子が軽いのか重いのかの情報を与えてしまえば、あとは１の効率で切り出すことが出来るはずである。（軽い可能性のある玉と重い可能性のある玉が混在している場合、実際に行う場合には玉の組み合わせを間違えてアボーンする可能性が上昇するが、原理的には変わらない）
  4. しかし、一回目でその情報を与えてしまわなくても、n-1回で残りを測り切れれば問題ない。この考え方を再帰適用すると（この解法では）等比数列的な解になることがわかる。
  5. しかし、１の解法で出てくるXの最大は１，３，９，２７…となり全て奇数であるため、天秤では余裕を持たせてひとつ少なめに切り出すことしかできない。（この時点でn=3のとき１回目の操作で32-1=8個を切り出すこと確定、残り4個なら測るの楽勝→12個クリア）
  6. ここから先はUnknownなままの残りの玉について考える。二回目以降は重さが既知の玉を使用できるため奇数個切り出すことが可能となり、3n-m個測り出すことができる。（一回目で過半数切り出しているので全部の軽重を一回で出すことが出来るが、4の考え方を適用するため、ここではしない）
  7. 最後に一個Unknownな玉が残っていてもOKなので+1できる。各回で測り出せる玉の数は以下になる
    • 1回目　3(3-1)-1=8
    • 2回目　3(2-1)=3
    • 3回目　3(1-1)=1
    • 最後の残り　1
  8. というわけで、8+3+1+1=13個までなら解けることがわかる。最初の-1がなくなれば14個いけることもわかるので14+1個もクリア。（また、Unknownは最後の一個のみしか残らないので最大数-1個の場合は全ての玉の軽重を測ることが出来ることもわかる）
  9. n個の場合をまとめると以下のようになる。
    • 3n-1+3n-2+...31+30+1(Unknown)-1(最初のロス)
  10. 数列表現にすれば��3x-1(x=1...n)、単純な等比数列になり、答えは以下。n=3は確かに13になる。
    • (3n-1)/2　(ただしn>1)