Saudi Arabian Mathematical Competitions, 2015

Let $0 \leq k \leq n$ be two integers written in base $3$ as
$$n = ^{(3)} \overline{n_{m} n_{m-1} \cdots n_{1} n_{0}}, \quad k = ^{(3)} \overline{k_{m} k_{m-1} \cdots k_{1} k_{0}}$$
such that $n_{m} \neq 0$. We know from Lucas's theorem that
$$r_{k} \equiv \binom{n}{k} \equiv \prod_{i=0}^{m} \binom{n_{i}}{k_{i}} \quad (\bmod 3)$$
If there exists $0 \leq i \leq m$ such that $k_{i} > n_{i}$ then $\binom{n_{i}}{k_{i}} = 0$ and therefore $r_{k} = 0$. Therefore, from now on we will restrict to $0 \leq k \leq n$ with $k_{i} \leq n_{i}$ for all $0 \leq i \leq m$.
Let $0 \leq i \leq m$. If $n_{i} = 0$ then $k_{i} = 0$. If $n_{i} = 1$ then $k_{i} \in \{0, 1\}$. In all these cases $\binom{n_{i}}{k_{i}} = 1$. If $n_{i} = 2$ then $k_{i} \in \{0, 1, 2\}$ and $\binom{n_{i}}{k_{i}} = 1$ if $k_{i} \neq 1$ and $\binom{n_{i}}{k_{i}} = 2$ if $k_{i} = 1$. Therefore, if the number $a$ of pairs $(n_{i}, k_{i}) = (2, 1)$, when $0 \leq i \leq m$, is odd then $\binom{n}{k} \equiv 2^{a} \equiv 2 \pmod{3}$, otherwise $\binom{n}{k} \equiv 1 \pmod{3}$. We deduce that
$$s(n) = 2A(n) + B(n),$$
where $A(n)$ is the number of pairs of integers $(n, k)$ such that $0 \leq k_{i} \leq n_{i}$ for all $0 \leq i \leq m$ and the number of pairs $(n_{i}, k_{i}) = (2, 1)$, when $0 \leq i \leq m$, is odd, while $B(n)$ is the number of pairs of integers $(n, k)$ such that $0 \leq k_{i} \leq n_{i}$ for all $0 \leq i \leq m$ and the number of pairs $(n_{i}, k_{i}) = (2, 1)$, when $0 \leq i \leq m$, is even.
Denote by $r$ the number of $0$'s in $n_{0}, n_{1}, n_{2}, \ldots, n_{m}$, by $s$ the number of $1$'s and by $t$ the number of $2$'s. We have
$$A(n) = 2^{s} \left( \binom{t}{1} 2^{t-1} + \binom{t}{3} 2^{t-3} + \binom{t}{5} 2^{t-5} + \cdots \right)$$
and
$$B(n) = 2^{s} \left( \binom{t}{0} 2^{t} + \binom{t}{2} 2^{t-2} + \binom{t}{4} 2^{t-4} + \cdots \right).$$
We deduce that
$$\begin{aligned} s(n) & = 2^{s} \left( (\binom{t}{0} + \binom{t}{1}) 2^{t} + (\binom{t}{2} + \binom{t}{3}) 2^{t-2} + \cdots \right) \\ & = 2^{s} \left( \binom{t+1}{1} 2^{t} + \binom{t+1}{3} 2^{t-2} + \cdots \right) \\ & = 2^{s} \cdot \frac{(2+1)^{t+1} - (2-1)^{t+1}}{2} = 2^{s-1} (3^{t+1} - 1). \end{aligned}$$

a. If the first digit on the left of $n$ is $2$ then
$$\begin{aligned} n \geq \overline{2 \underbrace{00 \cdots 0}_{r} \underbrace{11 \cdots 1}_{s} \underbrace{22 \cdots 2}_{t-1}} & = 2 \cdot 3^{r+s+t-1} + \frac{3^{s} - 1}{2} \cdot 3^{t-1} + 2 \cdot \frac{3^{t-1} - 1}{2} \\ & = \frac{4 \cdot 3^{r+s} + 3^{s} + 1}{2} \cdot 3^{t-1} - 1 \end{aligned}$$
Therefore
$$n - s(n) \geq \frac{(4 \cdot 3^{r} + 1) \cdot 3^{s} - 9 \cdot 2^{s} + 1}{2} \cdot 3^{t-1} - 1 + 2^{s-1}.$$
- If $r \geq 1$ then $n - s(n) \geq \frac{13 - 9 + 1}{2} \cdot \frac{1}{3} - 1 + \frac{1}{2} > 0$
- If $r = 0$ and $s \geq 2$ then
$$n - s(n) \geq \frac{45 \cdot 3^{s-2} - 36 \cdot 2^{s-2} + 1}{2} \cdot 3^{t-1} - 1 + 2 > 0.$$
- If $r = 0$ and $s = 1$ then $n \leq \overline{22 \cdots 2 1}_{t} = 3^{t+1} - 2 < 3^{t+1} - 1 = s(n)$.
- If $r = s = 0$ then $n = \overline{22 \cdots 2}_{t} = 3^{t} - 1 < \frac{3^{t+1} - 1}{2} = s(n)$.

b. If the first digit on the left of $n$ is $1$ then $s \geq 1$ and
$$\begin{aligned} n \geq \overline{1 \underbrace{00 \cdots 0}_{r} \underbrace{11 \cdots 1}_{s-1} \underbrace{22 \cdots 2}_{t}} & = 3^{r+s+t-1} + \frac{3^{s-1} - 1}{2} \cdot 3^{t} + 2 \cdot \frac{3^{t} - 1}{2} \\ & = \frac{2 \cdot 3^{r+s-1} + 3^{s-1} + 1}{2} \cdot 3^{t} - 1 \end{aligned}$$
Therefore
$$n - s(n) \geq \frac{(2 \cdot 3^{r} + 1) \cdot 3^{s-1} - 6 \cdot 2^{s-1} + 1}{2} \cdot 3^{t} + 2^{s-1} - 1.$$
- If $r \geq 1$ and because $s \geq 1$ we have
$$n - s(n) \geq \frac{7 \cdot 3^{s-1} - 6 \cdot 2^{s-1} + 1}{2} \cdot 3^{t} + 2^{s-1} - 1 \geq 1 + 1 - 1 > 0.$$
- If $r = 0$ and $s \geq 3$ then
$$n - s(n) \geq \frac{3 \cdot (3^{s-1} - 2^{s}) + 1}{2} \cdot 3^{t} + 2^{s-1} - 1 \geq 2 + 4 - 1 > 0.$$
- If $r = 0$ and $s = 2$ then $n \leq \overline{1 \underbrace{22 \cdots 2}_{t} 1} = 2(3^{t+1} - 1) = s(n)$, and the equality is satisfied precisely when $n = \overline{1 \underbrace{22 \cdots 2}_{t} 1}$.
- If $r = 0$ and $s = 1$ then
$$n = \overline{1 \underbrace{22 \cdots 2}_{t}} = 3^{t+1} - 3^{t} - 1 < 3^{t+1} - 1 = s(n).$$

Finally, we deduce that if in the digits of $n$ written in base $3$,
(a) there is at least one $0$, or three $1$'s, or no $0$'s and two $1$'s with the digit on the left is $2$, then $s(n) < n$;
(b) $n = \overline{122 \cdots 21}$, then $s(n) = n$;
(c) there are no $0$'s and two $1$'s with the digit on the left is $1$ and the digit on the right is $2$, or there are no $0$'s and at most one $1$, then $s(n) > n$.