• View
• Edit
• History
• Print

20120815k

Prison break

The director of the Alcatraz prison celebrates his 60th birthday next week. For this special occasion he decided to free some prisoners. He came up with the following game. In the prison there are 600 cells, numbered from 1 to 600. At the beginning all cells are closed. The guard goes to the 1st door and flips every lock. Then goes to 2nd cell and flips every second lock from this door (closes if it was opened, opens if it was closed). Then goes to the 3rd cell , and flips the lock of every third cell. Etc, he repeats this procedure with every cell. The prisoners whose doors are opened are free to go.

Question: who are those lucky guys that are freed at the end? (Look at the result. Do you see some pattern?)

Example with 8 doors:

00000000        initialization, all doors are locked
11111111        1st step, flip every lock
10101010        2nd step, flip every second lock
10001110        3rd step, flip every third lock
10011111        4th step, flip every fourth lock
10010111        5th step, flip every fifth lock
10010011        6th step, flip every sixth lock
10010001        7th step, flip every seventh lock
10010000        8th step, flip every eighth lock

Self check

Write down the number of the opened doors next to each other and submit the result. For instance if doors 5, 13, and 67 are open at the end, then send the following number: 51367 .