Problem 1668

### Part (a)

Construct a $5$-city that includes some entry that is at least $150$:

$$\begin{pmatrix} 1 & 16 & 2 & 198 & 22 \\ 63 & 1 & 4 & 176 & 5 \\ 54 & 17 & 1 & 55 & 39 \\ 15 & 14 & 10 & 1 & 6 \\ 58 & 4 & 3 & 113 & 1 \end{pmatrix}$$

### Part (b)

LEMMA: The largest element in an $n$-city is at most $F_{n^2 - n + 2}$, where $F_a$ denotes the $a$-th term of the Fibonacci sequence defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for all integers $n \ge 2$.

PROOF:

1. Existence of 1 in Each Row:
- Note that in each row of a city, there exists at least one element that is equal to $1$. By the well-ordering principle, this row of the city has a least term. Assume for the sake of contradiction that it is not equal to $1$. If so, then it must be equal to the sum of another element in the row and a positive integer, meaning it must be greater than another element in the row, which contradicts the fact that it is the least term. Therefore, in each row of a city, there exists at least one element that is equal to $1$, meaning that in an $n$-city, there exist at least $n$ terms equal to $1$.

2. Numbering Elements:
- Number the elements in order from greatest to least. Let $E_n$ denote the element of the $n$-city that is numbered with $n$. Note the largest element is equal to $E_1$, and elements $E_{n^2-n+1}$ through $E_{n^2}$ will all be equal to $1$, as they are the $n$ smallest terms and there exist at least $n$ terms equal to $1$.

3. Best-Case Scenario:
- Note that in a best-case scenario, each element is the sum of the two largest elements less than or equal to itself. This means that $E_1 \le E_2 + E_3 \implies E_1 \le (E_3 + E_4) + (E_4 + E_5) \ldots$. Working downwards in this manner, we will eventually reach a string of elements equal to $1$ whose sum is equal to $E_1$. The number of $1$s in this string is equal to the maximum value of $E_1$ in this best-case scenario.

4. Final String Composition:
- Note that each element equal to $1$ in this final string is either equal to $E_{n^2-n+1}$ or $E_{n^2-n+2}$. The two are both achievable, as $E_{n^2-n-1} = E_{n^2-n+1} + E_{n^2-n}$ and $E_{n^2 - n} = E_{n^2-n+1} + E_{n^2-n+2}$. However, $E_{n^2-n+3} \ldots E_{n^2}$ could only be achieved by adding the two next-smallest elements together; however, since both of these must be equal to $1$, they will not show up in the final string. This final string then consists exclusively of multiple instances of the elements $E_{n^2-n+1}$ and $E_{n^2-n+2}$.

5. **Sequence Function $f(x)$:**
- Define $f(x)$ to be the number of sequences with first term $1$ and last term $x$ such that the $k$-th term of the sequence minus the $k-1$-th term of the sequence is equal to either $1$ or $2$ for all integers $2 \le k \le x$. I claim that the number of terms equal to $1$ in the final string is at most $f(n^2 - n) + f(n^2 - n + 1)$.

6. Counting Terms:
- Note that the total number of instances of $E_{n^2-n}$ is equal to $f(n^2-n)$. Each instance of $E_{n^2-n}$ will produce one instance of $E_{n^2-n+1}$ and one instance of $E_{n^2-n+2}$. However, each instance of $E_{n^2-n-1}$ will also directly add a new instance of $E_{n^2-n+1}$ (as $E_{n^2-n-1}$ turns into $E_{n^2-n} + E_{n^2-n+1}$, only the $E_{n^2-n+1}$ is added to the count). Therefore, the number of terms equal to $1$ in the final string is equal to $f(n^2 - n) + f(n^2 - n + 1)$.

