Numbers whose reverse equals 9 times the original

Problem

Given a positive integer $n$, let $f(n)$ represent the number of n-digit numbers whose reverse equals 9 times the original, with no leading zeros allowed. Find $f(n)$.

Solution 1:

We observe the following:

1. The smallest such number is $1089$, which is also the only 4-digit number with the property, i.e. $f(1)=f(2)=f(3)=0,f(4)=1$.

2. Numbers obtained by concatenating $10$, an arbitrary number of 9s, then $89$, (e.g. $1089$, $10989$, $109989$, $1099\dots 9989$) always have the desired property.

3. More such numbers can be constructed by concatenating strings in 2) in a symmetric manner, e.g. $10989\mathrm{\#}1089\mathrm{\#}10989$.

4. Zeros can be inserted during concatenation while keep the property, e.g. $1089\mathrm{\#}00\mathrm{\#}10989\mathrm{\#}00\mathrm{\#}1089$.

Because of zeros, we define $g(n)$ to be the number of n-digit numbers whose reverse equals 9 times the original, WITH LEADING ZEROES ALLOWED. Then we have $g(0)=g(1)=g(2)=g(3)=1$ and $g(4)=2$ ($0000$ and $1089$). If we allow leading zeroes, then any such string with length $n$ either has a leading zero or not, and if there is a leading zero, then there must be a corresponding trailing zero, hence we have the following relation: $$g(n)=g(n-2)+f(n)$$ where $g(n-2)$ is the number of strings with leading zero and $f(n)$ is the number of string without leading zero.

We also noticed that by symmetry, when $n\ge 4$, $g(n)$ can be recursivedly defined as below: $$\begin{array}{rcl}g(n)=g(n-2)+g(n-8)+g(n-10)+\dots +g(2)+g(0)+1& & \text{ (n is even)}\\ g(n)=g(n-2)+g(n-8)+g(n-10)+\dots +g(3)+g(1)+1& & \text{ (n is odd)}\end{array}$$ Here $g(n-2)$ counts strings with leading zero, $g(n-8)$ counts strings starting and ending with $1089$, $g(n-10)$ counts strings starting and ending with $10989$ and so on. The last 1 represents the whole string as one piece in the format of $1099\dots 9989$.

By mathematical induction, we have $$g(0)=g(1)=g(2)=g(3),g(4)=g(5)⟹g(2k)=g(2k+1)$$ and also $$g(n)=g(n-2)+g(n-4).$$ Therefore $$g(n)=F_{\lfloor \frac{n}{2}\rfloor +1}$$ where $F_n$ is the Fibonacci sequence defined as $F_0=F_1=1$ and $F_n=F_{n-1}+F_{n-2}$.

Finally using the relation $$g(n)=g(n-2)+f(n),$$ we conclude that $\boxed{{\displaystyle f(n)=F_{\lfloor \frac{n}{2}\rfloor +1}-F_{\lfloor \frac{n}{2}\rfloor }=F_{\lfloor \frac{n}{2}\rfloor -1}}}$ for $n\ge 4$.

Remark: Using the construction 2 below, we can also show that $f(n)=g(n-4)$ for $n\ge 4$, which can be used to derive the Fibonacci relation for $f$ and $g$ respectively.

Code

We can write a program using dynamic programming to verify the correctness of the solution above. Below is an example of such a Python program (courtesy of ChatGPT).

```{python}
def compute_g_and_f(n):
    # Base cases for g(n)
    g = [0] * (n + 1)
    g[0] = g[1] = 1  # g(0) = g(1) = 1

    # Compute g(n) using dynamic programming
    for i in range(2, n + 1):
        if i - 2 >= 0:
            g[i] += g[i - 2]
        k = 4
        while i - 2 * k >= 0:
            g[i] += g[i - 2 * k]
            k += 1
        if i >= 4:
            g[i] += 1

    # Base cases for f(n)
    f = [0] * (n + 1)

    # Compute f(n) using g(n)
    # or using f(n) = g(n) - g(n-2)
    for i in range(4, n + 1):
        f[i] = 1
        k = 4
        while i - 2 * k >= 0:
            f[i] += g[i - 2 * k]
            k += 1

    return g, f


# Example Usage
n = 20
g, f = compute_g_and_f(n)
print("g[0:21] = ", *g)
print("f[0:21] = ", *f)
```

g[0:21] =  1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34 34 55 55 89
f[0:21] =  0 0 0 0 1 1 1 1 2 2 3 3 5 5 8 8 13 13 21 21 34

Solution 2:

This blog article (in Chinese) presents yet another elegant solution to this same problem.

Construction 1:

Instead of using mathematical induction in Solution 1, one can also show that $f(2k)=f(2k+1)$ and $f(2n+4)=f(2n+2)+f(2n)$ by construction.

To show that $f(2k)=f(2k+1)$, we can construct a one-to-one mapping from strings of length $2k$ to strings of length $2k+1$. The mapping is defined as below by extending the two digits in the middle of length $2k$ to the three digits in the middle of length $2k+1$.

“00” -> “000” (e.g. 1089001089 -> 10890001089)

“08” -> “098” (e.g. 1089 -> 10989)

“91” -> “901” (e.g. 10891089 -> 108901089)

“99” -> “999” (e.g. 109989 -> 1099989)

To show that $f(2n+4)=f(2n+2)+f(2n)$, we construct strings of length $2n+4$ from strings of length $2n+2$ and strings of length $2n$ using the following rules:

First if the input string is in the form $1099\dots 9989$, regardless of the length $2n-2or2n$, we will generate an output string of length $2n+4$ in the form $1099\dots 9989$. Note that here we have a 2-to-1 mapping.

If the input string is of length $2n+2$ and is not in the form $1099\dots 9989$, then we construct an output string of length $2n+4$ based on the two digits in the middle of length $2n+2$:

“99” -> “9999” (e.g. 10999989 -> 1099999989)

“00” -> “0000” (e.g. 1089001089 -> 108900001089)

“08” -> “0998” (e.g. 108910891089 -> 10891099891089)

“91” -> “9001” (e.g. 10891089 -> 1089001089)

Note that the middle two digits are either 99 or 00 in this case.

If the input string is of length $2n$ and is not in the form $1099\dots 9989$, then we construct an output string of length $2n+4$ based on the two digits in the middle of length $2n$:

“99” -> “989109” (e.g. 10999989 -> 109989109989)

“00” -> “010890” (e.g. 1089001089 -> 10890108901089)

“08” -> “089108” (e.g. 108910891089 -> 1089108910891089)

“91” -> “910891” (e.g. 10891089 -> 108910891089)

Note that the middle two digits are either 91 or 08 in this case.

Finally we do a special handling for the unique input string of length $2n+2$ and in the form $1099\dots 9989\mathrm{\#}1099\dots 9989$, there is a corresponding unique output string of length $2n+4$ and in the form $1099\dots 9989\mathrm{\#}1099\dots 9989$. Note that this unique string CANNOT be generated from any string of length $2n$ using the rules above (because no additional 1 is added).

This additional 1-to-2 mapping compensates the 2-to-1 mapping of $1099\dots 9989$, Therefore we have $$f(2n+4)=f(2n+2)+f(2n).$$

Construction 2:

Turns out that there are very simple and elegant rules for constructing such strings. The underlying Fibonacci relation $f(n)=f(n-2)+f(n-4)$ is also straightforward from this construction. (Pointed out by 申强老师)

Check the code below (courtesy of Gemini) and you will recognize the rules by yourself :-)

```{python}
def generate_strings(n):
  """
  Generates strings of length n based on the given rules.

  Args:
    n: The desired length of the strings.

  Returns:
    A set of strings of length n.
  """

  if n == 4:
      return {"1089"}
  elif n == 5:
      return {"10989"}
  elif n == 6:
      return {"109989"}
  elif n == 7:
      return {"1099989"}
  else:
      # Rule from n-4 to n
      strings_n4 = generate_strings(n-4)
      strings_n4_derived = {f"10{''.join(str(9 - int(d)) for d in s)}89" for s in strings_n4}

      # Rule from n-2 to n
      strings_n2 = generate_strings(n-2)
      strings_n2_derived = {s[:2] + '9' + s[2:-2] + '9' + s[-2:] for s in strings_n2}

      return strings_n4_derived.union(strings_n2_derived)

# Test with n from 8 to 15
for n in range(8, 16):
    print(f"{n}: {generate_strings(n)}")
```

8: {'10999989', '10891089'}
9: {'108901089', '109999989'}
10: {'1098910989', '1099999989', '1089001089'}
11: {'10890001089', '10999999989', '10989010989'}
12: {'109989109989', '109999999989', '109890010989', '108910891089', '108900001089'}
13: {'1099999999989', '1089000001089', '1099890109989', '1098900010989', '1089109891089'}
14: {'10989108910989', '10989000010989', '10999999999989', '10998900109989', '10999891099989', '10890000001089', '10891099891089', '10890108901089'}
15: {'109999999999989', '109890000010989', '108910999891089', '108901098901089', '109998901099989', '109891098910989', '108900000001089', '109989000109989'}