Maths Olympiad Prep

Library / /504 of 520

Number theory Difficulty 4.7 AIME Prove it

Prove by contradiction that the proposition "Among the natural numbers aa, bb, cc, exactly one is even" requires the assumption of:
A: aa, bb, cc are all odd
B: aa, bb, cc are all even
C: aa, bb, cc are all odd or at least two are even
D: aa, bb, cc at least two are even

Solution

To prove by contradiction that among the natural numbers aa, bb, and cc, exactly one is even, we need to assume the opposite of what we want to prove, and show that this leads to a contradiction.

Let's go through each of the provided options:
- Option A: Assuming aa, bb, and cc are all odd means there are no even numbers, which contradicts the statement that exactly one is even. This is a valid assumption for proof by contradiction.
- Option B: Assuming aa, bb, and cc are all even contradicts the premise outright since it provides more than one even number, but it is not a comprehensive contrary since it does not cover the cases where two numbers are even.
- Option C: Assuming aa, bb, and cc are all odd or at least two are even covers all possibilities that contradict the original statement. If all numbers are odd, there are no even numbers; if at least two numbers are even, then there are more than one even numbers. This option fully captures the essence of the contradiction.
- Option D: Assuming at least two numbers are even is only a partial contradiction, as it does not address the possibility that all might be odd.

To prove by contradiction, we must consider all cases contrary to the proposition that exactly one number is even. Option C is the most appropriate choice as it covers the full range of contradictory scenarios.

Thus, we have:
C: a, b, c are all odd or at least two are even \boxed{\text{C: }a,\ b,\ c\ \text{are all odd or at least two are even}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.