7
20d ago
[removed] — view removed comment
1
u/marty-mcfryguy 19d ago
Why would randomizing get you M=2026?
Randomizing would get you a win rate of 50%.
1
u/Fireline11 18d ago
The joke is that you "randomly" guess 2026 because it's the 2026 integral cup.
(That would not really be a random guess, but it fits with the more colloquial use of "random" to mean anything unexpected or without reasoning)
7
u/traderftw 20d ago
Well if you see a 1 or 1014, then you know how to win, so if the distribution was uniform you have at least 1/2 + 1/507. So what does the oracle do? They can't exclude 1 and 1014, or they'd just end up excluding everything. I suspect the condition is pgame with 1 and 1014=(1-p)game without and p looks like 1/507 or something. So M would end up looking like 1/5072? I'm not really sure I majored in math 14 years ago
8
u/dafugiswrongwithyou 20d ago
what does the oracle do? They can't exclude 1 and 1014, or they'd just end up excluding everything.
So there are these students, right? And on the Friday one week, just before the end of the day, the teacher says "I'm going to give you a Maths test next week, but I'm not telling you which day; it'll be a surprise. Nothing to worry about, you're all smart kids!"
That weekend, two of the students are discussing this. "Well, if we get to Friday and haven't had the test, we'll know it will happen then, and that wouldn't be a surprise, so can't be on the Friday." "Huh. Well, that means it can't be Thursday either, right? I mean, we know it can't be on Friday, so if we got to Thursday we'd be expecting it, and that wouldn't be surprising either!" "Hey, you're right! And that means it can't be on Wednesday... Or Tuesday, or Monday! She can't run a test at all!"
On Tuesday, the teacher hands out papers for the maths test. These students are surprised.
2
1
u/Fireline11 18d ago
They can't exclude 1 and 1014, or they'd just end up excluding everything.
This does not follow because they know your strategy, but you don't know theirs. So after you have decided on your strategy, they will pick the numbers to test it to its limits. For example: even though you will have an easy time if 1014 is flipped (if your strategy is even a little bit decent) you might still have trouble (depending on your strategy) when 1013 is flipped. If they pick 1013 and 1014, you might then only be succesfull one half of the time.
2
u/Fireline11 18d ago edited 18d ago
This is a really fun problem! Here's how to formalize the proof in case anyone is interested.
Your strategy can be summarised by a probability distribution. When card i is shown, you will yell "greater" with probability P(i) and "smaller" with probability 1 - P(i).
If your opponent chooses numbers 1 <= i < j <= 1014, you'll be right in two cases
- Card i is flipped and you yell it's smaller. Probability (1 - P(i)).
- Card j is flipped and you yell it's greater. Probability P(j).
Your total success probability is therefore
1/2 *( (1 - P(i)) + P(j)) = 1/2 + 1/2 * (P(j) - P(i))
That means for a successful strategy P, you want P(j) - P(i) to be larger than 2 / M for all i and j, since your opponent knows your probability distribution and is free to choose i and j.
Now we can write the telescopic sum of 1013 differences and apply inequalities:
1 >= P(1014) - P(1) = (P(1014) - P(1013)) + (P(1013) - P(1012)) + ... + (P(2) - P(1)) >= 1013 * (2/ M)
which shows M >= 2026.
Can we find a distribution P where P(j) - P(i) >= 2/2026 for all j and i? Yes, set P(i) = (i - 1) / 1013.
Since P(j) - P(i) = (j - i) / 1013 > 1/1013 = 2/2026 for all j > i. That proofs M = 2026.
1
u/two_are_stronger2 20d ago
Without the oracle, choose the middle of the interval and if the reveal is greater than 507, the response is "smaller" and vice versa. But if the oracle knew your strategy, she'd just put them on both sides of your partition value. So choose a random partition value, then she can't reliably put them on both sides of it. So she would instead make that target as small as possible and choose consecutive numbers. So now on the 1/1014 chance you match, you have a 50:50 chance (she'd obviously never choose the maximum or the minimum since you'd have a 100% chance on a match). So M is 2028.
1
u/Alive_Carpenter_7433 19d ago edited 19d ago
It would actually be 1/1013 chance to match. Your partition value could be 789.5, so you have a 50% chance if the consecutive pairs were less than 789.5, and 50% if it was greater. But if the 2 numbers happen to be 789 and 790, you win 100%. The trick is that there are 1014 numbers, but 1013 gaps btwn numbers for your partition to fit into. Thus every 1/1013 chance of getting the partition in between bumps M to 2026.
1
u/Alive_Carpenter_7433 19d ago
In addition, this still works for boundless real numbers. Simply expand your partition to every real number as well, from -infinity to infinity. Now it becomes a losing game of chance for the oracle, needing to dodge the minefield of the partition number. At best, its a 50% chance if the partition was off, either the higher or lower number could be revealed and correct. At worst, you picked a real number between the 2 the oracle chose. With infinite time, Your win rate will still be small but slightly higher than the oracle. (Ofc this assumes you have something that can generate a number with infinite precision).
1
u/dezholling 19d ago
Boundless is interesting. It doesn't really work but it also "sort of works". On the one hand, it is impossible to create a distribution over a boundless region that does not vanish in probability as you go to infinity, so we know P(n<x<n+1) -> 0 as n -> inf. Because the Oracle knows your distribution, she will just choose her value to exploit it. On the other hand, she must choose a finite number, so in practical terms there is some small but nonzero advantage you get, as you say. The problem is that the advantage isn't bounded. For a guaranteed winning probability of 1/2 + 1/M, there exists no M you can claim to achieve. For any arbitrarily large value of M you want to claim, the Oracle can target consecutive integers that does not achieve your claim. The only thing that could potentially give you an M to claim is to bring in practicalities like a time limit to write down the integers or a space limit on the cards.
1
u/Alive_Carpenter_7433 19d ago
Yes, but at the end of the day, it is technically strictly greater than 1 half. For the vanishing proabability, you could create a bell curve of every number, the normal distribution centered around 0. So every number is technically feasible, while it doesnt technically create a limit to the potential of your numbers, the oracle still loses a fraction of the time
1
u/two_are_stronger2 18d ago
Dang. I'm always the one who thinks of edge cases others miss too. Thank you!
1
u/Big-Excitement-11 20d ago
for the infinite set case, you can make a strategy such that the oracle can write numbers getting the win probability arbitrarily close to 1/2 but never equal to 1/2. this is the best you can do
1
u/Available-Light-8458 20d ago
Tge oracle will always choose adjacent numbers to minimise your chances of winning.
1
u/TheLonelyPotato666 19d ago
If i had this question in a competition, i would not consider randomizing as a strategy, and id be pissed if other people got it right simply because the answer is 2026
1
u/marty-mcfryguy 19d ago
The approach here is to randomize your guess based on the revealed card, i.e, "If I see integer [n], I will guess 'higher' [P_n]% of the time, and of course therefore guess 'lower' [1-P_n]% of the time."
In other words, you'll have a table of n and P% values, that looks something like
n P_n%
1 100%
2 99.9%
3 99.8%
...
1012 0.2%
1013 0.1%
1014 0%
So if you're shown a 1012, then 0.2% of the time you'll guess "higher", and 99.8% of the time you'll guess "lower".
What the oracle knows going in is the exact table of n/P_n% values you're using.
The ideal approach (with k different values) is to look, for each n, at the number (x_n) of different values that are greater than n, and set your P_n to simply equal x_n / k-1.
So with k = 1014 distinct numbers, then for n = 1 (which gives x = 1013) you obviously set it to P_1 = 1013/1013 = 100% of the time you guess "higher".
For n=2 you rate that down slightly; x=1012 and you set P_2 = 1012/1013 = ~99.9013% of the time you guess higher.
For n = 506, you get x of 507 and use P_506 = ~50.0494%.
n = 507 => x = 506 => P_507 = ~49.951%
Why do you set it that way? Anything else is suboptimal.
Obviously for n = 1 you're always going to use 100%. But for n=2, if you also use 100% then you're opening yourself up to her attacking you by picking 1 and 2 as her two numbers: In the actual game, if she's picked 1 and 2, and you use P_2 = 100%, then:
If 1 comes up, you guess higher and you win (because the other is 2). But if 2 comes up you also guess higher, and you lose. Both are equally likely, so probability of you winning is only 50%.
So you want to use a lower value for P_2. Let's say you're worried about her picking 1-2, and so you bring P_2 way down, to 50%. Then if 1 if comes up you still always win, and if 2 comes up, then 50% of the time you guess higher and lose but 50% you guess higher and win, meaning you win 50%*100% + 50%*50% = 75% of the time.
Which is great, but now you're weak to other combos she might pick. If instead of 1-2 she picked 2-3, now the fact that you're guessing "high" half the time on a 2 hurts rather than helps, and the only way to get a 75%-of-the-time win rate (like you have for 1-2) is if you set P_3 to 0%; meaning you *always* guess "higher" if a 3 shows up. Which of course means that if she pairs a 3 with anything lower you're screwed, and always lose if a 3 shows up.
So you can't be that greedy when setting P_2. You can raise your win probability by dropping it from 100% to something a little lower, but if you try to raise you win probability all the way to 75% you're going to screw yourself in the other combos.
What you need to do is balance it, and set P_n = x_n / (k-1) as above.
For P_2 that's 1012/1013. For P_3 that's 1011/1013. And you can see how that balance: if she goes 1-2, then your odds of winning are 100% if the 1 comes up and (1-(1012/1013)) = 1/1013 if the 2 comes up, for overall probability of 50%*[1 + (1 - 1012/1013)] = 50% *(1014/1013). Same result if she goes with 2-3, but now it's 1012/1013 if the 2 comes up and (1-1011/1013) = 2/1013 if the 3 comes up, so again it's 50%*1014/1013.
So that's how you play it, and you're guaranteed a win percentage of no worse than 50%*1014/1013 = 50% + 1/(1013*2) = ~ 50.0049%.
From the oracle's perspective, she's always going to want to do a pair of numbers exactly one apart, to squeeze you as much as possible. For example if she picked 1-3 rather than 1-2, she's just giving you free win percentage whenever the 1 does not come up. That is, you're going to choose "lower" more often when a 2 comes up than you will when a 3 comes up, meaning if she's letting you see a 3 rather than a 2 you're going to steal a win every now and then (exactly 1/1013 of the time when the 1 doesn't come up).
Same deal with any pair of numbers, and any spread. Given the approach she's forcing you into, it would be silly for her to choose, say, 200-450 when 200-201 would mean she wins more often when the 200 doesn't come up. Similar to "Price is Right" bidding logic.
1
u/Same_Art_6971 18d ago
Declare that face up number i is the larger one with probability p_i = (i-1)/1013 and that it's the smaller one with probability 1-p_i = 1-(i-1)/1013. This way the optimal strategy for the oracle would be to pick any two sequential numbers, but we can still guarantee our win with probability (p_(i+1)+(1-p_i))/2 = (i/1013 + 1 - (i-1)/1013)/2 = (1 + 1/1013)/2 = 1/2 + 1/2026
M=2026 (what a surprise)
1
u/Cool_Homework_7411 20d ago
I can see a way to get the winrate up to 1/2 but not over it. If you choose completely randomly whether to swap or not you have 50% chance of guessing correctly(if you just guess after the oracle but before the referee reveal) plus a minor chance that the other number is an edge case where you can beat the oracle, but the oracle wouldn't put the numbers there since then they would make the game solvable. The same logic doesn't apply to the number 2 since if you have a strategy (eg if the number is below a certain threshold, swap) the oracle will know it and can beat you, you have to be random
So I would say a strategy to get to 1/2 is to flip a coin after the referee and stay depending on that
1
u/OneSharpSuit 20d ago
Given the referee chooses randomly, “always say over” (or under) is equivalent to flipping your own coin.
Still not sure how to beat it, though.
1
u/lesuperhun 20d ago
(1 and 1014 are deterministic outcomes : if you see them, you automatically know you cannot lose : the other number is known to be under/over : those are the two that tip you over, with odds of 2/1014 per card, )
but, those would only grant you an advantage if the oracle chose them. and they won't, since they'd make you win.
but then, we reach paradox territory.because now, we know they are choosing a number between 2 and 1013. and can repeat the whole thing to exclude them again.
as such, the oracle can't choose any number willingly. so i'll just assume they're gonna pick two at random.
but, skipping over that : given the one revealed is random, saying something, no matter what, makes you win 50% of the time. just say "under" if it's 1014 and "over" if it's 1.
that's why the second one is harder : as it is a real number, there is no more edge, and the only way to gain an edge is to attempt a bribe. the odds of it working aren't zero, so the final odds would still be over 1/2.
1
u/OneSharpSuit 20d ago
Psychic Oracle avoids the paradox, because if it knows you’ll pick over on a 2 then it can select [1,2] and limit you to a 50/50 win rate
0
u/Jman15x 20d ago
She knows what you are going to say so she flips the card that makes you lose. I don't get it
3
1
u/Fireline11 18d ago
Order is as follows:
1.. You chose your strategy
2. She chooses the numbers
3. Referee flips one of the two numbers ***at random***
11
u/InfiniteJank 20d ago edited 20d ago
Pick a number uniformly at random between 1 and 1014, excluding the face-up number. If the face-up number is higher than the number you chose, guess that the face-up number is the higher of the two cards. Otherwise, guess that it is lower.
Your chance of winning is (1013-(lower card))/2026+(higher card)/2026, so your edge over a coin flip is the difference between the cards over 2026. Therefore the oracle can enforce M = 2026 by choosing consecutive integers.
Conversely, no matter what your strategy is, the oracle can restrict you to this edge by choosing a pair of consecutive integers in the range uniformly at random. There are 1013 such pairs, and there will be a 1/1013 chance that a 1 or 1014 is flipped over, but if any other number gets flipped your odds are exactly 50-50, since there are exactly two scenarios that any given number could appear flipped except for 1 or 1014. This limits you to an M = 2026 edge no matter your strategy.
For the bonus, you can get an arbitrarily small but positive edge by taking a probability distribution supported on the entire real line and sampling from that using a similar strategy as before.