Category Archives: Puzzle

Saturday Puzzle #28 – Ones and Zeros

I like puzzles that are easy to state and don’t require a lengthy explanation. Today’s puzzle falls into that category. It comes from my good friend of 30 years, Ken O’Brien, who asked me this simple but perplexing question: “What is the smallest number evenly divisible by 225 that contains only the digits 1 and 0?”

If you’re not able to find the answer analytically, see if you can solve it algorithmically. In other words, see if you can come up with a procedure (brute force method or something more efficient) for finding the answer and leave me a comment with your results (I’ll post the answer on Tuesday). Oh, and by the way, don’t try to use ones and zeros for commercial purposes – they’re patented.

Solution: I know of three ways to solve this problem:

  1. The Slow Search Method – This approach starts with 225 and multiplies it by an ever-increasing sequence of integers looking for a number that contains only ones and zeros. Here’s the Python code to implement this method:

    import time
    
    start = 225    # starting number
    num = start
    cnt = 1
    binary_digits = ('0', '1')
    keep_looking = True
    
    # capture start time
    start_time = time.clock()
    
    while keep_looking:
        num += start
        # check for all 1s and 0s in num
        keep_looking = False # assume we found desired number
        for i in str(num):
            if i not in binary_digits:
                keep_looking = True # nope, not the desired number
                break
        cnt += 1
        
    elapsed = time.clock() - start_time # calculate elapsed time
    
    # we exit the above loop when we've found the desired number
    print('after', cnt, 'iterations and', elapsed, 'seconds:', num)

    Which prints the following result:
    after 49382716 iterations and 83.33 seconds: 11111111100

  2. The Fast Search Method – This strategy observes that the desired result looks like a binary number (albeit in base 10) so it tests a sequence of binary numbers, treating each as a base 10 number, looking for one that’s evenly divisible by 225. This is much faster than the previous method because it automatically skips all the base 10 numbers that have digits other than 1 and 0. Here’s the Python code:

    import time
    
    def convert(num, b1, b2):
        '''convert the passed num from base b1 to base b2'''
        result = 0
        digits = []
        while num:
            digits.append(num % b1)       
            num //= b1
        digits.reverse()
        for i in digits:
            result = (result * b2) + i
        return result
    
    start = 225
    num = 1000 # start with smallest possible answer > 225
    cnt = 1
    
    # capture start time
    start_time = time.clock()
    
    while True:
        if (num % start) == 0:       
            break
        # convert to base 2, increment, then convert back to base 10
        num = convert(num, 10, 2)
        num += 1
        num = convert(num, 2, 10)
        cnt += 1
        
    elapsed = time.clock() - start_time # calculate elapsed time
    
    # we exit the above loop when we've found the desired number
    print('after', cnt, 'iterations and', elapsed, 'seconds:', num)

    which prints the following result:
    after 2037 iterations and 0.04 seconds: 11111111100

  3. The Analytical Method – Because 225 ends in 25, multiples of 225 will end in one of four possible digit pairs: 25, 50, 75 or 00. The only one that meets our requirements (only 1s and 0s allowed) is the last one so we know that the result must end with two 0s. We can also see that 225 is divisible by 9 (recall the rule from grade school about summing the digits to check if a number is divisible by 9) and, therefore, any multiple of 225 must also be divisible by 9. Thus, the digits in the result must also sum to 9, so the smallest possible number meeting our requirements will contain nine consecutive 1s and will end with two 0s: 11111111100.

Obviously the fast search method is much more efficient than the slow search method (nearly 50,000,000 fewer loop iterations and 2,000 times faster) but the analytical approach is the clear winner because it doesn’t require any searching at all. The most efficient program of all is the one you don’t need to write. :)

Saturday Puzzle #27 – Let’s Make A Deal!

Today’s puzzle is so much fun and so counter-intuitive (accomplished mathematicians often get this one wrong), that I created a whole web site for it, hosted on Google App Engine.

You can find the website here: http://montyhallpuzzle.appspot.com. It includes a Javascript simulation, so if you don’t believe the answer you can try it for yourself. There’s also an “Auto-Run” capability which runs many trials very quickly. Enjoy!

Saturday Puzzle #26 – The Eight Queens Problem

You don’t have to be a chess player, or even know the rules of chess, to have a good time with today’s puzzle. All you need to know is that the queen is the most powerful chess piece – she can move as far as she likes in any direction: forward and back, sideways to the right or left, and diagonally. The diagram on the right illustrates the queen’s awesome power.

Today’s challenge is to place eight queens on a chess board such all 64 squares are attacked and no two queens are attacking each other. To make this puzzle easy and fun, I’ve created a custom software simulation, which you can use to try to solve it yourself right here on my blog (so you don’t even need a chess set). Just click on a square below to add a queen, and keep going until you’ve placed eight queens or run out of space with fewer than eight. You can click on an existing queen to undo a placement and there’s a reset button below the board in case you want to start over. You can also click the “solve” button to have your computer quickly find a random solution (there are many). Have fun and leave me a comment if you manage to solve this one!

Queens placed: 0 Covered (occupied + attacked) squares: 0

Saturday Puzzle #25 – Penny For Your Thoughts

IMG_7961 by Drown, on Flickr
Creative Commons Attribution-Share Alike 2.0 Generic License  by  Drown 

Imagine a very wealthy and eccentric friend (which is the best kind of friend to have) offers you the following choice:

  • One penny on the first day of January, two cents on the second day, four cents on the third day, and so on, doubling the amount you receive each day up to the 31st day of January.
  • One million dollars

Which option would you choose?

Solution: Today’s problem illustrates the power of a geometric series. It starts out very slowly, 1 cent, 2 cents, 4 cents…it seems like child’s play but by the end of the month, watch out! The number of pennies you receive on day N is given by 2 raised to the power N-1, which we can write mathematically like this: f(x) = 2**(x-1). The following graph of this function illustrates the sudden, rapid growth of a geometric series:

