# How many $3$-tuples $(a, b, c) \in M^3$ are there such $a+b+c$ is even?

$M= \left \{ 1,2, ... 99,100 \right \}$

How many $3$-tuples $(a, b, c) \in M^3$ are there such $a+b+c$ is even?

I tried to solve it this way:

There are only two possibilities that $a+b+c$ is even:

First I look at this as a unordered set: Order isn't important and you can put something back gives me:

one element is even and the other two are not:

$$\binom{50+1-1}{1}\binom{50 +2 - 1}{2}$$

or all three elements are even which gives me:

$$\binom{50+3-1}{3}$$

Now I add both and multiply it by $3!$ because there are $6$ possibilities for an unordered set to be ordered and order is important in tuples.

I get $$3! \cdot \left[\binom{50 +2}{3} + 50 \binom{50 +1}{2}\right] = 515. 100$$

I think the solution is $500.000$ isn't it? Can't find my mistake...

• Since others have provided you with pretty much full answers, so I just point out where you got wrong in your work. You cannot just multiply everything by $3!$; say the tuples $(8; 8; 8)$ indeed satisfies the condition, but you cannot shuffle this tuple. The same goes for $(11; 11; 6)$, there are not 6, but only 3 arrangements for this tuple. – user49685 Feb 12 '16 at 11:42

The problem is tuples with repeated numbers. If you've counted $(2,4,4)$ as a tuple in the first stage, then there are only $3$ (not $3!$) permutations of the unordered numbers.

If it helps, there are $125.000$ combinations with all $a,b,c$ even, and $375.000$ with two odd and one even.

Total number of tuples - $100^3$. Half of them are even, half of them are odd by symmetry. So, answer is $500,000$. (Remember!! $a,b,c$ can be equal)
Proof for symmetry? Well, see this- For every sum which is odd, there exists a sum which is even, obtained by adding $1$ to one of the numbers contributing to the odd sum!
eg: If you give me $100+100+99 = 299$, I give you $100+100+100=300$
similarly, prove the inverse- For every sum which is even, there exists a sum which is odd, obtained by subtracting $1$ from one of the numbers contributing to the even sum!

Your assumption that there are $3!$ of arranging each ordered triple $(a, b, c)$ is only valid if $a$, $b$, and $c$ are distinct. However, $(a, b, c) \in M^3$, so $a$, $b$, and $c$ need not be distinct.

Let's consider cases.

Three even numbers are selected:

1. There are $50$ ordered triples of the form $(a, a, a)$.
2. Ordered triples $(a, b, c)$ in which exactly two of the numbers are equal. We have $50$ choices for the repeated number, $\binom{3}{2}$ choices for their places in the triples, and $49$ choices for the other even number, so there are $$50 \cdot 49 \cdot \binom{3}{2}$$ such triples.
3. Ordered triples $(a, b, c)$ in which each even number is distinct. There are $50$ choices for $a$, $49$ choices for $b$, and $48$ choices for $c$. Hence, there are $50 \cdot 49 \cdot 48$ of these.

One even number and two odd numbers are selected:

1. Ordered triples with one even number and a repeated odd number. There are $50$ choices for the even number, $3$ choices for its location, $50$ choices for the repeated odd number, and one way of placing the repeated odd number in the open locations. Hence, there are $50^2 \cdot 3$ of these.

2. Ordered triples with one even number and two distinct odd numbers. There are $50$ choices for the even number, $\binom{50}{2}$ choices for the two odd numbers, and $3!$ permutations of the three distinct numbers. Hence, there are $$50 \cdot \binom{50}{2} \cdot 3!$$ of these.

Since the cases are mutually exclusive, the total number of ways in which the numbers can be selected is $$50 + 50 \cdot 49 \cdot \binom{3}{2} + 50 \cdot 49 \cdot 48 + 50^2 \cdot 3 + 50 \cdot \binom{50}{2} \cdot 3! = 500,000$$

You could just list the permissible odd-even configurations as:

$OEE,\;\; EOE,\;\; EEO,\;\;$ and $\;\;EEE\;\;$ each with $50^3$ possibilities,

thus ans $=4\times50^3$