Problem 18 - Discrete Mathematics with Applications

Question

Prove that any set \(S\) of three integers contains at least two integers whose sum is even. (Hint: Define a suitable function \(f: S \rightarrow\\{0,1\\}\) and use Exercise \(17 .\) )

Step-by-Step Solution

Answer

To prove that any set $S$ of three integers contains at least two integers whose sum is even, we define the function $f: S \rightarrow \{0,1\}$ as $f(x) = x \pmod{2}$, where x belongs to $S$. Since there are only two possible outputs for $f(x)$ and three integers in $S$, by the Pigeonhole Principle, at least two integers in $S$ share the same parity (either both are even or both are odd). When two integers with the same parity are added, the result is always even. Therefore, there must be at least two integers in $S$ whose sum is even.

Step 1: Understanding the Pigeonhole Principle (Exercise 17)

The Pigeonhole Principle states that if k+1 items are put into k containers, then at least one container has more than one item. In this problem, we will use the function "f" to map the integers to the containers 0 and 1. We will define this function appropriately to ensure that the Pigeonhole Principle applies to the three integers in set S.

Step 2: Define the function f

We'll define the function f in the following manner: For each integer x in set S, f(x) = x modulo 2. In other words, f(x) takes the remainder when dividing x by 2. The function f will either output 0 or 1, representing even integers (remainder 0) or odd integers (remainder 1), respectively.

Step 3: Apply the Pigeonhole Principle to set S with function f

As we have three integers in the set S, and our function f only has two possible outputs (0 and 1), by the Pigeonhole Principle, at least one of the outputs must occur twice. This means that among the three integers in the set S, at least two of them have the same parity (either even or odd). We can represent the three integers as a, b, and c, and the corresponding function values as f(a), f(b), and f(c).

Step 4: Summing the two integers with the same parity

Since we know that at least two of the integers in the set S have the same parity, let's say that f(a) = f(b), without loss of generality. Since f(x) was defined as the remainder when dividing x by 2, f(a) = f(b) implies that both a and b have the same remainder when divided by 2. In other words, both a and b are either even or odd. Now we need to sum up these two integers. If both a and b are even, their sum is even (even + even = even). If both a and b are odd, their sum is also even (odd + odd = even).

Step 5: Conclusion

We have shown that no matter the integers in set S, there will always be two integers with the same parity (either even or odd) by applying the Pigeonhole Principle to the function f. Additionally, we have demonstrated that the sum of any two integers with the same parity is even. Therefore, any set S of three integers contains at least two integers whose sum is even.

Key Concepts

Understanding Even and Odd Integers

Even and odd integers are fundamental in understanding various mathematical concepts such as sums and remainders. An even integer is any integer that can be divided by 2 without leaving a remainder. Examples are 0, 2, 4, 6, and so forth.
Odd integers are numbers that, when divided by 2, leave a remainder of 1. Common examples include 1, 3, 5, 7, etc.
Clarifying this classification helps in determining the nature of sums:

• Adding two even numbers results in another even number (e.g., 2 + 4 = 6).
• When you add two odd numbers, the result is always an even number (e.g., 3 + 5 = 8).
• An even number plus an odd number results in an odd number (e.g., 2 + 3 = 5).

These properties are why determining the evenness or oddness of numbers in a set allows one to predict the evenness or oddness of their sums.

Decoding the Modulo Operation

The modulo operation is a mathematical tool that finds the remainder after division of one number by another. It is often used to determine the evenness or oddness of a number.
When an integer is divided by 2, if the remainder is 0, the number is even. If the remainder is 1, the number is odd.
For example:

• For 7 modulo 2, the calculation is 7 ÷ 2 = 3 with a remainder of 1, thus 7 is odd.
• For 8 modulo 2, the calculation gives a remainder of 0, classifying 8 as even.

In the context of integer sets, using modulo 2 helps categorize numbers into two groups: those that are even and those that are odd. This classification is crucial when applying principles like the Pigeonhole Principle, where grouping allows easier analysis on possible outcomes.

Grasping the Concept of Parity

Parity refers to whether an integer is even or odd, and is a basic characteristic utilized in various mathematical proofs and operations.
It comes into play substantially when assessing integer sums or sequences, as having common parity (both even or both odd) among numbers often leads to specific consequences in mathematical operations.
For example, when two integers share the same parity:

• If both have even parity (both even), their sum is also an even integer.
• If both have odd parity (both odd), surprisingly, their sum will be even as well.

This phenomenon of parity is leveraged to make predictions about the evenness or oddness of sums in a set based on the individual properties of its elements. Understanding parity is crucial for implementing concepts like the Pigeonhole Principle in advanced mathematical reasoning.