SCHWEITZER 1992 Problem 2

Let p be a prime and $a_1 , a_2 , ..., a_k$ pairwise incongruent modulo p . Prove that $[\sqrt {k-1}]$ of the elements can be selected from $a_i$ 's such that adding any numbers different from the selected ones will never give a number divisible by p .