Hacker News new | past | comments | ask | show | jobs | submit login
NSA's Puzzle Periodical (nsa.gov)
135 points by edgartaor on Aug 22, 2016 | hide | past | web | favorite | 67 comments

Ava always guesses the same color as Bobs forehead. Bob always guesses the opposite color as Ava's forehead.

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.

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.

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...?

Yeah, that sounds right. Through that lens, the first problem is a special case of the second problem.

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.

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.

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.

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.

1. You got your signs messed up. They should subtract the observation from the total.

2. C correctly guesses 0 in your example.

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)

`m` is the result; this scratch here is meant to resemble algebra, not programming.

You know, solve for `m`, etc.

But the subtraction is simpler. I didn't want to confuse anyone with moduloing a negative number.

Thanks! I misread the answer and took it for the solution to a different but related puzzle

That is very, very clever.

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.

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.

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.

Ava is betting they have the same color, while Bruce is betting they have different colors. One of them is bound to be correct.

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.

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.

Bob is correct when they both have the same card, Ava is correct when they have opposite cards. That covers all 4 color combos.

A variant of the puzzle of identical twins? One brother always lies and the other always tells the truth.

Can you crack puzzles devised by the brilliant cryptological minds at the NSA? Find out by logging in to our totally legit, completely innocuous, not in any way a honeypot that collects extensive info on you, puzzle site!

GCHQ has been known to do this for recruiting purposes.[1]

[1] https://web.archive.org/web/20130912120456/https://canyoufin...

The german BND too:


German video resolving the first of three challenges: https://www.youtube.com/watch?v=mZH094d0M6A

I get NSA jokes, but did you actually go to the link? Seems like a decent periodical.

> Can you crack puzzles devised by the brilliant cryptological minds at the NSA?

almost obligatory snark:

is this the same NSA which allowed/enabled one Edward Snowden to walk out with a gigantic treasure trove of super ultra mega top secret documents, vital to national security, on a USB thumb drive (or whatever it was)?

sincere question

because this point is among the many data points I now have in my mind, as a US citizen and adult voter, when I get to decide exactly how much power I'd like those "smart" folks to have, as they build/run a global 24x7 passive data snoop system on, effectively, all of humanity.

equations may be elegant, perfect, ideal

executable software: less so

human procedures & rules & everyday happenstance & one-off oopsies: far less

That site doesn't get any more information than any other site. No login is required.

"The players may not communicate in any way" - It seems to me that all the answers are a form of communication. In fact the dictionary defines communicate as, "share or exchange information."

What a joke: "find a strategy for the players to determine the colours of their hats based on the hats they see and what the other players do"

I interpreted it in the same way as you did - communication on any level is not allowed. If there is no sharing of information then I think it is impossible to solve the puzzle.

It is possible without communication (also without seeing what the other players do).

How so?

Some answers have been posted already.

To me it looks like a mix between the Prisoner's Dilemma (https://en.wikipedia.org/wiki/Prisoner%27s_dilemma) and Blind man's bluff poker (AKA Indian Poker) https://en.wikipedia.org/wiki/Blind_man%27s_bluff_(poker)

The solution to the 4 person problem is actually pretty simple. Let's assume that we know the answer to the 2 person problem. We have 4 persons; A, B, C and D. At first the persons guess their colour (without revealing it of course) based on their direct neighbor. So for instance:

    A <-----> B
    C <-----> D
A and B being neighbors, they guess their colours based on the solution of the 2 persons problem. Same goes for C and D. Without loss of generality, let's assume C guesses correctly his card colour. Since he can see the cards of A and B, he knows who will guess their colour correctly. For instance, if they have the same colour, A will guess correctly, if not, then B will guess correctly. Without loss of generality, let's assume A guesses correctly his card colour. He then sees that C will guess correctly.

The participants agreed beforehand that clubs and hearts are associated with 0 while diamonds and spades are associated with 1. A and C now apply the solution to the 2 person problem to guess their shape group (either (diamonds or spades) or (clubs or hearts)):

    A       B
    C       D
It is guaranteed that at least one has guessed the shape group correctly. Since they both guessed correctly the color, it is guaranteed that one of them will guess the shape correctly.

I'm more of a Car Talk "Puzzler" type of guy.

"If you think you know the answer, write it on the back of your classified one time pad key and send it to: NSA, Box 35 Fort Meade (our fair city) Maryland".

"I can only sell you the car for 20k. That includes the car-salesman-markup-ripoff tax." "Hmm, sounds like a puzzle solved."

Use this one weird trick to win the guess what card is on my forehead game. Casinos hate it!

Are there any puzzles that help you master "plausible deniability" much better ?

