From the first link: I find it difficult to believe that in the entirity of Jimmy Carter's Navy career, he wrote zero lines of code.
Hello, World
31–40 of 121 posts
Re: Hello, World
#32Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
My experience arriving at this solution made me a bit curious as to how others solved it. Was there reasoning involved before you arrived at a strategy and verified it, or did the strategy just come to you? Did you try multiple strategies, and if so, was there a method to generating/iterating on them, or were they just coming to you and you tried them?
For me, I immediately guessed the strategy on my first guess (one same, one opposite) and somehow automagically intuited it was correct, but did not really understand why. Then I understood once I looked at the thread.
Re: Hello, World
#33Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
My experience arriving at this solution made me a bit curious as to how others solved it. Was there reasoning involved before you arrived at a strategy and verified it, or did the strategy just come to you? Did you try multiple strategies, and if so, was there a method to generating/iterating on them, or were they just coming to you and you tried them?
As a team, they get two guesses. So those two guesses have to cover the space of possibilities, and a guess has to be of a form such that seeing one's own coin implies the guessed value of the hidden coin. (So, "Bob has heads" is not a valid strategy guess. A strategy guess has to describe the state of both coins, so each perskon's strategy guess cannot include two pairs of the form "mine=X, other=H " and also "mine=X, other=T".
This seems a bit awkward, but information theory "guessing" is called "error correction", and parity-checking is the simplest and by far most common strategy. (Advanced algorithms are fancier multidimensional parity computations) So, their two guesses are "same" and "different" (aka parity 0 and 1). A and B each are allocated one of the two strategyGuesses, and translate observedCoin+strategyGuess=hiddenCoinGuess
Re: Hello, World
#34Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
It helped me to think of it this way: Alice is guessing that their coins are different (one possibility) and Bob is guessing that their coins are the same (the other possibility), so from either direction they are covered.
Re: Hello, World
#35Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
Yes, the intuitive way to think of it could be that the coins will either be the same (bob gets it right) or they will be different (alice gets it right)
Re: Hello, World
#36Bonus points:
What if only one of them gets a coin to flip and then they must both come to an agreement on what the result was. They can talk but the NSA overhears everything they say and can crack every cipher they use. Can you maximize the chance that the NSA can't guess who got that coin AND Alice and Bob agree on the correct result?
Note: An open problem. You can look up cryptogenography for current results.
Re: Hello, World
#37Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
My experience arriving at this solution made me a bit curious as to how others solved it. Was there reasoning involved before you arrived at a strategy and verified it, or did the strategy just come to you? Did you try multiple strategies, and if so, was there a method to generating/iterating on them, or were they just coming to you and you tried them?
One of the things I learned was from the Singapore test question (about Cheryl's birthday) which was to parse the question for any clues. What tipped me off was the requirement that either or both of them could get the correct answer to satisfy the problem statement. Once I figured that out I came to the conclusion to try out the truth table where one participant holds their answer constant and the other does a negation of their answer. The truth table worked out.
I have to say I feel somewhat inadequate coming to the answer experimentally as opposed to what others did here.
Re: Hello, World
#38Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
My experience arriving at this solution made me a bit curious as to how others solved it. Was there reasoning involved before you arrived at a strategy and verified it, or did the strategy just come to you? Did you try multiple strategies, and if so, was there a method to generating/iterating on them, or were they just coming to you and you tried them?
My thought process: It seemed obvious that fixed-guess strategies couldn't work, both from the proof in the article and from intuition that the inverse of your fixed guesses will always represent a failure case.
If a fixed strategy can't work, then the guesses must be decided dynamically. At the time the guess is made, only one bit of information (their own flip) is available to each participant, so each guess has to be based on that. With one bit of information, you could only choose two things: do the same, or do the inverse. The correct, asymmetric pair of strategies popped into my head at this point, and a quick truth table check confirmed it.
Re: Hello, World
#39Spoiler: Bob always chooses the same as his flip, Alice always chooses the opposite of her flip. B A H H - Bob chooses heads, Win H T - Alice chooses heads, Win T H - Alice chooses tails, Win T T - Bob chooses tails, Win
It helped me to think of it this way: Alice is guessing that their coins are different (one possibility) and Bob is guessing that their coins are the same (the other possibility), so from either direction they are covered.
Thanks. I think this was the reply that actually helped me understand this.
Re: Hello, World
#40From the first link: I find it difficult to believe that in the entirity of Jimmy Carter's Navy career, he wrote zero lines of code.
Considering he left the Navy in 1953, I find it easy to believe.
I wouldn't be shocked if W had written some excel macros, though. Even less so if Romney had.