Problem

Source: 2018 Saudi Arabia IMO TST III p2

Tags: number theory



A non-empty subset of $\{1,2, ..., n\}$ is called arabic if arithmetic mean of its elements is an integer. Show that the number of arabic subsets of $\{1,2, ..., n\}$ has the same parity as $n$.