# Saturday Puzzle #8 – An Open And Shut Case

For today’s puzzle, I’m taking you back to school. Imagine you’re standing at one end of a corridor, with exactly 100 lockers all in a row, numbered 1 to 100, all of which are initially closed. Your math teacher walks by and asks you to perform the following sequence of tasks:

• Task 1: Visit every locker (1, 2, 3, …, 100) and, for each locker visited, change its state, i.e. if you find it open, close it and if you find it closed, open it. Since all lockers start out closed, this first task amounts to opening all 100 lockers.
• Task 2: Visit every 2 lockers (2, 4, 6, …, 100) and, for each locker visited, change its state (again, if you find it open, close it and if you find it closed, open it).
• Task 3: Visit every 3 lockers (3, 6, 9, …, 99) and, again, for each locker visited, change its state.
• Tasks 4 through 100: Continue doing the same sort of task for every 4 lockers, every 5 lockers, etc., all the way up to every 100th locker (which entails visiting only locker 100), each time changing the state of every locker visited.
• Here’s the big question (drumroll): after doing all 100 tasks above, how many lockers are open?

Solution: Let’s think about one particular locker, say, locker 12. Which tasks affect locker 12 (and how)?

• task 1 opens locker 12 (because 12 is divisible by 1)
• task 2 closes locker 12 (because 12 is divisible by 2)
• task 3 opens locker 12 (because 12 is divisible by 3)
• task 4 closes locker 12 (because 12 is divisible by 4)
• task 5 does not affect locker 12 (because 12 is NOT divisible by 5)
• task 6 opens locker 12 (because 12 is divisible by 6)
• tasks 7-11 do not affect locker 12 (because 12 is NOT divisible by any of those numbers)
• task 12 closes locker 12 (because 12 is divisible by 12)
• tasks 13-100 do not affect locker 12 (because 12 is NOT divisible by any of those numbers)

So at the end of all 100 tasks, locker 12 will be closed. Now let’s look at the list of tasks that affected locker 12: 1, 2, 3, 4, 6, 12. Notice anything interesting about that list? It’s a list of the factors of 12, i.e. the numbers that can be divided evenly into 12. So, for any given locker, the set of factors is going to be important.

Another thing to notice: If a locker is opened as many times as it is closed, then it will end up closed. Since locker 12 has an even number of factors (6 factors, to be exact), it ends up closed. The only lockers that will be left open are those that contain an odd number of factors. Any idea which numbers have an odd number of factors? Let’s look at a few numbers and see if we can spot a pattern:

locker    factors even or odd number of factors?
1 (1) ODD
2 (1, 2) even
3 (1, 3) even
4 (1, 2, 4) ODD
5 (1, 5) even
6 (1, 2, 3, 6) even
7 (1, 7) even
8 (1, 2, 4, 8) even
9 (1, 3, 9) ODD
10 (1, 2, 5, 10) even
11 (1, 11) even
12 (1, 2, 3, 4, 6, 12)    even

Do you see a pattern? 1, 4 and 9 are the only numbers in the above list that have an odd number of factors. It turns out that perfect squares (any whole number that is the product of another whole number multiplied by itself) always have an odd number of factors. I like to think of it this way: every number has pairs of factors but perfect squares have one pair of factors that includes the same number twice, which is what causes them to have an odd number of factors. Thus, only the lockers that correspond to perfect squares will be left open at the end.

Here’s the list of perfect squares between 1 and 100 (inclusive): 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. As you can see, there are ten numbers on this list, so there will be ten open lockers when all is said and done.

Hats off to Al Pessot, who solved this puzzle analytically, and Simon and Muzaffer, both of whom solved the puzzle by a so-called “brute force” method – they wrote a program to perform the 100 tasks in software and count the resulting open lockers. Well done!

# Saturday Puzzle #7 – The Königsberg Bridge Problem

I first read about today’s puzzle as a young boy and it’s stayed with me all these years later. In Germany, there was a city named Königsberg (it’s now a Russian city called Kaliningrad), which is set on a river. Situated in this river are two islands, which are connected to the river banks and to each other by a series of seven bridges, as illustrated in the image on the right.

Here’s the challenge: starting anywhere you like, can you traverse all seven bridges once and only once? According to the book I read as a child, this challenge was a popular pastime in the 1700s – on Sundays, the families of Königsberg would set out on a leisurely promenade in an attempt to traverse all seven bridges once. Did anyone succeed? Can you find a non-overlapping route across all seven bridges? I’ll be very impressed if you can. Check back tomorrow for the solution.

