SOLUTION: Let S be a set of distinct integers. What is the smallest number of elements that S must contain, to ensure that S has a nonempty subset, where the sum of the elements in the subs

Question 1210235: Let S be a set of distinct integers. What is the smallest number of elements that S must contain, to ensure that S has a nonempty subset, where the sum of the elements in the subset is divisible by 2?
Found 3 solutions by CPhill, greenestamps, ikleyn:
Answer by CPhill(1959)   (Show Source): You can put this solution on YOUR website!
That's an interesting problem involving divisibility! Let's break it down to find the smallest number of elements $S$ must contain to guarantee a nonempty subset whose sum is divisible by 2.
Consider the remainders when an integer is divided by 2. There are only two possibilities: 0 (for even numbers) or 1 (for odd numbers).
Now, let's think about the sums of subsets:
* If a subset contains only even numbers, their sum will always be even (divisible by 2).
* If a subset contains an even number of odd numbers, their sum will be even.
* If a subset contains an odd number of odd numbers, their sum will be odd.
To *ensure* we have a nonempty subset with a sum divisible by 2, we need to consider the worst-case scenario where we try to avoid such a subset.
Suppose we pick elements for our set $S$. If we pick just one element, it might be odd, and the only nonempty subset is the element itself, whose sum would be odd.
If we pick two elements, say $a$ and $b$.
* If both are even, then $\{a\}$ has an even sum, and $\{b\}$ has an even sum.
* If both are odd, then the subset $\{a, b\}$ has an even sum ($odd + odd = even$).
* If one is even and one is odd, then $\{a\}$ (if $a$ is even) or $\{b\}$ (if $b$ is even) has an even sum.
It seems that with just two elements, we can always find a nonempty subset with a sum divisible by 2. Let's formalize this using the Pigeonhole Principle.
Consider the remainders of the elements of $S$ when divided by 2. Each element can have a remainder of 0 or 1.
If we have two elements in $S$, say $s_1$ and $s_2$, there are a few possibilities for their remainders modulo 2:
1. Remainder of $s_1$ is 0, remainder of $s_2$ is 0. Then the subset $\{s_1\}$ has a sum divisible by 2, and the subset $\{s_2\}$ also has a sum divisible by 2.
2. Remainder of $s_1$ is 1, remainder of $s_2$ is 1. Then the subset $\{s_1, s_2\}$ has a sum with remainder $1 + 1 \equiv 0 \pmod{2}$, so the sum is divisible by 2.
3. Remainder of $s_1$ is 0, remainder of $s_2$ is 1 (or vice versa). Then the subset $\{s_1\}$ has a sum divisible by 2.
In all cases with two elements, we can find a nonempty subset whose sum is divisible by 2.
Now, what if $S$ only has one element? If that element is odd, then the only nonempty subset has an odd sum.
Therefore, the smallest number of elements that $S$ must contain to ensure that $S$ has a nonempty subset where the sum of the elements in the subset is divisible by 2 is 2.
Answer by greenestamps(13198)   (Show Source): You can put this solution on YOUR website!

Suppose the set S is {N}, where N is an even integer.

The nonempty set {N} is a subset of the given set S, and the sum of the elements of that nonempty subset is divisible by 2.

So the set {N} satisfies all the conditions; so the smallest number of elements a set must contain to satisfy the conditions is 1.

ANSWER: 1

Answer by ikleyn(52777)   (Show Source): You can put this solution on YOUR website!
.
Let S be a set of distinct integers. What is the smallest number of elements that S must contain,
to ensure that S has a nonempty subset, where the sum of the elements in the subset is divisible by 2?
~~~~~~~~~~~~~~~~~~~~~~~~~

I will treat the problem differently.

First, the problem says " Let S be a set of distinct integers."
So, I will assume that the number of elements in S is at least 2 (two), in order for the term
"distinct integers" would make its natural sense.

Second, I will assume that when the problem says " the sum of the elements in the subset ",
it means that at least two elements of the subset are involved/included into the sum;
otherwise it is like " dance tango alone ". <---> Alhough it is possible, but it is unnatural.

Then the answer to the problem's question is
        "the smallest number of elements that S must contain is 3 (three)".

Indeed, if the set S contains three or more distinct integers, then inevitably EITHER there is a pair of two distinct even integers in S, giving the even sum, OR there is a pair of two distinct odd integers in S, giving the even sum. So, any set S containing three or more distinct integers, satisfies the condition. On the contrary, the set of two distinct integers may have one even number and one odd number; then the sum of these two integer numbers is an odd integer. So, such a set S of two integers of different parity fails the condition. Thus, if to treat the problem this way, then the answer is "the smallest number of elements that S must contain is 3 (three)".

Solved.

RELATED QUESTIONS
Let S be the universal set, where: S={1,2,3,...,18,19,20} Let sets A and B be subsets... (answered by KMST)
Let S be the universal set, where: S={1,2,3,...,18,19,20} Let sets A and B be subsets... (answered by ikleyn)
Let s be the set of all integers that can be written as n^2 +1 , where n is a nonzero... (answered by london maths tutor)
Let S be the set of all integers that can be written as {{{n^2 + 1}}}, where n is a... (answered by stanbon)
(a) Prove that the set S of rational numbers (in lowest term) with odd denominators is a (answered by khwang,venugopalramana)
Let S be the universal set, where: S={1,2,3,...,18,19,20} Let sets A and B be subsets... (answered by ikleyn)
Let f(x) be a polynomial with integer coefficients. There exist distinct integers p, q,... (answered by math_tutor2020)
Let S be the set of all integers that can be written as n2 + 1, where n is a nonzero... (answered by Jk22)
is set A has 3 elements and set B has 4 elements: a. what is the greatest number of... (answered by stanbon)