Can You Fend Off The Alien Armada?
Illustration by Guillaume Kurkdjian
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,1 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 or send me an email.
Note: There will be no column on Jan. 13. The next column will appear on Jan. 20.
Riddler Express
From Richard Jacobson comes a matter of bewildering basketball:
You and a friend are shooting some hoops at your local basketball court when she issues a challenge: She will name a number, which we’ll call N. Your goal is to score exactly N points in as many ways as possible using only 2-point and 3-point shots. The order of your shots does not matter.
For example, there are two ways you could score N = 8 points: four 2-pointers or two 3-pointers and one 2-pointer.
Your apparently sadistic friend chooses 60 for the value of N. You try to negotiate this number down, but to no avail. However, she says you are welcome to pick an even larger value of N. Does there exist an integer N greater than 60 such that there are fewer ways to score N points than there are ways to score 60 points?
Riddler Classic
From James Anderson comes a puzzle to stave off galactic disaster:
The astronomers of Planet Xiddler are back in action! Unfortunately, this time they have used their telescopes to spot an armada of hostile alien warships on a direct course for Xiddler. The armada will be arriving in exactly 100 days. (Recall that, like Earth, there are 24 hours in a Xiddler day.)
Fortunately, Xiddler’s engineers have just completed construction of the planet’s first assembler, which is capable of producing any object. An assembler can be used to build a space fighter to defend the planet, which takes one hour to produce. An assembler can also be used to build another assembler (which, in turn, can build other space fighters or assemblers). However, building an assembler is more time-consuming, requiring six whole days. Also, you cannot use multiple assemblers to build one space fighter or assembler in a shorter period of time.
What is the greatest number of space fighters the Xiddlerian fleet can have when the alien armada arrives?
Solution to the last Riddler Express
Congratulations to ÑбâÑб÷âбâбâ¤Ðбâ Paul Menchini ÑбâÑб÷âбâбâ¤Ðбâ of Hillsborough, North Carolina, winner of the last Riddler Express.
Last week, you had to make it to 2023. And if you’re reading this right now, that means you made it! More specifically, you had to make it to 2023 using a “tribonacci” sequence, which starts with three whole numbers, with each new term equal to the sum of the preceding three.
Of course, many tribonacci sequences included the number 2023. For example, if you had started with 23, 1000 and 1000, then the very next term would have been 2023. Your challenge was to find starting whole numbers a, b and c (with a ≤ b ≤ c) so that 2023 was somewhere in their tribonacci sequence and the sum a + b + c was as small as possible.
A few solvers tried out various values of a, b and c — some with computer assistance, like Ria Skies and Ryan McShane. But there was a way to solve this puzzle with a lot less guesswork, as with a similar puzzle from about a year ago that was about Fibonacci, rather than tribonacci, sequences.
No matter your two starting values, every Fibonacci sequence eventually converged to the same ratio between consecutive terms. Without proving this fact, a quick and dirty way to solve for this ratio was to assume that three consecutive numbers in the sequence had a common ratio, so we could call them x, ax and a2x. Since they were in a Fibonacci sequence, that meant x + ax = a2x. Dividing through by x and rearranging produced the quadratic equation a2 − a − 1 = 0, which had a positive solution of (1+√5)/2, the golden ratio.
The same sort of pattern emerged for tribonacci numbers, no matter which three numbers you started with. This time, the common ratio was the solution to the cubic equation a3 − a2 − a − 1 = 0, which had one real solution of approximately 1.8393.
At this point, let’s take a step back and return to the actual puzzle. You wanted a, b and c to be small, which meant you effectively wanted 2023 to show up as late as possible in the sequence. By that point, the ratios between consecutive terms should have converged somewhat. That meant the term prior to 2023 should have been close to 2023/1.8393, or about 1100. And the term before that should have been close to 1100/1.8393, or about 598.
From there, you could find each prior term in the sequence by taking a given term and subtracting the two preceding terms. Working backwards, the resulting sequence was 2023, 1100, 598, 325, 177, 96, 52, 29, 15, 8, 6, 1 and 1. It might have been tempting to go a step further (and generate another term, 4), but the requirement of a ≤ b ≤ c meant you had to stop there. In the end, this sequence had the minimum initial sum: a = 1, b = 1 and c = 6.
In case you’re looking ahead to next year, solver Darren L. of Grand Blanc, Michigan, found the smallest starting triplet for 2024 as well: a = 3, b = 4 and c = 20. But let’s not get ahead of ourselves.
Solution to the last Riddler Classic
Congratulations to ÑбâÑб÷âбâбâ¤Ðбâ Dan Potterton ÑбâÑб÷âбâбâ¤Ðбâ of Atlanta, winner of the last Riddler Classic.
This past Christmas, puzzle submitter Gary Yane and his family had a pairwise gift exchange. So if cousin Virginia gave uncle Justin a gift, then Justin gave Virginia a gift.
There were 20 people in the gift exchange. In the first round, everyone wrote down the name of a random person (other than themselves) and the names went in a hat. Then if two people randomly picked each other’s names out of that hat, they exchanged gifts and no longer participated in the drawing. The remaining family members went on to round two. Again, they wrote down the name of anyone left, and again, any two people who picked each other exchanged gifts.
This continued until everyone was paired up. And yes, if exactly two people remained, they still went through the process of selecting each other, even though they knew who their partner would ultimately be.
On average, what was the expected number of rounds until everyone was paired up?
First, as pointed out by several readers, this was admittedly a rather inefficient way to run a puzzle exchange. Instead, the 20 people should each have simply placed their own names into the hat, guaranteeing that every name was in there exactly once. With the convoluted way Gary’s family ran the exchange, it was quite likely that there were duplicate names as well as missing names in the hat. But I digress.
Second, the puzzle was ambiguous as to whether the family members picked names from the hat with replacement (i.e., once a name was selected it was placed back in the hat) or without replacement (i.e., once a name was selected it was not placed back in the hat). As is typical with gift exchanges, my own interpretation of the puzzle was to assume no replacement. But in the end, I accepted solutions that made either assumption.
Let’s return to the puzzle. Before taking on the case with 20 people, suppose there were just two (again, let’s call them Virginia and Justin). What was the probability that they paired up in a single round? That required whoever picked first — say, Virginia — to pick out Justin’s name rather than her own, which happened half the time. Then, since we assume no replacement, Justin picked Virginia’s name. The other half the time they each picked their own name. So with two people, there was a 50 percent chance they paired up in one round, a 25 percent chance they paired up in two rounds, a 12.5 percent chance they paired up in three rounds and so on. To find the expected number of rounds, you had to evaluate the arithmetico-geometric series 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + …, which had a sum of 2.
(With replacement, instead of picking each other’s names half the time, they only did this a quarter of time. This meant it took an average of four rounds to pair up. Based on this, it was apparent that replacement resulted in a greater expected number of rounds with 20 participants.)
Of course, that was just with two people. With four people in the exchange, things immediately got a lot more complicated. Each person now had three names to choose from when writing one down, resulting in 81 cases to consider. But in theory, it was possible to compute the transition probabilities that four people would result in no pairs (leaving all four people to play another round), one pair (leaving two people to play the next round) or two pairs (meaning the exchange was complete).
At this point, several readers got sidetracked by an article that referenced a game called “Look Up and Scream.” This game was similar to Gary’s gift exchange, with people arranged in a circle and pointing to each other at the same time. However, one key difference was that in the gift exchange, it was possible for you to pick your own name from the hat (i.e., if someone else wrote it down) — something that wasn’t possible in “Look Up and Scream.” So while “Look Up and Scream” lasted an average of about 17.16 rounds when starting with 20 people, Gary’s gift exchange lasted a little longer.
Through simulation, solver David Ding found that it took an average of about 22.1 rounds when there was no replacement and an average of about 26.7 rounds when there was no replacement. Here are the distributions for the number of rounds that David found in both cases:
By the way, if everyone had simply placed their own name in the hat (as several readers suggested) and then picked without replacement, the exchange would have been more efficient, lasting an average of about 20 rounds. And with replacement in this case, it would have lasted an average of about 24.2 rounds.
Want more puzzles?
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 riddlercolumn@gmail.com.
