Calvin's River Crossing Attempt

Note that the number of ways to throw $n$ 4 sided dice such that the sum is a multiple of 5 is the same number of ways to throw $n-1$ 4 sided dice such that the sum is not a multiple of 5 because whenever the sum of the first $n-1$ 4 sided dice is not a multiple of 5, there is a specific roll for the last die so that the sum would be a multiple of 5, and when the sum of the first $n-1$ 4 sided dice is a multiple of 5, there would be no roll for the last die so that the sum would be a multiple of 5 as the possible rolls are 1, 2, 3 or 4.

Let the number of ways to roll $x$ 4 sided dice such that the sum of the numbers on the dice is a multiple of 5 be $f(x)$ . Note that we are looking for $f(6)$ . Let $g(x)$ be the number of ways to roll $x$ 4 sided dice so that the sum is not a multiple of 5. We know that $f(x) = g(x-1)$ and $f(x) + g(x) = 4^x$ . This allows us to calculate that

$\begin{aligned}\\ f(1) = 0, & g(1) = 4^1 - 0 = 4 \\ f(2) = 4, & g(2) = 4^2 - 4 = 12 \\ f(3) = 12, & g(3) = 4^3 - 12 = 52 \\ f(4) = 52, & g(4) = 4^4 - 52 = 204 \\ f(5) = 204, & g(5) = 4^5 - 204 = 820\\ \end{aligned}$

Hence, there are 820 different dice throws.

[Edits for clarity - Calvin]

Let the number of different throws that result in crossing the river when throwing k dice be x(k). We want x(6). Obviously, x(1)=0, for none of 1,2,3,4 is divisible by 5.

Also, the number of different throws that result in not crossing the river when throwing k dice would be 4^k-x(k). In these scenarios Calvin ends up with sum = 1,2,3, or 4 (mod 5).

Now let's establish the recursion between x(k) and x(k-1): For every throw of k-1 dice that results in not crossing, (i.e., the sum =1,2,3, or 4 mod 5), there is one throw of the kth die that complements the current sum and results in 0 mod 5 after the kth throw.

Namely, x(k)= 4^(k-1)-x(k-1).

Spell this out, we have: x(6) = 4^5 - x(5) = 4^5 - 4^4 + x(4) = .... = 4^5 - 4^4 + 4^3 - 4^2 +4 = 820.

Let $P(n)$ be the number of ways to roll $n$ dice such that their sum is divisible by $5$ . We claim that $P(n) = 4^{n - 1} - P(n - 1)$ . To see this, first consider that since the dice are distinct, there are $4^n$ ways to roll $n$ die. Moreover, for any given roll of $n - 1$ dice, let their sum be $s$ . If $s \equiv 0 \mod 5$ , then no matter the result of rolling the last die, the total sum will not be divisible by $5$ . Alternatively, if $s \not\equiv 0 \mod 5$ , then there will be exactly one outcome of rolling the last die in which the sum is divisible by $5$ , namely when $5 - s$ is rolled. Therefore, there is a equivalence between the number of ways to roll $n$ dice whose sum is divisible by $5$ , and $n - 1$ dice whose sum is not divisible by $5$ , and so $P(n) = 4^{n - 1} - P(n - 1)$ .

Now, since there is exactly $1$ way to roll $0$ dice, and that sum is divisible by $5$ , $P(0) = 1$ . Furthermore, $P(1) = 4^0 - P(0) = 0$ ; $P(2) = 4^1 - P(1) = 4$ ; $P(3) = 4^2 - P(2) = 12$ ; $P(4) = 4^3 - P(3) = 52$ ; $P(5) = 4^4 - P(4) = 204$ ; and $P(6) = 4^5 - P(5) = 820$ , as needed.

Let the number of throws of $n$ dice that result in the sum on the $n$ dice being a multiple of $5$ be $a_n$ . Observe that, for $n \geq 2$ , if the sum on the first $n-1$ dice is a multiple of $5$ , then the sum on the first $n$ dice can never be a multiple of $5$ , whatever the $n^{th}$ dice shows. However, if the sum on the first $n-1$ dice is not a multiple of $5$ , then there is exactly one possibility for the $n^{th}$ dice such that the sum on the first $n$ dice to be a multiple of $5$ . There are $4^{n-1}$ possibilities for the first $n-1$ dice, so $a_n = 4^{n-1} - a_{n-1}$ . Noting that $a_1 = 0$ , we may apply this recurrence relation to find $a_2, ... , a_6$ , so $a_6 = 820$ . Alternatively, we may prove by induction that $a_n = \dfrac{4^n+4(-1)^n}{5}$ , so $a_6 = 820$ .

To get a multiple of 5 from 6 four-sided dice, we need to get a sum of 10, 15 or 20,

To get 10, there are four different ways of choosing the 6 numbers:

{1,1,1,1,2,4} ..... $\frac {6!}{4!}$ = 30

{1,1,1,1,3,3} ..... $\frac {6!}{4!2!}$ = 15

{1,1,1,2,2,3} ..... $\frac {6!}{3!2!}$ = 60

{1,1,2,2,2,2} ..... $\frac {6!}{4!2!}$ = 15

Note: the numbers calculated are distinct permutations of that particular set of numbers

To get 15, we have 8 sets:

