Fix $k\in \mathbb{N}$. Let $a_1, a_2, \cdots, a_k\in\left\{1,2,\cdots, k-1\right\}$.
I'm looking for an algorithm to choose an index set $I\subset\left\{1,2,\cdots,k\right\}$ such that $$\sum_{i\in I}a_i=k\cdot N $$ for some integer $N$.
I guess there must be a such index. Is there an good algorithm to be recommended?
You have that $$ a_{1}, a_{1} + a_{2}, \dots, \sum_{i=1}^{t} a_{i}, \dots, a_{1} + a_{2} + \dots + a_{k} $$ are $k$ (not necessarily) distinct numbers. If they have distinct remainders when divided by $k$, then one of the remainders will have to be zero, so that particular sum, say $\sum_{i=1}^{t_{0}} a_{i}$ will be divisible by $k$.
If the remainders are not distinct, we will have for some $t_{0} < t_{1}$ amd some $q_{0}, q_{1}$ and $0 \le r < k$ $$ \sum_{i=1}^{t_{0}} a_{i} = q_{0} k + r = q_{1} k + r = \sum_{i=1}^{t_{1}} a_{i}, $$ hence $$ \sum_{i=1}^{t_{1}} a_{i} - \sum_{i=1}^{t_{0}} a_{i} = \sum_{i=t_{0} + 1}^{t_{1}} a_{i} = (q_{1} - q_{0}) k $$ is divisible by $k$,