4

Part of 2013 China Second Round Olympiad

Problems(1)

Exist subset with sum divisible by n

Source: China Second Round (A) 2013 Q4

n,k

be integers greater than

1

n<2^k

. Prove that there exist

2k

integers none of which are divisible by

n

, such that no matter how they are separated into two groups there exist some numbers all from the same group whose sum is divisible by

n