0

I've been given the following riddle by my boss, and while I think I might have figured out the answer, I'm not entirely sure how to check that it's correct since I kind of cheated and wrote a python script to do it the long way for me.

The Riddle:

You're in a room with 100 lockers labeled from 1 to 100. A bomb is tripped and the only way to disarm it is to open a specific set of lockers and only that set.

The process to figure out the set is:

  1. Open all the lockers
  2. Close every second locker
  3. Switch the state (open/closed) of every third locker
  4. Switch the state of every 4th locker
  5. Switch the state of every 5th locker
  6. Repeat until the 100th locker

Which lockers must be opened to diffuse the bomb?

You have no time limit, but the bomb is wired to blow by the 10th iteration.

As you can tell I've ignored the last instruction in favor of just figuring out which damn doors need to be opened, so I assume there has to be a much easier way to do it.

This is what my script is spitting out at the moment:

'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN'

And this is the actual script in case anyone wanted to look at it:

arraycounter = 0
statearray = [] #array of door states

#Set all doors to 'open'
while arraycounter <= 99:
    statearray.append(1)
    arraycounter = arraycounter + 1

#Reset arraycounter
arraycounter = 0

#Loop through each door in array
while arraycounter <= 99:
    arraycounter = arraycounter + 1 # ?
    counter = 0
    counter = counter + arraycounter

    #Change door states
    while counter <= 99:
        if statearray[counter] == 0: # If door set to closed, set to open
            statearray[counter] = 1
        elif statearray[counter] == 1: # If door set to open, set to closed
            statearray[counter] = 0
        counter = counter + arraycounter # Move on to next item in array

#Beautify output
arraycounter = 0
while arraycounter <= 99:
    if statearray[arraycounter] == 1:
        statearray[arraycounter] = "OPEN"
    elif statearray[arraycounter] == 0:
        statearray[arraycounter] = "CLOSED"
    arraycounter = arraycounter + 1

print statearray

Am I completely wrong? How would I go about solving this without having to write a script?

Thorium
  • 101
  • 2
    Hint: Compare the number of times a locker is opened/closed to the number of factors the locker's number has. When does a number have an even number of factors? When does it have an odd number of factors? No coding is necessary. – JMoravitz Mar 30 '16 at 00:45
  • I think your script has started indexing with $0$. That's not unusual for computer stuff, but kind of odd for locker numbers. It's probably more enlightening to print the indices of all closed lockers, rather than a string of OPENs and CLOSEDs. This will give you some inspiration for the easier way. (But I have no idea what this has to do with bomb disarming; I've just seen the "locker question" before that only asks what lockers are open/closed after going all the way through). – pjs36 Mar 30 '16 at 00:45
  • 2
    Alternate solution: if a bomb is tripped but there's no time limit, does it need to be disarmed at all? – Patrick Shambayati Mar 30 '16 at 00:46
  • You should take a look at this question: http://math.stackexchange.com/questions/408109/the-security-guard-problem – user222031 Mar 30 '16 at 00:46
  • how can you consider the first locker to be one of "every second locker"? – Klint Qinami Mar 30 '16 at 01:10
  • This was a problem in the New York Times’s “Numberplay” column a few years ago. I wrote a blog post about it here, where you’ll also find a link to the Times article. http://www.stevekass.com/2012/06/04/numberplay-a-picture-is-worth-100-doors/ – Steve Kass Mar 30 '16 at 01:45
  • The script result is way off target. And you should not need a script at all. – Oscar Lanzi Mar 30 '16 at 02:21

2 Answers2

4

A locker is switched at stage n when n is a divisor of the locker number. So we have an odd number of swithces, meaning the locker ends up open, when the locker number has an odd number of divisors. Can the asker work out what sort of numbers have an odd number of divisors? Hint: The sixth such number is 36.

JMoravitz mentioned this in the comments and he is, uh, squarely on target.

Oscar Lanzi
  • 39,403
0

The doors that get opened have a number $n$ with an odd number of divisors (including the one).

The function that counts divisors is $$ d(n) = \sum_{d\mid n} 1 $$ If the unique prime factorization of $n$ is $$ n = \prod_i p_i^{e_i} \quad (*) $$ then $$ d(n) = \prod_i (e_i + 1) \quad (**) $$ as we can vary each power $e_i'$ of the prime factorization of a divisor $d = \prod p_i^{e_i'}$ between $0$ and $e_i$.

So $d(n)$ is odd for the doors that have to be opened and this means all the factors in $(**)$ need to be odd and thus all $e_i$ in $(**)$ and $(*)$ need to be even.

This means we can take $n^{1/2}=\prod_i p_i^{e_i/2} = \sqrt{n}$ and stay in the integers.

mvw
  • 34,562