Sometime in the future, when physical college lectures are once again allowed, one hundred students are attending a lecture of the Multivariate Calculus course. The students, after hearing multiple savvy jokes about their intellect and ability regarding calculus, decide to play a prank on the professor and his colleagues. They plan to boobytrap some of the one hundred doors on the 7-th floor of the Duisenberg building. However, knowing that the professors are quite brilliant, they need to allocate the boobytraps in a manner that is hard to figure out. Near the end of the lecture they proudly come up with the following plan:

Student 1 places a boobytrap on every door.
Student 2 goes to every other door, so starting at door 2, removing the boobytrap placed by the first student.
Student 3 goes to every third door, so starting at door 3, removing a boobytrap if present and placing one if not present.
Student 4 goes to every fourth door, starting at door 4, also removing a boobytrap if present and placing one if not so.
This goes on until student 100, who only visits the hundredth door. 

More formally: Student goes to doors (with the highest door number being 100) at which he/she removes a boobytrap if present and places a boobytrap if not present.

The next day, early in the morning, they execute their plan, confident that the unfortunate professors will not know which doors are boobytrapped. They finish up before anyone else gets to the 7-th floor and then make their way down the Duisenberg building to attend their morning lectures.

As they probably should have known, professor Van Edam overheard their plan during his Multivariate Calculus lecture the day before. Having great mathematical ability, he had hardly kept himself from laughing when hearing the plan of his students. He goes up to the 7-th floor and removes all 10 of the boobytraps, saving himself and his colleagues from the students’ prank.
Do you know how he figured out which doors were boobytrapped?

Answer:

The riddle seems hard at first, and with the 100 students all placing or removing boobytraps at certain doors, it can be hard to detect a resulting pattern.
The key to the solution is to figure out, for a particular door, which students have placed or removed a boobytrap. Let’s have a look:
The first door’s boobytrap state was only changed by student 1. The second door’s state was changed by student 1 and student 2.
The sixth door’s state was changed by student 1, student 2, student 3 and student 6.

We find that a particular door’s state is only changed by a student with a number that is one of the divisors of the door’s number.
Door 30, for example, has had its boobytrap state changed by students 1, 2, 3, 5, 6, 10, 15, 30.

Now how does this insight help us figure out the solution?

It is obvious that when a door’s state is changed an even number of times, the boobytrap will be removed by the last student visiting that door, leaving it clear in the end. An odd number of changes will therefore result in the door being left with a boobytrap.
Now most numbers will have an even amount of divisors, as their divisors come in pairs. Factoring 6 we have, for example, 1×6 = 6 and 2×3 = 6. For 20, the six divisors can be paired as 1×20, 2×10 and 4×5.
So which doors’ states were changed an odd number of times? Well, some numbers’ divisors cannot be perfectly paired: 25 has divisors 1, 5 and 25, which is an odd amount. The reason for this is that 25 can be factored as 5×5; it is a perfect square!
We can now conclude that the only doors that had their boobytrap states changed an odd number of times are those with a number that is a perfect square!
The doors that had their boobytraps removed by professor Van Edam are therefore doors  1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.

Dit artikel is geschreven door Pieter Dilg