Regex Crossword

I'm going to phone this one in, sort of, because it's an entire site of puzzles. Regex Crossword is a twist on the traditional crossword concept. In each cell you have to enter in a character that satisfies two or more regular expressions that apply to the cell in question. They start out really trivial but start to get very difficult later on. This is the last one I solved and holy shit was it ever tough:

I'm hooked. Go check these out.

The Merchants and the Coin Purse

Three merchants saw in the road a purse [containing money].
One said, "If I secure this purse, I shall become twice as rich as both of you together."
Then the second said, "I shall become three times as rich."
Then the third said, "I shall become five times as rich."
What is the value of the money in the purse, as also the money on hand [with each of the three merchants]?

(Source: The Penguin Book of Curious and Interesting Puzzles by David Wells, this puzzle by way of the Bakhshali manuscript)

Let $p$ be the value of the contents of the purse and $m_1$, $m_2$ and $m_3$ be the values of the cash on hand held by the first, second and third merchants, respectively. If you read the problem right, this problem becomes a system of linear equations:

\begin{align*}
p + m_1 &= 2(m_2 + m_3) \\
p + m_2 &= 3(m_1 + m_3) \\
p + m_3 &= 5(m_2 + m_3)
\end{align*}

You may notice that there are four unknowns and only three equations, making the system underdetermined. (But that's just as well given that my knowledge of medieval Indian currency is effectively nonexistent.) That being said, to the extent that it can be solved—I did so in Maxima—the answer is $p = 3$, $m_1 = \frac{r_1}{5}$, $m_2 = \frac{3 r_1}{5}$, $m_3 = r_1$, where $r_1$ is effectively an arbitrary constant. But if we hone in on the solution that has the smallest values possible without allowing fractional coins, then the merchants, in order, hold one, three and five coins of equal value, respectively, and the purse contains 15 coins of that value. This means, for example, that by securing the purse, the first merchant would then hold 16 coins, twice as many as three held by the second and the five held by the third added together.

Extracting the Cherry

This puzzle is a golden oldie, with a simple but elusive answer.

The cocktail cherry is inside the glass, which is formed from four matches. Your task is to move at most two of the matches, so that the cherry is then outside the glass. You can turn the glass sideways or upside down if you wish, but the shape must remain the same.

Move two matches to extract the cherry.

(Source: Professor Stewart's Cabinet of Mathematical Curiosities by Ian Stewart)

The solution I came up with was to shift the horizontal match far enough to the right that its non-flammable end touches that of the lower vertical match and then take the left vertical match at the top and set it perpendicular to the flammable end of the horizontal match, so that it forms a new "side" of the glass. (Of course this process can also by started by shifting the horizontal match to the left and the answer will be symmetrical to the one obtained doing things how I did them.)

If that description was confusing—I wouldn't blame you for finding it thus—here's how it's portrayed in the solutions:

Hitler and Goering

Add Hitler to Goering and get—what? Letters substitute for digits in the sum below. The same letter stands for the same digit wherever it appears, and different letters stand for different digits.

The slightly inappropriate addition puzzle

Find the digits the letters represent.

(Source: Brain Puzzler's Delight by E.R. Emmet)

The key to getting started is focusing on the leftmost column, where the result of the addition is an H. This can only be a one carried over from the column to the right, so H is equal to one. Then we turn our attention to second leftmost column. Recalling that this column carries over into the last, the only possibility with only one number in the column is for G to be nine with a carryover from the third leftmost column, adding to ten, making T zero. In turn, that carryover from the third leftmost column is only possible if—remembering that each letter stands for a different digit—there was a carryover from the fourth leftmost column and if O is equal to eight. Four letters are already knocked out!

Now look at the rightmost column. This contains two known columns and one unknown that can be solved. G (nine) adds with R, resulting in H (one) and a carry digit, meaning that G plus R equals 11. This means that R is equal to two. The middle column that contains R can then be figured out. T (zero) adds with R (two), resulting in L. Again, because each of the letters stands for a different digit, the only way this is possible is if there was a carryover from the column to the right, with the result that L is equal to three.

The last three letters fall into place pretty quickly now. The least significant digit of L (three) plus I is H (one), meaning that they added up to 11. Eight has already been used up by O, so I is equal to seven, and there was a carryover from the column to the right. In turn, the least significant digit of I (seven) plus E is L (three), meaning they added up to 13, which is only possible if E is equal to six. Finally, the least significant digit of E (six) plus N is H (one) again, meaning they added up to 11. Recall that there is a carry digit from the rightmost column, so N is equal to four.

Final answer: 1,170,362 plus 9,862,749 equals 10,033,111.

Carnival Dice Game

The following dice game is very popular at fairs and carnivals, but since two persons seldom agree on the chances of a player winning, I offer it as an elementary problem in the theory of probability.

On the counter are six squares marked 1, 2, 3, 4, 5, 6. Players are invited to place as much money as they wish on any one square. Three dice are then thrown. If your number appears on one die only, you get your money back plus the same amount. If two dice show your number, you get your money back plus twice the amount you placed on the square. If your number appears on all three dice, you get your money back plus three times the amount. Of course if the number is not on any of the dice, the operator gets your money.

To make this clearer with an example, suppose that you bet $1 on No. 6. If one die shows a 6, you get your dollar back plus another dollar. If two dice show 6, you get back your dollar plus two dollars. If three dice show 6, you get your dollar back plus three dollars.

A player might reason: the chance of my number showing on one die is 1/6, but since there are three dice, the chances must be 3/6 or 1/2, therefore the game is a fair one. Of course this is the way the operator of the game wants everyone to reason, for it is quite fallacious.

Is the game favorable to the operator or the player, and in either case, just how favorable is it?

(Source: Mathematical Puzzles of Sam Loyd, Volume 1, edited by Martin Gardner)

This is an example of the binomial distribution in action. The probability that exactly one die comes up with the chosen number is $\binom 31 \left(\frac{1}{6}\right)^1 \left(\frac{5}{6}\right)^2$ or about 0.347. Computed in much the same way, the probabilities that exactly two or three die come up with the chosen number are, respectively, about 0.069 and 0.005. One notices there is actually a more or less geometric decay in the probabilities of these latter outcomes, and that should be seen as foreshadowing. The probability of none of the dice coming up with the chosen number is then one minus the sum of the three other probabilities, or about 0.579. The expected value of the game is then about $0.579 \times -1 + 0.347 \times 1 + 0.069 \times 2 + 0.005 \times 3$ or a little more than negative 8¢. The game is favorable to the operator, but only by a bit. This is also how the standard game of craps goes, although the edge in favor of the house is even smaller, a bit more than 1¢. Perhaps this can help explain why craps remains popular while—to my knowledge—this game is no longer played at carnivals. (Samuel Loyd lived from 1841 to 1911.)

Have Your Cake and Eat It Too

Classic puzzles are fun to revisit now and then, especially if there's a new twist.

In this puzzle, see if you can be as successful as John in retrieving water for his mother. The new twist? The buckets are different sizes.

John's mother told him to go to the river and bring back exactly 9 gallons of water in one trip. She gave him a six-gallon bucket and a five-gallon bucket to complete his task. Of course, John's mother told him she'd bake his favorite cake if he came back with the 9 gallons.

John had his cake and ate it, too. Can you?

(Source: The Big Book of Mind-Bending Puzzles by Terry Stickels)

John took the following steps:

1. He filled the five-gallon bucket.
2. He emptied the five-gallon bucket into the six-gallon bucket.
3. He filled the five-gallon bucket again.
4. He topped off the six-gallon bucket with the five-gallon bucket, leaving four gallons in the latter.
5. He emptied the six-gallon bucket back into the river (or on the ground, whatever you like).
6. He emptied the five-gallon bucket into the six-gallon bucket which, per step four, left four gallons of water in the latter.
7. He filled the five-gallon bucket.
8. Then he went home with exactly nine gallons.

Given that, at this point, the six- and five-gallon bucket respectively weighed about 33 and 42 lbs., he may have worked up quite an appetite by the time he got home.

Beef and Sausages

"A neighbour of mine," said Aunt Jane, "bought a certain quantity of beef at two shillings a pound [i.e. at 24 pence a pound], and the same quantity of sausages at eighteenpence a pound. I pointed out to her that if she had divided the same money equally between beef and sausages she would have gained two pounds in the total weight. Can you tell me exactly how much she spent?"

"Of course, it is no business of mine," said Mrs. Sunniborne; "but a lady who could pay such prices must be somewhat inexperienced in domestic economy."

"I quite agree, my dear," Aunt Jane replied, "but you see that is not the precise point under discussion, any more than the name and morals of the tradesman."

(Source: Amusements in Mathematics by Henry Ernest Dudeney)

(This background information on currency may be useful.) 

The key here is to focus on a variable, let's call it $b$ (for budget, denominated in pence) and then relate that to the amounts of each product bought. It should be clear that, if she had bought one pound of beef and another of sausages, she would have spent a total of 3s.6d. (or 42 pence). If it had been two pounds of each, she would have spent 7s. even (or 84 pence) and so on.

It is also important to note that the amount of beef bought is equal to $b \times \frac{24}{42} \times \frac{1}{24}$, or just $\frac{b}{42}$. This means to say that the amount of beef bought is equal to the fraction of the budget spent on beef, divided by the price per pound. Similarly, the amount of sausages bought is also $\frac{b}{42}$. Therefore the total amount of pounds of meat bought all told is $\frac{b}{21}$.

If, on the other hand, the neighbor had spent an equal amount of her budget on both of the two foodstuffs, then the amount of beef bought would have been $b \times \frac{1}{2} \times \frac{1}{24}$ and, of sausages, $b \times \frac{1}{2} \times \frac{1}{18}$. All that remains now is to add two to the poundage of the items that she did in fact buy and equate it with the poundage that she might have bought as described here. Simplifying a bit:

\[ \frac{b}{21} + 2 = \frac{b}{2} \times \left(\frac{1}{24} + \frac{1}{18}\right) \]

Solving for $b$ reveals that it is equal to £8.8s. (or 2016 pence). Because the total poundage of meat bought is equal to the budget divided by 21, she bought 96 total, or 48 of each. Had she spent equal amounts on each of the two foodstuffs she would have bought 42 pounds of beef and 56 of sausages for a total of 98.