Spy And Radio

A spy is being commissioned by the government to infiltrate a mafia rank in order to find out who the head honcho is. There are sixteen potential candidates and the government needs to know which one of them is the leader. However, the spy only has one chance to pass the information back to the government before she gets murdered.

On an previously-agreed date, the local radio station will announce the winning lottery number. This number will be from 0 to $2^{15}-1$ inclusive, and will be saved as a 15 binary digit data in that radio station's computer. The spy only has one chance to infiltrate the radio station's computer mainframe, change one bit (or none) in that number, and leave. The broadcaster will announce the number without knowing that the spy has changed it, and the government agents will listen to that changed number. The government and the spy don't know the winning number in advance and they have no further power to rig the lottery.

To make things more complicated, the spy does not have that much time in the radio station's computer room. Therefore, she would not be able to perform lengthy and complex calculations. Of course, lengthy and complex is a relative term, but she is a sufficiently accomplished mathematician and she needs to perform this task in less than one minute.

What strategy can be done by the spy and the government so that she can pass the mafia leader's identity accurately with that one chance?

Remark: The following weaker versions of the problem are due to David Rager:

1. Prove that if there are 3 mafia members and 3 bit number lottery winner, you can pass the information with only 1 flip.

2. Prove that if there are 27 mafia members and 27 bit number lottery winner, you can pass the information with only 3 flips.

Solution:

This problem is identical to the room and lights game puzzle available here: http://dharmath.thehendrata.com/2009/10/02/prisoners-and-hats/

The solution is available there.