Here is another of my favorites: Player 1 thinks of a polynomial P with coefficients that are natural numbers. Player 2 has to guess this polynomial by asking only evaluations at natural numbers (so one can not ask for $P(\pi)$). How many questions does the second player need to ask to determine P?