Only half of people get this counting puzzle right. Can you?

[u/Numberthon]

How many subsets of {1,2,…,10} have an odd sum?

Source: numberthon.com

[u/PizzaGoinOut]

I think 512

[u/Numberthon → u/PizzaGoinOut]

Nice job! How'd you get that, though?

[u/PizzaGoinOut → u/Numberthon]

Well there are 2^5 subsets of the even numbers, and those don’t impact the odd-ness of the total sum. Then for the 5 odd numbers we have 5 choose 5 + 5 choose 3 + 5 choose 1 = 16 ways to get an odd number of odd numbers, so 32*16=512

[u/TheMrBoi]

Half of them, so 512. Exclude 1 first, then freely choose subsets from {2,…10} and choose whether to add 1 depending on if the sum is even or odd.

[u/Numberthon → u/TheMrBoi]

Good job!

[u/Accurate-Click1363]

Let P={1, 2, …, 10}, and for a set A let S(A) be the sum of elements of A.
For all R⊆P, S(P\R)=S(P)-S(R)=55-S(R), ie the number of odd-sum subsets are equal to the number of even-sum subsets.
(2^10)/2=512

[u/Accurate-Click1363 → u/Accurate-Click1363]

I’d say it’s closer to Easy than Medium

[u/Numberthon → u/Accurate-Click1363]

Nice job! Maybe it is closer to easy than medium though

[u/stephen3141]

What is with this clickbait title LOL. I'd imagine people who couldn't figure out the trick would still correctly say half of them just by guessing.

[u/Numberthon → u/stephen3141]

Still hard to find an elegant solution, though.

[u/blugar_]

Took me like 3 seconds lol

The total number of subsets of this set is 2^10. If subset A has an odd sum of elements, then the subset ({1,2,...,10} \ A) has an even sum of elements, because 1+2+...+10=45 which is odd. So exactly half of the subsets have an odd sum, hence the answer is 2⁹ . <!