News for hackers. Stuff that matters.
Re:NSA's Puzzle Periodical by IIAOPSW on Monday August 22, 2016 @12:47AM (#12334170)
Ava always guesses the same color as Bobs forehead. Bob always guesses the opposite color as Ava's forehead.
Re:NSA's Puzzle Periodical by im4w1l on Monday August 22, 2016 @01:05AM (#12334226)
For the four people puzzle. Assign every suit a number 0-3. All four people guess differently what the sum of all the cards is modulo 4, meaning exactly one person will get it right. Using the sum and the view of the other cards the one who guessed right can work out their own card.
Re:NSA's Puzzle Periodical by brian_cloutier on Monday August 22, 2016 @08:09AM (#12335691)
To give some intuition as to why these answers are "obviously" correct; for the 2-person case you have 4 possible results:

(Ava, Bob) -> (B, B), (B, R), (R, B), (R, R)

It's easy to see that there are only two alternatives: they either both have the same suit or they have different suits. Luckily, there are two players, and so they can try both options simultaneously.

The same thing works in the 4-player case. You can try 4 strategies at once, is there any way to somehow reduce the state space to 4 options?

If you give every suit a number from 0-3, then the sum of all the suits is obviously going to be somewhere between 0-3 modulo 4.

Re:NSA's Puzzle Periodical by philbarr on Monday August 22, 2016 @08:03AM (#12335661)
It seems that we could expand this for n people with n choices.

So in the first case where there are only 2 people and 2 colours, they assign, say 0 to black and 1 to red. Then they each sum up the other choices they can see (which happens to be only one other choice in this case) plus their own assigned number (0 or 1) and answer that modulo 2.

Er..I think...?

Re:NSA's Puzzle Periodical by brian_cloutier on Monday August 22, 2016 @08:24AM (#12335778)
Yeah, that sounds right. Through that lens, the first problem is a special case of the second problem.
Re:NSA's Puzzle Periodical by ulrikrasmussen on Monday August 22, 2016 @01:48AM (#12334353)
I don't think the players can see the other players' answers. The puzzle reads like an instance of the 100 hats puzzle, but instead of maximizing the number of correct answers, you just have to guarantee at least one.

Edit: I should've read your answer more carefully.

Re:NSA's Puzzle Periodical by josefdlange on Monday August 22, 2016 @02:02AM (#12334390)
Gist of this, since formatting got screwy: https://gist.github.com/josefdlange/04c9eb14a9ddbdfae8eb2e34...

Seeing the others' answers I don't think matters in this solution.

The strategy -- given that it's allowable to discuss strategy before drawing cards -- is each person has a different modulo result (x) they have to compute the number they must add [to the sum of the other three], (m) in the following algebra. Solve for m to get the suit your should guess.

x = ([sum of others] + m) % 4

Suits: 0: Diamond 1: Heart 2: Club 3: Spade

Example: [PLAYER]: (SUIT THEY HAVE), (CHOSEN MODULO RESULT) A: (0) (0) B: (1) (1) C: (3) (2) D: (3) (3)

For A's m: ((1 + 3 + 3) + m) % 4 == 0, therefore m = 1 For B's m: ((0 + 3 + 3) + m) % 4 == 1, therefore m = 3 For C's m: ((0 + 1 + 3) + m) % 4 == 2, therefore m = 2 For D's m: ((0 + 1 + 3) + m) % 4 == 3, therefore m = 3

D guesses correct.

There are many permutations of the drawn cards, but I think this one does solve it. All props to the person up this thread who initially answered the 4-player problem; I'm just explaining their methodology as I understood it.

Re:NSA's Puzzle Periodical by javitury on Tuesday August 23, 2016 @08:21PM (#12348819)
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.

Re:NSA's Puzzle Periodical by pliny on Monday August 22, 2016 @03:19AM (#12334634)
If they have (A,B,C,D) = (0,1,0,1):

A sees 1+0+1 -> guesses (2+0)%4 = 2 (wrong)

B sees 0+0+1 -> guesses (1+1)%4 = 2 (wrong)

C sees 1+0+1 -> guesses (2+2)%4 = 0 (wrong)

C sees 0+1+0 -> guesses (1+3)%4 = 0 (wrong)

EDIT: This is twice incorrect, as indicated below.

Re:NSA's Puzzle Periodical by im4w1l on Monday August 22, 2016 @03:45AM (#12334709)
1. You got your signs messed up. They should subtract the observation from the total.

