.@neubigさんのクイズに挑む人達

Graham Neubig @neubig

貴重なワインの瓶27本を持っていて、その内1本は毒で汚染されている。特殊な紙切れ3枚も持っていて、毒に触れた紙切れは1日で完全に溶けてしまう。ワインの出荷まで後2日間。この紙切れ3枚を使って、毒の入っている瓶を特定せよ。 (ここから： http://bit.ly/qcKetj)

Graham Neubig @neubig

@ta_makino さすがにマーケティングの人たちがかわいそうだったので意訳しておきましたw

しましま @shima__shima

.@neubig 紙1枚の情報量は1ビット，それに対して不確実性は log2(27) だから 2^(log(27)-3)=3.375 だから3〜4個ににしか絞り込めないような気が… それとも，言葉の問題？

machinaga @machy

できた！ RT @neubig: 貴重なワインの瓶27本を持っていて、その内1本は毒で汚染されている。特殊な紙切れ3枚も持っていて、毒に触れた紙切れは1日で完全に溶けてしまう。ワインの出荷まで後2日間。この紙切れ3枚を使って、毒の入っている瓶を特定せよ。

Yoh Okuno @yoh_okuno

@shima__shima 溶けなかった紙は再利用できるということですかね？

しましま @shima__shima

.@nokuno なるほど，それは考えてませんでした．でも，1度目で1枚ぐらいは溶けるので，それでも4ビット．log2(27)-4でもまだ0.75ビットほど残ってるので，これをどうやって乗り越えるかですね

Hiroshi Manabe @takeda25

.@shima__shima 二日間あるというのがポイントですよー（ワイン問題）

shnya_m @shnya_m

@machy お、俺も解けた。“@machy: できた！ RT @neubig: 貴重なワインの瓶27本を持っていて、その内1本は毒で汚染されている。特殊な紙切れ3枚も持っていて、毒に触れた紙切れは1日で完全に溶けてしまう。ワインの出荷まで後2日間。この紙切れ3枚を使って、毒の入

しましま @shima__shima

.@takeda25 最初に3枚，一枚失って2回目は2枚で合わせて5ビットとかいう感じの戦略なわけですね

Hiroshi Manabe @takeda25

@shima__shima 情報をフル活用する必要があります。でもそのおかげで、逆算して考えると考えやすいように思います。

Yoh Okuno @yoh_okuno

@shnya_m @machy @neubig 私も解けましたー，ベタに8+4*3+2*3+1=27とか計算しましたが，一般化できますかね？

Hiroshi Manabe @takeda25

二枚で二日なら五本だけか

Hiroshi Manabe @takeda25

あ、違うか

Yoh Okuno @yoh_okuno

@takeda25 9本ですね～

Hiroshi Manabe @takeda25

@nokuno そうでした～

Yoh Okuno @yoh_okuno

日数が無限大だった場合は収束するのかな

Yoh Okuno @yoh_okuno

収束しないじゃん！(遅

machinaga @machy

紙がm枚、日にちがd日あるときf(m,d)本だとすると、f(m,1)=m+1, f(1,d)=d, f(n,d)=Σ[i=0..n]Comb(n,i)*f(i,d-1) でメモ化DPで解けそうだけど、一般式は立つのかな・・・

Hiroshi Manabe @takeda25

4枚で2日だと、65本？ なんか不規則で半端だなぁ

Hiroshi Manabe @takeda25

@machy f(m, 1) は 2^m ですよね。

Yoh Okuno @yoh_okuno

@machy f(m,1)は2^mでは？

machinaga @machy

すみません。間違えました・・・

Ryohei Sasano @cacaho

@takeda25 81では？たぶんn > 1 の一般項は ∑_i nCi×2^i = 3^n とかな気がします

shnya_m @shnya_m

@nokuno @machy ちょっと考えましたがk日間というのが一般化式作りにくそうとか思ってうまくまとまらなかった・・・。漸化式は作れそうですね。

shnya_m @shnya_m

@nokuno @machy と思ったらmachyさんがもう書いてた。後は任せました・・・ぐふ・・・。