Guess 1 out of 100 numbers

[Muktombu]

Hello all,

I have come across an incredibly difficult riddle which I would like to share with you:

100 people are assigned with natural numbers between 1 and 100. These numbers are entirely random and independent of one another, meaning there can be duplicates (and consequently missing numbers). Each person receives an anonymous list of 99 numbers representing everyone else's numbers but not her own.

She then makes a guess regarding her own number based on the numbers she sees and the strategy that was agreed upon in advance by the group. They cannot communicate in any way and cannot hear what others have guessed, i.e. they are completely isolated all the way through.

The strategy they develop should guarantee that at least 1 person makes a correct guess regardless of the given numbers.

I have battled through this brain crushing puzzle, and would be glad to see your ideas and thoughts.

Cheers!

Btw, I am sorry if this riddle was already posted, I tried searching before posting.

Edited November 4, 2013 by Muktombu

[superprismatic]

You're correct that puzzles with a similar solution have been on this forum before.

The strategy insures that precisely one person will be correct. That means, of course, that everyone else will be wrong.

[phil1882]

hmm. i don't see a solution myself either.

with 2 people for example, you have 4 possible results

A B

1 1

1 2

2 1

2 2

at best each person can eliminate half, leaving 1 result uncounted for.

[phil1882]

okay i think i got it.

A B

1 1

1 2

2 1

2 2

let A pick the opposite of what he sees, and B pick the same value.

if A sees 1 he'll pick 2. now when B picks, when he picks the same value as he sees, he's guaranteed to be right, if A was wrong.

now to try to figure out 3.

[flamebirde]

Why not have each person guess a number in order. Write a list beforehand and have each person memorize their number. Therefore, with each person on a number from 1 to 100, at least one person must be right.

[phil1882]

no doesn't work.

consider the preselected list 1-100.

if people are assigned the numbers 2-101%100, then they fail.

it needs to be something like my above post.

Edited November 5, 2013 by phil1882

[phil1882]

one possible solution for 3

took me a while to find this, and i have no idea how you would extend it to 4.

let prisoner 1 take the two values, add them, remainder mod 3, add 1.

let prisoner 2 take the two values he is given, subtract them, mod 3 positive version, add 1.

let prisoner 3 take 3 if both values are equal, else subtract mod 3, positive version. don't add 1.

[BMAD]

if i have a list of 99 numbers that contains all numbers but my own, why not just figure out the missing number?

[phil1882]

you can have duplicates.

so everyone can be 1 for example.

[BMAD]

you can have duplicates.

so everyone can be 1 for example.

help me understand this sentence: "Each person receives an anonymous list of 99 numbers representing everyone else's numbers but not her own."

it reads to me, that a person would have a list of numbers that excludes the number they have.

[superprismatic]

you can have duplicates.

so everyone can be 1 for example.

help me understand this sentence: "Each person receives an anonymous list of 99 numbers representing everyone else's numbers but not her own."

it reads to me, that a person would have a list of numbers that excludes the number they have.

Let's look at a smaller problem with 10 people and integers between 1 and 10 inclusive. Suppose the 10 numbers given out were 1, 2, 2, 2, 3, 6, 7, 8, 8, and 10.

Further suppose that Mary has been assigned the number 2 (not known to her, of course). Then Mary would be given the list 1, 2, 2, 3, 6, 7, 8, 8, and 10. One of the 2s would be

missing -- one that represents what she has been assigned. This is the intent of that sentence.

[BMAD]

you can have duplicates.

so everyone can be 1 for example.

help me understand this sentence: "Each person receives an anonymous list of 99 numbers representing everyone else's numbers but not her own."

it reads to me, that a person would have a list of numbers that excludes the number they have.

Let's look at a smaller problem with 10 people and integers between 1 and 10 inclusive. Suppose the 10 numbers given out were 1, 2, 2, 2, 3, 6, 7, 8, 8, and 10.