Solution: Hats off to Muzaffer, Simon and Al for finding the answer. Al gets the creativity prize for coming up with a solution involving swimming. :)

If you tried to solve this problem by looking for a route across all seven bridges, I’m betting you got pretty frustrated, as I did when I first tried to solve it. No matter where you start or how many different paths you try, you always seem to end up needing to cross a bridge twice. After a while, you begin to suspect there might not be any solution. In mathematics and computer science, we often find problems, like this one, which we suspect may not have a solution. But it’s not enough to suspect there is no solution – it could be that one exists and we just haven’t found it yet. In order to be sure, we need to prove there is or is not a solution. That’s exactly what we’re going to do now.

The first step is to redraw the map to simplify the problem. Notice that we effectively have four land masses (A, B, C and D in the diagram above) and seven bridges. If we collapse the land masses into single points (we’ll call these nodes) and represent the bridges as lines between our points (we’ll call these arcs), we get the picture on the right. Using this diagram, which, in mathematical terms is called a graph, we can restate our challenge like this: starting at any of the four nodes A, B, C or D, find a path through the graph such that you travel across each arc exactly once.

Before we go on, we need to understand something about the nodes in this, and any, graph: if a node has an even number of arcs, then if you start at that node (and you traverse each arc exactly once), then you must also end your route at that same node. On the other hand, if a node has an odd number of arcs, then if you start at that node (and you traverse each arc exactly once) then you must end your route at some other node.

Armed with that knowledge, let’s imagine you start your stroll at node A. In order to cross one or more bridges, you’re going to have to move to some other node so let’s assume you then move to node C. Notice that node C has five arcs, however, you’ve already used one of them (you might think about this as literally “burning your bridges” every time you cross an arc), so it’s as if you’re now starting at a node with an even number of arcs. We know from the previous paragraph that means your route must end at node C. Where to next?

Let’s say you then move to node B, which also has an odd number of arcs. Again you’ve used up one arc and you’re left with an even number of arcs at node B, which implies your route must end at node B. But we’ve just established that your route must end at node C so we have a contradiction, Thus, given your starting path (A->C->B), no route meeting the required conditions is possible.

How can we generalize this conclusion to apply to all possible routes? Notice that all four nodes have an odd number of arcs. Therefore, it doesn’t really matter where you start – the second node you visit is going to have an even number of arcs left after you arrive there and, therefore, we must end our route on that second node. But the same thing will be true of the third node we visit. So, regardless of the path we take through our first three nodes, we’re going to conclude that our path must end at our second AND third nodes. No route could end in two places so we’ve effectively proven, by contradiction, that no possible route can be found which satisfies our conditions.

This problem was originally solved by the great mathematician Leonhard Euler and spawned an entire branch of mathematics called Graph Theory. You can read more about the Bridges of Konigsberg here. According to this article, two of the bridges were destroyed during WWI and three were rebuilt. Thus, there are now five bridges of Konigsberg, now Kaliningrad, two of which date back to Euler’s time.

# Saturday Puzzle #6 – Finding The Time

The original incarnation of today’s puzzle talks about winding a clock but who, under the age of 40, knows what that means anymore? Here’s a slightly more modern formulation…

While you’re asleep one night, there’s a power outage. When you wake up, your alarm clock is flashing (but running), alerting you to the fact that you lost power for some period of time but you have no idea how long the outage lasted, and therefore no idea what time it is. You would like to reset your alarm clock to the current time but you don’t own any other clocks or watches or any communication devices whatsoever – no TV, no radio, no telephone, no cell phone, no computer, etc. And you live all alone in a very isolated place. Your only hope is a friend who has an accurate clock, however, he lives a long walk away from your house. So you walk to your friend’s house, stay overnight, then walk back home (assume the same amount of travel time in both directions). When you return home, you are able to accurately set your clock. How do you do it?

The answer will be posted tomorrow, along with the names of any readers who guess the solution.

Solution: Hats off to Al P. & Kimberly C., who cleverly worked out the correct solution. The trick is to record the times shown on your clock when you leave and return home, as well as the times shown on your friend’s clock when you arrive at, and leave, his house. Here’s what you do with that information:

1. When you return home, subtract the time shown on your clock from the time shown when you left home – this is the total amount of time you’ve been gone.
2. Subtract the time shown on your friend’s clock when you left from the time shown when you arrived – this is how long you stayed at your friend’s house.
3. Subtract the amount of time spent at your friend’s house from your total time away from home, this is the two-way travel time to and from your friend’s house.
4. Divide the travel time by two, to get the one-way travel time.
5. Add the one-way travel time to the time shown on your friend’s clock when you left his house. That result is the current time.