{1,1,1,4,4,4} ..... $\frac {6!}{3!3!}$ = 20

{1,1,2,3,4,4} ..... $\frac {6!}{2!2!}$ = 180

{1,1,3,3,3,4} ..... $\frac {6!}{3!2!}$ = 60

{1,2,2,3,3,4} ..... $\frac {6!}{2!2!}$ = 180

{1,2,2,2,4,4} ..... $\frac {6!}{3!2!}$ = 60

{1,2,3,3,3,3} ..... $\frac {6!}{4!}$ = 30

{2,2,2,2,3,4} ..... $\frac {6!}{4!}$ = 30

{2,2,2,3,3,3} ..... $\frac {6!}{3!3!}$ = 20

To get 20, we have 4 sets,

{1,3,4,4,4,4} ..... $\frac {6!}{4!}$ = 30

{2,2,4,4,4,4} ..... $\frac {6!}{4!2!}$ = 15

{2,3,3,4,4,4} ..... $\frac {6!}{3!2!}$ = 60

{3,3,3,3,4,4} ..... $\frac {6!}{4!2!}$ = 15

Adding them up, we get $4\times15 + 2\times20 + 4\times30 + 4\times60 + 2\times180 = 820$

We can solve the problem as such:-

First find out all the possilble single arrangements i.e.

the arrangements are

111241 - 6!/4! 111313 - 6!/(4! 2!) 111322 - 6!/(3! 2!) 111444 - 6!/(3! 3!) 112344 - 6!/(2! 2!) 113343 - 6!/(2!*3!) . . . . . and as such all the possible outcomes and than adding them up like

24+15+60+20+180+60+....+...= 820 <===> ANSWER

Define x 1, x 2, x 3, x 4, x 5 as the number of different dice throws with sum congruent to 1,2,3,4,5 (mod 5), given x dice. We want to find 6 5.

Observe that:

1 1 = 1 2 = 1 3 = 1 4 = 1;

1_5 = 0

2 1 = 2 2 = 2 3 = 2 4 = 3

2_5 = 4

(writing out 2_i is unnecessary, but helps in seeing the pattern)

Let x 1 + x 2 + ... + x_5 = f(x)

Observe that f(x) = 4^x.

Note that :

x i = f(x-1) - (x-1) i

this also implies that x 1 = x 2 = x 3 = x 4 for all x.

Note that if x is odd, x 1 = x 5 + 1; if x is even, x 1 + 1 = x 5, by simple induction, as we have the base case for 1 dice throw and 2 dice throws (though 2 is unnecessary); and its easy to see that the induction step is true:

if x 1 = x 5 + 1,

(x+1) 1 = f(x) - x 1 = f(x) - x_5 - 1

(x+1) 5 = f(x) - x 5 = (x+1)_1 + 1

and similar reasoning for the even---> odd case.

thus 6_5 = ((4^6 - 1)/5) + 1 = 820

We solve this problem using generating functions. Consider $f(x) = ( x + x^2 + x^3 + x^4 )^{6}$ . The number of ways to get a sum of $N$ by throwing six 4-sided dice is equal to the coefficient of $x^N$ in $f(x)$ . We are interested in the sum of all coefficients of $x^N$ , where $N$ is a multiple of 5.

Let $\omega$ be a fifth root of unity, so $\omega^5 = 1$ and $\omega^4 + \omega^3+ \omega^2 + \omega + 1 = 0$ . Then $\omega^{4k} + \omega^{3k} + \omega^{2k} + \omega^k + 1 = \begin{cases} 5 & \mbox{ if } k \equiv 0 \pmod{5}\\ 0 & \mbox{otherwise}. \\ \end{cases}$ Hence, the sum of all coefficients of $x^N$ , where $N$ is a multiple of $5$ is given by $\frac { f(1) + f(\omega) + f(\omega^2) + f(\omega^3) + f(\omega^4) } {5}$ , which is equal to $\frac {4^6 + (-1)^6 + (-1)^6 + (-1)^6 + (-1)^6 }{5} = 820$ .

Note: Students may guess the answer by looking at small cases, and realizing the answers are close to $\frac {4^k}{5}$ .

There are 4^6ways to get an arrangement of numbers from the dice. Each arrangement of dice will have a sum. Since we assume that one fifth of the rolls of the dice will be a multiple of five, then we know that is the solution (note, we used the ceiling function because we knew any remainder from division would still count as a roll.

Python:

1
2
3
4
5
6
7

from itertools import product
dice = range(1, 5)
ways = 0
for roll in product(dice, repeat=6):
    if sum(roll) % 5 == 0:
        ways += 1
print "Answer:", ways

The generating function is $(x^1+x^2+x^3+x^4)^5$ and if you expand this, the coefficient of $x^{10}$ is 120, the coefficient of $x^{15}$ is 580 and the coefficient of $x^{20}$ is 120. These are the only terms where the power of x is a multiple of 5 so the answer is 120+120+580= $\boxed{820}$

There are $4^{6}$ ways to get an arrangement of numbers from the dice. Each arrangement of dice will have a sum. Since we assume that one fifth of the rolls of the dice will be a multiple of five, then we know that $\lceil \frac{4^{6}}{5}\rceil$ is the solution (note, we used the ceiling function because we knew any remainder from division would still count as a roll.