[ad_1]
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either, and you may get a shoutout in the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Leonard Cohen comes a timely matter of touchdowns:
In the Riddler Football League, you are coaching the Arizona Ordinals against your opponent, the Detroit Lines, and your team is down by 14 points. You can assume that you have exactly two remaining possessions (i.e., opportunities to score), and that Detroit will score no more points.
For those unfamiliar with American football, a touchdown is worth 6 points. After each touchdown, you can decide whether to go for 1 extra point or 2 extra points. You happen to have a great kicker on your team, and your chances of scoring 1 extra point (should you go for it) are 100 percent. Meanwhile, scoring 2 extra points is no sure thing — suppose that your team’s probability of success is some value p.
If the teams are tied at the end of regulation, the game proceeds to overtime, which you have a 50 percent chance of winning. (Assuming ties are not allowed.)
What is the minimum value of p such that you’d go for 2 extra points after your team’s first touchdown (i.e., when you’re down 8 points)?
Riddler Classic
Amare the ant is traveling within Triangle ABC, as shown below. Angle A measures 15 degrees, and sides AB and AC both have length 1.
Amare starts at point B and wants to ultimately arrive on side AC. However, the queen of his colony has asked him to make several stops along the way. Specifically, his path must:
- Start at point B.
- Second, touch a point — any point — on side AC.
- Third, touch a point — any point — back on side AB.
- Finally, proceed to a point — any point — on side AC (not necessarily the same point he touched earlier).
What is the shortest distance Amare can travel to complete the queen’s desired path?
Solution to last week’s Riddler Express
Congratulations to 👏 Mayukha Vadari 👏 of Redmond, Washington, winner of the last Riddler Express.
Last week, you had to solve a cryptarithm based on a puzzle originally by Frank Mrazik:
As with any cryptarithm, each letter represented one of the digits from 0 to 9, and different letters represented different digits.
The catch? This puzzle had two possible solutions — that is, two distinct sets of letter-to-number assignments. Could you find both solutions?
To no one’s surprise, many solvers found the answers via brute force. There were nine letters in the cryptarithm, each of which had to be assigned to one of 10 digits without repetition. That meant there were 10·9·8·7·6·5·4·3·2, or 10!, cases to consider. That was well beyond one’s ability to manually check, but not a problem for a computer. Solvers Steven Goldburg and David Wanner wrote code that went through all of the approximately 3.6 million possible letter assignments, checking for any that followed the pattern in the cryptarithm.
However, it was (borderline) feasible to find the solutions deductively. Looking at the hundred-thousands place, where an L became an H, solver Rich Erikson immediately recognized that H was one more than L. (Technically, L could be 9 and H could be 0, but having numbers with a leading 0 would be bad form.) Meanwhile, in the ten-thousands place, H+I had be at least 10 (or 9 if there was carrying), and both H and I had to be greater than O.
At this point, you found that most values of L didn’t work. For example, if L was 0 (meaning H was 1), then I had to be 8 or 9, which then meant O had to be 0. But O couldn’t have been 0, since that meant it would have had the same value as L. In the end — after a lot of careful casework — you found that the only ordered pairs (L, H) with corresponding solutions were (5, 6) and (7, 8).
Here was the solution when (L, H) was (5, 6):
And here was the solution when (L, H) was (7, 8):
I hope this riddle kept you in puzzling shape over the holidays!
Solution to last week’s Riddler Classic
Congratulations to 👏 John Massman 👏 of Seattle, Washington, winner of the last Riddler Classic.
Last week’s Classic was an extension of the tax collector game, which was relayed to me by Fawn Nguyen. The game consisted of paychecks with different whole number dollar amounts, 1 to N. You chose different checks, one at a time. For any check you chose, the tax collector immediately took any remaining checks (i.e., not already taken by you or the tax collector) whose dollar values were factors of the one you chose. For example, if you chose the $10 check, then the tax collector would immediately take the $1, $2 and $5 checks — if any of them was available. Importantly, the tax collector had to get something for each paycheck you chose. So if the $10 check was available, but the $1, $2 and $5 checks were not, then you could not take the $10 check. When there were no more checks you could take, the game was over and all remaining checks went to the tax collector.
In the original version of the puzzle, your goal was to make more money than the tax collector when N was 12 (or 24 or 48). When N was 12, you could make $50 to the tax collector’s $28, meaning you won about 64 percent of the total. When N was 24, you could win about 61 percent of the total, and when N was 48, you could win about 62 percent.
For this puzzle, not only did you want to get more money than the tax collector, you also wanted to win the biggest possible fraction of the available money. Which value of N (greater than 1) would you have chosen, so that you could win the greatest fraction of available money?
Finding an optimal strategy for a given N (without the aid of a computer) was, well, hard. Most solvers realized your first move should always be to take the largest prime, because the tax collector would always take the $1 check away on your first move, and then you would never have the opportunity to get another prime.
But before we dive any further into the strategy of the game, let’s take a step back and try to find an upper bound. In other words, how close to 100 percent could you hope to get? Remember, the tax collector had to take at least one check for every check you took, meaning they got at least half the checks. So even if you took all the checks from the “top half” (i.e., from ⌈N/2⌉+1 to N), you could never exceed 75 percent of the total value. So then, how close to 75 percent could you get?
Solvers Nelson Daou and Jason Shaw next checked small values of N. When N was 2, you took $2 and left the tax collector with $1, meaning you got about 67 percent of the total. Not bad. But you could do even better when N was 6. Your first move was to take the largest prime, $5, while the tax collector took $1. Next, you had to decide between the $4 and $6 checks. If you took the $6 check, the game would end, and you’d have $11 out of a total of $21, or about 52.4 percent. But if you had taken the $4 check, the tax collector took the $2 check, leaving you to take the $6 check on your final turn. In the end, you earned $15, or about 71.4 percent. That was awfully close to 75 percent!
The next value of N where you could do even better was 10. Once again, you started by taking the largest prime, $7, while the tax collector took $1. Next, you could take $9, while the tax collector took $3. Then it was time to take $6, while the tax collector got $2. Finally, you could take the $8 and $10 checks in either order, leaving the tax collector with the $4 and $5 checks. Indeed, you got the “top half” of the checks, $6 to $10, for $40 out of a total of $55. That corresponded to 72.7 percent, even closer to the upper bound of 75 percent.
As I mentioned, finding the optimal strategy for a given N was hard. That’s why solvers like Mike Strong turned to their computers, using recursion to exhaustively search across all possible strategies. The chart below shows the greatest share you could win when N was between 2 and 701, courtesy of Brian Chess. The greatest amount of money you could win for each of these values of N also happens to be an OEIS sequence.
Sure enough, the best you could do was 72.7 percent, when N was 10.
I am pleased to report that I received several good arguments as to why this was the optimal solution. As noted by solver Michael Haugh, for larger values of N, there was an increasing amount of prime numbers in the “top half” of checks that the tax collector would always win. Solver Emily Boyajian took a closer look, finding that the density of primes was sufficiently low for generating a result better than 72.7 percent when N was in the billions.
In the end, no one was able to submit a rigorous proof that 72.7 percent was the best you could do. To my knowledge, this remains an open problem. But as Emily concluded, “…if there is another value of N that allows for a greater proportion of winnings, it would take longer than a human lifetime to play the game, and the game would [probably] involve an amount of money greater than the world’s GDP.”
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email Zach Wissner-Gross at [email protected].
[ad_2]
Source link
