Middle European Mathematical Olympiad 2018 Problem T-4

Let $n$ be a positive integer and $u_1, u_2, \ldots, u_n$ be positive integers not larger than $2^k$, for some integer $k \geq 3$. A representation of a non-negative integer $t$ is a sequence of non-negative integers $a_1, a_2, \ldots, a_n$ such that $$t = a_1 u_1 + a_2 u_2 + \cdots + a_n u_n.$$

Prove that if a non-negative integer $t$ has a representation, then it also has a representation where less than $2k$ of the numbers $a_1, a_2, \ldots, a_n$ are non-zero.