何回で満点とれる？【ちょまど問題に挑む人々】

Lucky_Cloud@NT-D @Lucky_Cloud1218

@chomado 設問1の答えを変更 1.点数が上がれば次の設問へ 2.点数が下がれば正しい答えに戻して次の設問へ 3.点数が変わらなければ違う答えに変更 を繰り返したら40回以内に…？問題は毎回全く同じです？

na2hiro 💿 93連休終わった @na2hiro

しまった，1〜3で変化したら変化したところだし，変化しなかったら4で確定だから，最悪3*10=30回だな．

ふみ (DJ Monad) @fumieval

6回でできる気がする

ちょまど@ ITエンジニア @chomado

あー！なるほどです！！>RT

ちょまど@ ITエンジニア @chomado

な、なるほど、 回答パターン: 4^10 うまいパターン: 4*10 か！！(((o(*ﾟ▽ﾟ*)o)))>RT

投機的実行《アクセラレーション・ブースト》 @yuba

1111111111 2111111111 3111111111 の3回の試行で1問目はわかる、と。

na2hiro 💿 93連休終わった @na2hiro

最終問題が4だった場合はもう一度必要なので31回でFA

投機的実行《アクセラレーション・ブースト》 @yuba

2問目以降は、"1"が試行済みなので *211111111 *311111111 の2回の試行でわかります。

くりんぺっと @climpet

下限どこだろう

投機的実行《アクセラレーション・ブースト》 @yuba

うん言い切れる。1問目の“4”は試行してないけど、4が正解なら1点上がるって補正するだけで4111111111の点数はわかるから。だから3+2*9で21回の試行で正解は全問わかる。

くりんぺっと @climpet

m択問題がn問与えられ，その正解数だけが分かる場合に，全問正解に必要な試行回数の情報量的下限…になるのかしら

ふみ (DJ Monad) @fumieval

解答は40bitなのに対し、得点は11通りだからおよそ3.46bitなので、理論上は6回で正解するのに十分な情報量が得られる

ふみ (DJ Monad) @fumieval

40bitじゃない20bitだ

くりんぺっと @climpet

1回あたりの情報量は2.706bitっぽい？

くりんぺっと @climpet

理論上8回になるのかしら．具体的な手順は分からないけれど．

くりんぺっと @climpet

ん，これ期待値だっけ

™ @tmaehara

「○回で可能」だけでなく，ちゃんと「○回は必要」も示しましょう．

na2hiro 💿 93連休終わった @na2hiro

確かにうまくやれば複数の選択肢を動かして2つ以上の正解数の変動を観測することで絞れそうだけどぱっとアルゴリズム思いつかん

ゆん🫑🐏有能な怠け者 @myayun_gil

なるほど、 ４択×10問に対して、最適方法での最大試行回数か 全部１を選択して１度回答決定し、 １問ずつ１→２→３→４と変更しながら回答し決定し、得点に変化があればそれが正解となる この場合、正解が全部４の時に最大試行になるので、 １＋３×10＝31が最大試行回数になりそうだね

E_Rubik @E_Rubik

4択10問で正解数わかる場合の探査、1*9,2で10問探査すれば1と2の正解位置わかるから、あとは3,4で同じことすればいけるのでは。というわけで最低20回かな

™ @tmaehara

ちなみに「選んだ解答に対する得点だけがわかる」設定は，まさに圧縮センシングの問題設定なので，Terry Tao に殴られて死ぬ．

na2hiro 💿 93連休終わった @na2hiro

重複ありblowなしHit and blowと言えば話が早い(?)

na2hiro 💿 93連休終わった @na2hiro

東大の田中哲朗先生がHit and blowの最適戦略の論文書いてる dell.tanaka.ecc.u-tokyo.ac.jp/~ktanaka/paper…

くりんぺっと @climpet

正解数(11通り)が一様に出るというわけではないから，1回あたりの情報量は3.46bitではない…はず(?)

くりんぺっと @climpet

1回あたり2.4734bit…になるのかしら…？