Topic: 1..100 an interesting puzzle
 Message: Posted by: Nir Dahan (Jul 31, 2005 12:31PM)
A guy (which will will call the "organizer") gathers 100 people for a game.

1 - Each person is being sent to a room with a computer. The rooms are completely isolated from one another and the only communication available is through the computer to the organizer alone. No communication whatsoever between the people after the game starts.

2 - The Organizer then runs a totally random number generator and assigns a number from 1 to 100 for each of the 100 participants. A number may repeat itself. i.e. John can get the number 32 and Jane can also be assigned 32. This number is being saved on the organizer's machine and he is the only one who can access it.

3 - An email is then being sent from the organizer to each of the participants. Each email contains a list of the 99 numbers all the OTHER participants have been assigned to (in random order). this email is missing the number assigned to the receipient!!! so all in all 100 emails are being sent with 100 different lists containing each 99 numbers.

4 - each person is then asked to send an email back to the organizer with the number he THINKS he was assigned. this number is obviously between 1 and 100.

5 - the organizer then collects the answers and compares them to the original numbers assigned to them. if at least ONE is right the entire group gets 1 million dollars.

THE 100 PEOPLE ARE ALLOWED TO MEET BEFORE THE GAME STARTS TO DECIDE UPON A STRATEGY.
----------------------------
is there a strategy that guarentees a sure win? if so what is it? if not prove it.

this is a wonderful little puzzle I hope you guys enjoy it the same as I did.

Nir
 Message: Posted by: Mehtas (Jul 31, 2005 01:25PM)
Let me get this right

I as a participants receive an email containing a list of 99 numbers from 1 to 100. the missing number is the one that I have been assigned.

Right ??

Then I don't see any problem in guessing the right number I was assigned.
 Message: Posted by: Stephen Buxton (Jul 31, 2005 01:47PM)
NOt really, as there could be repeats. As each number is not dependant on the others, it is possible that all 100 numbers are the same number. Unlikely, but nevertheless possible
 Message: Posted by: Mehtas (Jul 31, 2005 02:16PM)
The strategy I guess would be this....

When I get my list of 99 numbers through email, I will look for repeating numbers from the list of 99 numbers. if I find a repeating number (eg No 28). so if there are two figures of 28, I will email back the same number from all 100 email accounts.

Im not sure if that guarentees a win but its possible.

:kewl:
 Message: Posted by: Stephen Buxton (Jul 31, 2005 02:26PM)
I've been pondering this with my Father-in-law, and we've come up with a possible strategy... I doubt that there is any strategy that will allow a certain win, due to the non-dependancy of the randomness of assigning numbers (is that a proper sentence?), however, it might be possible to improve your odds.

Are you familiar with the birthday probablilty? If you get 25 people chosen at random, the chances are roughly 50/50 that two people will share the same birthday.

So, if you have 100 people with 100 numbers chosen at random, the probability moves far closer to certainty that there are two people with the same number. In fact, my gut feeling is that there will be a lot of pairs.

So, what each person should do is cross off the pairs in their list (if there are three identical numbers, still only cross off two), and look to see what numbers remain (there will be at least one number remaining). The person can then choose one of those numbers, and email that.

I suppose an additional strategy could be to assign people in groups of ten to each of the ten ranges: 1 to 10, 11 to 20 through to 91 to 100. Given a choice of un-paired numbers, they should select a single number within their assigned range. If there is no unpaired number in their range, they can choose any of the others at random as their choice.
 Message: Posted by: stanalger (Jul 31, 2005 03:06PM)
No guarantee of a win...so the object is to maximize the odds of winning.
If two (or more) people are assigned the same number, then they will
receive the same list of 99 numbers. The only way of improving the odds
of winning is to devise a scheme in which folks who receive the same list
of 99 numbers are sure to submit DIFFERENT numbers as guesses.

Here's one way: Number 100 slips of paper, each with a different number
from 1 to 100. Before retreating to their individual rooms, each participant
draws a slip. Each participant then goes to his/her own room, receives the
list of 99 numbers, adds those 99 numbers PLUS the number on their slip
of paper. Each reduces the total mod 100, adds 1, and submits THAT number
as their guess.

I can't imagine a strategy that would increase the odds any better than this.

Stan Alger
 Message: Posted by: stanalger (Jul 31, 2005 03:28PM)