Further suppose that Mary has been assigned the number 2 (not known to her, of course). Then Mary would be given the list 1, 2, 2, 3, 6, 7, 8, 8, and 10. One of the 2s would be

missing -- one that represents what she has been assigned. This is the intent of that sentence.

ah ha brilliant. i get it now.

[phaze]

@BMAD I think it also excludes the numbers that nobody has

for 4 people and numbers 1 to 4 a possibility is

Person 1 has 4

1 2 2

Person 2 has 2

1 2 4

Person 3 has 1

2 2 4

Person 4 has 2

1 2 4

due to possible overlap no-one can be certain which number they have.

I think this is what he means by "These numbers are entirely random and independent of one another, meaning there can be duplicates (and consequently missing numbers). "

[harey]

I like the Phil1882 idea of modulo and tried the following rule:

- sum the numbers you got

- add $ (your "position")
- modulo N

It works for some examples for N=4 (with no counterexample so far). The next steps should be an exhaustive computer simulation and a strong therie. Someone is willing to continue?

Edited November 7, 2013 by harey

[phil1882]

close but not quite.

consider the possible assignment:

input output

A B C D A B C D

1 1 1 2 2 3 4 4 - no one correct

the true answer for N seems to be

some kind of permutation of addition and subtraction, mod N

[superprismatic]

The strategy is simply to give each of the 100 prisoners a different "secret"

number between 0 and 99 inclusive. A prisoner's "secret" number is unique to
her and, for that prisoner, is to represent the modulo 100 sum of all hundred
assigned prisoner numbers. After being given the numbers of the other 99
prisoners, it is an easy matter for her to find out what her assigned number
must be in order to make all hundred numbers add up (modulo 100) to her
"secret" number. Since the modulo 100 sum of all assigned numbers must be
the "secret" number of precisely one of the hundred prisoners, the prisoner
who has it will correctly guess her own assigned number. All of the other
prisoners will give incorrect guesses. But the one correct guess is all that
is needed!

[bonanova]

The strategy is simply to give each of the 100 prisoners a different "secret"

number between 0 and 99 inclusive. A prisoner's "secret" number is unique to

her and, for that prisoner, is to represent the modulo 100 sum of all hundred

assigned prisoner numbers. After being given the numbers of the other 99

prisoners, it is an easy matter for her to find out what her assigned number

must be in order to make all hundred numbers add up (modulo 100) to her

"secret" number. Since the modulo 100 sum of all assigned numbers must be

the "secret" number of precisely one of the hundred prisoners, the prisoner

who has it will correctly guess her own assigned number. All of the other

prisoners will give incorrect guesses. But the one correct guess is all that

is needed!

Suppose I'm the person who guesses correctly, and my secret number is 13.

I add up (modulo 100) the numbers on my list. What will that sum be?

[superprismatic]

The strategy is simply to give each of the 100 prisoners a different "secret"

number between 0 and 99 inclusive. A prisoner's "secret" number is unique to

her and, for that prisoner, is to represent the modulo 100 sum of all hundred

assigned prisoner numbers. After being given the numbers of the other 99

prisoners, it is an easy matter for her to find out what her assigned number

must be in order to make all hundred numbers add up (modulo 100) to her

"secret" number. Since the modulo 100 sum of all assigned numbers must be

the "secret" number of precisely one of the hundred prisoners, the prisoner

who has it will correctly guess her own assigned number. All of the other

prisoners will give incorrect guesses. But the one correct guess is all that

is needed!

Suppose I'm the person who guesses correctly, and my secret number is 13.

I add up (modulo 100) the numbers on my list. What will that sum be?

Say the number on your head is X. Your secret number is 13.

The sum of the 99 numbers on your list is L modulo 100.

Then L=13-X modulo 100 because L+X=13 modulo 100.

Assuming your guess was correct.

[bonanova]

So I would calculate L and subtract that from my secret number. Cool. Thx.

[Tom Riddle]

On 12/3/2013 at 10:20 PM, superprismatic said:

 

Hidden Content

Why does this work? Is there a mathematical explanation?

[Todd]

96