I can’t remember where I came across this clever little puzzle and what precise form it took, but here’s my version of it:

A famously eccentric inventor and recreational mathematician has invited you to tour the factory where his company manufactures locks, keys, safes, cash-boxes and so on. At the end of the tour he brings you to a conference room, pours you a glass of wine, and invites you to test your wits against a puzzle. He points out that a hundred numbered boxes have been set out on two long tables in the room. You sip your wine as you listen to him explain that each box is locked and contains a slip of paper bearing a number between 0 and 9. If you accept the challenge, the inventor will order a hundred workers to walk in turn past the boxes, using a master-key to unlock or lock the boxes like this:

The first worker will use the key on every box (boxes #1,2,3…), the second worker will use the key on every second box (boxes #2,4,6…), the third worker the key on every third box (boxes #3,6,9…), and so on.

Now, you can’t tell by simply looking at a box whether it’s unlocked or not, but it’s obvious that the first box will be unlocked when all that is over. Box #1 is originally locked and the master-key will be used on it just once. But how many other boxes will be unlocked? If you can choose nothing but the unlocked boxes, you get to keep the contents. Otherwise you get nothing. That is, if you choose one or more locked boxes, you get nothing.

And what good are the contents of the unlocked boxes? Well, if you take the numbered slips of paper they contain in order, they will give you the combination of a locked safe the inventor now points out in the wall behind you. The safe contains the antidote for the deadly but slow-acting poison he secretly slipped into the wine you have been sipping as you listened to him explain the details of the puzzle. So you have to choose all and only the unlocked boxes to save your life. Can you do it?

Solution

I’m sure there’s a simpler explanation of which boxes will be unlocked, but here’s my complicated one:

Whether box #n is locked or unlocked in the end depends on how many divisors the number n has. If it has an even number of divisors, it will be locked; if it has an odd number of divisors, it will be unlocked. Take box #12. The number 12 has six divisors: 1, 2, 3, 4, 6 and 12. So workers #1, #3 and #6 will unlock it with the master-key, but workers #2, #4 and #12 will lock it again. Worker #12 will be the final worker to use the master-key on the box, so it will be locked.

Now take box #16. The number #16 has five divisors: 1, 2, 4, 8 and 16. So workers #1, #4 and #16 will unlock the box with the master-key, while workers #2 and #8 will lock it. Worker #16 will be the final worker to use the master-key on the box, so it will be unlocked.

In other words, the puzzle reduces to this: Which numbers from 1 to 100 have an odd number of divisors? To work out the number of divisors n has, you add 1 to the exponent of each of its prime factors and multiply the results. For example, 24 has eight divisors thus:

• 24 = 2^3 * 3^1 → (3+1) * (1+1) = 4 * 2 = 8, so 24 has eight divisors: 1, 2, 3, 4, 6, 8, 12, 24

But 36 has nine divisors thus:

• 36 = 2^2 * 3^2 → (2+1) * (2+1) = 3 * 3 = 9, so 36 has nine divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36

36 demonstrates that a number has to have only even exponents on its prime factors to have an odd number of divisors (the only number without prime factors is 1, which has one divisor, namely itself). Numbers with only even exponents on their prime factors are square numbers:

• 4 = 2^2 → (2+1) = 3, so 4 has three divisors: 1, 2, 4
• 9 = 3^2 → (2+1) = 3, so 9 has three divisors: 1, 3, 9
• 16 = 2^4 → (4+1) = 5, so 16 has five divisors: 1, 2, 4, 8, 16
• 25 = 5^2 → (2+1) = 3, so 25 has divisors: 1, 5, 25
• 36 = 2^2 * 3^2 → (2+1) * (2+1) = 3 * 3 = 9, so 36 has nine divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36
• 49 = 7^2 → (2+1) = 3, so 49 has three divisors: 1, 7, 49
• 64 = 2^6 → (6+1) = 7, so 64 has seven divisors: 1, 2, 4, 8, 16, 32, 64
• 81 = 3^4 → (4+1) = 5, so 81 has five divisors: 1, 3, 9, 27, 81
• 100 = 2^2 * 5^2 → (2+1) * (2+1) = 3 * 3 = 9, so 100 has nine divisors: 1, 2, 4, 5, 10, 20, 25, 50, 100

So if you choose boxes #1, #4, #9, #16, #25, #36, #49, #64, #81 and #100, you’ll get the combination for the safe and save your life.

Appendix

Here’s the full description of what happens to the boxes:

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