My guess : 2^x / (1+x) >= 100, x + 1 = 12

来源: ettubrute 于 2008-06-11 21:29:01 [] [旧帖] [给我悄悄话] 阅读数 : (1426 bytes)
本帖于 2008-06-12 08:11:50 时间, 由普通用户 康MM 编辑

This is the way I think.

Formulate all questions that ask for sets of specific numbers. For example, "Is the number 1,4,8 ... or 94?"
Let x be the minimum number of guesses required.
Construct a chart of 100 * x.

1 2 3 4 5 ... 100
1 Y N N Y N Y
2
.
.
.
x

Columns represent the possible value of the unknown number. Rows represent the question number.
The chart indicates the possible value of the unknown number asked in each question. Y means that the column number is asked as a possible value. N means that the column number is not. For example, if the first row only has V under 1, 4, and 100, the question is "Is the number 1, 4, or 100?"

If Alice is not allowed to lie, a number can be a possible value in case the answers to all questions match the chart. The value can be determined if only one number is a possible value.

Since Alice may lie, a number is possible if less or one answer to the questions does not match the chart. Therefore, x + 1 combinations of answers allow a number to be possible. Since there are 100 possible values, at least 100*(x+1) different combination is needed.

2^x >= 100*(x+1)
x >= 11

One last guess is needed to declare the unknown value.


I am not sure whether a combination of 11 questions can be formulated so that the answers under any two numbers have at least two differences.

所有跟帖： 

• 很好的分析 -dynamic- ♂ 给 dynamic 发送悄悄话 (783 bytes) () 06/12/2008 postreply 11:19:14

• 回复：很好的分析 -HF:- ♀ 给 HF: 发送悄悄话 (745 bytes) () 06/12/2008 postreply 12:16:22

• brilliant answer... however that question is not allowed -dynamic- ♂ 给 dynamic 发送悄悄话 (154 bytes) () 06/12/2008 postreply 13:08:34

• 回复：brilliant answer... however that question is not allowed -HF:- ♀ 给 HF: 发送悄悄话 (475 bytes) () 06/12/2008 postreply 13:24:54

• Does this mean that 9 guesses is enough? -ettubrute- ♂ 给 ettubrute 发送悄悄话 (136 bytes) () 06/12/2008 postreply 13:07:32

• why do you think so? -dynamic- ♂ 给 dynamic 发送悄悄话 (348 bytes) () 06/12/2008 postreply 13:13:20

• I just realize my mistake -ettubrute- ♂ 给 ettubrute 发送悄悄话 (0 bytes) () 06/12/2008 postreply 13:17:03

• 回复：很好的分析 -HF:- ♀ 给 HF: 发送悄悄话 (461 bytes) () 06/12/2008 postreply 14:15:52

• for N=100, 10 questions to ask -HF:- ♀ 给 HF: 发送悄悄话 (834 bytes) () 06/12/2008 postreply 20:13:24

• I think that there is a mistake at the eighth guess -ettubrute- ♂ 给 ettubrute 发送悄悄话 (284 bytes) () 06/12/2008 postreply 20:36:40

请您先登陆，再发跟帖！