On the last day of January you would receive 2**(N-1) = 2**30 or 1,073,741,824 (over one billion) pennies, which is more than 10 million dollars! But it gets even better because we have to sum the pennies received throughout the entire month of January. The sum of all pennies received through day N is given by (2**N) – 1, which, in our case, would be (2**31)-1. That comes to 2,147,483,647 cents or, roughly, 21.5 million dollars.

Congrats to Simon Banks, Morag Livingston, Mudassir Ansari and Neal Starkman, all of whom wisely chose the pennies. Neal also pointed out the need for penny wrappers and hired help, which presumably can be paid with a portion of your $20M windfall.

Saturday Puzzle #24 – This Puzzle Has Its Ups and Downs

One of the nice things about living in Seattle is that on clear days we get a great view of Mt. Rainier. Considered an active volcano, Mt. Rainier is the third-highest mountain in the lower 48 states at 14,411 feet, and the most ice-covered, with 25 major glaciers covering 34 square miles (source).

Let’s imagine that at noon one day you set out from the base of Mt. Rainier and you reach the summit exactly 24 hours later, at noon the following day. You pause for a few moments to take in the view and celebrate your accomplishment and then you turn around and head back down the mountain. You may or may not travel the same route down the mountain but assume the descent takes exactly the same amount of time as the ascent: 24 hours on the dot. Thus, you spend precisely two days on this venture, one day going up and one day coming back down (in reality, the climb and descent would take less than a full day but I’m taking a bit of “puzzle license” here).

Here’s the big question: during those two days spent going up and down the mountain, was there a point where you were situated at the exact same elevation, at the exact same time of day? (For example, at 10:42:29pm on both days you were exactly 6,531 feet above sea level). Leave me a comment with your guess below.

Solution: Congrats to Al Pessot, Katy Gustafson, Dylan Gustafson, Mehmet Said, Doug Needham and Muzaffer Peynirci, all of whom found that there is sure to be one time of day when you are at precisely the same altitude.

The rigorous but esoteric way to prove this fact is to use something called the intermediate value theorem from calculus. But there’s a much simpler and more intuitive way to understand this puzzle. Instead of thinking about one person climbing and then descending a mountain, imagine two people – one starting at the bottom and one starting at the top, ascending and descending in parallel. At some point, those two climbers are guaranteed to pass each other, altitude wise, at precisely the same time.

Al Pessot came up with a formulation which makes this point more dramatically: imagine the two climbers are constrained to follow the same path up and down the mountain. At some point, they will literally bump into each other, and that point will be, of course, at the same altitude and time of day.

Finally, Katy Gustafson came up with an interesting “border case” solution I hadn’t considered: the ascent and descent start and end, respectively, at the same altitude and time of day (base camp at noon), which is absolutely correct. Sometimes the easiest solution is the one right in front of your nose. :)

Saturday Puzzle #23 – Lighten Up

Light Switch by krossbow, on Flickr
Creative Commons Attribution 2.0 Generic License  by  krossbow 

You are standing in a hallway with three light switches. Each switch has an accurately labeled on and off position. In an adjoining room, behind a closed door, there is a bare lightbulb, which is controlled by one of the three switches. The other two switches are not connected to anything. You are free to manipulate the switches any way you like and for as long as you like, and you are permitted to enter the room containing the lightbulb once and only once. If and when you exit the room, you must close the door behind you – you are never permitted to view the lightbulb while manipulating the switches.

Here’s your challenge: figure out which of the three switches controls the lightbulb.

Solution: This blog may not have a lot of visitors but I sure do have some smart, creative readers. The comments below make one thing abundantly clear: there are multiple correct answers to this week’s puzzle. People found solutions involving roasting human hair, monitoring power meters, breaking the switches, installing a doggie door, self-electrocution, and several other ideas, which you can read about yourself below. My favorite solution, and the one I had in mind, goes as follows:

  1. Set switch #1 to the on position and switches #2 and #3 to the off position.
  2. Wait ten minutes.
  3. Turn switch #1 off and switch #2 on.
  4. Enter the room and examine the bulb. If the bulb is on, then it’s controlled by switch #2. If the bulb is off and warm or hot, then it’s controlled by switch #1 (because it was recently left on for ten minutes which caused it heat up). If the bulb is off and room temperature, then, by process of elimination, it must be controlled by switch #3.

Saturday Puzzle #22 – Chain Gang

This week’s puzzle is an original trivia quiz with a twist. The answer to each question is the name of a famous person, where the last name of one answer gives the first name of the next answer (give or take a letter or two). The resulting sequence of answers form a chain, like this one: Elton John, John Wayne, Wayne Brady, etc. See how many names you can find and post your answers in a comment below. If you get stuck, googling is allowed. Have a great weekend!

  1. William Hurt’s co-star in 1985 film Kiss of the Spider Woman
  2. A very pretty woman
  3. Perhaps the best to ever play the royal game
  4. Stage and screen actor who played George Minkowski on Lost
  5. American rocker currently standing in judgement
  6. Filmmaker who popularized a character named Madea
  7. Popular TV lawyer created by Earle Stanley Gardner
  8. Composer of a famous guitar piece, fortunately not named Vintage Flatulence
  9. 50s era movie star seen floating in Norma Desmond’s pool
  10. Protagonist of a famously reclusive novelist’s beloved book

Solution: Congrats to Katy Gustafson, Morag Livingston and Olaf Buehler for finding the chain of names. Here are the correct answers…

  1. Raul Julia
  2. Julia Roberts
  3. Robert (Bobby) Fischer
  4. Fisher Stevens
  5. Steven Tyler
  6. Tyler Perry
  7. Perry Mason
  8. Mason Williams
  9. William Holden
  10. Holden Caulfield

Saturday Puzzle #21 – Palindromically Speaking

Have you ever heard of a palindrome? It’s a word, phrase, sentence (or more) that’s spelled exactly the same way backward and forward. Here are a few well known palindromes:

  • race car
  • A man, a plan, a canal, Panama!
  • I prefer pi
  • Dammit, I’m mad!
  • Ma is as selfless as I am
  • Never odd or even

