The Marshal Conundrum

Question

I've thought of a problem which I would like to know the solution to without having to brute force the answer.

The Marshal Conundrum

About

I thought of The Marshal Conundrum after getting the Marshal badge of SFF.SE. I wondered how long it would take me to get 100 comment flags per day on any site just by flagging comments.

The Rules

• Every flag I submit per day is approved, none are ever declined.
• I'm not earning rep so cant gain flags from rep.
• I gain a flag for every 10th helpful flag.
• Once I've used all my flags for that day I have to wait for the next day
  • Unless I've gained a flag, in which case I can use that flag that day.

Example.

If I wanted to reach 15 flags, it would take me 4 days. This is because:

• On day one I would use 10 flags. I would then gain a flag and use an 11th.
• On day two I use 11 flags. However my 1 extra from the day before and 9 of my 11 today gave me a new flag. I therefore end the day having submitted 12 flags.
• On day three I use my 12 flags. 3 extra from the day before + 7 from today gain me a flag. I end the day with 13 flags submitted.
• On day four I use my 13 flags. 6 extra from the day before + 4 from today gain me a flag. I use the remaining 10 which earns me another extra flag. I end the day having done 15 flags.

---

How many days does it take me to be allowed to cast 100 flags in a day? Is there a rule to generalise it for n flags gained for every m flags cast?

Answer 1

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.

Answer 2

Here is an estimation (expanded from the comments).

Say on a given day we start with $F$ flags. Using them all will reward us with $0.1F$ new flags. Using them again reward us with $0.01F$ flags, and so on. In total we're rewarded $0.111\ldots F=\frac19F$ flags. The next morning our $F$ flags are replenished and we're ready to use $\frac{10}9F$ flags.

So for each day, the number of available flags increase with a factor of $\frac{10}9$, so after $n$ days we have $10\left(\frac{10}9\right)^n$ flags. To find when we reach $100$ flags we solve $10\cdot\left(\frac{10}9\right)^n=100$, which gives $n=21.85$ days. Thinking about what the decimals mean (solving, for instance, $10\cdot\left(\frac{10}9\right)^n=11$ and comparing the answer to the known exact solution) this means that our estimation is that we reach $100$ flags on the $22$nd day of flagging.

This will overestimate our stockpile of flags, because the estimation allows us to use fractional flags that we don't really have and thus gain more rewards than we should. That means it underestimates the number of days it takes to reach a certain size.