document.write( "Question 1071053: each of 25 pupils must choose 2 tasks from 5 possible tasks. Use the pigeonhole principle to show that at least three will choose the same task. \n" ); document.write( "

Algebra.Com's Answer #685991 by ikleyn(52781) $\"\"$ $\"About$

You can put this solution on YOUR website!
.
\n" ); document.write( "Much more stronger statement is true:\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "     Each of 25 pupils must choose a combination of 2 tasks from 5 possible tasks. \r\n" );
document.write( "     Use the pigeonhole principle to show that at least three pupils will choose the same combination of two tasks.     (*)\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( "I underlined the words/the terms that I added to make your formulation unambiguous.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "According to my formulation, at least 3 pupils choose not only the same task, but the same combination of two tasks. \r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Proof\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "

\r\n" );
document.write( "The number of combinations of 5 items taken 2 at a time is  = 10.\r\n" );
document.write( "\r\n" );
document.write( "So, there are only 10 different combinations of 2 tasks that the pupils choose from 5 tasks.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "          Now consider these 10 combinations of 2 tasks as 10 pigeonholes, and consider 25 pupils as pigeons.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "With it, apply the pigeon principle (which in other mathematical cultures is called \"the Dirichlet's principle\").\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "And you immediately will find at least 3 pigeons in one/(in some one) pigeonhole.\r\n" );
document.write( "In other words, those 3 pupils that choose the same combination of two tasks.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "It implies that the statement (*) is TRUE.\r\n" );
document.write( "

\r
\n" ); document.write( "\n" ); document.write( " * * * Proved and Solved. * * *\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Notice that I proved more strong and more accurately formulated statement than your original.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "Also notice that even 21 pupils is just enough for the statement to be true.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " On \"pingeonholes principle\" see this Wikipedia article.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "

\n" );