Hacker News new | past | comments | ask | show | jobs | submit login

Take a look at: https://gist.github.com/javiertury/bf71d37ff26643eca939c6642...

I've tried my best to illustrate why this is the correct solution in the url above.

Long story short:

Call S to the sum of all the numbers on the hats of every player. The sum of all the numbers a player can see will be less than S but the difference with S will be less than "n - 1". Also the difference between the largest guess(for the sum of all the hats) and S won't be larger than "n - 1".

There is now a problem, we want a set of guesses with a size no larger than "n" but in reality it can be as large as size "2(n - 1) + 1 = 2n - 1". Taking the set of possible rational guesses modulo "n" creates a collision, now some guesses will share the same remainder modulo n. However because no guess can be farther than "n - 1" with respect to S, the set of guesses modulo "n" won't create that collision for "S mod n". Any player that was told to make the remainder of the total sum mod n equal to "S mod n" will always have the correct answer.

If you want to think visually imagine the modular clock for "n" which has "S mod n" as the reference point. Because no other point can't be farther apart than "n - 1" distance from S, only S can give the remainder "S mod n". If there are "n" players and we assign each one a different remainder "mod n", one of them will have the correct answer for sure.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: