Balkan Mathematical Olympiad competition problems

Solution 1. We will show that there is a unique such $n$-tuple: $a_k = 2^{n-1} + 2^{k-1} - 1$ for $k = 1, \dots, n-1$.
Write $N = 2^n - 1$ and $f_k(x) = \left[ \frac{2^k x + a_k}{N} \right]$ for $k = 0, 1, \dots, n-1$, where $a_0 = 0$. Since
$$\sum_{k=0}^{n-1} f_k(m) - \sum_{k=0}^{n-1} f_k(m-1) = 1,$$
for each $m \in \mathbb{Z}$, there is exactly one $k$ for which $f_k(m) = f_k(m-1) + 1$. We work modulo $N$. The last equality holds if and only if $2^k m + a_k \in \{0, 1, \dots, 2^k - 1\}$. I.e. if and only if
$$2^k m \in \{-a_k, 1-a_k, \dots, 2^k-1-a_k\}.$$
Multiplying with $2^{n-k}$, and noting that $2^n \equiv 1 \bmod N$, we get the following:
For each $m \in \mathbb{Z}$ there is a unique $k \in \{0, 1, \dots, n-1\}$ such that $m \in B_k$ (modulo $N$) where
$$B_k = \{b_k, b_k + 2^{n-k}, \dots, b_k + (2^k - 1)2^{n-k}\}$$
with $b_k = -2^{n-k}a_k$. Therefore the problem condition is equivalent to $\bigcup_{k=0}^{n-1} B_k$ being a partition of $\{0, 1, \dots, N-1\}$.
For a number $b$ and set a $A \subseteq \mathbb{Z}$ we write $b + A = \{b + a : a \in A\}$. With this notation, $B_{n-1} = b_{n-1} + \{0, 2, 4, \dots, 2^n - 2\}$. The set $B_{n-2} = b_{n-2} + \{0, 4, 8, \dots, 2^n - 4\}$ is contained in $\overline{B_{n-1}} = b_{n-1} + \{1, 3, \dots, 2^n - 3\}$, implying $b_{n-2}, b_{n-2} + 2^n - 4 \in \overline{B_{n-1}}$, which holds only if $b_{n-2} \equiv b_{n-1} + 1$. Further, the set $B_{n-3} = b_{n-3} + \{0, 8, 16, \dots, 2^n - 8\}$ is contained in $\overline{B_{n-1}} \cup \overline{B_{n-2}} = b_{n-1} + \{3, 7, \dots, 2^n - 5\}$, so we must have $b_{n-3} \equiv b_{n-1} + 3$. Similarly, $b_{n-4} \equiv b_{n-1} + 7$ etc. In general, $b_{n-k} \equiv b_{n-1} + 2^{k-1} - 1$ for $k = 1, \dots, n-1$. It follows that $b_0 \equiv b_{n-1} + 2^{n-1} - 1$. On the other hand, we have $b_0 = 0$, which gives $b_{n-1} \equiv 1 - 2^{n-1}$ and therefore $b_k \equiv 2^{n-1-k} - 2^{n-1}$. Thus $a_k \equiv -2^k b_k \equiv 2^{n+k-1} - 2^{n-1} \equiv 2^{n-1} + 2^{k-1} - 1$ for $k = 1, \dots, n-1$.
Finally, $\sum_k f_k(0) = 0$ implies $a_k < N$ for all $k$, so we conclude that $a_k = 2^{n-1} + 2^{k-1} - 1$ for each $k = 1, 2, \dots, n-1$.

