wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 100 people, 100 numbers
        
(Message started by: brainer on Mar 23^rd, 2007, 3:19pm)

Title: 100 people, 100 numbers
Post by brainer on Mar 23^rd, 2007, 3:19pm

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?

Title: Re: 100 people, 100 numbers
Post by Aryabhatta on Mar 23^rd, 2007, 3:44pm

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?)?

Title: Re: 100 people, 100 numbers
Post by spanchap on Mar 23^rd, 2007, 5:02pm

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

Title: Re: 100 people, 100 numbers
Post by Archae on Mar 23^rd, 2007, 5:14pm

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.)

Title: Re: 100 people, 100 numbers
Post by Icarus on Mar 23^rd, 2007, 7:54pm

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.

Title: Re: 100 people, 100 numbers
Post by brainer on Mar 25^th, 2007, 2:30am

The people CANNOT hear other ones guess of course... other wise this is trivial...

Title: Re: 100 people, 100 numbers
Post by brainer on Mar 25^th, 2007, 2:32am

There is no order on the guesses

Title: Re: 100 people, 100 numbers
Post by brainer on Mar 25^th, 2007, 2:35am

Note that the strategy should not be the same for all people! (but should be decided in advanced)

Title: Re: 100 people, 100 numbers
Post by brainer on Mar 25^th, 2007, 2:38am

on 03/23/07 at 17:02:20, spanchap wrote:

Suresh, this was my first answer too. As you said, it does not work for all cases...

Title: Re: 100 people, 100 numbers
Post by Eigenray on Mar 25^th, 2007, 3:48am

Indeed, the strategy cannot possibly be symmetric:

Any given prisoner (let's call them prisoners) can see 100⁹⁹ 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 100¹⁰⁰ 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: [hide]prisoner 1 assumes the hats are different, and prisoner 2 assumes they're the same; exactly one will always be right[/hide].

[hideb]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.[/hideb]
There are, I guess, 100! * 40¹⁰⁰ strategies much like this one. Are there any others?

Title: Re: 100 people, 100 numbers
Post by spanchap on Mar 25^th, 2007, 9:54am

on 03/25/07 at 03:48:42, Eigenray wrote:

[hideb]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.[/hideb]
There are, I guess, 100! * 40¹⁰⁰ 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.

Title: Re: 100 people, 100 numbers
Post by towr on Mar 25^th, 2007, 10:01am

on 03/25/07 at 09:54:05, 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif is used rather than =. But in plain text it's easier to use the latter and hope people correctly interpret what you mean.)

Title: Re: 100 people, 100 numbers
Post by spanchap on Mar 25^th, 2007, 10:37am

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.

Title: Re: 100 people, 100 numbers
Post by Eigenray on Mar 25^th, 2007, 1:29pm

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 [hide]a sum of 5050-17 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 33 mod 100. Since he assumes the total sum is 17 mod 100, [/hide] he will guess 84. But prisoner 50 will see [hide]5000; since he assumes (correctly) that the sum is 50 mod 100[/hide], he will guess 50.

In fact, if the numbers are all distinct, then prisoner 50 will always be right.

Title: Re: 100 people, 100 numbers
Post by spanchap on Mar 25^th, 2007, 1:57pm

on 03/25/07 at 13:29:06, Eigenray wrote:

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

Title: Re: 100 people, 100 numbers
Post by Icarus on Mar 25^th, 2007, 2:08pm

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.

Title: Re: 100 people, 100 numbers
Post by Eigenray on Mar 25^th, 2007, 3:19pm

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1, i.e., they're different; and prisoner 2 assumes the sum is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 2, i.e., they're the same.

Title: Re: 100 people, 100 numbers
Post by spanchap on Mar 25^th, 2007, 5:25pm

on 03/25/07 at 15:19:28, Eigenray wrote:

[hide]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.
[/hide]

Very nice and very neat. Your solution (now that I understand it) is extremely elegant.

Title: Re: 100 people, 100 numbers
Post by River Phoenix on Jul 11^th, 2007, 1:36pm

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?

Title: Re: 100 people, 100 numbers
Post by Hippo on Jul 11^th, 2007, 3:31pm

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?)