Today we’re going to talk about palindromic dates, which I’ll define for you right now. If we write any date using the format MMDDYYYY, we get a string of eight digits (for example, today’s date would be written “04082011″). A palindromic date is any date for which the eight digit string looks the same whether written backward or forward.

Today’s date is not a palindrome because “04082011″ is not the same as “11028040″. How about this one: January 2, 2010? Is that a palindrome? Let’s see…written forward that would be “01022010″ and written backward it would be “01022010″. Yup, that’s a palindrome. Got it? Ok, now you’re ready for today’s challenge: Tell me the most recent palindromic date before January 2, 2010. Extra credit if you can give me the two most recent palindromic dates before 01/02/2010. You know the drill – leave your answer in a comment below.

By the way, there’s also a concept of a word level palindrome, where if you reverse a sequence of words, you end up with the same sequence of words you started with. Here are a few cute examples (none of which are original):

  • King, are you glad you are king?
  • Says Mom, “What do you do?” – You do what Mom says.
  • You know, I did little for you, for little did I know you.
  • Please me by standing by me please.
  • Blessed are they that believe that they are blessed.
  • Escher, drawing hands, drew hands drawing Escher.

That last one blows my mind. Have a nice weekend. :)

Solution: Let’s work our way backward, in years, from 2010. 2009 doesn’t work because when written backwards it gives us an invalid month (90). Same story for 2008 through 2002 (month numbers 80, 70, …, 20). But 2001 gives us both a valid month (10) and day of month (02). That gives us the first answer: October 2, 2001 (10022001) is the most recent palindromic date before 01/02/2010.

Continuing backwards, 2000 gives us an invalid month (00) so that year is out. All of the 1900s are out because they imply an invalid day of month (91). Ditto the 1800s, 1700, 1600s, 1500s and 1400s. Finally, we come to the 1300s, which implies a valid day of month (31). 1399 through 1391 again give invalid months but 1390 gives us a a valid month (09) and a valid day of month (31). Alas, although September 31, 1390 (09311390) is palindromic, September has only 30 days! Back to the drawing board…1389 through 1381 yield invalid month numbers but 1380 gives us a valid month (08) and a valid day of month (31). Let’s see – that would be August 31, 1380 (08311380). Yup, that’s a palindrome and a valid date. That’s our second answer.

So the most recent palindromic date before January 2, 2010 occurred less than ten years ago. Amazingly, the next most recent palindromic date occurred over 600 years ago. Congrats to Ricardo Agudo, Katy Gustafson, Al Pessot, Lalo Hidalgo and John Holland for correct answers!

Saturday Puzzle #20 – Ace Ventura, Card Detective

You and two of your friends (not facebook friends, real world friends, remember those?) are playing a game. The dealer holds three cards, which may contain any number of aces (0, 1, 2 or 3). Each player is dealt a card face down, and asked to hold their card up against their forehead so the value side is facing out.

At this point, no player knows which card he/she holds but all three players can see the other two players’ cards. The dealer asks you to raise your hand if you see one or more Aces (of any suit). You look around and see both of the other players are showing an Ace, so you raise your hand. The other two players also raise their hands. So, almost immediately, all three players have their hands in the air.

Next, the dealer says: “If you know whether your own card is an Ace or not, lower your hand”. A few long minutes go by, as all three players ponder this question. All three hands remain in the air. Here’s the challenge: given everything I’ve told you, can you determine whether you have an Ace or not?

As always, leave your guess in a comment. I now support Facebook comments, so feel free to use that option if you like.

Solution: The way to solve this puzzle is to put yourself in the other guy’s shoes, so to speak. Let’s call the three players A (you), B and C. Player B’s hand is in the air because he sees at least one ace – player C’s card. Now let’s imagine that you hold some card other an ace. Player B will reason as follows:

Player C’s hand is in the air so she sees an ace but it can’t be A’s card because I (player B) can see that player A’s card is not an ace. Therefore, player C must be looking at my ace.

Player C can make a symmetric argument (if A doesn’t have an ace, then B must be looking at my ace). Thus, if you don’t hold an ace, with a moment of thought it will be obvious to both B and C that they hold aces and their hands will go down in short order. The fact that they don’t reach that conclusion suggests that you must be holding an ace.

The solution to this puzzle involves indirect thinking in the sense that it requires you to reach a conclusion based on other people’s inability to reach a conclusion. To be fair, I probably should have stated something like this: the other players in the game are known to be perfectly logical people. Even without that clarification, some smart readers figured out the solution – congrats to Katy, Gareth and Muzaffer!

Saturday Puzzle #19 – Measuring Mystery

This is another one that Microsoft and other companies have used as an interview question but it’s a little easier than some of my recent brain benders. You have two empty containers – one has a capacity of five liters of water and the other can hold at most three liters of water. Both containers are made of clear plastic and have absolutely no markings anywhere. Here’s your challenge: given an unlimited supply of water, I want you to come up with a way to measure exactly four liters of water. Leave me a comment if you find the answer. Good luck!

Solution: I received nine answers to this week’s puzzle and all of them were correct! I have some very smart friends. :) Before I share the solution, I’d like to recognize a few noteworthy submissions:

  • Simon Banks and Morag Livingston are living proof that married couples think alike.
  • Muzaffer Peynirci submitted a brilliant algorithm that works independently of which container holds five liters and which holds three. In essence, Muzaffer solved a much harder problem: measure the four liters of water using the two containers while blindfolded!
  • Demonstrating admirable perseverance, Al Pessot submitted one accurate solution and then followed up with an equally correct but more efficient algorithm. Similarly nice work was submitted by Mudassir Ansari and Ricardo Agudo.
  • Katy Gustafson submitted five (5!) different ways to find the answer, including one approach involving boiling water and another involving sound waves! She concedes that one of her solutions may be in error but that still gave her two more correct answers than anyone else, not to mention the Out of the Box Thinking Prize.

