Without loss of generality we may assume the $ x_i$ are nonnegative, by an appropriate (consistent) change in the signs of the $ a_i$. Now, take the set of $ k^n - 1$ nonzero vectors $ \textbf{a}$ formed by each possible combination of $ 0\leq a_i \leq k - 1$. Since the $ x_i$ are nonnegative, $ \textbf{a.x} \leq (k - 1)\sum x_i \leq (k - 1)\sqrt {n\sum x_i^2} = (k - 1)\sqrt {n}$ We therefore take each vector in our set and can put its dot product with x into one of the $ k^n - 1$ intervals $ \left[\frac {\lambda(k - 1)\sqrt {n}}{k^n - 1}, \frac {(\lambda + 1)(k - 1)\sqrt {n}}{k^n - 1} \right) (\lambda = 0,1,....,k^n - 2)$. If the $ \lambda = 0$ interval contains one of our dot products, we are done. Otherwise, by the pigeonhole principle, there exists an interval containing no less than two a vectors. Taking their difference gives a new vector lying in the desired $ |\textbf{a.x}| \leq \frac {(k - 1)\sqrt {n}}{k^n - 1}$ region, so such a vector always exists.

Apparently, this result was strengthened, by a paper of Moser (1970): The second moment method in combinatorial analysis. The following holds: Such $a_i's$ exist, so that $$ |\sum_i a_i x_i|\leqslant \sqrt{\frac{k^2-1}{k^{2n}-1}}. $$Note that as $n$ grows, Moser's bound is significantly stronger than this IMO problem. Now, a paper by Karmakar-Karp-Lueker-Odlyzko from 1986, titled ``Probabilistic Analysis of Optimum Partitioning" references the aforementioned result by Moser, and notes that a significantly weaker bound can be achieved by a very simple Pigeonhole argument, and lays out details, which precisely happens to be this IMO problem! I want to touch upon certain research problems revolving around this problem. This problem is broadly known as optimal partitioning (or number partitioning). Formally, let $X_1,\dots,X_n$ be real numbers. Find a vector $\sigma=(\sigma_1,\dots,\sigma_n)\in\{-1,1\}^n$ of signs such that $|\sum_{1\leq i\leq n}\sigma_i X_i|$ is as minimal as possible. In the case $X_1,\dots,X_n\in\mathbb{R}^d$, the problem is now known as vector balancing, where the idea is to find a set of indices as above such that $\|\sum_i \sigma_i X_i\|_\infty$ is as small as possible, where for a $v=(v_1,\dots,v_d)\in\mathbb{R}^d$, $\|v\|_\infty = \max_i |v_i|$. Since the search space involves $2^n$ elements, such problems are NP-hard, in the sense of computational complexity. Several interesting ideas around this problem are as follows. Let $X_1,\dots,X_n$ above be i.i.d. standard normal random variables. Then the optimal value of this partitioning is known to be $\Theta(\sqrt{n}2^{-n})$ with high probability, whereas the optimal polynomial time algorithm achieves a performance of only $\Theta(2^{-(\log n)^2})$! Closing such gaps, or showing evidence of computational hardness are currently open problems.

Just we can use PHP and C-S Inequality