Solution 2. We will use the identity
$$[x] + \left\lfloor x + \frac{1}{N} \right\rfloor + \left\lfloor x + \frac{2}{N} \right\rfloor + \dots + \left\lfloor x + \frac{N-1}{N} \right\rfloor = [Nx]$$
which holds for every $x \in \mathbb{R}$ and every $N \in \mathbb{N}$. (One can check this by noting that the difference between the two sides of the identity is periodic with period $1/N$ and that the identity clearly holds for $x \in [0, \frac{1}{N})$.)
Writing $a_0 = 0$ and $N = 2^n - 1$ we observe that
$$m = \sum_{k=0}^{n-1} \left\lfloor \frac{2^k m + a_k}{N} \right\rfloor = \sum_{r=0}^{2^k-1} \sum_{r=0}^{2^k-1} \left\lfloor \frac{m + \frac{a_k}{2^k}}{N} + \frac{r}{2^k} \right\rfloor = \sum_{k=0}^{n-1} \sum_{r=0}^{2^k-1} \left\lfloor \frac{m + \frac{a_k + rN}{2^k}}{N} \right\rfloor . \quad (1)$$
It follows that $c_{r,k} = \left\lceil \frac{a_k+rN}{2^k} \right\rceil$ are all distinct modulo $N$ for $k = 0, 1, \dots, n-1$ and $r = 0, 1, \dots, 2^k - 1$. Indeed if two (or more) of them are congruent to $t$, then writing $f(t)$ for the right hand side of (1) we get $1 = f(-t) - f(-t-1) \ge 2$, a contradiction.
Since $N = 2^n - 1$, then $c_{r,k} = r2^{n-k} + d_{r,k}$, where $d_{r,k} = \left\lceil \frac{a_k-r}{2^k} \right\rceil$. Because $c_{0,0} = 0$, then $c_{0,k} \ne 0$ for each $k \ne 0$ giving $a_k \ge 2^k$ for each $k \ge 1$. Setting $m = 0$ in the original equation gives $a_k < N$ for each $k$ and so $d_{0,k} \le 2^{n-k} - 1$ for each $k$. Furthermore
$$2^{n-k} - 1 \ge d_{0,k} \ge d_{1,k} \ge \dots \ge d_{2^k-1,k} \ge d_{2^k,k} = d_{0,k} - 1 \ge 0. \quad (2)$$
In particular $0 \le c_{r,k} = r2^{n-k} + d_{r,k} \le (2^n - 2^{n-k}) + (2^{n-k} - 1) = N$. For $k = 0, 1, 2, \dots, n-1$ define $A_k = \{c_{r,k} : r = 0, 1, \dots, 2^k - 1\}$. From the above, since $A_0 = \{0\}$, we must have that $A_1 \cup A_2 \cup \dots \cup A_{n-1} = \{1, 2, \dots, N-1\}$.
For a natural number $t$ let $v_2(t)$ be as usual the largest exponent such that $2^{v_2(t)}|t$. Let
$$f(t) = n - v_2(t) - 1, \quad g(t) = \frac{t - 2^{v_2(t)}}{2^{1+v_2(t)}} , \quad \text{and} \quad h(t) = 2^{f(t)} - 1 - g(t).$$
Note that $f(t)$ uniquely determines $v_2(t)$ and together with $g(t)$ they uniquely determine $t$. Similarly $h(t)$ and $g(t)$ uniquely determine $t$.
Claim. For each $t \in \{1, 2, \dots, 2^{n-1} - 1\}$ we have:
(i) $d_{g(t),f(t)} = 2^{v_2(t)}$,
(ii) $d_{h(t),f(t)} = 2^{v_2(t)} - 1$,
(iii) $c_{g(t),f(t)} = t$,
(iv) $c_{h(t),f(t)} = N - t$.
Proof of Claim. We proceed by induction on $t$. For $t = 1$ we have $v_2(1) = 0, f(1) = n-1, g(1) = 0$ and $h(1) = 2^{n-1} - 1$. From (2) we have $1 \ge d_{0,n-1}$ and $d_{0,n-1} - 1 \ge 0$ proving (i). Also, $c_{g(1),f(1)} = c_{0,n-1} = d_{0,n-1} = 1$ proving (iii). From (2) we have $1 \ge d_{2^{n-1}-1,n-1} \ge 0$. But $c_{2^{n-1}-1,n-1} = 2^n - 2 + d_{2^{n-1}-1,n-1} = N - 1 + d_{2^{n-1}-1,n-1}$. Since $c_{2^{n-1}-1,n-1} \le N-1$ we deduce both (ii) and (iv).
Assume now that the result is true for $t = s - 1$. We will prove the result for $t = s$.
Case 1: If $s - 1 = 2u$ is even, then $v_2(s) = 0$, so $f(s) = n-1, g(s) = u$ and $h(s) = 2^{n-1} - 1 - u$.
By the induction hypothesis, since all the $c_{r,k}$'s are distinct, we must have
$$s \le c_{g(s),f(s)} = 2u + d_{g(s),f(s)} = s - 1 + d_{g(s),f(s)}$$
and
$$N - s \ge c_{h(s),f(s)} = 2^n - 2 - 2u + d_{h(s),f(s)} = N - s + d_{h(s),f(s)}.$$
From the above we must have $d_{g(s),f(s)} \ge 1$ and $d_{h(s),f(s)} \le 0$. But from (2) any two $d_{r,k}$'s for fixed $k$ differ by at most 1. This can only be achieved if we have equalities everywhere proving (i)-(iv).
Case 2: If $s - 1 = 2u + 1$ is odd, then we write $s = 2u + 2 = 2^v w$ for some odd $w$. Then $v_2(s) = v$ and so $k = f(s) = n - 1 - v$ and $r = g(s) = (w - 1)/2$. Also $h(s) = 2^k - 1 - r$. By the induction hypothesis we must have
$$s \le c_{r,k} = r2^{n-k} + d_{r,k} = 2^v(w-1) + d_{r,k} = s - 2^v + d_{r,k}$$
and
$$\begin{align*} N - s \ge c_{h(s),k} &= (2^k - 1 - r)2^{n-k} + d_{h(s),k} \\ &= 2^n - 2^{v+1} - s + 2^v + d_{h(s),k} \\ &= N + 1 - s - 2^v + d_{h(s),k}. \end{align*}$$
From the above we must have $d_{r,k} \ge 2^v$ and $d_{h(s),k} \le 2^v - 1$. As in Case 1 we must have equalities everywhere proving (i)-(iv). $\square$
For $t = 2^{n-1} - 2^{n-k-1}$ we have $v_2(t) = n-k-1, f(t) = k, g(t) = 2^{k-1}-1$ and $h(t) = 2^k - 1 - (2^{k-1}-1) = 2^{k-1}$. Thus from (ii) and (iv) we get
$$\left[ \frac{a_k - (2^{k-1} - 1)}{2^k} \right] = 2^{n-k-1} \quad \text{and} \quad \left[ \frac{a_k - 2^{k-1}}{2^k} \right] = 2^{n-k-1} - 1.$$
This is only possible if $a^k = 2^k \cdot 2^{n-k-1} + (2^{k-1}-1) = 2^{n-1} + 2^{k-1} - 1$ as required.