(Optional but Encouraged!) 100 Doors

The questions below are due on Sunday July 07, 2024; 10:00:00 PM.

You are not logged in.
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

Note this assignment is not officially graded, but is a good logic puzzle and opportunity to make use of the range function with changing step size!

Part 1

In this exercise, we will study the 100 doors question. The setup is this: there are 100 doors in a row, numbered 1-100, each of which starts out locked. You make 100 passes through the doors. On the first pass, you switch the state of the locks (locked doors become unlocked, and unlocked doors become locked) on doors 1, 2, 3, 4, \ldots. On the second pass, you switch the state of the locks on doors 2, 4, 6, 8, \ldots, and on the third pass, you switch the state of the locks on doors 3, 6, 9, 12, \ldots, and so on. You do this until you reach 100, at which time you only switch the lock on door 100.

That is, on the m^{\text{th}} pass, you switch the state of the lock on every m^{\text{th}} door (those doors numbered k such that k\mod m = 0).

In the box below, paste a Python list containing, in increasing order, the numbers of the doors that are unlocked after 100 passes.

You probably want to write a Python script to help you figure this one out! Note that you will need some kind of a structure to store which doors are currently open, and which are closed. How can you represent the state of each door (locked vs unlocked)? How can you keep track of this for all the doors?

Try to think through a plan for your program conceptually. It might be useful to try simulating running the program on pen/paper, using a small number of doors. If you're feeling stuck, check here for a hint:

One option for keeping track of the door states is using a boolean for each door (True being locked and False being unlocked), and we can keep track of them in a list. For instance, if we only had 4 doors, we would start out as [True, True, True, True] but after the first pass, it would be [False, False, False, False] since they're all unlocked now. On the second pass it would be [True, False, True, False] since you switched the locks on every other lock.

Additionally, for simulating all of the rounds, you could consider nested loops - an outer loop to keep track of the step size: 1,2,3,...; and an inner loop to step over the doors changing the states for the multiples of the step_size. The range step_size argument in particular might be useful.

Link to relevant section of reading

Open doors:

Part 2

You might notice an interesting pattern in the numbers above! You want to investigate whether that pattern holds regardless of the number of doors considered.

To that end, write a function ndoors that takes a single integer argument representing both the number of doors to consider and the number of passes, and returns a list of the doors that are unlocked at the end.

No file selected

Next Exercise: Second Largest

Back to exercises