Well done, all! As noted, there are a few ways to solve this one but here’s a three step approach that I find the simplest:

  1. Let’s call the two containers C5 and C3. Fill up C5 and pour its contents into C3 until the latter is filled to the brim. At this point C5 has two liters and C3 has three liters.
  2. Empty C3 and pour the contents of C5 into C3. At this point C5 is empty and C3 has two liters.
  3. Fill C5 and pour its contents into C3 until the latter is filled to the brim. You’ve just added one liter to C3 and removed one liter from C5. Therefore, at this point C3 has three liters and C5 has four liters and you’re done.

Saturday Puzzle #18 – Weighing Your Options

Imagine you have nine uniformly sized white balls, eight of which weigh precisely the same amount, and one is decidedly heavier or lighter than the rest. You also have an accurately calibrated balance scale, which you can use to compare the weight of any two sets of objects.

Here’s today’s challenge: with only three weighings, tell me how you can discover which ball is different and whether it’s heavier or lighter than the other eight.

Bonus challenge for the hard core puzzlers: same problem with twelve balls instead of nine. Again, in only three weighings, tell me how you can find the odd ball (so to speak) and whether it’s heavier or lighter than the other eleven.

Leave me a comment below with your answer. I’ll post the solution on Tuesday. Happy puzzling!

Solution: Let’s partition the nine balls into three groups of three. Mark the first group A1/A2/A3, the second group B1/B2/B3 and the third group C1/C2/C3. Now weigh the three A balls against the three B balls. There are two possible outcomes:

  1. The scale balances. In that case, the odd ball is in group C so weigh C1 against C2.
    1. If the scale balances, then C3 is the odd ball. Weigh C3 against any other ball to see if it’s heavier or lighter than the others.
    2. If the scale doesn’t balance, let’s assume C1 is on top and C2 is on the bottom end of the scale (analysis of the reverse case is similar). So either C1 is light or C2 is heavy. Weigh C1 against any ball (other than C2) – if C1 ends up on the high end then C1 is light. If the scale balances then you know C2 is heavy.
  2. The scale doesn’t balance. Let’s assume group A is on top and group B is on the bottom end of the scale (analysis of the reverse case is similar). We therefore know that there is either a light ball in group A or a heavy ball in group B. Next weigh group A against group C. If the scale shows an imbalance, we know that group A contains a light ball. If the scale balances, we know group B contains a heavy ball.
    In either case, we’ve narrowed down the odd ball to one of three possibilities and we also know whether it’s light or heavy. With our last weighing, we take any two balls from the suspect group and weigh them against each other. If the scale balances, we know the odd ball is the remaining ball from that group (and we know whether it’s light or heavy). If the scale does not balance, we know which ball is odd by whether that group is known to contains a heavy or a light ball.

Now for the harder, twelve-ball problem…start in a similar fashion by partitioning the balls into three groups of four (marking them A1-4/B1-4/C1-4) and weigh group A against group B. Regardless of whether the scale balances or not, rotate three balls, i.e. shift A1-3 to the B side, B1-3 off the scale and three C1-3 onto the A side and weigh again, noting the outcome. There are five possible changes in the result between weighings one and two:

  1. The scale changes from balanced to unbalanced. Because the first weighing (between groups A and B) balanced, the odd ball must be in group C. The only new balls introduced to the scale in weighing two are C1-3 so one of them must be the odd one. We can also tell whether the odd ball from group C is light or heavy by whether the group C balls are on the top or bottom side of the scale after weighing two. And from the analysis of the nine ball problem, we know that when we have the odd ball narrowed down to one of three *and* we know whether it’s light or heavy, we can solve the problem with one additional weighing.
  2. The scale changes from unbalanced to balanced. If, after the first weighing, the scale was unbalanced, let’s assume group A was on top and group B was on the bottom end of the scale (analysis of the reverse case is similar). Therefore, we know we have either a light ball in group A or a heavy ball in group B. After the second weighing the scale becomes balanced. The only way that can happen is if the odd ball was one of the three from group B we removed from the lower end of the scale. Thus, we know one of B1-3 is heavy and we can find it in one additional weighing.
  3. The scale changes from unbalanced one way to unbalanced the other way (i.e. it reverses polarity). If, after the first weighing, the scale was unbalanced, let’s assume group A was on top and group B was on the bottom end of the scale (analysis of the reverse case is similar). Therefore, we know we have either a light ball in group A or a heavy ball in group B. After the second weighing the scale becomes unbalanced in the opposite way. The only way that can happen is if we shifted a light ball from group A (i.e. one of A2-4) to the other side of the scale. We therefore have a group of three balls containing one that is known to be light and we can find the odd ball in one additional weighing.
  4. Scale remains balanced. This implies that after the first two weighings, the odd ball has not yet appeared on the scale. But there’s only one ball that has never been on the scale: C4. So in our third weighing, we compare C4 with any other ball to see if it’s light or heavy.
  5. Scale remains unbalanced (in the same way). For both weighings, let’s assume group A was on top and group B was on the bottom end of the scale (analysis of the reverse case is similar). If the scale remains unbalanced in the same way for both weighings, then the odd ball is one that remained in the same position for both weighings. There are only two balls in that category: A4 and B4. So either A4 is light or B4 is heavy. In our third weighing, compare A4 to any ball (other than B4). If it doesn’t balance then A4 is light. If it does balance then B4 is heavy.

Saturday Puzzle #17 – Putting Your Cards on the Table

In front of you are four cards on a table, which look like this:

Each card has a letter on one side and a number on the other side. Obviously, you can only see one side of each card. Here’s the challenge: tell me which card(s) you need to turn over in order to test the following theory: “If a card has a vowel on one side then it must have an even number on the other side”. Take your time and think about it, then leave me a comment with your answer.

This puzzle has been around for at least forty years. I found it in the book How Would You Move Mt. Fuji? by William Poundstone, which is a fun read and full of interesting “interview puzzles” famously used by Microsoft and other high tech companies in the 90s. Nowadays, most tech companies, including Microsoft, rely more on interactive coding challenges and less on brain teasers, which is probably a good thing – these sorts of puzzles are fun but I don’t think they’re a good way to find talented programmers.

Solution: The key concept to understand here is the very specific nature of this statement:

If a card has a vowel on one side then it must have an even number on the other side.

In the study of formal logic, this statement is called an implication because, given one thing is true, it implies something else is true. We can write implications symbolically like this: A=>B, where, in our current problem A is “a vowel on one side” and B is “an even number on the other side”.

Now let’s look at each card, one at a time:

  • The first card shows a vowel (A) so we can test our theory by checking its other side. If the reverse side shows anything other than an even number, our theory is disproven. If the reverse side shows an even number, it supports our theory but it doesn’t prove it outright – we may still have other cards to check.

  • The second card shows a consonant (F). Our theory says nothing at all about consonants so examining the other side of this card is a waste of time – it will neither support nor disprove our theory.

  • The third card shows an even number (2). Our theory says that if we see a vowel, we should expect to see an even number on the other side but it says nothing about the opposite implication. It does NOT imply that if we see an even number, we should expect to see a vowel on the other wide. In formal logic, A=>B does not imply B=>A. So there is nothing to be gained by turning this card over.

  • Finally, the fourth card shows an odd number (7). It might seem, at first glance, that this card also has nothing to offer (because our theory talks about even numbers and this card shows an odd number) but think about this: what if the other side of this card has a vowel – wouldn’t that disprove our theory? For our theory to be supported, this card must have a consonant on the other wide – otherwise we’d be looking at an odd number on the other side of a vowel which would disprove our theory so we need to examine the back of this card as well.

So there you have it – in order to test our theory as completely as possible, we would want to turn over cards 1 and 4. Hats off to Ricardo and Denis for correct solutions to this week’s puzzle!

Saturday Puzzle #16 – Pink or Blue?

For the past 63 years in a row, babies born in the US have been slightly more likely to be a boy than a girl, at a rate of roughly 51% to 49% (source). For today’s puzzle, let’s ignore that complication and assume the odds of being born a boy or a girl are precisely 50%. Now, imagine you have four children and consider these three possible outcomes:

  1. all four children have the same gender (four boys or four girls)
  2. three have the same gender and one has the opposite gender (three girls and a boy or three boys and a girl)
  3. an even split (two boys and two girls)

Here’s today’s challenge: tell me which of the three scenarios above is the most likely one. If you’re not sure, just take a guess. Leave me a comment with your answer. Extra credit will be awarded if you can tell me the probability of the most likely outcome.

I myself come from a family of four children – my three siblings and I are pictured above.

Solution: The first step is to understand how many possible permutations we’re dealing with. We have four kids and each one has two possible states (male or female) so that gives us 2 to the 4th, which is 2*2*2*2 = 16 permutations. Another way of seeing that is to list the possible gender configurations. We can do this by starting with four girls, which can happen in only one way (GGGG), then listing the configurations with three girls (GGGB, GGBG, GBGG, BGGG), then those with two girls and so on (I’ve noted in parentheses which category each element in the list belongs to):

  1. GGGG (case 1)
  2. GGGB (case 2)
  3. GGBG (case 2)
  4. GBGG (case 2)
  5. BGGG (case 2)
  6. GGBB (case 3)
  7. GBGB (case 3)
  8. GBBG (case 3)
  9. BGGB (case 3)
  10. BGBG (case 3)
  11. BBGG (case 3)
  12. GBBB (case 2)
  13. BGBB (case 2)
  14. BBGB (case 2)
  15. BBBG (case 2)
  16. BBBB (case 1)

Next, we divide those 16 gender configurations into the three categories mentioned in the problem:

Case 1 (4/0): GGGG, BBBB

Case 2 (3/1): GGGB, GGBG, GBGG, BGGG, GBBB, BGBB, BBGB, BBBG

Case 3 (2/2): GGBB, GBGB, GBBG, BGGB, BGBG, BBGG

Finally, we sum the number of permutations in each group and divide by the the total number of possibilities (16) to get the probability of each case:

case 1: 2/16 = 1/8 = 12.5%
case 2: 8/16 = 4/8 = 50.0%
case 3: 6/16 = 3/8 = 37.5%

This result is a bit surprising – because things generally tend to even out over time, most people assume the correct answer is 2/2 but, as you can see, 3/1 is the most likely split. The photo was my way of giving a tiny hint because it depicted the 3/1 (BBBG) split in my own family.

I got several great responses to this one – congrats to my many brilliant readers and my apologies for a little bit of ambiguity in my formulation, which, I think, threw off a few responders. See you next Saturday!

Saturday Puzzle #15 – Ring Around the Earth

Imagine that in a future era humans decide to build a high speed train circumnavigating the globe at the equator. Ignore the impracticalities of such an undertaking (e.g. building railroad tracks across an ocean) and think about this question: How long does the track need to be? This is easy to answer if you know the circumference of the Earth, which is 24,902 (or roughly 25,000) miles at the equator.

Now, imagine our engineering team determines that, for technical reasons, the track needs to be elevated two feet off the ground. We were already planning to acquire 25,000 miles of track so the question is this: how much additional track do we need in order to build our equatorial railroad two feet above the Earth’s surface?

Leave your answer in a comment below. I’ll post a solution and the names of all puzzle solvers on Monday.

Solution: Think of the equator as a giant circle. Let’s call the radius of that circle R, the distance from the center of the Earth to any point on the equator. The elevated track can also be thought of as a giant circle, one with radius R+2 (since the track is two feet off the ground). Now the question of how many additional feet of track we need boils down to subtracting the circumference of the elevated track from the circumference of the equator.

The circumference of any circle is given by 2*Pi*r, where r is the circle’s radius so with a bit of algebra we get:

more track needed = track circumference – equator circumference
= 2*Pi*(R+2) – 2*Pi*R
= 2*Pi*(R+2-R)
= 2*Pi*(2) = 4*Pi ~= 12

So, to raise the track by two feet all 25,000 miles around the Earth, you only need to add approximately 12 feet of track! Even more amazing, because the solution is independent of the starting radius, the same answer applies to every possible circle. For example, if you tied a string around a basketball and then decided to raise that string two feet above the surface of the basketball, you’d need precisely the same amount of additional string: 12 feet.

