This week’s lovely puzzle was brought to my attention by one of our readers, Nicolas Audet. Nicolas says it was used as a brain teaser for a finance job interview. I have to hand it to Wall Street on this one—it’s a delightful little puzzle. Thanks for sharing, Nicolas!
The M3 MacBook Pro: Made Dark for Halloween
This is a great opportunity to remind you that if you know a cool puzzle, original or otherwise, send it my way and it may get featured here. Not sure if your puzzle is appropriate for this series? Try me and I’ll let you know. You can message me on Twitter @JackPMurtagh or email me at [email protected]
Did you miss last week’s puzzle? Check it out here, and find its solution at the bottom of today’s article. Be careful not to read too far ahead if you haven’t solved last week’s yet!
Puzzle #18 The Long Hall
There is a hallway with 100 doors labeled 1, 2, 3, etc. up to 100 in order. At first, all of the doors are closed. By toggling a door, I mean changing its position (i.e. opening it if it is closed and closing it if it is open). You walk down the hall and toggle every door (in this case, opening them all). Then a second person walks through and toggles every 2nd door (doors 2, 4, 6, etc.) Then a third person toggles every 3rd door (3, 6, 9, etc.) This continues until the 100th person only toggles the 100th door. Which doors are open at the end?
You could, of course, solve this by brute forcing a simulation of the hallway and merely observing which doors end up open. It will be much more satisfying to think through the problem and discover the reason that a door ends up open or closed.
We’ll be back next Monday with the solution and a new puzzle.
Solution to Puzzle #17: Poisoning Zombies
Last week, you sacrificed the undead to save your clan from thirst. To identify the poisoned barrel out of 1,000 in one day, you amazingly only need 10 zombies. You will feed zombies drops of water from multiple barrels and keep track of which barrels you feed to which zombies. The key idea is to assign each barrel a unique group of zombies to taste from it. To get a sense of how this works, let’s imagine we only had four barrels 1, 2, 3, 4 and two zombies A and B. We don’t feed either zombie from barrel 1; we feed barrel 2 to zombie A only; barrel 3 to zombie B only; and barrel 4 to both zombies. Then we observe who dies. If neither dies, then barrel 1 is the culprit. If only A dies, barrel 2 is the culprit, and so on. The subset of zombies that dies is a unique fingerprint tied to a specific barrel.
Notice that two zombies wouldn’t cut it if we had five barrels, because there are only four unique subsets that can be formed from two zombies. To scale the method up, the question becomes: how many unique subgroups can you form from 10 zombies? The answer is 210, or 1,024, more than enough to test all 1,000 barrels. If 210 is new to you, again think about fewer zombies for intuition. With only one zombie, there are two possible groups (2 = 21), namely the zombie itself and no zombie at all. With two zombies, we saw we get four possible subsets (4 = 22). Each zombie has two possible states: in the group or not in the group, so each additional zombie doubles the number of possible groups we can make.
The solution as written works. But if you want a slick systematic way for how to actually assign a unique group of zombies to each barrel, you can use binary numbers.
Number the barrels from 0 to 999 and then convert each barrel number into binary. The 1s in the binary representation of each barrel number will tell us which zombies to feed from that barrel, and the 0s will tell us which zombies to skip for that barrel. So for example, 771 in binary is 1100000011. Correspond this sequence of 10 digits to the 10 zombies. Lining up the zombies in a row, we’ll feed barrel 771 to the first two and last two only (corresponding with the ones in the binary representation of 771). If, for example, only the 3rd and 5th zombies from the left die, then we know that barrel 0010100000 = 160 is the culprit.
Shoutout to Eugenius for spotting the binary number solution and explaining it well.
Solution to Puzzle #17b
Having two days to run tests ramps up the complexity. To find the tainted barrel among the 2,000, you only need seven zombies! We’ll borrow our binary number trick from the first puzzle. This time however, for each barrel every zombie has three possible actions: don’t drink from it, drink from it on day 1, or drink from it on day 2. So we’ll assign each barrel a unique 7 digit label comprised of 0s, 1s, and 2s. Again, imagine we had two zombies A and B. When we only had one day to run tests, we could only handle four barrels with two zombies. With two days, we’ll be able to test nine. Here are our nine barrel labels:
00, 01, 02, 10, 11, 12, 20, 21, 22
Zombie A will drink according to the leftmost digits, meaning he won’t drink at all from the first three barrels, he’ll drink from the next three on day 1 and the final three on day 2. Zombie B will drink according to the rightmost digits. Note that zombie A might die after day 1 and never make it to day 2. This is okay though! Because if A dies from day 1, then we know that only barrels 10, 11, and 12 could be the culprit (A didn’t drink from barrels starting with 0 or 2 on day 1). So we no longer need to test the barrels that A was responsible for on day 2. If B never dies, then 10 is the culprit, if B dies after day 1, then 11 is the culprit, and if B dies after day 2, then 12 is the culprit.
This phenomenon scales up. If the nth zombie dies after day 1, it means that the nth digit of the poisoned barrel label is a 1. If the nth zombie digit dies after day 2, then the nth digit is a 2. If the nth zombie never dies, the nth digit is a 0. By observing which zombies die on which days, we can piece together the label.
Again, this reduces to the question, how many unique 7-digit labels (corresponding to seven zombies) comprised of 0s, 1s, and 2s can we make? These are called ternary numbers because they use three different digits (0, 1, and 2) just as binary numbers use two (0 and 1). There are 37 = 2187 such 7-digit labels, more than enough to test 2000 barrels.
Eugenius also solved part b in an instructive way, not using the ternary numbers approach and inadvertently discovering this neat combinatorial identity.