British puzzle maker H. E. Dudeney concocted an interesting puzzle about a bored

Question

British puzzle maker H. E. Dudeney concocted an interesting puzzle about a bored postman called the "Peevish Postman Problem". According to Dudeney, the postman worked in a small post office with consecutive letter boxes numbered 1 to 100. Each box was equipped with a door that could be opened and closed. Late one evening the postman made a "pass" through the boxes and opened every door. Still bored, he walked back to the beginning and made a second pass, this time visiting boxes 2, 4, 6 100. Since those doors were now open, he closed them. On the third pass he visited boxes 3, 6, 9,12 99 and if a door was open he closed it, and if the door was closed he opened it. He continued to make passes through the boxes and always followed the same rule: On each pass i from 1 to 100, he visited only boxes that were multiples of i,... and changcd the state of each door he visited. After making 100 passes at the doors, he surveyed the results and was surprised by the pattern of doors that he saw. The code below uses a boolean array to represent the doors. A true value in the array represents an open door, and a false value represents a closed one. You will have to write two nested loops in order to manipulate the array as described above. The inner loop will control the door number visited on a single pass, and the outer loop will control the number of passes. Print the state of each door after the 100th pass. The puzzle was conceived as a paper and pencil entertainment. Can you explain the pattern of doors? Because the doors are numbered starting at one, we will waste the first position in the array. In this case, the default value will be set to false. By ignoring the first position, the door numbers match their index positions in the array.

Explanation / Answer

Hi Please find my explanation.

A door is toggled in ith walk if i divides door number. For example the door number 45 is toggled in 1st, 3rd, 5th, 9th and 15th walk.
The door is switched back to initial stage for every pair of divisors. For example 45 is toggled 6 times for 3 pairs (5, 9), (15, 3) and (1, 45).
It looks like all doors would become closes at the end. But there are door numbers which would become open, for example 16, the pair (4, 4) means only one walk. Similarly all other perfect squares like 4, 9, ….
So the answer is 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.