Some of these are poorly worded. Why does the answer to the May one keep talking about 30 seconds passing when the only time mentioned in the problem is 30 minutes? 30 seconds gives Nick at least 10 seconds per possible solution, he should have tried them all by then.

It should talk about the number of tries so far (one each), the length of time it took is irrelevant. But why are they even taking turns when they have separate padlocks and could easily brute-force it? I get the concept they're going for but the premise doesn't fit and just confuses things.

Yeah. I didn't get what the big deal was about it until I read the 30 second and turns he mentioned in his explanation.

The NSA also has (had?) an internal puzzle in there cryptolog internal magazine. Some have been declassfied at https://www.nsa.gov/news-features/declassified-documents/cry.... An example of their puzzles: https://david.newgas.net/nsa-puzzle/

It said no communication during but you could devise a strategy before play. What I would do on the first challenge is say I would write down the opposite color of what I see and tell the other person the write down the same color they see so you will definitely at least win $50 "or 100$ if you have the same color". For the suite challenge do the same strategy but split 2 people write down the same suite and have a plan for the other 2 to pick what they don't see.

Coincidentally enough, this was a submitted puzzler to the NPR syndicated show "Car Talk," except there were 10 men in a line wearing black or white hats. The goal was to determine the optimal strategy for guessing hat colors.

Orienting the cards vertically or horizontally would count as communication, wouldn't it? Otherwise this would be trivial.

I'm not sure how orienting the card that is on your own head would help. You don't know what it is.

That being said the method of "Bob always tells the truth, Alice lies" is sort of a card orientation way for two people. Alice puts her card up sideways and Bob knows that to mean he should tell the truth. Likewise Bob doesn't rotate his and Alice knows to lie.

However that only works with two people and they have opposite spins.

Maybe it can work with more than two and you have two rounds of guessing. Also you need to know that you have differing spins.

You orient the card based on the other player's card, for their benefit. That's why I think it would be against the rules - it's the same as if you held up fingers or made a face, it's communication.

Bruce and Ava decide to put the card horizontally if they see a red card, or vertically if it's black. If Bruce sees a vertical card, he knows Ava sees a red card on his head.

In the game of four, the players decide one of them will guess, and two others will communicate information in binary:

horizontal, horizontal: hearts

horizontal, vertical: diamonds

vertical, horizontal: spades

vertical, vertical: clubs

However this latter method only requires three players, not four. But it is similar to how professional bridge players cheat, by communicating their hand (which is hidden from their partner) with secret signals: http://www.newyorker.com/magazine/2016/03/07/the-cheating-pr...

Wow, thanks for that link about cheating in bridge. Spent hours going over that and stories on http://bridgewinners.com/

There are so many potential hidden channels! If 2nd can see what the 1st one guessed -- that's also easy Or if they just agree on the timing of the guess..

The answer is pretty simple.

1. The strategy is that they should agree to write down the same colour(either red or black), irrespective of what they see on the opposite persons forehead

2. Same as above. This time all of them should agree to write any single suit.

By probability, at least one of them will get it right.

[Edit]: Didn't put it correctly before

1 They should write their own color, so this is not a winning strategy. [Spoiler] As stated by other the winning strategy is that one says always the other person's color and the other say the opposite. That's because or the color are the same or are different.

You're right

This won't work, it's perfectly possible that they draw the same color; which could be the opposite of what they agreed to write down.

True. The logic is flawed

Reminds me of "ponder this" from IBM research: https://researchweb.watson.ibm.com/haifa/ponderthis/index.sh...

The April one was.. disappointing.

The June one too. A simple three if then statements can solve the problem easily even increasing the 1000 coins to a number physically possible by the ship to hold.

Come back tomorrow as in Sep 1, 2017 for the answer I suppose.

There I cracked that one :)

Make Bruce guess opposite of what he sees on Ava and Ava guess same color as what she sees on Bruce. This covers atleast one correct guess for all for Cases BB, RR, BR, RB.


see my solution here

For the July one:

Always go first.

Assuming the table is symmetrical around only one point, the centre of the table, place the first coin on that point.

Every move after that place your coin in the location directly opposite the last coin played, the mirrored location around the point of symmetry.

Since you are always playing a symmetrical position, you know that there will always be a space available for you after the previous coin was played.

[edit] looks like the answer on the site is almost the exact wording as mine :)

This is actually very similar to a question I was asked when interviewing to read Maths at Oxford. In the Oxford version, your brother and you are also playing a game. You have a 2-dimensional block of chocolate with a poison piece somewhere in the block. The poison piece is bright green to the eye. You each take it in turn to break off some chocolate (you have to follow the rows and columns of the chocolate, and the break must be a single break). To win you must avoid eating the poison piece and end the game by handing it to your brother. You have the choice of going first or second? When should you choose either?

Nim in disguise

Come back tomorrow to see the answer!

But where?

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