document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1210235>Question 1210235</A>: <I><SPAN STYLE=\"word-break: break-all;\"> 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? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #851716 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=851716\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> 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.\r<BR>\n" );
document.write( "\n" );
document.write( "Consider the remainders when an integer is divided by 2. There are only two possibilities: 0 (for even numbers) or 1 (for odd numbers).\r<BR>\n" );
document.write( "\n" );
document.write( "Now, let's think about the sums of subsets:\r<BR>\n" );
document.write( "\n" );
document.write( "* If a subset contains only even numbers, their sum will always be even (divisible by 2).<BR>\n" );
document.write( "* If a subset contains an even number of odd numbers, their sum will be even.<BR>\n" );
document.write( "* If a subset contains an odd number of odd numbers, their sum will be odd.\r<BR>\n" );
document.write( "\n" );
document.write( "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.\r<BR>\n" );
document.write( "\n" );
document.write( "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.\r<BR>\n" );
document.write( "\n" );
document.write( "If we pick two elements, say $a$ and $b$.<BR>\n" );
document.write( "* If both are even, then $\{a\}$ has an even sum, and $\{b\}$ has an even sum.<BR>\n" );
document.write( "* If both are odd, then the subset $\{a, b\}$ has an even sum ($odd + odd = even$).<BR>\n" );
document.write( "* If one is even and one is odd, then $\{a\}$ (if $a$ is even) or $\{b\}$ (if $b$ is even) has an even sum.\r<BR>\n" );
document.write( "\n" );
document.write( "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.\r<BR>\n" );
document.write( "\n" );
document.write( "Consider the remainders of the elements of $S$ when divided by 2. Each element can have a remainder of 0 or 1.\r<BR>\n" );
document.write( "\n" );
document.write( "If we have two elements in $S$, say $s_1$ and $s_2$, there are a few possibilities for their remainders modulo 2:\r<BR>\n" );
document.write( "\n" );
document.write( "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.<BR>\n" );
document.write( "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.<BR>\n" );
document.write( "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.\r<BR>\n" );
document.write( "\n" );
document.write( "In all cases with two elements, we can find a nonempty subset whose sum is divisible by 2.\r<BR>\n" );
document.write( "\n" );
document.write( "Now, what if $S$ only has one element? If that element is odd, then the only nonempty subset has an odd sum.\r<BR>\n" );
document.write( "\n" );
document.write( "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. </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );