[sgreben]

Purely mechanically. Just writing down the problem statement we get:

    \exists f,g: \forall a,b: (f(b)=a) | (g(a)=b)

where f,g are the guesses and a,b are the flips. Each guess is a function of the information available to the respective player -- the outcome of his own coin flip. There's only 4 unary boolean functions:

    f,g \in {true,false,id,not} 

The constant functions are out and order doesn't matter, so we're left with

    {(id,not),(id,id),(not,not)}

Here I just tried (id,not) first, but 3 choices are easy to check exhaustively.

[learnstats2]

I followed almost exactly the same logic as sgreben, but without the notation.

First, I assume there is an answer, and at least a moderately interesting answer.

There is no way they can communicate information post-flip, therefore they must be able to cover every possible option.

They cannot cover every possible option by deciding what to write in advance, therefore they must decide what to write based on the flip. In fact, they must both decide based on the flip or they will not gain anything.

If you decide what to write based on the flip, there are only two real choices per player: write the same as what you got, or write the other one.

That leaves you with 3 overall options. Both taking the same of these choices won't work (I skipped over the calculation because they're not interesting solutions), so they must agree to take opposite choices.