Six standard six-sided dice are rolled. Let $p$ be the probability that the dice can be arranged in a row such that for $1 \leq k \leq 6$ the sum of the first $k$ dice is not a multiple of 3. Then $p$ can be expressed as $\frac{a}{b}$ where $a$ and $b$ are coprime positive integers. What is the value of $a + b$ ?
Details and assumptions
You get to choose the order that the dice is arranged. For example, if the dice thrown was $\{ 1, 1, 1, 2, 2, 3\}$ , then we can reorder them as $( 1, 1, 2, 1, 2, 3)$ which satisfies the conditions.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
We will instead count the probability that the dice can't be arranged with the above's property. An arrangement will be presented in the form of string of length 6 containing 3 types of numbers : '0','1','2' which represent the numbers from 1-6 which is 0,1,2 mod 3, respectively (and so each slot has probability of 1/3).
Let $a,b,c$ be the number of $1s,2s,3s$ in an arrangement of a dice, then the sum of the numbers is $a+2b+3c \equiv (a-b) \mod 3$
Now, divide into cases :
1) The sum of the number of the dices is a multiple of 3, means this will always fail the property for $k = 6$ . Regardless of the sum of numbers in the last 5 dices, only 1 from $\{1,2,3\}$ if used as the number in the 1st dice, will get you a sum which is divisible by 3, since they are pairwise distinct in mod 3. Same for $\{4,5,6\}$ . Hence the probability is $\frac{1}{3}$
2) The sum of the number is not a multiple of 3. It means that $3 \not| (a-b)$ and this implies that at least one of $a,b$ is positive (the arrangement can't solely contain $3s$ ), and $a \neq b$ . Divide into subcases :
2.1) Case where there are exactly 1 other type besides '3', which we can re-arrange into $1..13...3 (b=0)$ or $2..23..3 (a=0)$ (not necessarily contains a '3'). WLOG, we take the case $b=0$ (later multiplied by 2). Firstly, we can't have $a = 0,3,6$ as the sum will be divisible by 3.
For $a = 1$ , arrange as follows : $133333$ .
For $a = 2$ , arrange as follows : $113333$ .
If $a \geq 3$ , then we can't rearrange it to satisfy the property since no matter what, eventually we will have 3 of 1s,as we start counting the sum from the first to the last.
The probability for all possible rearrangement for $a =4 (111166)$ is $\left(\frac{1}{3} \right)^6 \dbinom{6}{4} = \frac{15}{3^6}$
The probability for all possible rearrangement for $a =5 (111116)$ is $\left(\frac{1}{3} \right)^6 \dbinom{6}{5} = \frac{6}{3^6}$
Hence, for this case, the probability is $2 \times \left(\frac{15}{3^6} + \frac{6}{3^6} \right) = \frac{14}{243}$
2.2) Case where there are exactly 2 other types besides '3', which we can re-arrange into $1..12..23..3$ (not necessarily contains a '3'), Since $a \neq b$ , WLOG assume $a > b$ , then later we multiplied by 2 as we can swap the $1s$ and $2s$ in the arguments. Clearly $a-b = 4$ as $a-b \geq 5$ implies that $a \geq b+5 \geq 6$ which is impossible.
For $a-b = 1$ , then arrange as $112333$ for $a=2,b=1$ and $112123$ for $a=3,b=2$
For $a-b = 2$ , then arrange as $112133$ for $a=3,b=1$ and $112121$ for $a=4,b=2$
For $a-b=3$ , then this will fail the condition $3 \not| (a-b)$
For $a-b = 4 \Rightarrow a=5,b=1$ we will always fail to get a rearrangement satisfying the propery, as will be shown here :
-) If we start by '2', then it must be followed by another '2' (since otherwise the sum is 3) which we don't have.
-) If we start by '1', then it must be followed with '1' (sum = 2). And then a '2' (sum = 4). And then a '1' (sum = 5). At the 5th position, we must add another '2', which we don't have.
Hence for this case, the total is just twice the probability of all rearrangements of $111112$ which is $2 \times \left(\frac{1}{3} \right)^6 \dbinom{6}{5} = \frac{4}{243}$
Giving us the grand total of $\frac{1}{3} + \frac{14}{243} + \frac{4}{243} = \frac{11}{27}$ for the probability that we can't arrange the dice.
Hence, the desired probability is just $1 - \frac{11}{27} = \frac{16}{27}$ which gives $16+27 = 43$ as the answer,
let $d_n$ be the value of the nth die. We want to avoid:
$\displaystyle \sum_{n=1}^k d_n \equiv 0 \pmod{3}$ for $1 \leq k \leq 6$
In base 3, our dice can take values of 0,1 or 2. We notice a total of $3^6$ or $729$ possible outcomes.
$0+0 = 0$
$0+1 = 1, 1 + 1 = 2$
$0+2 = 2 ,1 + 2 = 0, 2 + 2 = 1$
Next, we use the base 3 ternary addition rules above to create a method of rearranging the dice. The conditions below are sufficient (but not necessary) to avoid our beginning equivalence.
With our standard format we can consider all possible cases in terms of the zero valued dice.
Summing the useful number of orderings divided by the total number of orderings gives
$\frac{a}{b} = \frac{30+120+120+120+30+12}{729} = \frac{432}{729} = \frac{16}{27}$
$16 + 27 = \boxed{43}$
I am really sorry but I don't understand this solution. First do you want to say that we can consider numbers that dice shows as modulo 3? I think by mistake you said base 3. Second, what do you mean by sufficient condition for beginning equivalence?
This post is to try to augment the original solution and explain some parts in closer detail. Hope it helps.
With this problem, our plan of attack looks like this:
Simplify (if possible)
Convert ideas and concepts into a set of rules about which 'games' satisfy the question.
Plug numbers in to find out how many ways the dice you rolled can be rearranged into one of the winning 'games'
We see that $\sum_{n=1}^{k+1}d_n = \sum_{n=1}^kd_n + d_{k+1}$
(i.e. The sum of k+1 rolls = the sum of rolls so far + sum of next roll)
Consider moves that lose our game.
When $\sum_{n=1}^kd_n$ is 1 more than a multiple of three, if $d_{k+1}$ = 2 or 5 then our new total will divide 3 evenly.
When $\sum_{n=1}^kd_n$ is 2 more than a multiple of three, if $d_{k+1}$ = 1 or 4 then our new total will divide 3 evenly.
At the first roll, if $d_{k+1}$ = 3 or 6 then our new total will divide 3 evenly.
It doesn't matter whether $\sum_{n=1}^kd_n$ is 1 or 4 or 7 or 10, and it doesn't matter whether $d_{k+1}$ = 2 or 5, All these rolls lose our game. Try it with a few examples or see it by representing 4 as (3+1) and 5 as (3+2) etc if you need to convince yourself.
Because it doesn't matter if I get 8+1 or 8+4, or it doesn't matter if I get 5+1 or 5+4 we can simplify the problem by representing the whole thing in base three. This is equivalent to relabelling the dice with a Sharpie pen,
$4 \mapsto 1$ ,
$5 \mapsto 2$ ,
$6 and 3 \mapsto 0$
The problem can be restated as the first sentence of my original solution, we want to avoid that congruence.
So we simplified the problem, let's create some rules winning games follow.
Returning to $\sum_{n=1}^kd_n + d_{k+1} = \sum_{n=1}^{k+1}d_n$
$\boxed{0+0=0}$ $0+1=1$ $0+2=2$
$1+0=1$ $1+1=2$ $\boxed{1+2=0}$
$2+0=2$ $\boxed{2+1=0}$ $2+2=1$
We want to avoid the boxes. So for each $\sum_{n=1}^kd_n$ we have two options. Notice immediately that the first dice can not be 0. These are necessary and sufficient conditions.
In order to progress further, we abandon the idea that these rules must be necessary, so some winning games won't follow these rules. But these rules are sufficient because all sets which follow these rules will win. We can rearrange winning, rule-breaking sets to follow these rules.
For every other dice a 0 causes no change, so one way to rearrange out set of dice {d 1,d 2,d 3,d 4,d 5,d 6} is to put the zero dice to the back. The remaining middle dice, can not be zero, so if total so far is 1, k+1th roll must be 1, and if total so far is 2, k+1th roll be 2. This leads to a sufficient but not necessary set of conditions - First two dice are equal - subsequent dice alternate between 1 and 2 - Zeros go to end.
From these rules we can calculate the probability as $\frac{winning}{total}$ as in the original solution.
We are interested in multiples of 3, so let's consider the possible numbers mod 3: 0,1, and -1. We'll find all permutations consisting of 6 or less 1 and 2's. If such a permutation exists, we can add on threes to the end, leaving the sum unchanged mod 3. Make a table with columns labelled 1, 2, and 3. Starting with 0 threes, experiment with possible values for 1 and 2. Here are the possibilities: 4/2/0 2/4/0 3/2/1 2/3/1 1/3/2 3/1/2 1/2/3 2/1/3 2/0/4 0/2/4 1/0/5 0/1/5 For each case, calculate the number of ways to arrange the numbers in a line. For example, the expression for 4/2/0 would look like 6!/(4!2!), as the 4 one's, as well as the 2 two's are indistinguishable. The number of legitimate permutations is 432. The total number of permutations is 3^6=729. 432/729=16/27. 16+27=43, and we are done.
Firstly, we change the problem into an easier problem by treating the 6 sided dice as 3 sided dice. We have not changed the problem as the 5 can be replaced as a 2, the 6 as a 3 and the 4 as a 1.
We are left with 6 dice with 1, 2 and 3 on it. When rearranging, note that we can move all the 3s to the back of the sequence. Suppose the rearrangement started with a 1, then the full sequence without 3s would be 1, 1, 2, 1, 2, 1. If the rearrangement started with a 2, the full sequence would be 2, 2, 1, 2, 1, 2.
Replacing the ends of the sequence with 3s, it can be seen that the only possibilities to (#1s, #2s #3s) (# means number of) are:
(4, 2, 0) and (2, 4, 0)
{3, 2, 1} (All combinations of 3, 2, 1)
(2, 0, 4) and (0, 2, 4)
(1, 0, 5) and (0, 1, 5)
Counting the number of ways to roll for these cases gives us:
$4 \times \frac{6!}{4! \times 2!} + 2 \times \frac{6!}{5! \times 1!} + 6 \times \frac{6!}{3! \times 2! \times 1!}=60+12+360=432$
Counting the number of possible rolls gives $3^6=729$
Thus, the probability of an arrangement is $\frac{432}{729}=\frac{16}{27}$
Dealing with multiples of 3, we may choose to approach the problem modulo 3. That is represent 1 and 4 as 1 (mod 3), 2 and 5 as -1(mod 3), 3 and 6 as 0(mod3). We can either start with a 1 or -1. Set the number of 1's as a and the number of -1's as b. For a string of 6 numbers composed of 1,0,-1, for the first k terms to be indivisible by 3, $|a-b|$ is either 1 or 2, and $a+b \leq 6$ . The ordered pairs a and b satisfying this are: (0,1), (0,2), (1,2), (1,3), (2,3),(2,4) and interchanging a and b to get 6 more. The number of ways of doing this is $2\times (\frac{6!}{0!1!5!} +\frac{6!}{0!2!4!}+\frac{6!}{1!2!3!}+\frac{6!}{1!3!2!}+\frac{6!}{2!3!1!}+\frac{6!}{2!4!0!})=432$ . The total number of ways to get a string of 6 numbers is $3^6$ [not $6^6$ ]. Hence, the probability desired is $\frac{16}{27}$ , giving the answer of $43$ .
In this problem, it is sufficient to consider only the remainders of the dice numbers on a division by $3$ (that is, $0,1$ and $2$ ). This view facilitates the cases we need to analyse, since we are interested in the divisibility of the number, not in the number at all. Hence, we dont need to look for the sum of the dice numbers. Instead, we add their remainders on a division by $3$ .
The key of the problem is to note that we can't have a row where the sum of its respective remainders on a division by $3$ is a multiple of $3$ . That would mean the sum would be a multiple of $3$ .
Therefore, let us list the favorables arrangements in function of their remainders, not by the dices itself. The feasible configurations and their permutations are:
$(1,0,1,2,1,2): 6!/3!2! = 60$ ;
$(1,1,2,1,2,1): 6!/4!2! = 15$ ;
$(1,0,0,0,0,1): 6!/4!2! = 15$ ;
$(1,0,0,0,1,2): 6!/3!2! = 60$ ;
$(1,1,0,0,2,1): 6!/3!2! = 60$ ;
$(0,0,0,0,0,1): 6!/5! = 6$ .
suming up to $216$ (the permutations were considered in the count because the enunciation allows us to choose the order of the dice). But note that we can also interchange the $2$ 's with $1$ 's, which gives us more $216$ favorable combinations.
Therefore, we have a total of $216+216=432$ possible arrangements that satisfies the condition of the problem.
And as the total of possible permutations is $3^6 = 729$ , our propability p is $p = \frac {432}{729} = \frac {16}{27}$ .
Therefore, $a=16$ and $b=27$ , which gives the desired answer $a+b=43$
First assume that only 1,2 and 3 are spun. It makes it simpler.Then replace 3 with 0, and 2 with -1. Now, any 6-tuple with the same number of +1s and -1s must fail for k=6 any solution where the difference of +1s and -1s is more than 2 or less than -2 cannot work either, (think of a random walk, but you can switch the moves order).So we find the number of 6-tuples of ${-1,0,1}$ that have a difference of either 1 or 2 in their -1s and 1s. Then we divide the cases by number of 0s in the tuple.
For no zero, there must be a 2-4 split. There are 2 ways to choose which side has the 2, and 15 to choose the 2,so that makes 30
For 1 zero, , there must be a 2-3 split. There are 2 ways to choose which side has the 2, and 10 to choose the 2, and 6 ways to choose the 0,so that makes 120
For 2 zeros, , there must be a 1-3 split. There are 2 ways to choose which side has the 1, and 4 to choose the 1,and 15 to choose the zeros,so that makes 120
For 3 zeros, , there must be a 1-2 split. There are 2 ways to choose which side has the 2, and 3 to choose the 1,and 20 to choose the zeros,so that makes 120
For 4 zeros, , there must be a 0-2 split. There are 2 ways to choose which side has the 2, 15 to choose the zeros,so that makes 30
For 5 zeros, , there must be a 1-0 split. There are 2 ways to choose which side has the 1,6 to choose the zeros,so that makes 12
These sum to 432 out of 729, which simplifies to 16/27
Problem Loading...
Note Loading...
Set Loading...
We shall attempt to solve this question systematically by listing cases according to the distribution of the dice.
Firstly, note that each 6-sided die can be reduced to a 3-sided one by taking $\pmod 3$ of each roll. For example, 1 and 4 are treated as identical because they both contribute $1\pmod3$ to the cumulative sum, which is what matters in this question.
There are 7 cases of distribution: $(6,0,0), (5,1,0), (4,2,0), (3,3,0), (4,1,1), (3,2,1), (2,2,2)$
Case 1: Distribution of $(6,0,0)$ (ie. 6 of a certain mod value and 0 of the other 2 values). In this case, the sum of values of the 6 dies is a multiple of 3, so when k = 6, case 1 fails.
Cases 4,5,7 : Distribution of $(3,3,0), (4,1,1), (2,2,2)$ All fail due to the same reason as case 1.
Case 2: Distribution of $5,1,0$ There are 6 possible sets here, of the form $(x,x,x,x,x,y)$ . When x =0, $(y,x,x,x,x,x)$ is a possible derangement that fulfils the requirements of the question. It works when y = 1 or 2. In each set of values for $(x,y)$ , there are $\frac {6!}{5!1!} = 6$ possible ways to choose 6 dice of that configuration, thus this contributes $6*2 = 12$ solutions to the question. When x = 1 or 2, by pigeonhole principle there exists a block of 3 numbers such that all 3 numbers are x. Thus the cumulative sum will cycle through all values of mod 3 including $0\pmod3$ . Thus this subcase fails. Therefore case 2 contributes 12 cases.
Case 3: Distribution of $(4,2,0)$ . There are 6 possible sets here, of the form $(x,x,x,x,y,y)$ . When x =0, $(y,y,x,x,x,x)$ is a possible derangement that fulfils the requirements of the question. It works when y = 1 or 2. In each set of values for $(x,y)$ , there are $\frac {6!}{4!2!} = 15$ possible ways to choose 6 dice of that configuration, thus this contributes $15*2 = 30$ solutions to the question. When x = 1, y = 2, and x = 2, y =1, there are solutions in $(1,1,2,1,2,1)$ and $(2,2,1,2,1,2)$ respectively, each contributing $\frac {6!}{4!2!} = 15$ solutions for a total of 30 solutions to the question. Lastly, when y = 0, x = 1 or 2, there will be a value of k, $1 \leq k \leq 5$ such that the cumulative sum is $0\pmod3$ , so this subcase fails. Therefore case 3 contributes a total of 60 solutions to the question.
Case 6: Distribution of $(3,2,1)$ There are 6 possible sets here, of the form $(x,x,x,y,y,z)$ . There are solutions for every set of values of $(x,y,z)$ , namely $(1,1,2,0,0,0), (2,2,1,0,0,0), (1,1,2,1,0,0), (1,1,2,1,2,0), (2,2,1,2,0,0), (2,2,1,2,1,0)$ for the cases where $(x,y,z)$ are $(0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), (2,1,0)$ respectively. Each solution here contributes $\frac {6!}{3!2!1!} = 60$ solutions to the question for a total of 360 solutions in case 6.
Thus, the final probability $p = \frac {12+60+360}{3^6} = \frac {432}{729} = \frac {16}{27}$ Thus $a+b = 43$