GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 18

Question

Bob writes down a number between 1 and 1,000. Mary must identify that number by asking "yes/no" questions of Bob. Mary knows that Bob always tells the truth. If Mary uses an optimal strategy then she will determine that answer at the end of exactly how many questions on the worst case?

• A. 999
• B. 500
• C. 32
• D. 10

Answer 1

We can use binary Search by always asking the middle number..

Answer 2

Though in Question it is not Clearly said that whether Mary asks to Bob that chosen number is lesser or greater (which was written by Bob)
But in question it is clearly said that Mary uses optimal strategy, Mary would have done like below mention approach:

(Mary chooses a number and asks to Bob whether is it right number, if Bob answers YES or NO.(assume Bob answers NO for worst case condition) Then again Mary asks to Bob whether is it greater?, Bob can answer YES or NO. If Bob says YES then Mary divides the Chosen number by 2 else multiply by 2 something like this....in recursive way)

Hence it is like Binary Search Algorithm and Mary asks two questions in each step:
In worst Case total question asked by Mary = 2 x log₂(1000) ≈ 20

But in Option Answer is given assuming Mary asks questions only one time in Each Step...!

Comments

yes @Kamlesh Maurya my thinking is same 

I think Mary asking questions like this to complete 1000 numbers to get that exact one between 1 to 1000.

There are only 2 possibilities to answer (YES/NO)

So the optimal approach here is =>

2^ no of question asked to determine the exact number

2^1= 2 

2^2= 4

2^3=8

.

.

.2^10 =1024 

so answer= 10

---

@Priyotosh2001

You mean Mary starts from 2 and starts asking whether is it right number?( If Bob says yes then it is best case) Hence Bob says No then Mary asks for 2^2 ...if again Bob says No then Mary asks for 2^3 and so on .... Till 2^10.

But suppose Bob was written number 663. Now suppose Mary at 9th step and asks for 2^9 and Bob says No the again Mary will ask for 2^10(>1000) Bob will say No, Mary failed here.....

That's why I have said Mary would ask for two questions in each step: (1) whether it was correct number that she had chosen and (2) whether is it greater or less from the number she has chosen.

So according to this she starts from choosing number 1000 (suppose Bob was written the number 663) and asks to Bob, Bob says No then again Mary asks second question whether is it greater Bob will say YES and Mary will do 1000/2(=500). Now in next step Mary will ask to Bob whether 500 is correct Bob will say No and again she ask question whether is it greater Bob will say No then Mary will do 500 + 500/2(=750) so like this.... It is same as binary search.

Since in question it is asked for number of questions Mary asks, and now it is clear that Mary asks 2 questions in each step and in worst case there will be 10 steps hence total number of questions asked by Mary would be 20