Title: Re: 100 people, 100 numbers
Post by chetangarg on Jul 13^th, 2007, 2:02am

i think hippo is absolutely right..
so is there any other solution to this fantastic problem???

Title: Re: 100 people, 100 numbers
Post by srn347 on Sep 4^th, 2007, 8:26pm

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.

Title: Re: 100 people, 100 numbers
Post by Obob on Sep 4^th, 2007, 9:05pm

on 09/04/07 at 20:26:41, srn347 wrote:

they wink at another person

They have NO CONNECTION. For the love of god, at least read the riddle before you post.

Title: Re: 100 people, 100 numbers
Post by srn347 on Sep 6^th, 2007, 4:26pm

They get in pairs and each person says the other ones number. Then they all guess correctly.

Title: Re: 100 people, 100 numbers
Post by pex on Sep 6^th, 2007, 9:59pm

on 09/06/07 at 16:26:25, 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?

Title: Re: 100 people, 100 numbers
Post by JiNbOtAk on Sep 7^th, 2007, 4:46am

on 09/04/07 at 21:05:50, Obob wrote:

They have NO CONNECTION. For the love of god, at least read the riddle before you post.

Hee hee, calm down Obob, he's not worth it. :P

Title: Re: 100 people, 100 numbers
Post by Obob on Sep 7^th, 2007, 7:00am

I know he's not. It's just so annoying though, that he and some other newbies, most of whom have become bored and left, conduct themselves in such a manner. While I've been reading most of the forums for about 4 years now, I have not even attained 150 posts yet. The reason for this? I think before I post, and try to only post when I have something interesting to add to the conversation.

To see the boards watered down with so many terrible posts pains me. It pains me even more to see the hard and putnam sections corrupted by somebody who has absolutely no business posting "solutions" within 2 minutes of "reading" the threads. Having to sift through so much crap because a 13-year-old thinks its fun to make a fool and an ass of himself sucks.

Of course, srn347 won't read this post. But yes, I am talking about him.

Title: Re: 100 people, 100 numbers
Post by Barukh on Sep 7^th, 2007, 9:28am

on 09/07/07 at 07:00:34, Obob wrote:

While I've been reading most of the forums for about 4 years now, I have not even attained 150 posts yet. The reason for this? I think before I post, and try to only post when I have something interesting to add to the conversation.

I would like to tell you, Obob, that I always read your posts with great interest!

Title: Re: 100 people, 100 numbers
Post by Aryabhatta on Sep 7^th, 2007, 3:49pm

on 09/07/07 at 09:28:06, Barukh wrote:

I would like to tell you, Obob, that I always read your posts with great interest!

Second that.

Title: Re: 100 people, 100 numbers
Post by Obob on Sep 7^th, 2007, 11:55pm

Thanks, guys. I didn't mean for that to come out so harsh, but you can imagine my frustration with all my posts directed at him being nearly completely ignored.

Title: Re: 100 people, 100 numbers
Post by mikedagr8 on Sep 8^th, 2007, 3:22am

on 09/07/07 at 23:55:59, Obob wrote:

Thanks, guys. I didn't mean for that to come out so harsh, but you can imagine my frustration with all my posts directed at him being nearly completely ignored.

I think totally. Nearly would imply that he hasn't ignored them. This is not the case.

Title: Re: 100 people, 100 numbers
Post by Whiskey Tango Foxtrot on Sep 8^th, 2007, 10:22am

on 09/08/07 at 03:22:54, mikedagr8 wrote:

I think totally. Nearly would imply that he hasn't ignored them. This is not the case.

This is a little ridiculous.

Title: Re: 100 people, 100 numbers
Post by Ajax on Sep 10^th, 2007, 3:07pm

