Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"

Unread post by Anindya Biswas » Fri Apr 30, 2021 5:33 pm

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$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"

Unread post by Mehrab4226 » Mon May 03, 2021 8:29 pm

I couldn't solve it myself :oops: . 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$
Last edited by Mehrab4226 on Mon May 03, 2021 9:21 pm, edited 1 time in total.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 04 - National Math Camp 2021 Combinatorics Test - "Alternating Parity"

Unread post by Mehrab4226 » Mon May 03, 2021 8:30 pm

After seeing the solution, I was like "Keno parlam na!!!"
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply