puzzleup 9.30

geslon

Number Game


You 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个数字，你需要多少轮？
注：你最后指出他的三个数字时，不算一轮。

056254628

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

是吗？

056254628

下面是我的最多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}

geslon

我的答案是5轮。

056254628

题目可以推广：
你和朋友玩一个游戏。朋友从S个不同的数字中选n个不同的数字(你来猜)。你每轮猜k个不同数字，你的朋友将告诉你猜中了几个他选择的数字。
为了能确定他到底选择哪些数字，你至少需要多少轮？
把这个最少的轮数记作  g(S,n,k)。
那么g(S,n,1)=S-1
       g(9,3,4)就是楼主的题。

geslon

你不管前两问结果是啥，第三问都是1278，这显然不够科学，导致了你必须6轮。

比如对于你说的1234和1256都是1的情况，我第三次不是问1278，我问的是3578.

056254628

1234和1256都是1的情况一共有18种，你问的是3578，如何根据f(3578)的结果在剩下的2步中区分它们？

056254628

f(3578)
=0         469
=1        179    189    279  289   369   459   467   468
=2        178   278   359   367   368   457   458
=3        357   358
-------------------------------
f(3578)=1的情况8种，如何在两步中区分它。

mathe

这个有点复杂,应该需要借助计算机来解决.