Ok, This is an extension of my binary coin idea.

How about creating a logic trick on the table. You get four (or more) coins and say that heads are 1's.

You then get some paper and draw logic gates on them ie. NOT, NAND, AND, OR, XOR and so on.

You get the spec to toss the four coins then try to pass them through the logic maze.
Some research on logic puzzles should give some basic idea of the most challenging puzzles.
The idea would be to make the spec play the game when only one binary solution is right.
I think I will mark this down for later this year unless one of you would like to run with it.