This is a problem I first heard as a kid and to this day it still strikes me as incredibly surprising. Hat’s off to Mudassir Ansari, Dan Stoops, John Baldi, Ricardo Agudo and Jim Goss for coming up with the correct answer!

Saturday Puzzle #14 – Perilous Pills

You’re a pharmacist and you’ve just taken delivery of ten bottles of 1,000 pills each. All pills are of the same type with the same dosage. But before you have a chance to put them away, your supplier calls to inform you that, due to a glitch at the factory, one of the ten bottles is tainted. The pills are supposed to contain 10 milligrams of medication, but all of the pills in the bad bottle contain one extra milligram.

Obviously, you can’t allow your customers to buy the overdosed pills, but this medication is very expensive so you can’t afford to throw away the whole lot. Fortunately, you have a smart assistant, who suggests weighing the pills. “Brilliant!”, you exclaim, “All we have to do is weigh each bottle – nine will register the same weight and one bottle will weigh an extra 1,000 mg”. “You could do it that way”, adds your assistant with a sly grin, “but that could take up to ten weighings. I can think of a plan that’s guaranteed to find the tainted bottle in only one weighing”.

What was your assistant’s plan? Hint: you may open the bottles and weigh any combination of pills and/or bottles you like. Leave your guess in a comment below. Today’s puzzle is adapted from the book Aha! by the late, great puzzlemaster Martin Gardner.

Solution: The key insight comes from the observation that if you weigh a different number of pills from each bottle then the excess weight can be used to identify the bad bottle. More specifically…

  1. Mark each bottle with a unique number from 1 to 10.
  2. Take one randomly selected pill from bottle one, two pills from bottle two, etc. Weigh the resulting 55 pills together (1+2+3+4+5+6+7+8+9+10 = 55) and note the result.
  3. If all 55 pills were legitimate, the expected result would be 550 mg (10 mg per pill times 55 pills) but the actual result is going to exceed the expected weight because you’ve included some number of overdosed pills in your sample. Subtract the actual weight from 550 mg to find the number of extra milligrams and, hence, the number of bad pills in your sample.
  4. Because you included a different number of pills from each bottle, you can trace the number of bad pills directly to the bad bottle. One bad pill implicates bottle one, two bad pills implicate bottle two, etc.

Hat’s off to Simon Banks, Doug Needham and Kimberly Cohen for submitting correct answers.

Saturday Puzzle #13 – Egyptian Trivia Test

Today we’re doing a good old-fashioned trivia quiz with a topical theme: every answer has something to do with Egypt. There’s something here for everyone: pop culture, ancient history, modern history, geography, politics, you name it. Submit a comment below with as many answers as you can come up with (no googling allowed!). The comment with the most correct answers gets a shout out in an update. Come back later to see all the answers – in the words of Bill Cosby, if you’re not careful, you might learn something!

Can you name these things related to Egypt?

  1. A famous canal
  2. The main language spoken in Egypt
  3. A Woody Allen movie
  4. The three countries bordering Egypt
  5. A long running American TV game show
  6. Of the seven wonders of the ancient world, the only one still standing
  7. A song by The Bangles
  8. An ancient formal writing system combining logographic and alphabetic aspects
  9. The last pharaoh of ancient Egypt
  10. The world’s longest river
  11. The President who preceded Mubarak
  12. The country Egypt was part of before gaining independence on Feb 22, 1922 (2/2/22!)
  13. The three leaders who signed the Camp David Accords in 1978
  14. A mythical creature with a human head on a lion’s body
  15. Answer to the ancient riddle posed by the creature in the previous question
  16. The monetary currency currently used in Egypt
  17. A very costly movie starring Elizabeth Taylor
  18. The two most prevalent religions in current day Egypt
  19. Title character played by Lon Chaney Jr. in a 1944 horror film
  20. Horrendous Steve Martin song, which I may never be able to get out of my head

Solution: Hats off to the brilliant and lovely Kimberly Cohen, who demonstrated her impressive Egypt IQ by scoring correct answers on 15 out of 20 questions.

  1. A famous canal – Suez
  2. The main language spoken in Egypt – Egyptian Arabic
  3. A Woody Allen movie – The Purple Rose of Cairo
  4. The three countries bordering Egypt – Israel (west), Libya (east), and Sudan (south)
  5. A long running American TV game show – The $10,000 Pyramid
  6. Of the seven wonders of the ancient world, the only one still standing – the Pyramids
  7. A song by The Bangles – Walk Like an Egyptian
  8. An ancient formal writing system combining logographic and alphabetic aspects – hieroglyphics
  9. The last pharaoh of ancient Egypt – Cleopatra (Queen Cleopatra VII)
  10. The world’s longest river – the Nile
  11. The President who preceded Mubarak – Anwar Sadat
  12. The country Egypt was part of before gaining independence on Feb 22, 1922 (2/2/22!) – the United Kingdom
  13. The three leaders who signed the Camp David Accords in 1978 – Menachim Begin, Anwar Sadat and Jimmy Carter
  14. A mythical creature with a human head on a lion’s body – the Sphinx
  15. Answer to the ancient riddle posed by the creature in the previous question – man
  16. The monetary currency currently used in Egypt – Egyptian pounds
  17. A very costly movie starring Elizabeth Taylor – Cleopatra
  18. The two most prevalent religions in current day Egypt – Islam (90%) and then Coptic Christianity
  19. Title character played by Lon Chaney Jr. in a 1944 horror film – The Mummy
  20. Horrendous Steve Martin song, which I may never be able to get out of my head – King Tut

Saturday Puzzle #12 – The Disappearing Dollar

Three co-workers are on a business trip. They arrive at their hotel only to learn their reservations have been lost. The desk clerk tells them there is only one room still available but it can be shared by the three companions. The cost of the shared room is $30 (this is an old puzzle :). Reluctantly, they each chip in $10 and take the room. After settling in, the manager finds out about the situation and instructs the desk clerk to provide a reduced rate of $25, as compensation for the guests’ trouble. The clerk sends a clever bellhop to refund the $5 overpayment. Realizing $5 can’t be evenly divided by the three room occupants, the bellhop pockets two dollars and returns $3 to the roommates, each of whom happily accepts his $1 discount.