7. Fibonacci Sequence:
- Note that $f(1) = 1$ and $f(2) = 1$. In addition, $f(k) = f(k-1) + f(k-2)$ (as the second-to-last term in any such sequence from $1$ to $k$ can be $k-2$, yielding $f(k-2)$ sequences, or $k-1$, yielding $f(k-1)$ sequences). Therefore, $f(k) = F_k$, the $k$-th Fibonacci number. The number of terms equal to $1$ in our final string, and therefore our largest term $E_1$, is therefore at most $F_{n^2 - n} + F_{n^2 - n + 1} = F_{n^2 - n + 2}$, as desired.

8. **Bounding with $3^{\binom{n}{2}}$:**
- Now, to prove that our largest term is at most $3^{\binom{n}{2}}$, it remains sufficient to show that $F_{n^2 - n + 2} \le 3^{\binom{n}{2}}$ for all positive integers $n \ge 1$. This is clearly true when $n = 1$ as $F_2 = 1$ and $3^{\binom{1}{2}} = 1$, so it remains sufficient to demonstrate this for all positive integers $n \ge 2$. Note this can be proven by proving that $F_{2k+2} \le 3^k$ for all positive integers $k \ge 2$ and then letting $k = \binom{n}{2}$ for all possible values of $n$. Binet's Formula states that the $n$-th Fibonacci number is equal to $\frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$. Letting $n = 2k + 2$ and substituting this in gives us $\frac{\phi^{2k+2} - (-\phi)^{-2k-2}}{\sqrt{5}} \le 3^k \implies \phi^{2k+2} - (-\phi)^{-2k-2} \le \sqrt{5} \cdot 3^k$.

9. Simplifying the Inequality:
- Note that $2k+2$ is always even, so $(-\phi)^{-2k-2} = \phi^{-2k-2}$. We then have $\phi^{2k+2} + \frac{1}{\phi^{2k+2}} \le \sqrt{5} \cdot 3^k$. Since $\phi^{2k+2} + \frac{1}{\phi^{2k+2}} > \phi^{2k+2}$, it is sufficient to show that $\phi^{2k+2} \le \sqrt{5} \cdot 3^k$ for all positive integers $k \ge 2$.

10. **Substituting $\phi$:**
- We substitute in $\frac{1 + \sqrt{5}}{2}$ for $\phi$ and multiply both sides by $2^{2k+2}$, which simplifies our inequality to $(1 + \sqrt{5})^{2k+2} \le 2^{2k+2} \cdot 3^k \cdot \sqrt{5}$. Note that $2^{2k+2} = 4^{k+1}$, so the right-hand side is equal to $4^{k+1} \cdot 3^k \cdot \sqrt{5} = 12^k \cdot 4\sqrt{5}$.

11. Final Simplification:
- Our inequality has now been simplified to $(1 + \sqrt{5})^{2k+2} \le 12^k \cdot 4\sqrt{5}$. Note that $(1 + \sqrt{5})^{2k+2} = (6 + 2\sqrt{5})^{k+1} = (6 + 2\sqrt{5}) \cdot (6 + 2\sqrt{5})^k$, further reducing this inequality to $(6 + 2\sqrt{5}) \cdot (6 + 2\sqrt{5})^k \le 12^k \cdot 4\sqrt{5}$. Dividing both sides by $12^k$ gives us $(\frac{6 + 2\sqrt{5}}{12})^k \le 4\sqrt{5}$. Note that this can be directly computed and shown to be true when $k = 2$. Additionally, $0 < \frac{6 + 2\sqrt{5}}{12} < 1$. Higher values of $k$ will then be equivalent to repeatedly multiplying a value between $0$ and $4\sqrt{5}$ by a value between $0$ and $1$, which will only further decrease the value of the LHS while keeping the RHS constant. Therefore, our inequality holds true for all $k \ge 2$, thus proving that the largest element in an $n$-city can never be greater than $3^{\binom{n}{2}}$ for all integer $n \ge 1$.

$\blacksquare$

The final answer is $3^{\binom{n}{2}}$