That might seem a bit complicated but it’s not really that bad – let’s work through a specific example. Suppose I wake up to a flashing alarm clock displaying 9:00 am. I immediately leave for my friend’s house and, as soon as I arrive, I note that his clock displays 11:24 am. I stay at my friend’s house exactly 24 hours and leave the next morning at 11:24 am (per his clock). When I return home, I note that my clock displays 9:48 am. Now we simply follow the steps above:

1. Subtracting the time shown on my clock when I returned home from the time shown when I left tells me I’ve been gone for 1 day and 48 minutes (9:48 – 9:00 on the previous day).
2. I know that I spent exactly 1 day at my friend’s house.
3. Subtracting the time spent at my friend’s house (1 day) from the total time away from home (1 day, 48 mins) gives me the total travel time of 48 minutes.
4. Dividing the total travel time by two gives me a one-way travel time of 24 minutes.
5. Therefore, I left my friend’s house 24 minutes ago, when his (accurate) clock showed the time to be 11:24 am so I can confidently set my clock to 11:48.

Now my alarm clock is back in synch with the current time and I can rest easy – until the next power outage!

# Saturday Puzzle #5 – The Birthday Problem

How surprised should we be to find a common birthday in a random group of people? When you meet a new acquaintance, the chances are only 1 in 365 that s/he will share your birthday. But the odds of any two people having a common birthday in a large group of, say, 100 people, are extremely high. Like last week’s challenge, today’s puzzle comes with a custom-built software simulation to illustrate the answer. We’ll take this challenge in two parts…

Part 1
Imagine a random group of N people. What is the smallest value of N that will guarantee that two or more people in the room have the same birthday?

Part 2
The likelihood of a common birthday increases with N. When N=1, there’s zero chance of having two people with the same birthday. When N=2, there’s a small chance (1/365) that those two people share the same birthday. When N=3, the odds of a common birthday increase ever so slightly (because any pair of those three may share a common birthday). So here’s the question: what is the smallest value of N such that the odds of a common birthday in the group reach 50%? In other words, how large a group do you need to convene in order to have a 50-50 chance that two people in the group share a birthday?

If you’re not sure, take a guess based on your intuition and check back tomorrow to see how close you got. For those who can’t wait till tomorrow, I’ve implemented a software simulation below. Enter the desired number of people in the group, click start and the software will rapidly simulate the scenario for you. See if you can tune the simulator to find the “50% point”, which solves the puzzle.

Number of People in Group    Experiment Number    Success (Common Birthday) Rate

Solution:

Part 1
Imagine this very unlikely (but possible) scenario: 365 people enter a room and they all have different birthdays – every day of the year is spoken for by one and only one person. Now the 366th person enters the room and there are no more unclaimed days – that person must share a birthday with one of the 365 people already in the room. Thus, the smallest value of N such you are guaranteed to have at least one common birthday is 366.

Part 2
Let’s call the probability that two or more people in the group share a common birthday P(CB) (“common birthday”). The easiest way to solve this part of the puzzle is to calculate the opposite of what you’re interested in, i.e. the probability that no pair of people in the group share a birthday (we’ll call this P(NCB), “no common birthday”) and then subtract that value from one. This works because the sum of the probabilities of two opposite, mutually exclusive events is always one.

So how do we calculate P(NCB) for some group N? When the first person enters the room, P(NCB) = 1 because you can’t have a shared birthday with only one person. When the second person enters the room, P(NCB) = (364/365). When the third person enters the room, P(NCB) = (364/365) * (363/365), and so on.

Click to generate a table of values for P(NCB) and P(CB) with N varying from 10 to 30. By examining the generated table, you can see that P(CB) first exceeds .5 at N=23. In other words, any time you assemble 23 or more people in a group, there’s a better than 50% chance that two or more people in the room have a common birthday. You can read more about this puzzle here.

# Saturday Puzzle #4 – Flipping Coins

Imagine tossing a coin repeatedly until you get a certain pattern, let’s say HTT (head, tail, tail). For example, in this sequence of outcomes:

HHTHHTHHTTHHTTTHTH

the desired pattern was reached after the 10th toss (highlighted in red).

Now let’s imagine you repeat that same experiment and each time you record the number of tosses needed to see the desired pattern. The first time you might see HTT after 10 tosses (as in the example above), the second time you might see HTT after 7 tosses, the third time after 15 tosses, etc. After many such experiments, you calculate the average number of tosses needed to see the HTT pattern.

At the same time, imagine your friend does the same number of experiments but she’s looking for a different pattern:  HTH (head, tail, head).

