So today I encountered an interesting math task that I would like to share with you:
There are 2 old men and 16 stones. All stones are coloured in 4 different colours, there are 4 stones of each colour. 2 men play game: each round they randomly pick 1 stone from the pile, after every round they switch turns. The game ends in victory, if one of the men has gathered 3 stones of the same colour, otherwise it's a draw. The task is to calculate the probability of the game ending in victory.
Now, I already know the answer for this problem, but I would love to see how cf community is gonna solve it, cause there's 1 detail about this problem that I consider interesting. I'll share it after some answers.
The answer is 1 — P(2-2 split for every color) and assume all rocks are distinguishable for easier computation to get 1-(4c2)^4/(16c8) = 643/715.
How did you calculate all possible outcomes?
my guess is 1-draw will end up victory. So each one will ccertainly have 2 stones each.
we need to calculate that each person ends up taking 8 stones of 4 different colour that is player A={2,2,2,2}~10/100 so most likely ans is 1-10/100=90/100(very much approximate)
tho i can wrong with probability p=99/100.
thanks.
is the answer 1-((8c2 * 6c2 * 4c2 * 2c2)^2)/(16c4 * 12c4 * 8c4 * 4c4) ? My idea is that the game ends in a draw if both players end up with 2 stones of each colour, so i just count the probability of getting that configuration and then subtract from 1
hmmmm, I think the answer is $$$\tfrac{643}{715}$$$
The losses are $$$\tfrac{72}{715}$$$. A loss happens when both players get exactly 2 of each color. Otherwise, one of them will have 3 or more.
You can just concatenate all choices into a sequence of length $$$16$$$. Since the process is random, all sequences are equally likely.
The positions for each player are fixed (for example, player 1 has $$$1,4,5,8,\dots$$$ — 8 positions total). We need to count the bad sequences and divide by the total.
Total sequences: $$$16!$$$
Bad sequences: for every color, choose 2 for the first player $$$\binom{4}{2}$$$. For 4 colors: $$$\binom{4}{2}^4$$$.
Arrange them in the 8 fixed slots: $$$8!$$$ ways for player 1, and $$$8!$$$ for player 2.
So bad = $$$\binom{4}{2}^4 \cdot 8! \cdot 8!$$$, and probability = $$$\dfrac{\binom{4}{2}^4 \cdot 8! \cdot 8!}{16!} = \tfrac{72}{715}$$$.
Final answer: $$$1 - \tfrac{72}{715} = \tfrac{643}{715}$$$.
orz
So I'm gonna summarise my answer to all higher comments under this comment. Yeah, basically 643/715 is the correct answer to this problem, it can easily be seen, using Monte Carlo method, that probability is approximately 0.90 (while 643/715 = 0.899...). The thing I faced with this problem is that the solution was kinda counter intuitive (for me at least). The first thought would be to calculate example with 1 — m/n, where m — is undesirable outcomes and n — all possible outcomes. However, if we consider that outcome doesn't require all stones to be picked, this formula will lead to a wrong answer, because all these outcomes aren't equally possible. This thing bugged me out the most, cause it wasn't intuitive for me and I couldn't see that for quite a long time. The coorect approach would be to extend the rulse of the game, so that all 16 stones would have to be picked (even after the win). This way all outcomes are equally possible and our formula works (also it mathematically explains why original outcomes didn't have evenly distributed probability). The second thing I'd like to point out is that inattentively ignoring and disregarding the rule about the game's end would also lead to a correct answer (as I've seen with some of my friends), but in this case I believe that logic is a bit flawed as it condradicts the rules of the game without explaining the reason for doing it. So this is also one of the rare cases, when incorrect approach can lead to a correct answer.
The logic is not flawed. You think that because Baskot and defactopdiddy haven't explain theirs solutions well enough for you to understand why they work. I will try to explain Baskot's approach(I believe that my explanation for his solution is a bit simpler to understand). Just think that you will allow your players to play after one of them has won. Notice that sum of probabilities for all continuations is equal to the probability of just this game if you would have assumed that they will stop playing, because its just:
Thanks to this we know that we can compute the probability of a game ending in victory, so the probability of the complement of the victory(draw) too.
That's what I said btw: "The coorect approach would be to extend the rulse of the game, so that all 16 stones would have to be picked (even after the win)."
My concern wasn't that logic tho, it's the fact that if a person inattentively decides to ignore the fact that by original rules game has to end after the win (which I define as a flawed logic since in this case mentioned person extends the rules by mistake and not as a part of solution), then it would still lead to a correct answer. I didn't make this assumption about these 2 people so I don't really understand what you're talking about.
And I understand the solution since I've already solved this task by myself.
I thought that you've solved the problem but you think that some solutions might be flawed(and I thought that you meant the solutions posted as comments under this post). Is it unreasonable based on your comment? I'm sorry if I've understood something wrong, but for me not explaining it fully and the word 'inattentively' in this context don't mean that someone isn't aware of the logic why they can do this, though it might be because English is not my first language.
That's okay, it might also be the fact that English is not my first language either)
Ok think about it like this, once you reach a bad state(one of them has 3 of one color) then you stop. This is the same thing as going through all permutations of the remaining rocks and calling them all bad because you already hit a bad state. So regardless of them continuing to play or not the answer will be the same.
Yeah, I see.
P(Draw) = ((4C2)^4) / (16C8) = 72/715; P(Win) = 1 — P(Draw) = 1 — 72/715; => P(Win) = 643/715;