The puzzle

https://m.whitehouse.gov/blog/2015/05/17/hello-world

Alice and Bob are playing a game. They are teammates, so they will win or lose together. Before the game starts, they can talk to each other and agree on a strategy.
When the game starts, Alice and Bob go into separate soundproof rooms - they cannot communicate with each other in any way. They each flip a coin and note whether it came up Heads or Tails. (No funny business allowed - it has to be an honest coin flip and they have to tell the truth later about how it came out.) Now Alice writes down a guess as to the result of Bob's coin flip; and Bob likewise writes down a guess as to Alice's flip.
If either or both of the written-down guesses turns out to be correct, then Alice and Bob both win as a team. But if both written-down guesses are wrong, then they both lose.
The puzzle is this: Can you think of a strategy Alice and Bob can use that is guaranteed to win every time?

The reasoning

As stated in the OP, any static strategy (Alice and Bob choosing any combination of Heads or Tails) will not work.

Also, the only information Alice and Bob have at the point of making a guess for the other's coin toss is the result of their own coin toss.

So, with one bit of information as input and one bit of information as output, there's not a lot that can happen in between: the result will be either

• Independent of the input (always guess Heads)
• Independent of the input (always guess Tails)
• The same as the input
• The opposite of the input

But those are the four possible strategies for just Alice or Bob. (You could say there are more e.g. choose randomly, but I don't think they are worth considering to win the game deterministically every time.)
The combined team strategy is a pair of individual strategies that doesn't necessarily have to be the same. That's 16 possible team strategies.

And how can we tell if a single team strategy wins the game every time? We play the game with every possible coin toss result (4) and check our guesses against them.

That's a solution space of 16*4=64 possibilities, which is quite feasible to explore by hand. Even more so when we can discard a bunch of strategies outright, like the "static" ones that is easy to reason all have counterexamples.

But where's the fun in that? Lets instead code a little program to check every strategy combination and see what happens!

        var strategyTester = function (aliceGuessGenerator, bobGuessGenerator) {
            var gameResult = function (resultAlice, resultBob) {
                var guessAliceForBob = aliceGuessGenerator(resultAlice);
                var guessBobForAlice = bobGuessGenerator(resultBob);
                if (guessAliceForBob !== resultBob && 
                guessBobForAlice !== resultAlice) {
                    return false;
                } else {
                    return true;
                }
            };
            return gameResult('Heads', 'Heads') &&
            gameResult('Heads', 'Tails') &&
            gameResult('Tails', 'Heads') &&
            gameResult('Tails', 'Tails');
        };
        var headsGenerator = function (ownResult) {
            return 'Heads';
        };
        headsGenerator.printName = 'Heads';
        var tailsGenerator = function (ownResult) {
            return 'Tails';
        };
        tailsGenerator.printName = 'Tails';
        var sameGenerator = function (ownResult) {
            return ownResult;
        };
        sameGenerator.printName = 'Same';
        var oppositeGenerator = function (ownResult) {
            return ownResult === 'Heads'?'Tails':'Heads';
        };
        oppositeGenerator.printName = 'Opposite';
        
        var individualStrategies = [headsGenerator, tailsGenerator, 
        sameGenerator, oppositeGenerator];
        
        window.results = [];
        individualStrategies.forEach(function (aliceStrategy) {
            individualStrategies.forEach(function (bobStrategy) {
                window.results.push('Alice guesses "'+
                aliceStrategy.printName+'", Bob guesses "'+
                bobStrategy.printName +  '" and the result is: '+
                (strategyTester(aliceStrategy, bobStrategy)?'WIN':'lose'));
            });
        });

    

And the results of runing it:

The solution

We have a winner! One has to guess the same as their coin toss, and the other has to guess the opposite of their own coin toss.

Does that make sense? Yes, they cannot be both wrong at the same time if one guesses their coin tosses are the same, and the other guesses their coin tosses are different, now, can they? There you go, QED.