HMMT November

All 1 digit numbers, $0,1,2,3$, are solutions when, say, $b=5$. (Of course, $d \in \{0,1,2,3\}$ works for any base $b$ of absolute value greater than $d$ but not equal to 4 .) Consider now positive integers $n=\left(a_{d} \ldots a_{1} a_{0}\right)_{4}$ with more than one digit, so $d \geq 1, a_{d} \neq 0$, and $0 \leq a_{k} \leq 3$ for $k=0,1, \ldots, d$. Then $n$ has the same representation in base $b$ if and only if $|b|>\max a_{k}$ and $\sum_{k=0}^{d} a_{k}(-4)^{k}=\sum_{k=0}^{d} a_{k} b^{k}$, or equivalently, $\sum_{k=0}^{d} a_{k}\left(b^{k}-(-4)^{k}\right)=0$. First we prove that $b \leq 3$. Indeed, if $b \geq 4$, then $b \neq 4 \Longrightarrow b \geq 5$, so $b^{k}-(-4)^{k}$ is positive for all $k \geq 1$ (and zero for $k=0$ ). But then $\sum_{k=0}^{d} a_{k}\left(b^{k}-(-4)^{k}\right) \geq a_{d}\left(b^{d}-(-4)^{d}\right)$ must be positive, and cannot vanish. Next, we show $b \geq 2$. Assume otherwise for the sake of contradiction; $b$ cannot be $0, \pm 1$ (these bases don't make sense in general) or -4 , so we may label two distinct negative integers $-r,-s$ with $r-1 \geq s \geq 2$ such that $\{r, s\}=\{4,-b\}, s>\max a_{k}$, and $\sum_{k=0}^{d} a_{k}\left((-r)^{k}-(-s)^{k}\right)=0$, which, combined with the fact that $r^{k}-s^{k} \geq 0$ (equality only at $k=0$ ), yields $$\begin{aligned} r^{d}-s^{d} \leq a_{d}\left(r^{d}-s^{d}\right) & =\sum_{k=0}^{d-1}(-1)^{d-1-k} a_{k}\left(r^{k}-s^{k}\right) \\ & \leq \sum_{k=0}^{d-1}(s-1)\left(r^{k}-s^{k}\right)=(s-1) \frac{r^{d}-1}{r-1}-\left(s^{d}-1\right) \end{aligned}$$ Hence $r^{d}-1 \leq(s-1) \frac{r^{d}-1}{r-1}<(r-1) \frac{r^{d}-1}{r-1}=r^{d}-1$, which is absurd. Thus $b \geq 2$, and since $b \leq 3$ we must either have $b=2$ or $b=3$. In particular, all $a_{k}$ must be at most $b-1$. We now rewrite our condition as $$a_{d}\left(4^{d}-(-b)^{d}\right)=\sum_{k=0}^{d-1}(-1)^{d-1-k} a_{k}\left(4^{k}-(-b)^{k}\right)$$ Since $4^{k}-(-b)^{k} \geq 0$ for $k \geq 0$, with equality only at $k=0$, we deduce $$a_{d}\left(4^{d}-(-b)^{d}\right) \leq \sum_{k \equiv d-1}(b-1)\left(4^{k}-(-b)^{k}\right)$$ If $d-1$ is even $(d$ is odd $)$, this gives $$a_{d}\left(4^{d}+b^{d}\right) \leq(b-1) \frac{4^{d+1}-4^{0}}{4^{2}-1}-(b-1) \frac{b^{d+1}-b^{0}}{b^{2}-1}$$ so $4^{d}<(b-1) \frac{4^{d+1}}{15} \Longrightarrow b>1+\frac{15}{4}$, which is impossible. Thus $d-1$ is odd ( $d$ is even), and we get $$a_{d}\left(4^{d}-b^{d}\right) \leq(b-1) \frac{4^{d+1}-4^{1}}{4^{2}-1}+(b-1) \frac{b^{d+1}-b^{1}}{b^{2}-1} \Longleftrightarrow \frac{b^{d}-1}{4^{d}-1} \geq \frac{a_{d}-\frac{4}{15}(b-1)}{a_{d}+\frac{b}{b+1}}$$ If $b=2$, then $a_{d}=1$, so $\frac{1}{2^{d}+1}=\frac{2^{d}-1}{4^{d}-1} \geq \frac{11}{25}$, which is clearly impossible $(d \geq 2)$. If $b=3$ and $a_{d}=2$, then $\frac{9^{d / 2}-1}{16^{d / 2}-1} \leq \frac{8}{15}$. Since $d$ is even, it's easy to check this holds only for $d / 2=1$, with equality, so $a_{k}=b-1$ if $k \equiv d-1(\bmod 2)$. Thus $\left(a_{d}, \ldots, a_{0}\right)=\left(2,2, a_{0}\right)$, yielding solutions $(22 x)_{3}$ (which do work; note that the last digit doesn't matter). Otherwise, if $b=3$ and $a_{d}=14$, then $\frac{9^{d / 2}-1}{16^{d / 2}-1} \leq \frac{4}{15}$. It's easy to check $d / 2 \in\{1,2\}$. If $d / 2=1$, we're solving $16 a_{2}-4 a_{1}+a_{0}=9 a_{2}+3 a_{1}+a_{0} \Longleftrightarrow a_{2}=a_{1}$. We thus obtain the working solution $(11 x)_{3}$. (Note that $110=\frac{1}{2} 220$ in bases $-4,3$.) If $d / 2=2$, we want $256 a_{4}-64 a_{3}+16 a_{2}-4 a_{1}+a_{0}=81 a_{4}+27 a_{3}+9 a_{2}+3 a_{1}+a_{0}$, or $175=91 a_{3}-7 a_{2}+7 a_{1}$, which simplifies to $25=13 a_{3}-a_{2}+a_{1}$. This gives the working solutions $(1210 x)_{3},(1221 x)_{3}$. (Note that $12100=110^{2}$ and $12210=110^{2}+110$ in bases $-4,3$.) The list of all nontrivial ( $\geq 2$-digit) solutions (in base -4 and $b$ ) is then $11 x, 22 x, 1210 x, 1221 x$, where $b=3$ and $x \in\{0,1,2\}$. In base 10 , they are $12+x, 2 \cdot 12+x, 12^{2}+x, 12^{2}+12+x$, with sum $3\left(2 \cdot 12^{2}+4 \cdot 12\right)+4(0+1+2)=1020$ Finally, we need to include the trivial solutions $n=1,2,3$, for a total sum of 1026.