NSA's Puzzle Periodical
nsa.gov
nsa.gov
Sorry if your answer turns out to be obviously correct.
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.
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.
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.
What the strategy can influence is the correlation between Ava being right and Bob being right.
Edit: I should've read your answer more carefully.
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.
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.
2. C correctly guesses 0 in your example.
im4w1l's strategy is just:
Player i returns (i - [Sum of the other players' suits]) % 4
(With i ranging from 0 to 3)
You know, solve for `m`, etc.
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.
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...?
(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.
[1] https://web.archive.org/web/20130912120456/https://canyoufin...
https://www.bnd.bund.de/DE/Karriere/Reversing_Challenge/Reve...
German video resolving the first of three challenges: https://www.youtube.com/watch?v=mZH094d0M6A
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
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.
A <-----> B
C <-----> D
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 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.
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.
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...
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
There I cracked that one :)
see my solution here
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 :)
But where?