[hide]A predefined someone will go stand somewhere.
Whatever his number is, that many will move to another place (they will have already discussed who will walk first, second, etc).
By counting them, he will know his number.
In case the number is 100 (only 99 will be left), then no one will move.[/hide]

Title: Re: 100 people, 100 numbers
Post by RandomSam on Oct 3^rd, 2007, 4:38pm

on 03/25/07 at 15:19:28, Eigenray wrote:

N=2: prisoner 1 assumes the sum is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1, i.e., they're different; and prisoner 2 assumes the sum is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 2, i.e., they're the same.

For N=3, the three prisoners A, B and C can guess [hide]B+C, A+2C+2 and A + 2B + 1 (mod 3)[/hide] respectively. I found that result by [hide]trial and error using a truth table[/hide], but can't yet find a similar solution or N=4. :-/

EDIT: Woo! Found a general solution for any size! Will explain soon - it's stupidly late at night here.

Title: Re: 100 people, 100 numbers
Post by SMQ on Oct 3^rd, 2007, 7:32pm

on 10/03/07 at 16:38:29, RandomSam wrote:

EDIT: Woo! Found a general solution for any size! Will explain soon - it's stupidly late at night here.

Does it look anything like this solution posted earlier (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1174688369;start=0#16)? ;) If so, congratulations! That solution is both elegant and non-trivial to come up with.

--SMQ

Title: Re: 100 people, 100 numbers
Post by RandomSam on Oct 4^th, 2007, 6:05am

on 10/03/07 at 19:32:24, SMQ wrote:

Heh.... when reading the thread through, I was sure that solution had been proved wrong! On closer inspection, it turns out our algorithms aren't that different, but Eigenray expresses his much more elegantly than I did. [hideb]Given the condition that only one prisoner must guess correctly, I realised that the guesses g must be some linear function of the hat numbers x.
g = M x + c (mod 100)
Where M is a matrix which must have zeros along its diagonal, since your guess g_i can't depend on your own hat x_i.
g-x = (M - I)x + c (mod 100) must have one and only one zero element.
The solution to this that I found is

	/	-1	1	1	1	...	1	\
	\|	1	-1	-1	-1	...	-1	\|
(M - I)=	\|	1	-1	-1	-1	...	-1	\|
	\|	1	-1	-1	-1	...	-1	\|
	\|	:	:	:	:	:.	:	\|
	\	1	-1	-1	-1	...	-1	/

which basically results in a "leader" (the top row) guessing the sum of everyone else's hats (mod 100), and each other prisoner guessing with the leader's hat minus the sum of everyone else's hat, minus their own uniquely pre-allocated badge (again, mod 100).
Eigenray's solution equates to this matrix:

	/	1	1	1	1	...	1	\
	\|	1	1	1	1	...	1	\|
(M - I)= -	\|	1	1	1	1	...	1	\|
	\|	1	1	1	1	...	1	\|
	\|	:	:	:	:	:.	:	\|
	\	1	1	1	1	...	1	/

Perhaps it is obvious why that is simpler.
[/hideb]Whoa... hidden tables are difficult in BBCode... sorry for repeated edits as I try to get it all right!

Title: Re: 100 people, 100 numbers
Post by Hippo on Oct 6^th, 2007, 3:22pm

It seems to me both solutions correspond to general concept of latin hypercube solution (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1174688369;start=0#19).
The original solution was numbered by distance from origin, your numbering is more complicated.

Title: Re: 100 people, 100 numbers
Post by Hippo on Jan 20^th, 2008, 8:53am

on 07/11/07 at 15:31:31, Hippo wrote:

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?)

Actually the first paragraph is correct, but not only latin hypercubes are the solutions.
(0 0 1 | 1 2 0 | 2 1 2
0 2 1 | 2 0 1 | 1 2 0
2 1 2 | 0 1 2 | 1 0 0) is not latin hypercube and is solution as well.