document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=26952>Question 26952</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Imagine you are at a school that has student lockers. There are 1000 lockers all shut and unlocked and 1000 students.  Suppose the first goes along the row and opens every locker. Then the second student goes along and shuts every other locker beginning with the second locker. After that the third student changes the state of every third locker beginning with the third licker   (if the locker is open the student shuts it, and if the locker is closed the student open it.)  Next the fourth student changes the state of every fourth locker starting with the fourth locker.  Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will open and which will be closed?  and Why? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #96469 by </B><A HREF=/tutors/aboutme.mpl?userid=jim_thompson5910><B>jim_thompson5910(35256)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=jim_thompson5910><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=96469\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> It definitely helps to break this problem into smaller pieces and draw a picture.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Lets say we only have 10 people and 10 lockers. If person 1 opens all of the lockers, they're all open. Now person 2 goes, and all of the even numbered lockers are shut. Now it's 3's turn: locker 3 is shut, locker 6 is open again, and 9 is shut. Four takes a shot and locker 4 and 8 are reopened. 5 goes and 5 and 10 are shut. Students 6, 7, 8, and 10 only shut locker 6, 7,8, and 10 respectively; while person 9 opens locker #9.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So if we look at say locker #6, person 1 opens it, person 2 closes it, person 3 opens it, and finally person 6 closes it. So there are 4 people who interact with it (notice how its an even number). While with locker 4, only students 1,2,4 touch it, and it stays open. So by this reasoning, if an even number of people touch it, it stays closed. If an odd number of people touch it, it stays open. To find out how many people touch it, we simply find the number of factors the number has. With 6 there are 4 factors: 1,2,3,6. The four factors simply cancel each other out (one action of opening is undone by another action of closing). While the number 4 has 3 factors: 1,2,4. These factors dont cancel so it stays open. It turns out that every number, except the perfect squares, has an even number of factors. Think about it, to multiply to say 40, one could go 1*40,2*20,4*10,5*8,8*5,10*4,20*2,40*1. All of these factors are paired up, which means there are an even number of factors. Even prime numbers have an even number of factors, they are divisible by their own number and 1 (ie 61=1*61). However, even though perfect squares may seem to have an even number of factors (for instance 9:1*9,3*3,9*1) there is a repeated factor of 3. So there are only 3 factors in this number. This is true for all perfect squares, since there's always a repeated factor of the square root value. So every perfect square locker number will remain open because they have an odd number of factors. This makes it easier to count the number of open lockers since we only have to find perfect squares. So here's the list of perfect squares (and open lockers):\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "1<BR>\n" );
document.write( "4<BR>\n" );
document.write( "9<BR>\n" );
document.write( "16<BR>\n" );
document.write( "25<BR>\n" );
document.write( "36<BR>\n" );
document.write( "49<BR>\n" );
document.write( "64<BR>\n" );
document.write( "81<BR>\n" );
document.write( "100<BR>\n" );
document.write( "121<BR>\n" );
document.write( "144<BR>\n" );
document.write( "169<BR>\n" );
document.write( "196<BR>\n" );
document.write( "225<BR>\n" );
document.write( "256<BR>\n" );
document.write( "289<BR>\n" );
document.write( "324<BR>\n" );
document.write( "361<BR>\n" );
document.write( "400<BR>\n" );
document.write( "441<BR>\n" );
document.write( "484<BR>\n" );
document.write( "529<BR>\n" );
document.write( "576<BR>\n" );
document.write( "625<BR>\n" );
document.write( "676<BR>\n" );
document.write( "729<BR>\n" );
document.write( "784<BR>\n" );
document.write( "841<BR>\n" );
document.write( "900<BR>\n" );
document.write( "961<BR>\n" );
document.write( "And there happens to be 31 perfect squares less than 1000.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So there are 31 lockers left open. I hope this makes sense.  </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );