Our prisons are too crowded, so we need to release some inmates. For a high-security prison, there are 1000 inmates

Our prisons are too crowded, so we need to release some inmates. For a high-security prison, there are 1000 inmates and 1000 guards. Initially, all doors are locked. Beginning with the 1st guard, the ith guard switches the locked/unlocked state of every ith door. For example, the first guard would go through and unlock every door. Then the 2nd guard switches the (lock/unlock) state for every even door (effectively locking every even door while leaving every odd door unlocked). Then the 3rd guard switches the state for every 3rd door, unlocking the door if it is locked, or locking the door if it is unlocked. After the 1000th guard, how many doors are left unlocked

Leave a Reply

Your email address will not be published. Required fields are marked *