Jump to content
BrainDen.com - Brain Teasers
  • 1

Guess 1 out of 100 numbers


Muktombu
 Share

Question

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 by Muktombu
Link to comment
Share on other sites

20 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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 by harey
Link to comment
Share on other sites

  • 0

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!
Link to comment
Share on other sites

  • 0

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?

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...