Actually, this is a well-known conundrum. The best exposition I know is by Martin Gardner, chapter 10 in Penrose Tiles to Trapdoor Ciphers. It originally appeared as a Mathematical Games column in the early 80's, I believe. (No, I'm not that old, it's just your imagination.) It brings up some very interesting problems in mathematical induction, upon which your solution is based.

Try this on for size: your solution works even if C is totally blind! Read MG for the whole scoop.