A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way.
Well, surprisingly, she can actually do that.
Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I'm a spy in enemy territory. Fortunately, there is a radio broadcast tower in enemy territory, and everyday it sends out a 15-bit message. There's an example of a 15-bit message. Now, I can use that message to communicate with my boss, but I can't just change it arbitrarily to something completely different, because then people will know that something weird has happened. But I can flip just 1 bit. I can zap the message and change just one of the bits, and my boss then is going to hear that, and we'd like him to actually interpret that as the message that I want to send. How should I do that such that, when the boss receives the broadcast, he is like - Hmm...based on the 15-bit broadcast I'm hearing, and the protocol that my spy and I arranged in advance, I know that the message he is sending to me is 0110. Nice work, agent P.
Peter Winkler's video with Problem and Solution:
Peter Winkler gave the solution in the video. Wrote the solution in comments!