## Round 5: Problem 6

Let’s play a game.

A fair die is rolled repeatedly until two consecutive rolls are equal, at which point the game ends.

If we let S be the sum of the results of all of the rolls, is S more likely to be even or odd, or is it equally likely to be both?

Advertisements

Let s be a sequence, k = |s|,

For k = 2, S is even.

For k > 2:

Let a be the first element of s,

if a = 1, pair s with sequence s’ with a = 2,

if a = 3, … a = 4,

if a = 5, … a = 6.

Since all sequences with k > 2 can be paired as such,

There’s slightly higher chance of S being even.

anonymousMay 13, 2009 at 18:10

For odd k>2, it’s obvious: for every finite die roll sequence, map it to the sequence where each term is 7 minus the corresponding die roll in the original, and that will have the opposite parity. So there’s an equal chance of odd and even, without losing the condition that only the last two die can be a consecutive double.

For even k>2, it’s not so easy. Your argument doesn’t work if the first element of a particular sequence is 1 and the second element is 2. I thought this didn’t matter, but someone told me that these aren’t (always?) balanced. I haven’t check it myself yet, but I used a similar (and similarly faulty) argument.

Franklin LeeMay 13, 2009 at 22:14

The answer IS even, but it’s a smaller chance of being even than the faulty argument would suggest.

Franklin LeeMay 13, 2009 at 22:20

I don’t see what’s wrong with Mr. Anonymous’s argument. He is just pairing any sequence of length > 2 with the identical sequence in which the only change is to the first term.

Furthermore, there still needs to be some kind of argument that not all length sequences are equally likely. Indeed, 1 out of 6 times, the sequnce will have length 2 and the sum will thus be even. The remaining 5/6 of the times have an equal chance of being even or odd.

jimMay 15, 2009 at 19:53

Take the sequence 1233. If you change the 1 to a 2, making it 2233, then the sequence is invalid, because there’s no way to get a 3 after two 2’s in a row (because you would’ve stopped).

Take two random dice rolls, x and y, such that x is not equal to y. If x is odd, then y has a 2/5 chance of being odd and 3/5 chance of being even, so x + y has a 3/5 chance of being odd. If x is even, then y has a 3/5 chance of being odd, and again x+y has a 3/5 chance of being odd. So for all x,y where x!=y, x+y has a 3/5 chance of being odd.

Franklin LeeMay 16, 2009 at 02:17

I see. But instead of changing the 1 to 2, you can always change it to some other even number that doesn’t match the next roll.

jimMay 17, 2009 at 18:57

But there are two even numbers and three odd, so there’s no one-to-one correspondence if you do that. Two dice sequences will be mapped to the same sequence.

Franklin LeeMay 19, 2009 at 03:59

So, taking all this into consideration, we can match all k odd sequences, and all even ones (using Anonymous’s method) except those begining with 1,2 3,4 or 5,6 (or those reversed). In fact, unless all pairs of the (k even) sequence are those, we can always use anonymous’s method using the first pair that differs.

So what’s left is to count the sequences made up of the “bad” pairs and classify them as even or odd. This looks very doable since the count is the sum of a geometric series.

jimMay 24, 2009 at 10:56

What?

Franklin LeeMay 24, 2009 at 14:13

Never mind–it doesn’t work. I have another idea which I’ll make sure works before I post it.

jimMay 28, 2009 at 11:49

I made it work (in addition to my other solution which also works) but I don’t really like either of them.

Here’s the cleaned up version of the previous argument:

Where k is odd, we can match even and odd sums (as Franklin Lee shows above) so we’re only concerned with sequences where k is even. Look at the terms of the sequence as pairs. Find the first pair NOT of the form i, 7-i (If there is no such pair, we’ll deal with it later.) Then match this sequence with that in which each pair before this one is replaced by its complement mod 7, and in which the first half of this one has i replaced by 7-i. Since the second half of the pair isn’t 7-i, this is a legitimate sequence and has opposite parity (since an odd number of values have been replaced by their mod 7 complement.) We have thus been able to match even and odd sequences for all cases except one: Even k in which all pairs are of the form i, 7-i (with the exception of the terminating pair, which may even be the initial pair.) These sequences we will count and characterize as even or odd.

Each such sequence has zero or more pairs of the form i, 7-i. There are 6 such types of pairs (i = 1, …,6) and after the first one, any of 5 can follow, with 5 choices (unless there are no non-ending pairs) of and ending pair. Since k is even, let k-2 = 2n.

The probability of a sequence being one of these is thus 1/6 * (1/5)^n and a sequence will have an even or odd sum depending on weather n is even or odd.

We can sum these probabilities as infinite geometric sequences. The common ratio will be 1/25. The first term for even is 1/6 and for odd is 1/30, so even is more likely.

jimMay 30, 2009 at 12:24

i was thinking that since we know that the sum of the two last rolls is even (2x), and the other rolls before are a 50/50 chance to be odd or even, we have an advantage of 1 that it gonna be even. wouldn’t this mean that EVEN is the answer?

neSeptember 29, 2009 at 21:51

One of the problems in the 2009 contest was:

A fair die is rolled repeatedly until two consecutive rolls are equal, at which point the game ends.

If we let S be the sum of the results of all of the rolls, is S more likely to be even or odd, or is it equally likely to be both?

The exact probability of an even roll is 47/82. Does anyone have a reference to a published solution?

Stan RabinowitzMarch 24, 2010 at 10:02