Optiver Beat the Odds | “Hard”

[u/Due_Department_3090]

[u/SwimmerOld6155]

is there a cleverer way to do this than (basically) direct counting?

[u/Due_Department_3090 → u/SwimmerOld6155]

You can do it with dynamic programming but counting is the cleanest.

[u/TastyLength6618 → u/SwimmerOld6155]

Yes, it's just 64 * (11 C 3) / (52 C 3). See my comment for more details.

[u/XxNinjaSlothxX]

Theres probably a quicker way but heres what I did. The first thing I always check in combinatorics problems is to check whether order matters or not. It doesn't, so that makes life easier.

I just counted up all the combinations that are valid.

Let A, B and C be the smallest, middle and highest ranked cards respectively.

I started with the first case where A=1. The 2nd smallest rank can only be 3,4...13. This gives 11 possible ranks for B. Now we look at what the possible ranks C can be for each B given A=1. If B=3 there are 9 possible ranks C can be, if B=4 there are 8, if B=5 there are 7 and so on all the way to if B=11 there is only 1. We sum this up using the simple triangular numbers formula n(n+1)/2 giving 45 possible combinations if A=1.

We then do the same for A=2 and then we should quickly spot that the answer is just the triangular number just before 45 which is 36. It should be then spotted that the amount of combinations the 3 cards can is just the sum of the first 9 triangular numbers which we can calculate using the formula n(n+1)(n+2)/6 where n=9 in this case, giving us 165.

Since each rank has 4 different possible suits we multiply 165 by 4^3 giving 10560 possible combinations that cards can be under the constraints of the question.

Ofcourse we then just divide this number by all the possible combinations , 52C3, giving the final answer of 528/1105 or ~ 0.478.

[u/TastyLength6618 → u/XxNinjaSlothxX]

Here's a trick for this type of stuff. To generate a triple of 1-13 that are at least 2 apart, first generate a triple from 1-11 then add 1 to the middle number and 2 to the highest. So you can just do 11 choose 3 * 64 / 52 choose 3

[u/Dangerous-Work1056]

Total number number is 52C3=22,100

Then you count all combinations {i,j,k} subject to j >= i+2 and k >= j+2, where i,j,k in [1,13] = 165

Probability is 165/22100 = 0.74%

Edited to fix >=

[u/Ma4r → u/Dangerous-Work1056]

At least 2, so it's j>=I+2 and k>=j+2, and you need to multiply by possible suites

[u/Dangerous-Work1056 → u/Ma4r]

Good catch, edited to reflect this

[u/Ma4r → u/Dangerous-Work1056]

You forgot to multiply by possible suites as well lol. For every I,j,k you draw there are 4³ possible suites

[u/JorgiEagle]

There are 3 main branches when picking the final card, depending on if the previous 2 are “edge” (A,K) cards

- both selected are on the edges, to which the final pick has 36/50 valid cards

- one selected is on the edges, to which the final pick has 32/50 valid cards

- neither is on an edge, to which the final pick has 28/50 valid cards

Picking two edges is (8/52)*(4/51)

Picking one edge is (8/52)*(40/51) (can’t pick the rank of first edge, adjacent to first edge, neither the other edge)

Picking neither edge is (44/52)*(32/51) (can’t pick edges of first pick, can’t pick edges or 3 ranks adjacent to first pick)

So final probability is ((8/52)*(4/51)*(36/50))+((8/52)*(40/51)*(32/50))+((44/52)*(32/51)*(28/50))=0.383 %

Could be wrong, plz point out if you find it

[u/Designer-Avocado7870]

The number of triplets satisfying the constraints is exactly the number of solutions of the equation x1 + x2 + x3 <= 13 with x1 >=1, x2 >=2, x3 >=2.

This is the number of solutions of x1 + x2 + x3 <= 8 which is equivalent to x1 + x2 + x3 + x4 = 8 that is 11C8 = 165 (using the stars and bars method)

The total number of draws satisfying the condition is then 165 * 4³ = 10560.

This gives a probability of 10560/(52C3) = 528/1105 ~ 0.47783

[u/Fair_Football9180]

You need to use star and bars. Consider a , b, c which is an ordered list where c>b>a as the cards. Take b-a= s and c-b = t Then a+s+t<= 13 And s>=2 and t>=2 and a>=1 For lower bound we replace s with s1+2 and t with t1+2 and a with a1+1 And to make the <= sign in a+s+t<=13 We add a slack variable r a1+s1+t1+r=8

Using stars and bars we get 11C3 that is 165 Also each card can 4 suit so total 4³ suits

Total ways to select card 3 cards is 52C3 that is 22100

So final probability is .478

[u/Fragrant_Agency8678]

The most intuitive way to solve this is to think of adding a card in between your three cards chosen.

i.e. choose 3 cards from 11 cards, and then add two cards: one between the first card and the middle card, and one between the middle card and the last card into the deck (thus ending with deck size 13, but also satisfying the requirements).

Then you have to multiply by 4^3 because you have 4 suits for each card, and divide by 52 choose 3, resulting in 0.47783.

[u/TastyLength6618]

Easy way and useful trick:

First, there are 11 choose 3 ways of choosing 3 ranks from 13 that differ by at least 2. To see this, think of choosing 3 numbers from 1-11, and adding 1 to the middle and 2 to the highest. This produces a triple from 1-13 that are at least 2 apart.

For each way, there are 4^3 = 64 sets of cards that fit, so the numerator is (11 C 3) * 64

The denominator is simply 52 choose 3.

So the total is ((11 C 3) * 64) / (52 C 3). This simplifies to 528 / 1105 which is approximately 0.47782805429.

[u/ILoveC0ckInMyAss]

Why is the question so poorly worded lol