(a)
Let us assume that the magician and the assistant can perform for a number n. Then, the assistant has a way to change all possible settings of heads/tails into a setting that the magician will interpret as any given number. In other words, the duo have a way of interpreting any setting of heads/tails as a number from 1 to n, and changing any setting to a setting that reflects any given number.
How to do it: assume the audience choose k.
1. The assistant, given the setting of 2n coins, pairs each coin up with another one, to form n pairs.
[O O] [O O] [O O] ...
2. He interprets each pair as an individual coin by the following scheme: two heads or two tails = a head, a head and a tail either way = a tail. Let's call these new n coins "p-coins."
3. He calculates the remainder of k / n, replacing 0 with n. Let this be x.
4. He decides which p-coin to flip so as to make the p-coins show x. (He doesn't flip it or anything.)
5. He calculates r: if k > n, r=1, otherwise r=0.
6. He looks at the second coin of each p-coin, and computes how many heads are among this set of n coins, not p-coins.
7. He finds the result of step 6's remainder when divided by 2. Call this s.
8. He compares r (step 5) with s (step 7). If they are equal, then flip the first coin of the step 4 p-coin. If they are different, flip the second coin of the step 4 p-coin.
How the magician interprets:
1. Change the coins into p-coins by pairing them and valuing them with two alike = head and two unalike = tail like above, and calculate the p-coins' number like above.
2. Count the heads in the second coins of each p-coin. If the number is odd, add n to the step 1 number. Otherwise, do not.
This is the number.
Proof: Clearly, the p-coins can represent a number of our choice, and they are designed so that flipping any coin in a p-coin will change the p-coin, so that 2n coins can show a number from 1 to n. Now, we want to show a number from 1 to 2n, so we have the second-coin head count. Flipping any second coin will change the count's parity, while flipping any first coin will preserve it. This bit of information can decide between x and n+x. Now, from flipping the p-coin we have narrowed the flippable coins to a first coin and a second coin. The head count narrows the flippable coins to either all first coins or all second coins, and clearly now exactly one coin will work.
Q.E.D.
_________________
This statement is false.
   
Conclusion: "This statement is false" is not a statement.
|
