Gizmodo Monday Puzzle: Can You Pass This Finance Job Interview Test?

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!

WatchThe New M3-Powered iMacs Are Triggering Serious Deja Vu CCShare SubtitlesOffEnglishDid you miss last week’s puzzle? Check it out AdvertisementPuzzle #18 The Long HallThere 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?AdvertisementYou 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 ZombiesLast week, you AdvertisementNotice 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. AdvertisementNumber 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. AdvertisementSolution to Puzzle #17bHaving 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, 22Zombie 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. AdvertisementThis 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.AdvertisementEugenius also solved part b in an instructive way, not using the ternary numbers approach and inadvertently discovering this neat combinatorial identity.

Based on reporting by gizmodo.com.