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$.
Problem
Source: 2018 Saudi Arabia IMO TST III p2
Tags: number theory
05.03.2022 13:19
Let $2^{[n]}$ denote the family of subsets of $[n]:\{1, 2, \dots, n\}$. Then the map $f: 2^{[n]}\mapsto 2^{[n]} $ given by $$f: A\to n+1-A=\bigcup_{x\in A}\{n+1-x\}$$is a bijection. We may pair up $(A, f(A))$, unless $A$ is a fixed point of $f$. Thus we wish to calculate the parity of the set of fixed points of $f$. Notice that $A=f(A)$ iff $x\in A\implies n+1-x\in A$. When $n$ is even a fixed point $A$ would be the union of pairs $(x, n+1-x)$ (notice that these are different), so the average of this set would be $\frac{n+1}{2}\not\in \mathbb{Z}$. Thus we can pair the arabic sets up with $f$ and find that there is an even number of arabic sets. When $n$ is odd, consider the pairs $(x, n+1-x)$ $x\neq \frac{n+1}{2}$ and the singleton $(\frac{n+1}{2})$ by a similar reasoning the average will be ${n+1}{2}$, which this time is an integer (always!). The number of such pairs + singleton is $\frac{n+1}{2}$, so the number of non empty subsets is given by $2^{\frac{n+1}{2}}-1\equiv 1\pmod 2$, so this time the number of fixed points is odd. $\blacksquare$