To summarize, each traveler paid (10 – 1) = $9 so the three roommates together paid $27 and the bellhop kept $2 for a grand total of $29. But the initial outlay was $30. What happened to the missing dollar???

[Post your answer in a comment below. Comments will be hidden for now to avoid spoiling the answer but on Sunday night I'll post the correct solution and make all comments visible.]

Solution: This is a bit of arithmetic sleight of hand – there is no missing dollar. To see why, let’s examine the two transactions:

Event Guests Hotel Bellhop Total
After Check-In -$30 $30 0 0
After Rebate -$27 $25 2 0

After the rebate, the initial payment of $30 is irrelevant. The final payment of $27 is the amount that needs to be reconciled, which it is by adding the hotel’s $25 take and the $2 pocketed by the bellhop. Hat’s off to Sudhakar, Simon and Morag for solving the puzzle correctly. Dan gets the prize for most creative guess. :)

Saturday Puzzle #11 – Einstein’s Puzzle

Today’s puzzle is said to have been devised by Albert Einstein, who supposedly claimed that 98% of the population could not solve it. I haven’t researched the accuracy of this tale, but you can color me highly skeptical. Nevertheless, it’s a beautiful puzzle in the area of deductive reasoning. If you’ve seen this puzzle before you may notice that I’ve taken the liberty of modernizing it: men are replaced with women and cigarette brands are replaced with favorite musicians.

Assume there are five houses of different colors next to each other on the same street. In each house lives a woman of a different nationality. Each woman has a favorite drink, a favorite musician, and keeps a particular type of pet. All such attributes are unique – in other words, no two women share the same house color, nationality, pet, drink, or favorite musician.

Here are 15 facts you should know about this neighborhood:

  1. The Englishwoman lives in the red house.
  2. The Swede keeps dogs.
  3. The Dane drinks tea.
  4. The green house is just to the left of the white one (from in front of the houses).
  5. The owner of the green house drinks coffee.
  6. The Springsteen fan keeps birds.
  7. The owner of the yellow house likes Frank Sinatra.
  8. The woman in the center house drinks milk.
  9. The Norwegian lives in the leftmost house.
  10. The Beatles fan lives next to a woman who keeps cats.
  11. The woman who likes Elvis drinks beer.
  12. The woman who keeps horses lives next to the woman who likes Sinatra.
  13. The German likes Lady Gaga.
  14. The Norwegian lives next to the blue house.
  15. The Beatles fan lives next to a woman who drinks water.

Here’s the challenge: tell me who owns the pet fish.

Hint: A good methodology for tackling this one is to create a 5 by 5 table on a piece of scrap paper, like this:

House 1 House 2 House 3 House 4 House 5
Color
Nationality
Drink
Musician
Pet

Then, print out this article and work on the facts above. When you make one or more deductions from one of the facts, insert the new information into your table and cross that fact off the list. Eventually, you will have no facts left to work on and a nearly full table, at which point the answer will be apparent.

Don’t worry if don’t manage to solve this one – studies have shown that just trying to tackle this sort of problem makes you smarter!

Solution: Congratulations to Mudassir Ansari, who deduced the correct answer. Here’s an annotated sequence of deductions (houses are numbered 1-5, left to right):

  • The woman in the center house drinks milk – so house 3 occupant drinks milk
  • The Norwegian lives in the leftmost house – so house 1 occupant is Norwegian
  • The Norwegian lives next to the blue house – so house 2 is blue
  • The green house is just to the left of the white one (from in front of the houses) – so house 3 or 4 green (and 4 or 5 is white)
  • The owner of the green house drinks coffee – house 3 occupant drinks milk so house 4 is green, house 5 is white and house 4 occupant drinks coffee
  • The Englishwoman lives in the red house – all but house 3 have conflicting color or nationality so house 3 is red and occupied by englishwoman and house 1 must be yellow
  • The owner of the yellow house likes Frank Sinatra – so house 1 occupant listens to Sinatra
  • The woman who keeps horses lives next to the woman who likes Sinatra – so house 2 occupant keeps horses
  • The Dane drinks tea – all but 2 houses have conflicts so the Danish tea drinker must live in house 2 or 5. This is tricky part: in order to resolve whether the Dane lives in house 2 or 5, I tried placing her in each house to see if a contradiction arises. If you try putting the Danish tea drinker in house 5, then by this rule: “The woman who likes Elvis drinks beer”, house 2 must be occupied by the beer drinking Elvis fan. At that point there’s only one missing drink so the house 1 occupant (the Sinatra fan) must drink water but that contradicts the rule that says “The Beatles fan lives next to a woman who drinks water”. We have arrived at a logical contradiction, which means our hypothesis must be wrong – the Danish tea drinker cannot live in house 5. The only alternative is to place the Danish tea drinker in house 2.
  • The woman who likes Elvis drinks beer – all but house 5 have conflicting musicians or drinks so house 5 must be the home of the beer drinking Elvis fan and there’s only one empty drink left so house 1 occupant must drink water
  • The Beatles fan lives next to a woman who drinks water – so house 2 occupant likes the Beatles
  • The German likes Lady Gaga – all but house 4 have conflicting nationalities or musicians so house 4 occupant likes Lady Gaga. Only one nationality left (so a Swede must live in house 5) and only one musician left (so house 3 occupant must like Springsteen)
  • The Swede keeps dogs – so house 5 occupant keeps dogs
  • The Springsteen fan keeps birds – so house 3 occupant keeps birds
  • The Beatles fan lives next to a woman who keeps cats – so house 1 occupant keeps cats

