puzzleup 9.30
Number GameYou are playing a game with your friend. Your friend chooses three distinct numbers from the set (1, 2, 3, 4, 5, 6, 7, 8, 9). You will call four distinct numbers from the same set in each turn, and he will tell you how many of them are among the chosen numbers.
In order to guarantee to find these numbers in all cases, how many turns are needed?
Note: Naming these three numbers after your 4-number calls are finished does not count as a turn
【数字游戏】
你和朋友玩一个游戏。朋友从1-9中选3个不同的数字(你来猜)。你每轮猜4个不同数字，你的朋友将告诉你猜中了几个他选择的数字。
为了确定他到底是选择的哪3个数字，你需要多少轮？
注：你最后指出他的三个数字时，不算一轮。 6轮确保一定猜中。
设某轮猜的4个数为 a、b、c、d
用$f_n(a,b,c,d)$表示 第n轮猜a、b、c、d时猜中的个数。
那么$f_n(a,b,c,d)$=0或3的情况都相当简单，最远的步数在每轮$f_n(a,b,c,d)$=1或2.
以下假设前两轮的$f_n(a,b,c,d)$=1或2
第一轮猜1234，第二轮猜1256，第三轮猜1278，根据第3轮的结果，最多只要再猜3轮就可成功。 本帖最后由 raa 于 2009-10-4 22:47 编辑
是吗？ 下面是我的最多6轮的方案： →{ } 大括号里的是答案（即朋友选中的三个数）：
$f_1(1234)$ $f_2(1256)$
----------------------------------------------------------------------------------------------
=0 =0 →{789}
----------------------------------------------------------------------------------------------
=1 =3 $f_3(1789)$
=0 →{256}
=1 →{156}
----------------------------------------------------------------------------------------------
=3 =1 $f_3(1567)$
=1 →{134}
=0 →{234}
----------------------------------------------------------------------------------------------
=3 =2 $f_3(3567)$
=1 →{123}
=0 →{124}
----------------------------------------------------------------------------------------------
=2 =3 $f_3(5789)$
=1 →{125}
=0 →{126}
----------------------------------------------------------------------------------------------
=0 =2 $f_3(7123)$
=1 →{567}
=0 $f_4(8123)$
=1 →{568}
=0 →{569}
----------------------------------------------------------------------------------------------
=2 =0 $f_3(7125)$
=1 →{347}
=0 $f_4(8125)$
=1 →{348}
=0 →{349}
----------------------------------------------------------------------------------------------
=0 =1 $f_3(5123)$ $f_4(7123)$
=0 =0 →{689}
=1 =0 →{589}
=1 =1 $f_5(8123)$
=1 →{578}
=0 →{579}
=0 =1 $f_5(8123)$
=1 →{678}
=0 →{679}
----------------------------------------------------------------------------------------------
=1 =0 $f_3(3125)$ $f_4(7125)$
=0 =0 →{489}
=1 =0 →{389}
=1 =1 $f_5(8125)$
=1 →{378}
=0 →{379}
=0 =1 $f_5(8125)$
=1 →{478}
=0 →{479}
----------------------------------------------------------------------------------------------
=1 =1 $f_3(1278)$
=0 $f_4(3127)$ $f_5(5127)$
=0 =1 →{459}
=0 =0 →{469}
=1 =1 →{359}
=0 =0 →{369}
=1 $f_4(3129)$ $f_5(5129)$ $f_6(7129)$
=0 =0 =0 →{468}
=0 =0 =1 →{467}
=0 =1 =0 →{458}
=0 =1 =1 →{457}
=1 =0 =0 →{368}
=1 =0 =1 →{367}
=1 =1 =0 →{358}
=1 =1 =1 →{357}
=2 $f_4(1345)$ $f_5(7345)$
=0 =0 →{289}
=0 =1 →{279}
=1 =0 →{189}
=1 =1 →{179}
=3 $f_4(1345)$
=0 →{278}
=1 →{178}
----------------------------------------------------------------------------------------------
=1 =2 $f_3(1278)$
=0 $f_4(3789)$
=0 →{456}
=1 →{356}
=1 $f_4(1347)$ $f_5(5347)$
=0 =0 →{269}
=0 =1 →{259}
=1 =0 →{169}
=1 =1 →{159}
=2 $f_4(1349)$ $f_5(5349)$ $f_6(7349)$
=0 =0 =0 →{268}
=0 =0 =1 →{267}
=0 =1 =0 →{258}
=0 =1 =1 →{257}
=1 =0 =0 →{168}
=1 =0 =1 →{167}
=1 =1 =0 →{158}
=1 =1 =1 →{157}
----------------------------------------------------------------------------------------------
=2 =1 $f_3(1278)$
=0 $f_4(5789)$
=1 → {345}
=0 → {346}
=1 $f_4(1567)$ $f_5(3567)$
=0 =0 →{249}
=0 =1 →{239}
=1 =0 →{149}
=1 =1 →{139}
=2 $f_4(1569)$ $f_5(3569)$ $f_6(7569)$
=0 =0 =0 →{248}
=0 =0 =1 →{247}
=0 =1 =0 →{238}
=0 =1 =1 →{237}
=1 =0 =0 →{148}
=1 =0 =1 →{147}
=1 =1 =0 →{138}
=1 =1 =1 →{137}
----------------------------------------------------------------------------------------------
=2 =2 $f_3(1278)$
=1 $f_4(1789)$ $f_5(3789)$ $f_6(5789)$
=0 =0 =0 →{246}
=0 =0 =1 →{245}
=0 =1 =0 →{236}
=0 =1 =1 →{235}
=1 =0 =0 →{146}
=1 =0 =1 →{145}
=1 =1 =0 →{136}
=1 =1 =1 →{135}
=2 → {129}
=3 $f_4(7345)$
=1 → {127}
=0 → {128} 我的答案是5轮。 题目可以推广：
你和朋友玩一个游戏。朋友从S个不同的数字中选n个不同的数字(你来猜)。你每轮猜k个不同数字，你的朋友将告诉你猜中了几个他选择的数字。
为了能确定他到底选择哪些数字，你至少需要多少轮？
把这个最少的轮数记作g(S,n,k)。
那么g(S,n,1)=S-1
g(9,3,4)就是楼主的题。 你不管前两问结果是啥，第三问都是1278，这显然不够科学，导致了你必须6轮。
比如对于你说的1234和1256都是1的情况，我第三次不是问1278，我问的是3578. 1234和1256都是1的情况一共有18种，你问的是3578，如何根据f(3578)的结果在剩下的2步中区分它们？ f(3578)
=0 469
=1 179 189 279289 369 459 467 468
=2 178 278 359 367 368 457 458
=3 357 358
-------------------------------
f(3578)=1的情况8种，如何在两步中区分它。 这个有点复杂,应该需要借助计算机来解决.