[wolfgang]

A prisoner must cross three locked gates inorder to escape the jail.With him there is a man having 9 keys,these keys have numbers,1 to 9.Only three keys are the right ones(if a wrong key is used to any gate,it will stuck).

The man with keys always tells the truth,and he knows which key fit to each gate.

What is the best strategy to escape through all three gates,if he is allowed to ask only(yes or no)questions.

The minimum question number is better.

[Guest]

fastest i could come up with.

gate 1:

ask if the right key is either 1 or higher than 1 till 5, if not you know it will be 6 till 9, so i will deduct both solutions..

1-5:

ask for lower or equal to 3

if its lower, than ask for 2 or lower.

you now have the key

if its higher, ask for 4

you now have the key

6-9

ask if its 7 or 6

if yes, ask 6

you now have the key

if no, ask 8

you now have the key

gate 2:

you now have one less key which is vital, you now only have to do this:

ask if its one of the first 4 numbers that are left.

if its true, than ask for the first 2 and after that, pick 1 of the 2 that are left over.

you now have the key

you can do the exact same thing with the last 4 numbers.

you now have the key

gate 3:

you now have 7 keys left.

ask for the first 4 numbers that are left.

do the same as you did at gate 2.

you now have the key

at the last 3 numbers, you ask for 2 or 1. if its 3, you have the key, if not, ask for 2

you now have the keys

so in about 7-9 questions ^^

[plainglazed]

there are 9C3 or 84 combinations of keys, each of which has 6 permutations so 504 total permutations. Would think you can optimally eliminate with certainty half of those possible with each yes or no question so 504->252, 252->126, 126->63, 63->32, 32->16, 16->8, 6->4, 4->2, 2->1. so 9 questions total???

[wolfgang]

fastest i could come up with.

gate 1:

ask if the right key is either 1 or higher than 1 till 5, if not you know it will be 6 till 9, so i will deduct both solutions..

1-5:

ask for lower or equal to 3

if its lower, than ask for 2 or lower.

you now have the key

if its higher, ask for 4

you now have the key

6-9

ask if its 7 or 6

if yes, ask 6

you now have the key

if no, ask 8

you now have the key

gate 2:

you now have one less key which is vital, you now only have to do this:

ask if its one of the first 4 numbers that are left.

if its true, than ask for the first 2 and after that, pick 1 of the 2 that are left over.

you now have the key

you can do the exact same thing with the last 4 numbers.

you now have the key

gate 3:

you now have 7 keys left.

ask for the first 4 numbers that are left.

do the same as you did at gate 2.

you now have the key

at the last 3 numbers, you ask for 2 or 1. if its 3, you have the key, if not, ask for 2

you now have the keys

so in about 7-9 questions ^^

Welcome to Brain den Dear UNfire....please try to use the spoiler next time...thank you

[Guest]

Taking the longest possible path you are descibing

1. Bottom 5 ( else top 4, assume bottom 5)

2. Bottom 3 (else top 2, assume bottom 3)

3. Bottom 2 (else top 1, assume bottom 2)

4. Ask 1, you pass first gate

Second Gate (8 keys left)

5. Bottom 4 (else top 4, assume bottom 4 but it doesnt matter)

6. Bottom 2 (else top 2, again it doesnt matter)

7. ask 1 (you pass gate 2)

Third Gate (7 keys left)

8. Bottom 4 (else top 3, assume bottom 4)

9. Bottom 2 (else other, assume bottom 2)

10. ask 1, you escaped

That's between 3 and 10 questions needed

so in about 7-9 questions ^^

Edited December 27, 2010 by csv

[phaze]

I'd be very impressed if you can solve in in 8 questions or less.

The first door could be any of 9 keys (9 different possibilities)

The second door could be any of the 8 remaining positions in addition to this (9 * 8 = 72 possibilities for two doors)

The third door could be any of 7 remaining positions in addition to this (9 * 8 *7 = 504 possibilities)

You can only ask yes/no questions. Each question eliminates 50% of the possibilities (at best). As 2^9 = 512 it will only be after 9 questions (for 8 arrangements possibly 8) that you will be able to determine which keys fit which gates.

[Guest]

Couldn't we apply binary search here?

first gate: 4 questions second gate: 3 questions third gate: 3 questions total 10 questions

However, we can ask qualifying questions in the beginning to reduce this number. Assumption here is a key can open exactly one gate and vice versa.

[Guest]

Dudes...things are way simpler that you think

Think logicaly to what happens if you just make this question every single time:

Does this key open any gate?If not, throw it