Ooooops! I haven't solved the original challenge.
We must PROVE that there is no strategy which guarantees
a win.
 Message: Posted by: Nir Dahan (Jul 31, 2005 03:40PM)
Hi all,

as I stated before there is no communication whatsoever between the people after entering the rooms. they cant track other's email addresses or anything like that.
they get 99 numbers and have to send a number back. that is all.

it seems like all of you are wrong so far.
there is a strategy to insure a win - 100% of the time. I know it sounds strange but this is the beauty of the problem.

here is a strategy that works for two people and the numbers 1 and 2.
the first person sends back what he gets. the second person sends the complimentary of what he gets.

lets test a sample case:

first person gets "1", second person gets "2" - the first person answers "2" (that is what he got) the second answers "2" (he got "1" therefore answers "2")

here are all the cases summerized in a table:

----------------------------------------------
"1" , "2" |"2" , "2" |second
"1" , "1" |"1" , "2" |first
"2" , "1" |"1" , "1" |second
"2" , "2" |"2" , "1" |first
-----------------------------------------------

as can be seen from the table, whenever the received numbers are identical the first person gets it right, otherwise the second.

----------------------------------------------------------

these are two major hints for the solution
1 - there is a possible 100% solution
2 - I gave you the simplest case solution for 2 people

enjoy,

nir
 Message: Posted by: stanalger (Jul 31, 2005 07:34PM)
Nir,

Interesting. Your strategy for two people agrees with my strategy.
Player one adds one to the other player's number, reduces the total
mod 2, adds one, and gives that final total as his/her guess. Player
two adds two to the other player's number, reduces the total mod 2, adds
one, and gives that final total as his/her guess.

(Your rules are simpler, but equivalent.)

However, my strategy does not guarantee a win for the team in the
three person game.

I still can't see a winning strategy for three people. But I trust you're
correct, so I'll keep working on it.

Stan
 Message: Posted by: Nir Dahan (Aug 1, 2005 01:12AM)
[quote]
On 2005-07-31 20:34, stanalger wrote:
Nir,

Interesting. Your strategy for two people agrees with my strategy.
Player one adds one to the other player's number, reduces the total
mod 2, adds one, and gives that final total as his/her guess. Player
two adds two to the other player's number, reduces the total mod 2, adds
one, and gives that final total as his/her guess.

(Your rules are simpler, but equivalent.)

However, my strategy does not guarantee a win for the team in the
three person game.

I still can't see a winning strategy for three people. But I trust you're
correct, so I'll keep working on it.

Stan
[/quote]

Stan,

I actually found another algorithm yesterday that GIVEN A SOLUTION guarentees a win.
the problem with this one is that you have to prove a solution exists.
in any case it is by far less elegant than the first algorithm I have found which also shows there is always a 100% solution and is very very simple compared to the second one, and what makes it elegant and beautiful as well.

Nir
 Message: Posted by: TomasB (Aug 1, 2005 03:56AM)
Thanks for yet another excellent problem, Nir.

/Tomas
 Message: Posted by: stanalger (Aug 3, 2005 07:46AM)
Aha! I woke this morning with a solution in my head.

The participants number themselves 0-99, each getting a
different number. So each player has a different
group-assigned number.

Participants retreat to their rooms and the organizer
assigns a number between 1 and 100 to each of them.
(Not necessarily different.)

Since the total of the 100 organizer-assigned numbers must
reduce mod 100 to a number between 0 and 99, each player
adds the values of the other players' organizer-assigned
numbers and subtracts this total from their group-assigned
number. All of this arithmetic is done mod 100. The
player who gets an answer of 0 from the final subtraction
submits 100 as his/her guess. All other players simply
submit the result of the final subtraction as his/her
guess.

EXACTLY ONE of the 100 guesses will be correct. The group
will be guaranteed a win if they follow this strategy.

Yes, Nir, this is a great problem! Very nice!
 Message: Posted by: Sapient (Aug 3, 2005 09:37AM)
Stan,

Could you explain to my poor brain what you mean by "mod"? I'm asking on its behalf, as it is still asleep, and unavaliable to post messages at the moment.
 Message: Posted by: stanalger (Aug 3, 2005 09:59AM)
I just realized that my first posted strategy (which didn't
GUARANTEE a win for the team) can be "tweaked" to get a
strategy which DOES guarantee a win for the team.

