Author |
Topic: 100 people, 100 numbers (Read 6718 times) |
|
brainer
Newbie
Posts: 5
|
 |
100 people, 100 numbers
« on: Mar 23rd, 2007, 3:19pm » |
 Quote  Modify
|
There are 100 prisoners assigned by numbers in 1-100 (not uniquely, many can have the same number).
They can talk one time before they assigned and then don't have any connection.
Each one is requested to guess his number (they can use different strategies). He can see their numbers (but not their guess).
How can they do it so at least one of them guesses correctly his number?
|
| « Last Edit: Mar 25th, 2007, 5:06am by brainer » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: 100 people, 100 numbers
« Reply #1 on: Mar 23rd, 2007, 3:44pm » |
Quote Modify
|
Is there an order in which the people guess? Can the rest of the people hear another person's guess (perhaps answer is no, is that what you mean by cannot connect?)?
|
| « Last Edit: Mar 23rd, 2007, 3:45pm by Aryabhatta » |
IP Logged |
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: 100 people, 100 numbers
« Reply #2 on: Mar 23rd, 2007, 5:02pm » |
Quote Modify
|
Assumption:
Any person's guess cannot be heard by the others
Strategy: Each person guesses his number to be the lowest number that he/she sees being shared by the lowest number (>=2) of other people.
This works in all cases except when
[no two persons share the same number]
[a number is shared by no more than 2 people]
[or the lowest number which is shared is shared by only 2 people]
I cannot figure out a strategy that works for all cases
|
| « Last Edit: Mar 23rd, 2007, 5:26pm by spanchap » |
IP Logged |
|
|
|
Archae
Junior Member
Posts: 111
|
|
Re: 100 people, 100 numbers
« Reply #3 on: Mar 23rd, 2007, 5:14pm » |
Quote Modify
|
I don;t know exactly what is meant when you say the they 'cannot connect to others,' but I am assuming that the other 99 people can hear a certain person's guess.
If that is the case, have the first person guess 1+[the number of people he sees who have been given the number 1]
Then, the second person, if he doesnt not have a 1, guesses 1+[the number of people who have a 2]
And so on.
If everyone has a unique number, the last person will be able to correctly guess his number; and if two or more people have the same number, the second guesser with that number will know his number. (I am assuming our people can pay attention and are intelligent enough to make this strategy work, in which case I believe this strategy will work no matter how the numbers are distributed.)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 people, 100 numbers
« Reply #4 on: Mar 23rd, 2007, 7:54pm » |
Quote Modify
|
If they can hear others guesses, then have the first person guess a number he has seen. Everybody else then guesses the exact same number. Whoever has it is then guaranteed.
Since that strategy is trivial, I assume that brainer intends that no one can hear the guesses of anyone else.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
brainer
Newbie
Posts: 5
|
|
Re: 100 people, 100 numbers
« Reply #5 on: Mar 25th, 2007, 2:30am » |
Quote Modify
|
The people CANNOT hear other ones guess of course... other wise this is trivial...
|
|
IP Logged |
|
|
|
brainer
Newbie
Posts: 5
|
|
Re: 100 people, 100 numbers
« Reply #6 on: Mar 25th, 2007, 2:32am » |
Quote Modify
|
There is no order on the guesses
|
|
IP Logged |
|
|
|
brainer
Newbie
Posts: 5
|
|
Re: 100 people, 100 numbers
« Reply #7 on: Mar 25th, 2007, 2:35am » |
Quote Modify
|
Note that the strategy should not be the same for all people! (but should be decided in advanced)
|
|
IP Logged |
|
|
|
brainer
Newbie
Posts: 5
|
|
Re: 100 people, 100 numbers
« Reply #8 on: Mar 25th, 2007, 2:38am » |
Quote Modify
|
on Mar 23rd, 2007, 5:02pm, spanchap wrote:Assumption:
Any person's guess cannot be heard by the others
Strategy: Each person guesses his number to be the lowest number that he/she sees being shared by the lowest number (>=2) of other people.
This works in all cases except when
[no two persons share the same number]
[a number is shared by no more than 2 people]
[or the lowest number which is shared is shared by only 2 people]
I cannot figure out a strategy that works for all cases
|
|
Suresh, this was my first answer too. As you said, it does not work for all cases...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 100 people, 100 numbers
« Reply #9 on: Mar 25th, 2007, 3:48am » |
Quote Modify
|
Indeed, the strategy cannot possibly be symmetric:
Any given prisoner (let's call them prisoners) can see 10099 possible numberings; for each of those there are 100 possibilities for his own hat (prisoners are always wearing hats), but only one will agree with the number his strategy tells him to say. So each prisoner, whatever his strategy, will be correct for exactly 1/100 of the 100100 configurations. Since there are 100 prisoners, and for each configuration, at least one needs to be correct, it follows that there must be exactly one correct answer for each configuration.
But if the strategy was symmetric, then given all 1's, say, they'll either be all right or all wrong.
The above is actually a pretty strong hint towards the answer. For another hint, try to generalize the solution for 2 prisoners: prisoner 1 assumes the hats are different, and prisoner 2 assumes they're the same; exactly one will always be right.
| hidden: | In advance, label the prisoners 1,2,...,n. For each possible assignment A, consider the sum S(A) of all the numbers in this assignment. There will be a unique prisoner k such that S(A) = k mod n.
So have prisoner k assume that S(A)=k mod n. Then whatever n-1 numbers he sees will uniquely determine his own assigned number. That is, he should guess the number which, when added to all the numbers he can see, will result in a sum which is k mod n.
Then for any assignment A, prisoner k will be (the only one) correct, where k = S(A) mod n. |
There are, I guess, 100! * 40100 strategies much like this one. Are there any others?
|
| « Last Edit: Mar 25th, 2007, 3:54am by Eigenray » |
IP Logged |
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: 100 people, 100 numbers
« Reply #10 on: Mar 25th, 2007, 9:54am » |
Quote Modify
|
on Mar 25th, 2007, 3:48am, Eigenray wrote:
| hidden: | In advance, label the prisoners 1,2,...,n. For each possible assignment A, consider the sum S(A) of all the numbers in this assignment. There will be a unique prisoner k such that S(A) = k mod n.
So have prisoner k assume that S(A)=k mod n. Then whatever n-1 numbers he sees will uniquely determine his own assigned number. That is, he should guess the number which, when added to all the numbers he can see, will result in a sum which is k mod n.
Then for any assignment A, prisoner k will be (the only one) correct, where k = S(A) mod n. |
There are, I guess, 100! * 40100 strategies much like this one. Are there any others? |
|
Can you please elaborate? Is the mod function you are using the standard mod function: "A mod B is the remainder when A is divided by B". If yes, how can k mod n be equal to S(A) which is greater than k.
Assuming that I have understood you wrongly (very likely) and the strategy you suggest works, can you please show how your strategy would result in at least one prisoner guessing his/her number correctly when none of the prisoners share a common number.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 people, 100 numbers
« Reply #11 on: Mar 25th, 2007, 10:01am » |
Quote Modify
|
on Mar 25th, 2007, 9:54am, spanchap wrote:| Can you please elaborate? Is the mod function you are using the standard mod function |
|
'mod' as used there is not a function, but a modifier on the equality (or rather equivalence/congruence*) relation.
a = b mod n
can be read as
mod(a,n) = mod(b,n)
It is also often written as a = b (mod n), with the 'mod n' between parenthesis. See e.g. http://mathworld.wolfram.com/Congruence.html
(* if you look at the mathworld page, you'll see  is used rather than =. But in plain text it's easier to use the latter and hope people correctly interpret what you mean.)
|
| « Last Edit: Mar 25th, 2007, 10:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: 100 people, 100 numbers
« Reply #12 on: Mar 25th, 2007, 10:37am » |
Quote Modify
|
Thanks towr. Now that I understand the terminology used, (I think) I am not sure Eigenray's solution works, at least not when none of the prisoners share a common number.
|
| « Last Edit: Mar 25th, 2007, 10:44am by spanchap » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 100 people, 100 numbers
« Reply #13 on: Mar 25th, 2007, 1:29pm » |
Quote Modify
|
Yes, what I meant is "modulo n, S(A) is the same as k." This means that the integers S(A) and k are congruent, or, that the equivalence classes of S(A) and k are equal.
For example, suppose the numbers assigned are 1,2,...,100, in that order.
Prisoner 17, for example, will see a sum of 5050-17 33 mod 100. Since he assumes the total sum is 17 mod 100, he will guess 84. But prisoner 50 will see 5000; since he assumes (correctly) that the sum is 50 mod 100, he will guess 50.
In fact, if the numbers are all distinct, then prisoner 50 will always be right.
|
|
IP Logged |
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: 100 people, 100 numbers
« Reply #14 on: Mar 25th, 2007, 1:57pm » |
Quote Modify
|
on Mar 25th, 2007, 1:29pm, Eigenray wrote:Yes, what I meant is "modulo n, S(A) is the same as k." This means that the integers S(A) and k are congruent, or, that the equivalence classes of S(A) and k are equal.
For example, suppose the numbers assigned are 1,2,...,100, in that order.
Prisoner 17, for example, will see a sum of 5050-17 33 mod 100. Since he assumes the total sum is 17 mod 100, he will guess 84. But prisoner 50 will see 5000; since he assumes (correctly) that the sum is 50 mod 100, he will guess 50.
In fact, if the numbers are all distinct, then prisoner 50 will always be right. |
|
I think I might have misunderstodd your strategy.
Is the prisoners' k value assigned in advance when the prisoners initially confer? If yes, since the prisoner assignment happens in advance, (k is assigned in advance), why should prisoner 17 see 5050-17. He might be assigned 51 by the warden and sees a sum of 4999. Therefore he guesses 18 to get 5017 where 5017 mod 100 = k mod 100 = 17.
I think I am missing a key point you are making
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 people, 100 numbers
« Reply #15 on: Mar 25th, 2007, 2:08pm » |
Quote Modify
|
I'm sure Eigenray will be right along with a full reply, but in this case, the point you are missing is the phrase "For example". Eigenray is merely giving a counter-argument showing that it is quite possible for his strategy to cover the case where everyone has a distinct number.
Of course, he ends with the claim that it always works, and by adjusting the reasoning in his given example, you can prove it for all possible cases.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 100 people, 100 numbers
« Reply #16 on: Mar 25th, 2007, 3:19pm » |
Quote Modify
|
This is a bit confusing since the prisoners are, in advance, given labels (names) 1,...,n. Then they are also assigned numbers (hats) by the warden in the same range (it's times like these upper and lower case numbers would be useful).
Suppose (as in the situation you asked about) the prisoners are given distinct hats, that is, 1,2,...,100 each exactly once. Then prisoner named 50 (and only prisoner 50) will guess correctly.
The specific example I gave was when prisoner k was also given hat k. But suppose more generally that prisoner 50 is given hat X. If the hats are all distinct, he will see a sum of 5050-X. Since he's assuming the sum is 50 mod 100, he must guess X, since that's the only number in the range 1,...,100 which is congruent to X mod 100.
In short: each prisoner labelled k assumes the sum of the hats will be congruent to k modulo N. This uniquely determines his guess, and exactly one of them will be correct.
This generalizes the case N=2: prisoner 1 assumes the sum is 1, i.e., they're different; and prisoner 2 assumes the sum is 2, i.e., they're the same.
|
|
IP Logged |
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: 100 people, 100 numbers
« Reply #17 on: Mar 25th, 2007, 5:25pm » |
Quote Modify
|
on Mar 25th, 2007, 3:19pm, Eigenray wrote:In short: each prisoner labelled k assumes the sum of the hats will be congruent to k modulo N. This uniquely determines his guess, and exactly one of them will be correct.
|
|
Very nice and very neat. Your solution (now that I understand it) is extremely elegant.
|
| « Last Edit: Mar 25th, 2007, 5:55pm by spanchap » |
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: 100 people, 100 numbers
« Reply #18 on: Jul 11th, 2007, 1:36pm » |
Quote Modify
|
I don't think it's the case that exactly one prisoner must be correct. For instance, each could agree to play Eigenray's strategy except when viewing 99 identical numbers - then when all numbers are the same every prisoner will guess correctly.
Nevertheless can you prove that there is no solution among symmetric strategies?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 people, 100 numbers
« Reply #19 on: Jul 11th, 2007, 3:31pm » |
Quote Modify
|
Suppose there are 99 zeros and 1 one. Prisoner with number 1 was assigned number 1 ... in your strategy he guesses 0 instead of Eigenrays 1. Other prisoners use Eigenrays strategy so no other prisoner guesses 0. ... Noone guesses correctly!
(Oh, of course 0 means 100, but the counting is easier with 0.)
I have tought about the problem a litlle bit ... any function from n^n->n which gives all n values when you fix arbitrary n-1 coordinates can be used instead of sum mod n. k-th prisoner chooses his coordinate such that the function gives value k ...
this guaranties exactly one prisoner guesses correctly. It seems to me every solution can be described this way, otherwise you cannot guarantee "synchronised answers" ... no more, no less than one prisoner guesses correctly.
(Probably Eigenray told the same in previous posts? ... how many such functions ("latin hypercubes") are there?)
|
| « Last Edit: Jul 12th, 2007, 3:29pm by Hippo » |
IP Logged |
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: 100 people, 100 numbers
« Reply #20 on: Jul 13th, 2007, 2:02am » |
Quote Modify
|
i think hippo is absolutely right..
so is there any other solution to this fantastic problem
|
|
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: 100 people, 100 numbers
« Reply #21 on: Sep 4th, 2007, 8:26pm » |
Quote Modify
|
Each time one of them guesses, they wink at another person and choose 1 more than their number(if it's the highest number, they choose the lowest number). That person when guessing guesses correctly(and doesn't wink at a person). At least half of them will guess right.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: 100 people, 100 numbers
« Reply #22 on: Sep 4th, 2007, 9:05pm » |
Quote Modify
|
on Sep 4th, 2007, 8:26pm, srn347 wrote:| they wink at another person |
|
They have NO CONNECTION. For the love of god, at least read the riddle before you post.
|
|
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: 100 people, 100 numbers
« Reply #23 on: Sep 6th, 2007, 4:26pm » |
Quote Modify
|
They get in pairs and each person says the other ones number. Then they all guess correctly.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: 100 people, 100 numbers
« Reply #24 on: Sep 6th, 2007, 9:59pm » |
Quote Modify
|
on Sep 6th, 2007, 4:26pm, srn347 wrote:| They get in pairs and each person says the other ones number. Then they all guess correctly. |
|
You still haven't read it, have you?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print