Isaac is planning a nine-day holiday. Every day he will go surfing, or water skiing, or he will rest.

Question

On any given day he does just one of these three things. He never does different water-sports on consecutive days. How many schedules are possible for the holiday?

My try- Let surfing be denoted as the number 1, water skiing as 2 and resting as 3. So we need to find the number of 9 digit numbers having only 1, 2 and 3 such that 1 and 2 never come together. Here is where I am stuck. Any help would be appreciated.

Source - British Mathematical Olympiad

Answer 1

There is probably a more elegant way to see this, but:

Let $T_n$ be the desired answer. That is, the number of good strings of length $n$.

Let $A_n$ be the number which end in surf.

Let $B_n$ be the number which end in ski.

Let $C_n$ be the number which end in rest.

Then, of course, $$T_n=A_n+B_n+C_n$$

Recursively, it is clear that $$A_n=A_{n-1}+C_{n-1}\quad B_n=B_{n-1}+C_{n-1}\quad C_n=T_{n-1}$$ Adding we get $$T_n=A_{n-1}+B_{n-1}+C_{n-1}+C_{n-1}+T_{n-1}=2T_{n-1}+T_{n-2}$$

A quick calculation then gives $$\boxed {T_9=3363}$$

Answer 2

If he rests, he can do all three the next day. If he skis, then he can rest or surf. If he surfs, then he can rest or ski.

Now add up all the possibilities: He can rest in 3 scenarios, ski in 2 scenarios and surf in two scenarios.

Now to the next day. In all of the scenarios on the previous day, he can rest, so he can rest in 3+2+2=7 scenarios. He can't ski if he surfs, so he can ski in 3+2=5 scenarios, and the same for surfing.

Now continue the pattern:

REST: 1 3 7 17 41 99 239 577 1393
 SKI: 1 2 5 12 29 70 169 408  985
SURF: 1 2 5 12 29 70 169 408  985

The answer is 1393+985+985 = 3363.

Answer 3

Let $\mathcal{N}_n$ be the number of possible schedules when the number of holidays is $n$.

In addition to setting up recursion relations for $\mathcal{N}_n$, one can solve the problem by computing the OGF (ordinary generating function) associated with $\mathcal{N}_n$.

$$\mathcal{N}(t) \stackrel{def}{=} \sum_{n=0}^\infty \mathcal{N}_n t^n$$

One first write down a RE (regular expression) that represent the possible schedules unambiguously and then translate the RE to an OGF.

Let r, w, s be alphabets corresponds to Issac is resting/surfing/water skiing. One RE that represent the possible schedules is

   r* ( '' | (s+|w+)(r+(s+|w+))* r* )

For this RE, each of the possible schedule corresponds to exactly one accepting path. This allows us to extract the desired OGF using following recipe:

• associate the empty pattern '' with $1$.
• associate every occurrence of alphabet r,s, w with $t$.
• If patterns p, q corresponds to functions $P(t)$, $Q(t)$, then
  1. associate pattern pq with $P(t)Q(t)$.
  2. associate pattern p|q with $P(t) + Q(t)$.
  3. associate pattern p* with $\frac{1}{1-P(t)}$
  4. associate pattern p+ = pp* with $\frac{P(t)}{1-P(t)}$.

Apply these rules, we have

• (s+|w+) $\mapsto \frac{t}{1-t} + \frac{t}{1-t} = \frac{2t}{1-t}$.
• r+(s+|w+) $\mapsto \frac{t}{1-t}\frac{2t}{1-t} = \frac{2t^2}{(1-t)^2}$
• (s+|w+)(r+(s+|w+))* r* $\mapsto \frac{2t}{1-t}\frac{1}{1 - \frac{2t^2}{(1-t)^2}}\frac{1}{1-t} = \frac{2t}{1-2t-t^2}$
• r* ( '' | (s+|w+)(r+(s+|w+))* r* ) $\mapsto \frac{1}{1-t}\left(1 + \frac{2t}{1-2t-t^2}\right) = \frac{1+t}{1 -2t -t^2}$

So the desired OGF is

$$\begin{align} \mathcal{N}(t) = \frac{1+t}{1-2t-t^2} &= \frac{1+t}{(1-(1+\sqrt{2})t)(1-(1-\sqrt{2})t)}\\ &= \frac{1 + \frac{1}{1+\sqrt{2}}}{(1-(1+\sqrt{2})t))\left(1-\frac{1-\sqrt{2}}{1+\sqrt{2}}\right)} + \frac{1 + \frac{1}{1-\sqrt{2}}}{\left(1-\frac{1+\sqrt{2}}{1-\sqrt{2}}\right)(1-(1-\sqrt{2})t)}\\ &= \frac12\left[\frac{1+\sqrt{2}}{1 - (1+\sqrt{2})t} + \frac{1-\sqrt{2}}{1 - (1-\sqrt{2})t} \right]\\ &= \frac12\sum_{n=0}^\infty \left[ (1+\sqrt{2})^{n+1} + (1-\sqrt{2})^{n+1}\right] t^n \end{align} $$ Comparing the coefficients on both sides and notice $|1-\sqrt{2}| < \frac12$, we obtain

$$\mathcal{N}_n = \frac12 \left[(1+\sqrt{2})^{n+1} + (1-\sqrt{2})^{n+1} \right] = \frac12 \verb/round/\left((1+\sqrt{2})^{n+1}\right)\quad\text{ for } n \ge 1 $$

For the problem at hand, $n = 9$, so the number of possible schedules is

$$\mathcal{N}_9 = \frac12 \verb/round/\left((1+\sqrt{2})^{10}\right) = 3363$$

Reproducing the number derived in other answers using recursion relation.