At last, there is only one empty cell in your table. It’s the only unclaimed pet, which is fish, and it belongs to the German, coffee drinking, Lady Gaga listening woman in the green house (#4). For the record, here’s the finished table:

House 1 House 2 House 3 House 4 House 5
Color yellow blue red green white
Nationality Norwegian Danish English German Swedish
Drink water tea milk coffee beer
Musician Sinatra Beatles Springsteen Gaga Elvis
Pet cats horses birds fish dogs

Saturday Puzzle #10 – 24 P for Y to S

I was in sixth grade when I first saw this puzzle (thanks to Miss LaRusso) and it captivated me for three straight days, which tells you something about my personality: 1) I love a challenge, 2) I’m very determined, and 3) I have no problem wasting ridiculous amounts of time on useless activities (like this blog). But enough about me, let’s talk about today’s puzzle.

Each line below contains a phrase involving a number and only the first letter of each word. Your job is to figure out the missing letters and complete each phrase. For example, if the challenge was “50 W to L your L”, you might recognize that old Paul Simon song “50 Ways to Leave Your Lover”. Submit as many answers as you can find in a comment below.

This is the kind of puzzle where answers will pop into your head when you’re not even thinking about the phrases, so take your time. On Tuesday, I’ll post the names of the people who find the most correct answers. And for the puzzle obsessed among us, I apologize in advance for ruining your weekend.

  1. 7 W of the A W
  2. 1,001 A N
  3. 12 S of the Z
  4. 52 C in a D
  5. 9 P in the S S
  6. 88 P K
  7. 13 S on the A F
  8. 32 D F at which W F
  9. 18 H on a G C
  10. 90 D in a R A
  11. 200 D for P G in M
  12. 8 S on a S S
  13. 3 B M (S H T R)
  14. 4 Q in a G
  15. 24 H in a D
  16. 1 W on a U
  17. 5 D in a Z C
  18. 57 H V
  19. 11 P on a F T
  20. 1000 W that a P is W
  21. 29 D in F in a L Y
  22. 64 S on a C
  23. 40 D and N of the G F
  24. 50 L with a W N

Solution: Congratulations to Karl Wirka, who correctly solved all 24 problems. An honorable mention goes to Al Pessot, who found 20 or 24 correct answers. Here’s the complete solution:

  1. 7 W of the A W – 7 Wonders of the Ancient World
  2. 1,001 A N – 1,001 Arabian Nights
  3. 12 S of the Z – 12 Signs of the Zodiac
  4. 52 C in a D – 52 Cards in a Deck
  5. 9 P in the S S – 9 Planets in the Solar System
  6. 88 P K – 88 Piano Keys
  7. 13 S on the A F – 13 Stripes on the American Flag
  8. 32 D F at which W F – 32 Degrees Fahrenheit at which Water Freezes
  9. 18 H on a G C – 18 Holes on a Golf Course
  10. 90 D in a R A – 90 Degrees in a Right Angle
  11. 200 D for P G in M – 200 Dollars for Passing Go in Monopoly
  12. 8 S on a S S – 8 Sides on a Stop Sign
  13. 3 B M (S H T R) – 3 Blind Mice (See How They Run)
  14. 4 Q in a G – 4 Quarts in a Gallon (or 4 Quarters in a Game)
  15. 24 H in a D – 24 Hours in a Day
  16. 1 W on a U – 1 Wheel on a Unicycle
  17. 5 D in a Z C – 5 Digits in a Zip Code
  18. 57 H V – 57 Heinz Varieties
  19. 11 P on a F T – 11 Players on a Football Team
  20. 1000 W that a P is W – 1000 Words that a Picture is Worth
  21. 29 D in F in a L Y – 29 Days in February in a Leap Year
  22. 64 S on a C – 64 Squares on a Chessboard
  23. 40 D and N of the G F – 40 Days and Nights of the Great Flood
  24. 50 L with a W N – 50 Lashes with a Wet Noodle

Saturday Puzzle #9 – Apples and Oranges

In front of you are three boxes. One contains only apples, one contains only oranges and one contains a mix of apples and oranges. Each box is labeled, like this:

  • Box 1: “apples”
  • Box 2: “oranges”
  • Box 3: “apples & oranges”

Unfortunately, all three boxes are mislabeled. That’s where you come in – you’re going to help me fix those labels.

Here’s the challenge: You get to choose one, and only one, box. I will remove a randomly selected piece of fruit from your chosen box and show it to you (so you can tell if it’s an apple or an orange). After that, you will be able to accurately and definitively relabel all three boxes.

Choose wisely, grasshopper. If you manage to solve this puzzle, leave me a comment with your solution. Good luck and don’t forget to eat your fruit!

Solution: If you choose box 1 or 2, you may be in trouble. For example, suppose you choose box 1 (the box labeled “apples”) and you see an orange – then you won’t know if that box contains only oranges or a mix of apples and oranges. You face a similar dilemma if you choose box 2 (the box labeled “oranges”) and you see an apple.

Let’s see what happens if you choose box 3 (the box labeled “apples & oranges”). Let’s assume you see an apple drawn from box 3. You therefore know box 3 contains only apples. Why? It can’t contain a mix (because you already know it’s mislabeled) and it can’t contain only oranges (because you now know it contains at least one apple). There’s only one possibility left: box 3 contains only apples.

Now think about box 2, which is labeled “oranges”. Since we know it’s mislabeled, it can’t contain only oranges and we just discovered that box 3 contains only apples so box 2 must contain a mix of apples and oranges. By process of elimination, we then know that box 1 contains only oranges.

So, if the fruit removed from box 3 is an apple, then the correct labeling is as follows:

  • Box 1: “oranges”
  • Box 2: “apples & oranges”
  • Box 3: “apples”

By a very similar process, the details of which I’ll leave as an exercise to the reader :), if the fruit removed from box 3 is an orange, then the correct labeling is as follows:

  • Box 1: “apples & oranges”
  • Box 2: “apples”
  • Box 3: “oranges”

There you have it – if you wisely choose the box with the mix of apples and oranges for your free sample, everything falls into place. And if you worked that out for yourself, orange you glad I didn’t tell you the answer? Sorry, I couldn’t resist.

Hats off to Muzaffer, Maurice, Al, Simon and Kimberly for finding the answer!