3
$\begingroup$

The task is the following:

$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...

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user49685 Feb 12 '16 at 11:42
1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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$$

$\endgroup$
3
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.