2. C correctly guesses 0 in your example.

Re:NSA's Puzzle Periodical by nonsequitur on Monday August 22, 2016 @07:20AM (#12335478)
There's no assignment to the „m“ variables that would make your algorithm work in the general case.

im4w1l's strategy is just:

Player i returns (i - [Sum of the other players' suits]) % 4

(With i ranging from 0 to 3)

Re:NSA's Puzzle Periodical by josefdlange on Monday August 22, 2016 @09:43AM (#12336249)
`m` is the result; this scratch here is meant to resemble algebra, not programming.

You know, solve for `m`, etc.

Re:NSA's Puzzle Periodical by josefdlange on Monday August 22, 2016 @09:44AM (#12336251)
But the subtraction is simpler. I didn't want to confuse anyone with moduloing a negative number.
Re:NSA's Puzzle Periodical by ulrikrasmussen on Monday August 22, 2016 @02:07AM (#12334399)
Thanks! I misread the answer and took it for the solution to a different but related puzzle
Re:NSA's Puzzle Periodical by josefdlange on Monday August 22, 2016 @01:50AM (#12334359)
That is very, very clever.
Re:NSA's Puzzle Periodical by sopooneo on Monday August 22, 2016 @01:04AM (#12334224)
I haven't reasoned through your solution fully yet, but is that a guarantee that at least one of them is correct? How?

Sorry if your answer turns out to be obviously correct.

Re:NSA's Puzzle Periodical by atdt on Monday August 22, 2016 @03:04AM (#12334583)
There are four possible scenarios:

1. Ava's card is red, and Bruce's is black.

2. Ava's card is red, and Bruce's is red.

3. Ava's card is black, and Bruce's is red.

4. Ava's card is black, and Bruce's is black.

To win, Ava should pick the same color as the card she sees on Bruce's forehead, and Bruce should pick the color that is different from the card he sees on Ava's forehead. (Which player chooses which strategy doesn't actually matter.)

Here is how the strategy plays out for each of the four scenarios above:

1. Ava chooses black, and Bruce chooses black. Bruce guessed correctly.

2. Ava chooses red, and Bruce chooses black. Ava guessed correctly.

3. Ava chooses red, and Bruce chooses red. Bruce guessed correctly.

4. Ava chooses black, and Bruce chooses red. Ava guessed correctly.

Re:NSA's Puzzle Periodical by sopooneo on Monday August 22, 2016 @09:10AM (#12336044)
Thank you. There it is listed out.

I'm unsettled that a strategy involving using information that must have 0 correlation to each person's own correct answer could yield a collectively correct answer. I have heard problems similar to this before where I have been able to say "oohhhhhh" and find out why the answer does not seem to violate other overarching truths, but I'm not there with this one yet.

This is a like a person spelling out, step by step, how to build a perpetual motion machine, with no clear missteps, and the machine works, and I'm trying to understand how it jives with the second law of thermodynamics.

Re:NSA's Puzzle Periodical by BoppreH on Monday August 22, 2016 @10:00AM (#12336354)
Ava is betting they have the same color, while Bruce is betting they have different colors. One of them is bound to be correct.
Re:NSA's Puzzle Periodical by shmageggy on Monday August 22, 2016 @12:51PM (#12337612)
Agreed that the independence of each card makes this seem paradoxical, in a kind of Monty Hall way. I'm reconciling this by noticing that neither person can guarantee that they will themselves be correct, individually. This satifies the independence problem, since they really do have no way of knowing their own card.

Then how do they arrive at a correctively correct answer? I'm reconciling this by noticing that there is no possibility of them both being correct. That is, their strategy effectively divides up the answer space such that they are covering all two possible correct answers.

Re:NSA's Puzzle Periodical by im4w1l on Monday August 22, 2016 @01:11PM (#12337775)
No matter the strategy Ava will get the right answer 50% of the time, and Bob will get the right answer 50% of the time.

What the strategy can influence is the correlation between Ava being right and Bob being right.

Re:NSA's Puzzle Periodical by mertd on Monday August 22, 2016 @01:05AM (#12334230)
Bob is correct when they both have the same card, Ava is correct when they have opposite cards. That covers all 4 color combos.
Re:NSA's Puzzle Periodical by intended on Monday August 22, 2016 @01:20AM (#12334273)
A variant of the puzzle of identical twins? One brother always lies and the other always tells the truth.