Here's my earlier posted strategy:
[quote]
Number 100 slips of paper, each with a different number
from 1 to 100. Before retreating to their individual rooms, each participant
draws a slip. Each participant then goes to his/her own room, receives the
list of 99 numbers, adds those 99 numbers PLUS the number on their slip
of paper. Each reduces the total mod 100, adds 1, and submits THAT number
as their guess.
[/quote]

Change the last sentence to "Each reduces the total mod 100, subtracts
that answer from 100, and posts the difference as their guess."

A positive number mod 100 is simply the last two digits of the number.
234 mod 100 is 34.
394857 mod 100 is 57.
8383747 mod 100 is 47.
27 mod 100 is 27.
3 mod 100 is 3.
200 mod 100 is 0.

But a negative number mod 100 is
100 minus the last two digits. (Unless the result is a three digit
number, i.e. 100. In the case you say the number mod 100 is 0.)
(-2 mod 100) is (100 - 2) or 98
(-6453 mod 100) is (100 -53) or 47.
(-6467500 mod 100) is 0 (since (100-00) = 100.)

Let me post an easier to follow solution that doesn't involve
subtraction.
 Message: Posted by: Nir Dahan (Aug 3, 2005 10:10AM)
Very good Stan,
to you it came in a dream - to me during a boring meeting at work...
my strategy to the solution was practically identical, i.e. guarentee that the sum of all the numbers a person sees + the number he sends = a constant number distributed to him from 1-100 (no two same numbers can be distributed). This is exactly like saying "substruct .... "

Nir

p.s. Maybe you can also share with us some of your puzzles Stan?
p.p.s. I have tons more (I collect them) but I have to translate them from hebrew (my native tongue - therefore the poor phrasing sometimes)
 Message: Posted by: Sapient (Aug 3, 2005 10:14AM)
Thanks Stan. That all makes sense now. My brain would thank you, but it isn't here right now. Come to think of it, I haven't seen it in a long, long time.
 Message: Posted by: stanalger (Aug 3, 2005 01:08PM)
Okay, here's the streamlined strategy. It's easy for all
players to follow, even if they don't understand modular
arithmetic. (They may not understand [b]why[/b] this
strategy works, but they can easily follow the strategy.)
A subtraction is still involved, but it's
good old "regular" subtraction of the type we learned
early in grade school...before we were taught the concept
of negative numbers.

The players number themselves 1-100, each player getting
a different number. Call these numbers their group-
assigned numbers.

Once a player receives his/her list of the other 99
players' organizer-assigned numbers, the player adds
these 99 numbers PLUS the player's own group-assigned
number. The player ignores all but the last two digits
of this sum. This two digit number (00, 01, 02,..., or 99)
is subtracted from 100 and the result is submitted
to the organizer.

Exactly one player will submit a correct guess.
 Message: Posted by: MPHanson (Aug 4, 2005 12:38AM)
(1) I don't understand modular arithmetic.

(2) Based on that beautifully clear "streamlined" method, I can easily

(3) I don't understand why the strategy works.

So are you a mentalist, stanalger? -- 'cuz you read my mind....

Anyway, I tried to do this with 5 players, to get a handle on why it works, but that confused me more (players 1, 2, 3, 4, 5; numbers assigned = 4, 5, 2, 5, 1; addition totals for players = 14, 14, 18, 16, 21; then what???).

All that notwithstanding, this strikes me intuitively (that's about all I've got) as a really cool puzzle -- thanks Nir Dahan!!!

Mike
 Message: Posted by: MPHanson (Aug 4, 2005 12:41AM)
(1) I don't understand modular arithmetic.

(2) Based on that beautifully clear "streamlined" method, I can easily

(3) I don't understand why the strategy works.

So are you a mentalist, stanalger? -- 'cuz you read my mind....

Anyway, I tried to do this with 5 players, to get a handle on why it works, but that confused me more (players 1, 2, 3, 4, 5; numbers assigned = 4, 5, 2, 5, 1; addition totals for players = 14, 14, 18, 16, 21; then what???).

All that notwithstanding, this strikes me intuitively (that's about all I've got) as a really cool puzzle -- thanks Nir Dahan!!!

Mike
 Message: Posted by: TomasB (Aug 4, 2005 01:22AM)
Mike,

The streamlined method works with the easy wording of "The player ignores all but the last two digits of this sum" only because there is 100 people playing. I'm not sure they need to do the final subtraction from 100 in what Stan submitted. I think they can send in the last two digits immediately.