If yes, ask which one

in this very simple method you will have to ask at MAXIMUM of :

9 keyquestions + 3 WhichOpenquestions (bcouse three keys open gates) - 1 WhichOpenquestion(becouse the third time you take a yes answer, it will unlock the remaining door) - 1 keyquestions(about the last key, becouse if you have already found the other 3, it is obvious it doesn't open any gate.If not, it is obvious it is the last one.) = 9 + 3 - 1 -1 = 10 answers.

Easy to think, easy to remember, easy to do.And if you are very lucky, the minimum amount of questions is 5 becouse if we suppose the first three keys you grab, are the ones that open the three gates:

3 WhichOpenquestion + 3 keyquestions - 1 WhichOpenquestion = 3 + 3 - 1 = 5

Answer: 5 - 10

Edited December 30, 2010 by Tsopi

[dark_magician_92]

Divide the keys in 3 sets:-

set 1 having key 1,2,3 and 4

set 2 having key 5,6,7 and 8

set 3 having key 9

Case 1:- let the correct keys be 1,2 and 3

Q1. is there any set with all the 3 keys?

A1.Yes

Q2. Is the 1st set having the 3 keys?

A2. Yes

Q3.Are keys 1,2and 4 all correct ones?

A3. No

Q4.Are keys 1,3 and 4 correct?

A4.No

Q5. Are keys 2,3 and 4 correct?

A5.No

so we know 1,2 and 3 are correct

Case 2:- 4,1 and 9

Q1.any set with 3 keys?

A1. No

Q2.is 3rd set one of the right key?

A2.Yes

Q3.Is 1st set having 2 keys correct?

A3.Yes

Q4.Is 1,2 and 3 having both correct keys?

A4.No (that means 4 is correct one)

Q.5 Is 2,3 and having a correct one?

A5.Yes

Q.6 is 2 correct?

we got the keys

Next case:- 1,2 and 5

Q1.any set with 3 keys?

A1. No

Q2.is 3rd set one of the right key?

A2.no

Q3.Is 1st set having 2 keys correct?

A3.Yes

Q4.Is 1,2 and 3 having two correct keys?

A4.Yes (that means 4 is not correct one)

Q.5 Is 1,2 correct?

Q6.Is is 2,3 correct

similarly 2 more questions for 5,6,7and 8

so i guess 8 questions in worst possible case.

A prisoner must cross three locked gates inorder to escape the jail.With him there is a man having 9 keys,these keys have numbers,1 to 9.Only three keys are the right ones(if a wrong key is used to any gate,it will stuck).

The man with keys always tells the truth,and he knows which key fit to each gate.

What is the best strategy to escape through all three gates,if he is allowed to ask only(yes or no)questions.

The minimum question number is better.

[wolfgang]

Divide the keys in 3 sets:-

set 1 having key 1,2,3 and 4

set 2 having key 5,6,7 and 8

set 3 having key 9

Case 1:- let the correct keys be 1,2 and 3

Q1. is there any set with all the 3 keys?

A1.Yes

Q2. Is the 1st set having the 3 keys?

A2. Yes

Q3.Are keys 1,2and 4 all correct ones?

A3. No

Q4.Are keys 1,3 and 4 correct?

A4.No

Q5. Are keys 2,3 and 4 correct?

A5.No

so we know 1,2 and 3 are correct

Case 2:- 4,1 and 9

Q1.any set with 3 keys?

A1. No

Q2.is 3rd set one of the right key?

A2.Yes

Q3.Is 1st set having 2 keys correct?

A3.Yes

Q4.Is 1,2 and 3 having both correct keys?

A4.No (that means 4 is correct one)

Q.5 Is 2,3 and having a correct one?

A5.Yes

Q.6 is 2 correct?

we got the keys

Next case:- 1,2 and 5

Q1.any set with 3 keys?

A1. No

Q2.is 3rd set one of the right key?

A2.no

Q3.Is 1st set having 2 keys correct?

A3.Yes

Q4.Is 1,2 and 3 having two correct keys?

A4.Yes (that means 4 is not correct one)

Q.5 Is 1,2 correct?

Q6.Is is 2,3 correct

similarly 2 more questions for 5,6,7and 8

so i guess 8 questions in worst possible case.

Knowing the three keys is only the first step,you should know which key fits to each gate also....

[Guest]

Uh, but no offense, couldn't you just do this?

Ask him if this key opens a gate. If no throw away, if yes keep it. Keep on asking it, then ask does it open this one. blah blah blah yeah you get the point. My way will get you the least of 6-12 i think