• 0

Guess 1 out of 100 numbers

Question

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites

18 answers to this question

  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by phil1882
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

you can have duplicates.

so everyone can be 1 for example.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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!
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.