document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1209438>Question 1209438</A>: <I><SPAN STYLE=\"word-break: break-all;\"> The hundred-handed monster Briareus was hungry and attacked a flock of 98 sheep. He didn't want to eat them all, so he developed a strange way to decide which ones to eat. With his hundred hands he lined the sheep up in front of him and attached tags labeling the sheep from 1 to 98, from left to right. First he crammed all the sheep into his mouth. Then he spat out all the even-numbered sheep. Then for every sheep with a number divisible by three, he stuffed it into his mouth if it was outside or spat it out if it was already inside. He did the same for every sheep with a number divisible by 4, 5, and so on up to 98. At the end, he devoured the sheep that were left in his mouth. How many sheep were left in the flock after Briareus left?<BR>\n" );
document.write( "CC12#3<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #848860 by </B><A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><B>math_tutor2020(3817)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><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/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=848860\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "Answer: <font color=red>89 sheep</font>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Explanation\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This problem is practically identical to the locker problem<BR>\n" );
document.write( "<a  rel=nofollow HREF=\"https://math.stackexchange.com/questions/2017047/the-locker-problem-why-squares\">https://math.stackexchange.com/questions/2017047/the-locker-problem-why-squares</a><BR>\n" );
document.write( "and also the light switch problem<BR>\n" );
document.write( "<a  rel=nofollow HREF=\"https://math.hmc.edu/funfacts/toggling-light-switches/\">https://math.hmc.edu/funfacts/toggling-light-switches/</a><BR>\n" );
document.write( "They are basically the same idea just with a different coat of paint so to speak.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Any non-perfect square has an even number of factors. This leads to an even number of swaps.<BR>\n" );
document.write( "For instance sheep number 6 goes free since it has four swaps (due to the four factors 1,2,3,6)<BR>\n" );
document.write( "This sheep starts outside and ends outside. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Any perfect square has an odd number of factors, so those sheep numbers have an odd number of swaps.<BR>\n" );
document.write( "Those unfortunate sheep start outside the mouth and end up eaten. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "There are 9 perfect squares between 1 and 98 since 9^2 = 81 is the largest perfect square of the list.<BR>\n" );
document.write( "9 sheep are eaten and the other 98-9 = <font color=red>89</font> sheep survive.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "--------------------------------------------------------------------------\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Another approach\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's look at a smaller flock say of 10 sheep.<BR>\n" );
document.write( "The monster places all of them into its mouth.<BR>\n" );
document.write( "1, 2, 3, 4, 5, 6, 7, 8, 9, 10\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Erase the even numbers<BR>\n" );
document.write( "1, 3, 5, 7, 9\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Then go through the multiples of 3 between 1 and 10. <BR>\n" );
document.write( "If you find 3, 6, or 9 in that previous list, then erase it. <BR>\n" );
document.write( "Otherwise introduce it back into the list.<BR>\n" );
document.write( "We go from<BR>\n" );
document.write( "1, 3, 5, 7, 9<BR>\n" );
document.write( "to<BR>\n" );
document.write( "1, 5, 6, 7\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Now go through the multiples of 4. <BR>\n" );
document.write( "If you find 4 or 8 in the previous list above then erase it. Otherwise add it in.<BR>\n" );
document.write( "We go from <BR>\n" );
document.write( "1, 5, 6, 7<BR>\n" );
document.write( "to<BR>\n" );
document.write( "1, 4, 5, 6, 7, 8\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Keep this process going until reaching 10.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Here's the full process<BR>\n" );
document.write( "<TABLE  border = \"1\" cellpadding = \"5\">\n" );
document.write( "<tr><TD >Round</TD><TD >Sheep In Mouth</TD></tr><tr><TD >1</TD><TD >1, 2, 3, 4, 5, 6, 7, 8, 9, 10</TD></tr><tr><TD >2</TD><TD >1, 3, 5, 7, 9</TD></tr><tr><TD >3</TD><TD >1, 5, 6, 7</TD></tr><tr><TD >4</TD><TD >1, 4, 5, 6, 7, 8</TD></tr><tr><TD >5</TD><TD >1, 4, 6, 7, 8, 10</TD></tr><tr><TD >6</TD><TD >1, 4, 7, 8, 10</TD></tr><tr><TD >7</TD><TD >1, 4, 8, 10</TD></tr><tr><TD >8</TD><TD >1, 4, 10</TD></tr><tr><TD >9</TD><TD >1, 4, 9, 10</TD></tr><tr><TD >10</TD><TD >1, 4, 9</TD></tr>\n" );
document.write( "</TABLE><BR>\n" );
document.write( "We see that the perfect squares remain.<BR>\n" );
document.write( "These sheep are eaten. The others go free.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Applying this idea to numbers 1 through 98 will show that 1, 4, 9, 16, 25, 36, 49, 64, 81 are eaten.<BR>\n" );
document.write( "There are 9 of those values so 98-9 = <font color=red>89</font> sheep go free.<BR>\n" );
document.write( "It might help to make a 10 by 10 grid of numbers from 1 to 100. Cross off 99 and 100 since the list ends with 98.<BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );