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 changed 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?

Hint: 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

/**
*
*/

/**
* @author Srinivas Palli
*
*/

public class Peevish {
   public static void main(String[] args) {
       boolean[] door;
       final int NODOORS = 101; // We will not use door[0]
       final boolean OPEN = true;
       final boolean CLOSED = false;
       // Initialize the doors
       door = new boolean[NODOORS];

       // evening the postman made a “pass” through the boxes and opened every
       // door
       for (int i = 1; i < NODOORS; i++) {
           door[i] = OPEN;
       }

       // Print the state of each door (only doors 1-100)
       for (int i = 1; i < NODOORS; i++) {
           if (door[i] == true) {
               System.out.println("Door " + i + " is open.");
           } else {
               System.out.println("Door " + i + " is closed.");
           }
       }
       int k = 0;
       // to maintain no of pass
       for (int j = 2; j <= 100; j++) {
           if (j % 2 == 0)
               // for even pass
               k = 2;

           else
               // for odd pass
               k = 3;
           for (int i = k; i < NODOORS; i = i + 2) {

               if (door[i] = CLOSED)
                   door[i] = OPEN;

               else
                   door[i] = CLOSED;
           }

       }

       // Print the state of each door (only doors 1-100)
       System.out.println(" After 100 passes ");
       for (int i = 1; i < NODOORS; i++) {
           if (door[i] == true) {
               System.out.println("Door " + i + " is open.");
           } else {
               System.out.println("Door " + i + " is closed.");
           }
       }

   }

   // Your code here

}

OUTPUT:

Door 1 is open.
Door 2 is open.
Door 3 is open.
Door 4 is open.
Door 5 is open.
Door 6 is open.
Door 7 is open.
Door 8 is open.
Door 9 is open.
Door 10 is open.
Door 11 is open.
Door 12 is open.
Door 13 is open.
Door 14 is open.
Door 15 is open.
Door 16 is open.
Door 17 is open.
Door 18 is open.
Door 19 is open.
Door 20 is open.
Door 21 is open.
Door 22 is open.
Door 23 is open.
Door 24 is open.
Door 25 is open.
Door 26 is open.
Door 27 is open.
Door 28 is open.
Door 29 is open.
Door 30 is open.
Door 31 is open.
Door 32 is open.
Door 33 is open.
Door 34 is open.
Door 35 is open.
Door 36 is open.
Door 37 is open.
Door 38 is open.
Door 39 is open.
Door 40 is open.
Door 41 is open.
Door 42 is open.
Door 43 is open.
Door 44 is open.
Door 45 is open.
Door 46 is open.
Door 47 is open.
Door 48 is open.
Door 49 is open.
Door 50 is open.
Door 51 is open.
Door 52 is open.
Door 53 is open.
Door 54 is open.
Door 55 is open.
Door 56 is open.
Door 57 is open.
Door 58 is open.
Door 59 is open.
Door 60 is open.
Door 61 is open.
Door 62 is open.
Door 63 is open.
Door 64 is open.
Door 65 is open.
Door 66 is open.
Door 67 is open.
Door 68 is open.
Door 69 is open.
Door 70 is open.
Door 71 is open.
Door 72 is open.
Door 73 is open.
Door 74 is open.
Door 75 is open.
Door 76 is open.
Door 77 is open.
Door 78 is open.
Door 79 is open.
Door 80 is open.
Door 81 is open.
Door 82 is open.
Door 83 is open.
Door 84 is open.
Door 85 is open.
Door 86 is open.
Door 87 is open.
Door 88 is open.
Door 89 is open.
Door 90 is open.
Door 91 is open.
Door 92 is open.
Door 93 is open.
Door 94 is open.
Door 95 is open.
Door 96 is open.
Door 97 is open.
Door 98 is open.
Door 99 is open.
Door 100 is open.

After 100 passes

Door 1 is open.
Door 2 is closed.
Door 3 is closed.
Door 4 is closed.
Door 5 is closed.
Door 6 is closed.
Door 7 is closed.
Door 8 is closed.
Door 9 is closed.
Door 10 is closed.
Door 11 is closed.
Door 12 is closed.
Door 13 is closed.
Door 14 is closed.
Door 15 is closed.
Door 16 is closed.
Door 17 is closed.
Door 18 is closed.
Door 19 is closed.
Door 20 is closed.
Door 21 is closed.
Door 22 is closed.
Door 23 is closed.
Door 24 is closed.
Door 25 is closed.
Door 26 is closed.
Door 27 is closed.
Door 28 is closed.
Door 29 is closed.
Door 30 is closed.
Door 31 is closed.
Door 32 is closed.
Door 33 is closed.
Door 34 is closed.
Door 35 is closed.
Door 36 is closed.
Door 37 is closed.
Door 38 is closed.
Door 39 is closed.
Door 40 is closed.
Door 41 is closed.
Door 42 is closed.
Door 43 is closed.
Door 44 is closed.
Door 45 is closed.
Door 46 is closed.
Door 47 is closed.
Door 48 is closed.
Door 49 is closed.
Door 50 is closed.
Door 51 is closed.
Door 52 is closed.
Door 53 is closed.
Door 54 is closed.
Door 55 is closed.
Door 56 is closed.
Door 57 is closed.
Door 58 is closed.
Door 59 is closed.
Door 60 is closed.
Door 61 is closed.
Door 62 is closed.
Door 63 is closed.
Door 64 is closed.
Door 65 is closed.
Door 66 is closed.
Door 67 is closed.
Door 68 is closed.
Door 69 is closed.
Door 70 is closed.
Door 71 is closed.
Door 72 is closed.
Door 73 is closed.
Door 74 is closed.
Door 75 is closed.
Door 76 is closed.
Door 77 is closed.
Door 78 is closed.
Door 79 is closed.
Door 80 is closed.
Door 81 is closed.
Door 82 is closed.
Door 83 is closed.
Door 84 is closed.
Door 85 is closed.
Door 86 is closed.
Door 87 is closed.
Door 88 is closed.
Door 89 is closed.
Door 90 is closed.
Door 91 is closed.
Door 92 is closed.
Door 93 is closed.
Door 94 is closed.
Door 95 is closed.
Door 96 is closed.
Door 97 is closed.
Door 98 is closed.
Door 99 is closed.
Door 100 is closed.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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