In your case you number the people 0, 1, 2, 3 and 4 accordingly and add these position numbers to their totals and they will get 14, 15, 20, 19 and 25. Instead of looking at the last two digits as the case with 100 players was you have to divide with 5 and just look at the reminder. They will get 4, 0, 0, 4, 0 where 0, as said before, means that they send in 5 as their answer. The first guy will get it correctly.

Following exactly what Stan said you should subtract these answers from 5 and you will get 1, 5, 5, 1, 5 so the second guy is the winner then.

Great work, by the way, Stan!

/Tomas
 Message: Posted by: stanalger (Aug 4, 2005 06:46AM)
Without the final "subtract from 100" step, the team won't be
guaranteed a win.

Here's a counterexample:

The players have already numbered themselves 1-100.

Organizer assigns the number 2 to player 1, and assigns 1 to
all of the other players 2-100.

Player 1 receives a list consisting of 99 1's. He totals
the list to get 99, adds 1 (his player number) to get 100,
ignores all but the last two digits and submits 0 as his guess.
He's wrong since his number was 2 (not 0.)

Players 2-100 each receive a list containing 98 1's and a single 2.
Each of these list totals 100 (since 98*1 + 2 = 100.)

After players 2-100 add their player numbers to 100, they get totals
of 102, 103, 104, ..., 199, 200. Ignoring all but the last two
digits, they finish will 2, 3, 4, ..., 99, 0. If they submit these
numbers as their guesses, they are all wrong (since all of them
were assigned 1 by the organizer, but none submitted 1 as their guess.)

[If you add the final "subtract from 100" step, player 1 would subtract
0 from 100 and submit 100 as his guess. He's still wrong.
Players 2-100 would subtract 2, 3, 4, ...., 99, 0 from 100 and
submit 98, 97, 96,..., 1, 0 as their guesses. Player 99 would be
the only one submitting a correct answer...but that's a WIN for the
team!]

It's quite a generous game for the organizer to sponsor, since even with
NO strategy, the team will probably win. If the organizer's assignment
of numbers is random, and if the players ignore the lists and simply
guess at their numbers, they will win roughly 63% of the time.
(1-(99/100)^100=.63396765...)
The flawed strategy (missing the "subtract from 100" step), while not
perfect, increases the probability of success even more (but not all
the way to 100%.)
 Message: Posted by: TomasB (Aug 4, 2005 08:47AM)
Stan is of course very right that the final subtract needs to be done. I confused myself when I saw that it didn't matter if the players add or subtract their position in the modulo arithmetics. Exchanging addition for subtraction is the same as putting the players in the reverse order since (X + N) mod 100 = (X + (N - 100)) mod 100.

Follow-up puzzle: How many players should the organizer allow to give them at most even odds if they only guess?

/Tomas
 Message: Posted by: MPHanson (Aug 5, 2005 01:02AM)
Thank you for the amplification, Tomas. Nonetheless, I think I need to go back to the kiddie pool until I learn to swim a little better...

Mike
 Message: Posted by: Heinz Weber (Aug 5, 2005 03:39AM)
First I admitt I have not the sligthest idea WHY stans strategy works. I simulated it yesterday (to proof that it doesn't and to find a counterexample) and found it works. I also found: with random guessing (without any strategy at all) they have a 64,6% chance to win, and with the strategy 'without the last subtract from 100 -step' this is nothing better. I did this because my first approach to the problem was something similar, I tried to make sure that players with identical assigned numbers are guessing differently. But obviously I was (and I am) very fare from understanding the problem...

Stan (or Thomas) can you give us some insight why this works?

Thanks,
Heinz
 Message: Posted by: TomasB (Aug 5, 2005 04:59AM)
Heinz, Stan did explain why it works but I can try to make it clearer.

Imagine that you are a player and you KNOW the last two digits if you sum up ALL 100 numbers. Maybe you know that the number should end in 42. You get your list of 99 numbers and sum them up. You will then KNOW which number you should chose to make the sum end in 42. There can only be one such number between 1 and 100.

In reality no one knows what he sum of all 100 numbers end in but we know that it can only end in 00, 01, 02, ... , 98 or 99, which happens to be exactly 100 different cases. So let one player guess that the sum ends in 00. Let another guess that the sum ends in 01, etc. One (and exactly one) of them will be correct and will therefore guess his own number correctly.

/Tomas
 Message: Posted by: Heinz Weber (Aug 5, 2005 07:03AM)
Oh...

thank you!