document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1162751>Question 1162751</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Please use formal mathematical induction to prove that given any 37 positive integers, it’s possible to choose 7 whose sum is divisible by 7. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #786584 by </B><A HREF=/tutors/aboutme.mpl?userid=ikleyn><B>ikleyn(52858)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=ikleyn><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=ikleyn><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=786584\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> .\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The method of &nbsp;Mathematical &nbsp;Induction is &nbsp;IRRELEVANT &nbsp;to this problem.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The proof is constructed based on other principles.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<U>THE PROOF</U>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let an arbitrary set of &nbsp;37 positive integer numbers is given.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "I organize &nbsp;7 boxes numbered from &nbsp;0 &nbsp;to &nbsp;6.  &nbsp;So, &nbsp;the boxes are numbered &nbsp;0, 1, 2, 3, 4, 5 and 6.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "I distribute all these &nbsp;37 numbers in these &nbsp;7 boxes according their remainders modulo 7.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If some box has at least &nbsp;7 numbers, &nbsp;then these &nbsp;7 numbers provide the required sum.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( " <BR>\n" );
document.write( "If there is no a box with at least &nbsp;7 numbers, &nbsp;it means that each box has no more than &nbsp;6 numbers and all boxes have no more than &nbsp;6 numbers.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If all boxes have at least one number, &nbsp;then their sum  &nbsp;0 + 1 + 2 + 3 + 4 + 5 +  6 = 21 &nbsp;&nbsp;(mod7) &nbsp;&nbsp;is divisible by &nbsp;7.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If not all boxes have at least one number, &nbsp;it means that at least one box is empty.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "In this case, &nbsp;we have &nbsp;6 boxes with no more than &nbsp;6 numbers in each, &nbsp;which gives &nbsp;6*6 = 36 numbers.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "But then the &nbsp;37-th number breaks this scheme.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So, &nbsp;having &nbsp;37 numbers in &nbsp;7 boxes, &nbsp;we &nbsp;EITHER &nbsp;can find a box with at least &nbsp;7 numbers in it \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<PRE STYLE=\"white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;\">\r\n" );
document.write( "     and then this box provides the required sum of 7 numbers,\r\n" );
document.write( "</PRE>\r<BR>\n" );
document.write( "\n" );
document.write( "OR, &nbsp;otherwise, &nbsp;all &nbsp;7 boxes have at least one number each,\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<PRE STYLE=\"white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;\">\r\n" );
document.write( "    and then we can form the sum  0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 (mod7)\r\n" );
document.write( "\r\n" );
document.write( "    of numbers from these boxes which is divisible by 7.\r\n" );
document.write( "</PRE>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The proof is completed.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The key to the proof &nbsp;(and to the statement itself) &nbsp;is this equality &nbsp;&nbsp;37 = 6*6 + 1.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Done.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );