You have 100 doors in a row, all initially closed. You make 100 passes by the doors starting with the first door every time. The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The third time, every 3rd door (door #3, #6, #9, ...), and so on, until you only visit the 100th door.What state are the doors in after the last pass? Which doors are open, and which are closed?
Question
You have 100 doors in a row, all initially closed. You make 100 passes by the doors starting with the first door every time. The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The third time, every 3rd door (door #3, #6, #9, ...), and so on, until you only visit the 100th door.What state are the doors in after the last pass? Which doors are open, and which are closed?
Solution
The doors that are open at the end are the ones that have a perfect square number (1, 4, 9, 16, 25, 36, 49, 64, 81, 100). This is because they are the only ones that are toggled an odd number of times (which means they end up open).
Here's why:
-
A door is toggled every time one of its factors is visited. For example, door 12 is toggled when you visit doors 1, 2, 3, 4, 6, and 12.
-
Most numbers have an even number of factors. For example, door 12 has the factors 1, 2, 3, 4, 6, and 12. Pairs of factors multiply to give the number in question. In this case, 112, 26, and 3*4 all equal 12.
-
However, perfect squares are unique because they have one unpaired factor. For example, door 9 has the factors 1, 3, and 9. The pairs are 1*9 but 3 is unpaired.
-
Therefore, perfect squares are toggled one extra time, which leaves them open. All other doors are toggled an even number of times, which leaves them closed.
So, the doors that are open at the end are doors 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. All other doors are closed.
Similar Questions
You have 100 doors in a row, all initially closed. You make 100 passes by the doors starting with the first door every time. The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The third time, every 3rd door (door #3, #6, #9, ...), and so on, until you only visit the 100th door.What state are the doors in after the last pass? Which doors are open, and which are closed?
In this Java snippet that checks how many doors are in the room that you are in, which conditional statement is missing for line 5?1 Scanner input = new Scanner(System.in);2 int numOfDoors = input.nextInt();3 if (_____ == 0){4 System.out.println("You must be outside.");5 } ______ {6 System.out.println(________);7 }ifelseforelse if
An employee at a construction company is ordering interior doors for some new houses that are being built. There are 6 one-story houses and 7 two-story houses on the west side of the street, which require a total of 172 doors. On the east side, there are 6 one-story houses and 4 two-story houses, which require a total of 124 doors. Assuming that the floor plans for the one-story houses are identical and so are the two-story houses, how many doors does each type of house have?Each one-story house has doors, and each two-story house has doors.
In a Python simulation of the Monty Hall problem, what represents the doors and their contents1 pointVariablesFunctionsClassesLists
Howard made a simple robot. This robot is placed in the space outside a maze consisting of three rooms and six doors, as depicted in the following figure. Figure 1: The layout of the maze. 1 2 3 Whenever the robot is in a space or room with 𝑘 doors, it chooses each of these doors to move through next with probability 1/𝑘 . Suppose the robot is in Room 1, find the probability of it leaving the maze (for the first time) from Room 3.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.