Author |
Topic: Number Game (Read 618 times) |
|
R
Senior Riddler
Addicted!!!
Gender: 
Posts: 502
|
 |
Number Game
« on: Mar 18th, 2010, 10:19pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Number Game
« Reply #1 on: Mar 19th, 2010, 3:18am » |
Quote Modify
|
9 is enough:
Arrange the numbers 1-9 in a circle and ask every set of 4 consecutive numbers. 2 such sets give you how many numbers are chosen in any set of 8 consecutive numbers, which is enough to tell whether the remaining number is chosen or not.
8 is also enough:
because the sum of the 9 answers above is always 12. So you can skip the last question.
But this can probably be improved.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number Game
« Reply #2 on: Mar 19th, 2010, 4:05am » |
Quote Modify
|
You need at least 4 turns (probably more), because there are 84 sets of 3 numbers (so about 6.4 bits of uncertainty), and on average you get at most two bits of information each turn (because there are 4 possible answers).
A computer should be able to make short work of the problem. There's only 84 options you need to choose between and 126 'questions' you can ask. A decision tree algorithm should do reasonably well.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number Game
« Reply #3 on: Mar 19th, 2010, 8:33am » |
Quote Modify
|
You don't need more than 7
After the first turn, WLOG you know how many are in the first 4.
If it's 0, then you don't need more than 4 turns to find them among the other five (just use the same approach as Grimbal used) This totals 5 turns.
If it's 1, then you can find that 1 in two turns (by using binary search), and find the other two in 4 turns as above. This totals to 7.
If it's 2, then in 3 turns you can find those two, and in a further three turns you can find the other one with binary search. This also totals 7.
If it's 3, then you can find out which isn't in two further turn using binary search. So that totals 3 turns.
So at most, we use 7 turns. But it might still be improved on.
|
| « Last Edit: Mar 19th, 2010, 8:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Number Game
« Reply #4 on: Mar 19th, 2010, 8:53am » |
Quote Modify
|
The binary search is not as obvious as it seems.
I was about to say it is not obvious how to separate the binary search of 1 among 4 and the search of 2 among 5, because you have to call 4 numbers. So you step on the other side, interfering in the count.
But then I found the way.
You can call 1256 and 3456. This will tell you if the one in 1234 is in 12 or 34 and simultaneously give you the count in 56. Then you know enough to complete both sides independently.
PS: A simpler proof for 7 as a maximum:
By calling 1234, 1256, 3456, you can deduce the count in 12, 34, 56 and 789.
One of them in 0. The 3 other groups you can identify in maximum 1+1+2 turns. Having 2 digits excluded makes it easy.
|
| « Last Edit: Mar 19th, 2010, 9:03am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print