Harvard-MIT Mathematics Tournament

Solution:

Equivalently, a $k$-representation is given by a sequence $a_{p}, \ldots, a_{q}$, for some $p < q$, such that
$$\sum_{i=p}^{q} a_{i} = \sum_{i=p}^{q} a_{i} k^{i}.$$
We first show existence. Let the representation of $n-1$ in base $k$ be given by $\sum_{i=0}^{r} a_{i} k^{i} = n-1$. Let $l = \sum_{i=1}^{r} a_{i} (k^{i-1} + k^{i-2} + \cdots + 1)$. Now we extend the sequence $\{a_{i}\}$ by letting $a_{i} = k-1$ if $-l+1 \leq i \leq -1$ and $a_{-l} = k$. We claim that $a_{-l}, \ldots, a_{r-1}, a_{r}$ is a $k$-representation of $n$. Indeed,
$$\begin{aligned} \sum_{i=-l}^{r} a_{i} k^{i} & = (n-1) + \left( \sum_{i=-l}^{-1} (k-1) n^{i} \right) + k^{-l} \\ & = (n-1) + (k-1) k^{-1} \frac{1 - k^{-l}}{1 - k^{-1}} + k^{-l} = n \\ \sum_{i=-l}^{r} a_{i} & = \left( \sum_{i=0}^{r} a_{i} \right) + l(k-1) + 1 \\ & = \left( \sum_{i=0}^{r} a_{i} \right) + \left( \sum_{i=1}^{r} a_{i} (k^{i} - 1) \right) + 1 \\ & = \left( \sum_{i=0}^{r} a_{i} k^{i} \right) + 1 = n \end{aligned}$$
Now suppose there is another $k$-representation $\{b_{i}\}$ of $n$; then $\sum b_{i} = \sum b_{i} k^{i} = n$. This implies that $\sum c_{i} = \sum c_{i} k^{i} = 0$ where $c_{i} = a_{i} - b_{i}$. The following claim specifies all possibilities of $\{c_{i}\}$.

Claim: Suppose that $\sum_{i=p}^{q} c_{i} k^{i} = 0$, where $c_{i}, p, q \in \mathbb{Z}, p < q$, and $c_{i} \in [-k, k]$. Then the sequence $\{c_{i}\}$ must be the concatenation of subsequences of the form
$$\pm(1, 1-k, 1-k, \ldots, 1-k, -k)$$
possibly with 0's in between.

Proof. If $c_{i}$ is not the zero sequence, then without loss of generality, we may assume $c_{q} > 0$.
Since $\sum_{i=p}^{q} c_{i} k^{i} = 0$, we have
$$|c_{q} k^{q}| = |c_{q-1} k^{q-1} + \ldots + c_{p} k^{p}| \leq k^{q} + k^{q-1} + \ldots + k^{p+1} < \frac{k}{k-1} k^{q} \leq 2 k^{q}$$
so $c_{q} = 1$. Now we have
$$k^{q} + c_{q-1} k^{q-1} + \ldots + c_{p} k^{p} = 0$$
This means $(k + c_{q-1}) k^{q-1} + \ldots + c_{p} k^{p} = 0$. Hence, as above,
$$| (k + c_{q-1}) k^{q-1} | = | c_{q-2} k^{q-2} + \ldots + c_{p} k^{p} | < 2 k^{q-1}$$
Therefore, $|k + c_{q-1}| < 2$, which means $c_{q-1} = -k$ or $-k+1$.
If $c_{q-1} = -k$, then $c_{q} k^{q} + c_{q-1} k^{q-1} = 0$, and we get a subsequence $(1, -k)$.
If $c_{q-1} = -k+1$, then $c_{q} k^{q} + c_{q-1} k^{q-1} = k^{q-1}$. Thus
$$k^{q-1} + c_{q-2} k^{q-2} + \ldots + c_{p} k^{p} = 0$$
which has the exact same form as (1). We can then repeat this procedure to obtain a subsequence $(1, 1-k, 1-k, \ldots, 1-k, -k)$.
Once we have such a subsequence, the terms in the sum $\sum_{i=p}^{q} c_{i} k^{i} = 0$ corresponding to that subsequence sum to 0, so we may remove them and apply the same argument.

We now consider the cases.
If the base $k$ representation of $n-1$ contains no 0's, then $a_{i} \neq 0$ so it is impossible to have $c_{i} = a_{i} - b_{i} = -k$. On the other hand, we know that $c_{i}$ is composed of subsequences of the form $\pm(1, 1-k, 1-k, \ldots, 1-k, -k)$. Therefore, if $\{c_{i}\}$ is not the zero sequence, then the fact that $\sum c_{i} = 0$ implies that we must have both a subsequence $(1, 1-k, 1-k, \ldots, 1-k, -k)$ and a subsequence $-(1, 1-k, 1-k, \ldots, 1-k, -k)$, meaning that there exists $i$ for which $c_{i} = -k$, contradiction.
If the base $k$ representation of $n-1$ contains a 0, then picking the largest $i$ such that $a_{i} = 0$, we can change $a_{i}$ to $k$ and $a_{i+1}$ to $a_{i+1} - 1$, and append a $(1, -k)$ to the end of the sequence. This yields another $k$-representation of $n$, so a $k$-representation of $n$ is unique if and only if the base $k$ representation of $n-1$ contains no 0's, as desired.