Welcome to Paul's Website



Toggling State Riddle

Choose difficulty level:

 Easier Version Medium Version
 Story

At the academy of Polite Habits via Brainteasers (PHB), instructors teach students manners and instill good behaviors by offering puzzles that both reinforce good habbits and encourage deductive reasoning. During the winter months, PHB covers a program to "Talk about opening windows, talk about opening doors," in which students learn to open and hold doors open for others to pass through, and also to be sure to close windows and doors after they're done using them to avoid exorbinant heating bills. One of the brainteasers they use to reinforce these habbits is as follows:

There are 100 classrooms down PHB's longest hallway, each with a room number 1-100. Each classroom has an exterior window, which all begin closed. All 100 students will be assigned a distinct number 1-100, and lined up at one end of the hallway according to that number. The first student (Student #1) stops at every classrom: {1, 2, 3, ..., 100}, changing the state of the window in that classrom (i.e. opening them all, since they begin closed) as they walk down the hallway. The second student (Student #2) stops at every other classroom: {2, 4, 6, ..., 100}, changing the state of its window (in this case, closing them, as Student #1 opened the window in every classroom) as they walk down the hallway. The third student (Student #3) stops at every third classroom: {3, 6, 9, ..., 99}, changing the state of its window (i.e. closing it if it's open, and opening it if it's closed) as they walk down the hallway. The fourth student (Student #4) stops at every fourth classroom: {4, 8, 12, ..., 100}, changing the state (open vs. closed) of the window in each classroom they stop at as they walk down the hallway. This continues until every student has walked down the hallway, with Student #i stopping at each classroom that is a multiple of i, and changing the state of its window as they pass by.

After the 100th student has passed down the hallway (stopping only at classroom #100 and changing the state of its window), all students will choose a classroom to have classes in. Assuming you don't want to study in a classroom with an open window, which classrooms can you choose?

 Succinct Riddle

  1. There are 100 classrooms, numbered 1-100, each with a window (all windows are initially closed).
  2. There are 100 students, numbered 1-100.
  3. For each i in [1, 100], Student i stops at every classroom whose number is a multiple of i, and changes the state of that classroom's window: opening it if it was closed, and closing it if it was open.
After all 100 students have gone, which classrooms have windows that are open and which are closed?

 Hints

  • Rather than thinking about things from the "student-by-student" perspective (in terms of what each student does), shift your perspective and think about things from a "classroom-by-classrom" perspective.
  • Namely, for any classroom number i in [1, 100], think about which students will stop at this classroom.
    See if you can find a pattern relating the classroom number to the set of student numbers that stop at that classroom.
  • It doesn't matter the exact number of students that stop at a given classroom, only the parity of the number of students.
    Namely, if an even number of students stop by the classroom, then its window will be closed at the end: The first student to stop by it opens it, and the next closes it (and so on).
  • Combine the above two facts, to determine which (classroom) numbers satisfy the property that an even (or odd) number of students will stop at them.

 Answer

Succinct Answer: All windows will be closed, except windows that are in classrooms whose number is a perfect square: {1, 4, 9, 16, 25, 36, 49, 64, 81, and 100}.

Succinct Explanation: Factorization.

Explanation: Most riddles where factorization is a key theme to the solution have the property that the solution is usually related to prime numbers. This riddle is an exception, where it is NOT the prime numbers that enjoy a special property, but rather the PERFECT SQUARES: numbers that are equal to another number squared.

The reason for this is as follows: For any classroom number i, the students who stop by classroom i are exactly the students whose number divides i. For example, student 1 and student i both stop at classroom i (notice 1 and i both divide i). More generally, if a * b = i, then students numbered a and b will stop at classroom i. Notice that for any factor of i, that factor always has a "complementary" factor. Namely, if a divides i, then so does b = i / a. Thus, for every student a that stops by classroom i, there will be a complementary student b = i / a that *also* stops by classroom i. Thus, it would appear that every time some student a stops by a classroom to open the window, there will be another student b (= i / a) who will later stop by the classroom to close it again. The only exception to this if b = a, i.e. a student is "its own complement". Thus, the only time an odd number of students stop by a classroom i is if i has a factor a such that the complementary factor b = i / a also equals a; or in other words, i = a * a. Thus, the only classrooms that have an odd number of students stop at them are the classrooms whose number i is a perfect square.