Problem 605

[shirtandtieler]

Hello all, I have some confusion as to how the examples were reached in problem 605, and I'm hoping someone can at least point me in the right direction.

The premise of the problem is based on a game that's played with n people where each round has a coin flip to determine which of two players (who are chosen in sequential and circular order) wins that round - e.g. in a 3 person game, round 1 is player 1 vs player 2, round 2 is player 2 vs player 3, round 3 is player 3 vs player 1, etc.. Once a person wins two times in a row, they win the whole game.

The problem itself involves the probability P_n(k), where n = number of players and k = the target player to win the whole game. Examples given include: P₃(1) = 12/49 and P₆(2) = 368/1323, where each probability is a reduced fraction.

I attempted to find P₃(1) myself by writing out a timeline with chances for the given events, like so:

== Round 1 ==
Player 1 wins: 1/2
Player 2 wins: 1/2
Game Over    : 0

== Round 2 ==
Player 2 wins: 1/2
Player 3 wins: 1/2
Game Over    : 1/4
(Winner=Player 2)

== Round 3 ==
Player 3 wins: 1/2
Player 1 wins: 1/2
Game Over    : 1/4
(Winner=Player 3)

== Round 4 ==
Player 1 wins: 1/2
Player 2 wins: 1/2
Game Over    : 1/4
(Winner=Player 1)

And since I want game over in rounds 2 and 3 to not happen, I took the inverse of those probabilities (i.e. 3/4) and the probability that the game ended in round 4 (i.e. 1/4) and found the product, which came out to be 9/64...

Am I missing something about the problem? Or is it a problem with my (admittedly limited) knowledge of probability theorem? Thanks for any help that you guys can provide

[MuthuVeerappanR]

Dear shirtandtieler,
First of all, we are supposed to create problem specific questions in Clarifications on Project Euler Problems rather than here.

Second as the problem is relatively new, I don't know how can I clarify your doubt without spoiling the problem. But lemme say this: If you are trying to solve for $P_3(1)$, try enumerating instances where only the first player wins. then further break it down to the possible sequence where the first player wins round 1, round2, round3, etc.

You are trying to calculate a lot of things in one go which both complicated and (I think) wrong.

[DJohn]

Am I missing something about the problem? Or is it a problem with my (admittedly limited) knowledge of probability theorem? Thanks for any help that you guys can provide

It's a bit of both.

You're trying to find the probability that player 1 wins on round 4 (and no other), but P_3(1) is the probability that player 1 wins on any round. If they don't win on round 4, they might have another chance on round 7, then 10, and so on.

You've also got the probability for a win on round 4 wrong.

[shirtandtieler]

Dear shirtandtieler,
First of all, we are supposed to create problem specific questions in Clarifications on Project Euler Problems rather than here.

Second as the problem is relatively new, I don't know how can I clarify your doubt without spoiling the problem. But lemme say this: If you are trying to solve for $P_3(1)$, try enumerating instances where only the first player wins. then further break it down to the possible sequence where the first player wins round 1, round2, round3, etc.

You are trying to calculate a lot of things in one go which both complicated and (I think) wrong.

As for the location, I do apologize about that; I had debated which board would be better (i.e. combinatorics or Clarifications) and thought I would be going against the warnings of this not being a place to discuss solution methods or hints. But seeing that this is my first post here, I'm not debating your ruling

Regardless, thank you for the insight! That actually makes a lot more sense than my attempt and I'll give that approach a go!

[guy.scrum]

I feel like I must be misreading the problem statement here, because I've tried calculating $P_3(1)$ three different ways and keep end up getting $8/31$ instead of $12/49$. The most straightforward way, and the most literal way to translate the problem statement, is to just simulate a bunch of different instances of the game and calculate the frequency at which player one wins. To do this, I generate a large random binary string, find the first index $i$ at which "11" appears, and assign a win to player $(i\mod 3) + 1$. But again, that gets me a win frequency of $\sim 8/31$ for player 1, and I don't get $12/49$ for any of the other players either.

Is anyone else running into this problem? Is there some subtlety to the rules that I'm not appreciating?

[RobertStanforth]

Is there some subtlety to the rules that I'm not appreciating?

Remember that the game ends when the same player wins twice in a row.

[guy.scrum]

Is there some subtlety to the rules that I'm not appreciating?

Remember that the game ends when the same player wins twice in a row.

Ah, silly me, I was thinking that looking for two of the same coin flip was equivalent. Thanks!

[petrf]

I understand the problem description in the way that the chance to win for the second player is always \(\frac{1}{4}\) regardless of the players number.

Because player2 plays round 1 against player1 and the chance to win is \(\frac{1}{2}\). The second round is player2 vs player3 and the chance for player2 to win this round is again \(\frac{1}{2}\). So the chance the whole game is over after this two rounds is \(\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\). And this does not depend on the number of the players. So \(P_n(2) = \frac{1}{2}\) for any \(n\).

What I misunderstand?

[traxex]

If nobody wins during the first round of the circle, the game continues. The second player also has a chance to win a later round. You can see from the provided example that P_6(2)=368/1323 > 1/4.

[Animus]

So the chance the whole game is over after this two rounds is \(1/2 * 1/2 = 1/4\). And this does not depend on the number of the players.

Correct.

So \(P_n(2) = 1/4\) for any \(n\).

False, $P_n(2)$ is the probability that the game ends after 2 rounds, or after n+2 rounds, or after 2n+2rounds ect.