There are 100 mailboxes numbered 1 to 100 that are all initially closed. In the

Question

There are 100 mailboxes numbered 1 to 100 that are all initially closed. In the first step, visiting every mailbox (i.e. mailboxes 1, 2, 3, ..., 100), he flips them all. Then in the second step, visiting every second mailbox (i.e. mailboxes 2, 4, 6, ..., 100), he flips them. Then in the third step, visiting every third mailbox (i.e. mailboxes 3, 6, 9, ..., 99), he flips them. In this manner he goes in steps of 4, 5, ..., 10,...,50, and finally 100, wherein he directly goes to the 100th mailbox and flips it. At the end of this process, which mailboxes are open? Hint: Set up an array of Booleans all initialized to false representing closed mailboxes. Then, in steps of 1, 2, 3,

Explanation / Answer

Consider mailbox number 56, the person will visit it for every divisor it has.
So 56 has 1 & 56, 2 & 28, 4 & 14, 7 & 8.
So on pass 1 1st visitation will open the mailbox, pass 2 2nd one will close it, pass 4 open, pass 7 close, pass 8 open, pass 14 close, pass 28 open, pass 56 close.

For every pair of divisors the door will just end up back in its initial state.

But there are cases in which the pair of divisor has same number for example mailbox number 16.

16 has the divisors 1 & 16, 2 & 8, 4&4. But 4 is repeated because 16 is a perfect square, so you will only visit door number 16, on pass 1, 2, 4, 8 and 16… leaving it open at the end.

So only perfect square mailboxes will be open at the end.

1, 4, 9, 16, 25, 36, 49, 64, 81, 100 are the mailboxes which will be open.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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