Back to Top

NSA's 2018 Puzzle Periodical

Try your hand at this month's problem written by a member of our expert workforce.

July 2018 Puzzle Periodical - Marble Math

Creator Challenge Difficulty Rating: Easy - Hard

Puzzle created by:
Dr. Benjamin E., NSA Research Mathematician
Dr. Sean W., NSA's Super Genius Extraordinaire (ala Wile E. Coyote), NSA Research Computer Scientist

Problem

  1. (Easy Difficulty) You are given two bags of marbles, one contains only white marbles and the other contains only black marbles. You decide, for fun, to randomly take a number between zero and 20 marbles from each bag and put them in a bowl. Once you've done this, you mix the marbles up and pick two marbles from the bowl sight unseen. If the two marbles are both black, you put a black marble back in the bowl. However, if at least one of the two marbles is white you put a white marble back in the bowl. You repeat this process (drawing two marbles, putting one marble back based on this rule) until you are left with a single marble in the bowl, in which case you note the color of the final marble. You then put all the marbles back in the correct bags and repeat the experiment again with different numbers of white and black marbles. After doing this lots of times, you notice that sometimes there is a black marble left and sometimes a white marble left.
    Can you figure out when the last marble will be black and when it will be white?

  2. (Easy Difficulty) This is same as the first part, except this time when you draw two marbles, if at least one of the two marbles is black then you put a black marble back, while if both of the marbles are white you put a white marble back.
    Can you figure out when the last marble is black and when it's white?

  3. (Hard Difficulty) For the third experiment, you put a black marble back if and only if the two marbles you draw are different (i.e. one white and one black). If they are the same color (both black or both white) you put a white marble back.
    Can you figure out when the last marble is black and when it's white?

Hint:

For all three parts, try working with small numbers first. For example, try all the cases where there are two marbles in the bowl, then three marbles, etc. When you find a pattern, see if that pattern must always hold.

Click to see the answer!

Solution

  1. If there is at least one white marble in the bag at the beginning, then every time you select two marbles and put one back you are sure to have a white marble still in the bag: either you didn't select the white marble, in which case it's still in the bag, or you did pick the white marble, in which case you have to put a white marble back in. Thus, if the bag starts with at least one white marble it is guaranteed to always have a white marble, so that the final marble must be white. If there are no white marbles to start, then clearly the final marble will be black.
  2. This is the opposite of the first puzzle: if there is at least a single black marble then the final marble will be black. The reasoning is similar: assuming there is at least one black marble in the bag, then either you select two different marbles or you select at least one black marble, and in either case the bag is guaranteed to have a black marble afterwards. If it starts with no black marbles, the final marble must be white.
  3. This is trickier: if there are an odd number of black marbles to start then the final marble will be black; otherwise it's white. One way to see this: no matter what the colors of the marble are, the number of black marbles in the bowl is either the same or it's reduced by two. Thus, if there is an odd number before drawing two marbles, there will be an odd number afterwards. If there is only one marble left, it must be black. On the other hand, if there is an even number of black marbles to start, then it will remain even after every drawing and replacing. Thus, if there is one marble left, it must be white.

Another way to view these puzzles is as logical operators on the Boolean values True and False. Think of white as False and black as True. Then the first puzzle describes logical AND. If you AND Boolean values together, the output is True (i.e. black) if and only if every value was True (i.e. every marble is black), otherwise it's False (i.e. white). The second puzzle is logical OR, where the output is True (black) if and only if at least one is True (i.e. at least one marble is black). The third puzzle is XOR, i.e. exclusive OR. The output of XORing Boolean values is True if there is an odd number of True and False otherwise.