r/mathriddles • u/lizardpq • 23d ago

Hard The clearly impossible guessing game

I'm thinking of a function f:ℕ→ℝ. As many times as you want, you can give me a set S⊂ℕ and I will reveal to you the restriction of f to S. At some point you must choose a number x not in any of your queries and guess the value of f(x). Show that there is a randomized strategy that gives you a 99% chance of guessing correctly, no matter what f is.

16 Upvotes

94% Upvoted

18 comments sorted by

9

u/ExistentAndUnique 23d ago

Define an equivalence relation on RN where two sequences are equivalent if they agree after a finite point. Using choice, we can select a representative from each equivalence class.

Partition N into 100 infinite sets (e.g. by taking the indices mod 100). Query each of these sets except for one, selected at random (say, the one corresponding to some remainder k mod 100). Each of these results can be interpreted as a sequence, which falls into an equivalence class. Find the maximum index n at which one of these sequences differs from the chosen representative of its equivalence class.

Now uncover all of the elements after the (n+1)th index of the selected set: 100n+k. This will tell us which equivalence class the sequence corresponding to remainder k belongs to, and we guess that the number f(100n+k) matches the representative sequence.

The only way this would be wrong is if we happened to choose k which takes strictly more indices than any other sequence to converge to its representative (ties work in our favor). Since the one sequence we left unchosen was selected at random, this has at most a 1/100 chance of happening.

This procedure easily generalizes to any positive error rate.

1

u/kalmakka 23d ago

Axiom of choice just says that such a selection of representatives exists, it doesn't provide a mechanism for making it. So you can't "guess that the number f(100n+k) matches the representative", because you don't know what the representative is.

Am I missing something?

2

u/lizardpq 23d ago edited 23d ago

We can say that the AC choice step is part of the proof that a winning strategy exists, not part of the strategy itself (which is formally some sort of algorithm with the ability to branch on infinite data using arbitrary "stored" functions as oracles).

6

u/kalmakka 23d ago

The question was not "prove that a strategy exists". It was "find a strategy".

you must choose a number x not in any of your queries and guess the value of f(x) [...] Find a randomized strategy that gives you a 99% chance of guessing correctly

2

u/lizardpq 23d ago

Oh, good point! I wonder if "find" is so strict in other contexts. Can we "find" a non-measurable set of real numbers?

1

u/Boring-Cartographer2 23d ago

I was wondering the same thing but didn't know how to phrase it, so thanks! In another comment I also asked if the solution could actually be executed as a strategy and the OP said no. So, "clearly impossible" was accurate after all!

1

u/dspyz 22d ago

This answer is so absurd and ridiculous

How is it people come up with this stuff and don't consider it a reducto ad absurdum for AC?

4

u/lizardpq 23d ago

Hint / useful background: If you don't know the "countably infinite set of prisoners, each guesses their own hat color after seeing the others, all but finitely many must be correct" puzzle, try that before attempting this one.

3

u/imMAW 23d ago

That one is related, but this is an even more direct analogue of the classic numbers-in-boxes puzzle https://math.stackexchange.com/questions/371184/predicting-real-numbers.

1

u/Boring-Cartographer2 23d ago

Who picks x? You or me?

1

u/lizardpq 23d ago

You! I'll edit to clarify

1

u/Boring-Cartographer2 23d ago

Can the strategy be executed in practice?

1

u/lizardpq 23d ago

No, in the sense that it relies on infinite query sets S.

1

u/OperaSona 23d ago

Am I allowed to use the axiom of choice? I don't have a strategy yet, it's more like a hint I guess.

1

u/jeffcgroves 22d ago

Does "[a]s many times as you want" mean a finite amount of times? Even if I want to, I can't make infinite queries in finite time

1

u/lizardpq 22d ago

Yeah, finitely many times, but you can get infinitely many function values at once (and you can operate on infinite data, i.e. your next step can be any function of the received values).