The Marshal Conundrum

Let me begin by introducing the exact recursion formula.

Define $n \text{ pmod } 9$ as the unique $r \in \{1, \cdots, 9\}$ such that $n \equiv r \text{ (mod 9)}$. Now let $R_0 = 0$, $F_0 = 10$ and

$$ R_{n+1} = (F_n + R_n) \text{ pmod }9, \qquad F_{n+1} = \frac{10}{9}F_n + \frac{R_n - R_{n+1}}{9}. \tag{1} $$

Then $F_n$ is the number of flags used in the $n$-th day. So

$$ F_0 = 10, \quad F_1 = 11, \quad F_2 = 12, \quad F_3 = 13, \quad F_4 = 15, \quad \cdots. $$

Let us first entertain the consequence of $\text{(1)}$.

Because of the $\text{pmod}$ operation in $\text{(1)}$, it seems very daunting to produce a simple and exact formula for $F_n$ although it makes computation slightly easier. But surprisingly we can give an approximate formula. The following proposition summarizes some consequences.

Proposition. Let $(R_n, F_n)$ be defined by $\text{(1)}$. Then there exists a constant $c > 0$ such that $$\left| F_n - c\left(\tfrac{10}{9}\right)^n \right| \leq \tfrac{8}{10} \tag{2} $$ for all $n \geq 0$. More precisely, we have the formula $$ c = F_0 - \tfrac{1}{90} \sum_{k=1}^{\infty} \left(\tfrac{9}{10}\right)^k R_k. \tag{3} $$

Both $\text{(2)}$ and $\text{(3)}$ easily follows by noting that $ c_n = (\frac{9}{10})^n F_n$ satisfies

$$c_{n+1} - c_n = \tfrac{1}{10}(\tfrac{9}{10})^n R_n - \tfrac{1}{9}(\tfrac{9}{10})^{n+1} R_{n+1} $$

and $R_n \in \{1, \cdots, 9\}$ for all $n \geq 1$. Then by using $F_0 = 10$, we have the bound

$$ 9.1 = F_0 - \tfrac{1}{90} \sum_{k=1}^{\infty} \left(\tfrac{9}{10}\right)^k 9 \leq c \leq F_0 = 10. $$

From this and $\text{(2)}$, we find that $ F_{21} \leq 92$ and $ F_{23} \geq 102$. This computation also justifies why the approximation $F_n \approx F_0 (\frac{10}{9})^n$ gives a good guess to the actual answer. Finally, this argument can be refined by using the values

$$(R_1, \cdots\ R_7) = (1, 3, 6, 1, 7, 5, 5), $$

from which it follows that $c \leq 9.75725676$ and hence $F_{22} \leq 99$. So $n = 23$ is the solution.

The following is the approximate value of $c$ obtained from $F_{1000}$.

$$c \approx 9.567894269669703072501237496424161411067649282(4) \tag{4} $$

(The parenthesized digit refers to the first digit whose value is uncertain.) Although computing this value requires the knowledge of $F_1, \cdots, F_{100}$, once this value is known then you can approximate $F_n$ quite well for $n$ relatively smaller than $1000$. For instance, this value together with $\text{(2)}$ proves that $F_{22} = 97$ and $F_{23} = 108$.

---

Proof of $\text{(1)}$. At the $n$-th day,

• $F_{n-1}$ denotes the number of flags used in the previous day, and
• $R_{n-1}$ denotes the total number of flags used until the previous day modulo $10$.

Now consider $(R_{n-1}, F_{n-1})$ as a point in the plane $\Bbb{R}^2$. Using one flag corresponds to the move

$$(x, y) \to (x+1, y-1)$$

in the plane, reflecting the fact that the total count of flag use is increased by 1 and the number of flag stocks is decreased by 1. Now this move will be hindered if we have no flags left, i.e., this move cannot cross the $x$-axis. This suggests that we can interpret the problem as the number of moves before we hit a border in $\Bbb{R}^2$. Without rewarding rule, this border will be the $x$-axis.

Of course, we have to take the rewarding rule into consideration. We realize this by modifying the border as follows:

\begin{align*} B &= \bigcup_{k=0}^{\infty} [10k, 10k+9] \times \{-k\} \\ &= \big( [0,9]\times\{0\} \big) \cup \big( [10,19]\times\{-1\} \big) \cup \big( [20,29] \times\{-2\} \big) \cup \cdots. \end{align*}

In other words, for each 10th helpful flag, we are rewarded with lowering of the border by 1 unit so that you can make an extra move.

Now the idea is to replace this border $B$ by a more easy-to-compute one with the same effect. Indeed, consider the line $L$ defined by $y = (9 - x)/10$. Then for $(a, b) \in \Bbb{Z}^2$ above the border $B$, we can check that the followings are equivalent:

1. The move starting at $(a, b)$ is stopped at $(s, t) \in \Bbb{Z}^2 \cap B$

2. Two lines $y = b - (x-a)$ and $L$ intersects at $(s', t') \in \Bbb{R}^2$ satisfying $\lceil s' \rceil = s$ and $\lfloor t' \rfloor = t$.

The following figure demonstrates the case $(a,b) = (2,12)$.

$\hspace{6em}$

Here the bold red line segments represent $B$, while the dashed line represents $L$. And blue arrows represent the moves made as well as part of the line $y = b - (x-a)$. Notice that this line intersects $L$ in the half-open square $S = (s-1, s]\times[t,t+1)$ exactly when the move stops at the right-bottom corner $(s,t)$ of the square $S$.

Now a simple algebra shows that $s = \lceil \frac{10}{9}(a + b)\rceil - 1$. Then $s - a$ corresponds to the number of moves made in this day and $s \text{ mod } 10$ represents the total number of moves made up to this day modulo 10. Applying this to $(R_{n-1}, F_{n-1})$ and utilizing the following observation

$$ \lceil \tfrac{10}{9}m \rceil - 1 = \tfrac{10}{9}m - \tfrac{1}{9}(m \text{ pmod } 9), \qquad \forall m \in \Bbb{Z} $$

produces $(R_n, F_n)$ given by $\text{(1)}$, completing the proof.