Here’s the question:  on average, will it take more flips to see HTT than HTH, or vice versa, or about the same number of flips to see both patterns? The answer may surprise you. Submit your guess in a comment below and I’ll post the solution tomorrow.

If you can’t wait till then, try the software simulation below (which I’ve personally written for today’s puzzle) and the answer will reveal itself. This puzzle comes from a fascinating TED talk on how statistics fool juries.

Pattern Experiment Average Flips Last Sequence
HTT
HTH

Solution: If you didn’t figure this one out, you’re in good company because distinguished mathematicians routinely get it wrong. Most people think it should take the same number of tosses to see both patterns but, as the software simulation above shows, on average, it takes more tosses to see HTH (10) than HTT (8). Here’s why…

Imagine you’re waiting for HTH and you see a head followed by a tail. You’re two thirds of the way there! On the next toss one of two things will happen: either it’s a head, in which case you’re done, or it’s a tail, in which case you have to start all over again. Now imagine the same scenario when you’re looking for HTT. You see a head followed by a tail, at which point you are, again, one toss away from success. If the next toss is a tail, you’re done, but if the next toss is a head, you don’t have to go all the way back to the beginning – you’re immediately one-third of the way toward another potential HTT sequence. A failed HTT sequence overlaps with the next potentially valid sequence. This fact gives HTT a small built-in advantage over HTH. If that’s not sufficiently satisfying, this page gives a more formal explanation.

# Saturday Puzzle #3 – How much does a brick weigh?

I like puzzles that are easily stated. Today’s challenge, from the fertile mind of the late, legendary puzzle master Martin Gardner, is a model of simplicity:

How much does a brick weigh if it weighs 5 pounds plus half its own weight?

Here’s how the Saturday puzzle series works:

• To avoid prematurely divulging the answer, all comments are hidden by default.
• Twenty four hours after posting a new puzzle I make all comments visible and I recognize all correct submissions in an update to the main article

Happy puzzling!

Update: We have two winners: Simon Banks and Kimberly Cohen. Let’s call the brick’s weight W. If the brick weighs 5 pounds plus half it’s weight, we can state that fact algebraically like this: W = 5 + .5W. Subtracting .5W from both sides gives us .5W = 5. Multiplying both sides by 2 yields W = 10, so the brick weighs 10 pounds.

# Saturday Puzzle #2 – Burning Strings

I first heard today’s puzzle several years ago from a co-worker who had recently returned from a job interview at Microsoft, where he’d been asked to solve this one in real time. I’m not a big believer in those sorts of puzzle interview questions – they’re good for spotting people who think quickly on their feet (or who already know the answer :), but I don’t think they necessarily help you find great programmers. Nevertheless, it’s a cute puzzle…

Imagine you have two lengths of string, each of which is known to have the following characteristics:

• When lit at one end, each string takes exactly one hour to burn completely.

• The strings burn at a non-uniform rate, i.e. there’s no way of predicting what proportion of a string will burn in any given time period (apart from the fact that 100% of the string will burn in exactly one hour, per the previous item).

Here’s the challenge: given these two strings and two matches, how can you measure a 45 minute time interval? As always, the first correct responder gets a shout out in this post.

For an interesting discussion of Microsoft’s famous interview puzzles, see How Would You Move Mount Fuji?.

UPDATE: We have a winner…actually two winners: Kimberly Cohen and Al Pessot. You can read their answers in the comments to this post but here’s the key insight: if you light both ends of a string, it’s guaranteed to burn in exactly half the time it would take for the entire string to burn when lit from one end. To see why this must be true, imagine that when the string is lit from both ends it takes something other than than 30 minutes to burn, let’s say 25 minutes. That would imply that if we lit the string from one end, it would take 2 x 25 = 50 minutes to burn, which contradicts one of our basic assumptions. Using this fact, and some adroit match work, you can measure two successive intervals of 30 and 15 minutes for a total of 45 minutes.

# Saturday Puzzle #1 – An Unusual Paragraph

If you manage to solve this puzzle, post your answer in a comment here, (or on facebook or twitter) and I’ll update the main article to congratulate the first correct responder. No googling allowed – you’ll get a lot more out of it if you work out the answer on your own.

How quickly can you find out what is unusual about this paragraph? It looks so ordinary that you would think that nothing was wrong with it at all and, in fact, nothing is. But it is unusual. Why? If you study it and think about it you may find out, but I am not going to assist you in any way. You must do it without coaching. No doubt, if you work at it, it will dawn on you. Who knows? Go to work and try your skill. Par is about half an hour. Good luck!

Question: What is unusual about the above paragraph?