document.write( "Question 1208373: Prove that given any set of $17$ integers, not all odd, there exist nine of them whose sum is divisible by $2.$\r
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

Algebra.Com's Answer #846755 by ikleyn(52786) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "Prove that given any set of 17 integers, not all odd, there exist nine of them whose sum is divisible by 2.
\n" ); document.write( "~~~~~~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "Let m be the number of odd  integers in our sets of 17 integer numbers, and\r\n" );
document.write( "\r\n" );
document.write( "let n be the number of even integers in our sets of 17 integer numbers.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "We have m + n = 17.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "        It implies that  EITHER  m >= 9  OR  n >= 9.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In other words, one of the two integer numbers, m or n, must be at least 9.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Indeed, otherwise the sum  m+n  would not be more than  8 + 8 = 16;  but m+n = 17.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "If n >= 9, then we can take 9 even integer numbers from our set.  \r\n" );
document.write( "\r\n" );
document.write( "           Their sum will be divisible by 2, so in this case these 9 integer numbers are the seeking set.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "If m >= 9, then there are two sub-cases:\r\n" );
document.write( "\r\n" );
document.write( "           - (a)  all integer numbers in our set are odd.  \r\n" );
document.write( "                  It contradict to the imposed condition,  so this case can not happen.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "           - (b)  there is at least one even number in our set of 17 integer numbers.\r\n" );
document.write( "\r\n" );
document.write( "                  In this case, we form the set of 9 numbers, taking 8 odd numbers and this even number.\r\n" );
document.write( "\r\n" );
document.write( "                  The sum of these 9 integer numbers is even number.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, we proved that in any case, it is possible to find a subset of 9 integers with even sum.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "The proof is complete and the problem is solved.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );