Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"
Posted: Fri Apr 30, 2021 5:33 pm
by Anindya Biswas
Let $n\geq1$ be an integer. A non-empty set is called “good” if the arithmetic mean of its elements is an integer. Let $T_n$ be the number of good subsets of $\{1,2,3,\cdots,n\}$. Prove that for all integers $n$, $T_n$ and $n$ leave the same remainder when divided by $2$.
Re: Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"
Posted: Mon May 03, 2021 8:29 pm
by Mehrab4226
I couldn't solve it myself . But since no one is posting the answer I am doing it.
This problem came in the Putnam-2002(A3)
Note that each of the sets $\{ 1\} ,\{ 2\} ,...,\{ n\}$ has the desired property. Moreover, for each set $S$ with integer average m that does not contain m, $S \cup {m}$ also
has average $m$, while for each set $T$ of more than
one element with integer average $m$ that contains$ m$,
$T \ {m}$ also has average $m$. Thus the subsets other than
$\{ 1 \},\{ 2 \},...,\{ n \} $can be grouped in pairs,
So $T_n= \text{All the sets like S or T} + \text{All the sets with 1 element} = Even+n$
So $n$ and $T_n$ have the same parity. $\square$
Re: Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"
Posted: Mon May 03, 2021 8:30 pm
by Mehrab4226
After seeing the solution, I was like "Keno parlam na!!!"
. But since no one is posting the answer I am doing it.