Ernie and the Chance to Save a Beautiful Relationship

Question

I should have smelt a rat when Ernie invited me to an event at the local club rooms, because when I asked why his wife was not attending, he replied that she had another engagement for that night. “I can’t understand how that happened”, he mused, “because she has known about it for ages”. His promise of a 4-course meal, exciting speakers, pub games, and an open bar convinced me to attend. But when I saw the sign over the door, reading “Annual Number Theorists Reunion Party”, I realized that the evening might not be quite what I had envisaged.

The invitees (twelve mathematicians, each with a non-mathematical guest), sat at four tables (three mathematicians and three guests at each). My assigned seat had Ernie to my left and a charming woman named Beryl to my right. In front of each table setting was a card with a number printed on it. The Chairman, replete with belly, beard, and boater, welcomed us to the event and invited each of us to introduce ourselves and say something interesting about our assigned number. That distinguished the mathematicians from their guests. The former group waxed lyrical about their numbers - “It’s the 1st Keith number, 3rd Square Pyramidal number, 4th Catalan number, and 30th prime gap number…”, while the guests would pause awkwardly and then murmur something irrelevant such as – “It’s the street number of my Granny’s house”.

I offered Beryl a wine [she had beautiful mauve eyes] and the evening’s entertainment began. First course (prawn cocktail), followed by the first talk “A generalization of Cramer’s Conjecture to… blah, blah, blah”. Beryl and I discovered that, as long as we spoke quietly, we could chat without interrupting the speakers [we had interests in common: Thai food, competitive unicycling, Iranian movies]. Second course (soup), more wine and “The phylogeny of abacuses in ancient… blah, blah, blah” [she had a wicked sense of humor and an infectious laugh]. Third course (steak), more wine and “Computability, Undecidability, and… blah, blah, blah” [she was currently unattached and would like to meet up with me again!!!].

Finally, after dessert (and wine), the Chairman rose to tell us it was game time [we also both loved pub quizzes]. But Beryl and I were disappointed when he explained how the game worked:

1. Each of you has a unique Natural number, in the range 1-24, on your card.
2. In each round I will announce a random four-digit Natural number and you need to match it using your table’s numbers, plus some elementary mathematical operations.
3. In each round you must use each of your table’s numbers exactly once.
4. The only operations allowed are addition, subtraction, multiplication, and division. But you may use any of them as many times as you require.
5. Any intermediate result, at any stage in your calculation, must be a Natural number.
6. In each round, your table scores one point if you find a solution.
7. First table to exceed the score of any other table (at the end of a round) wins the gold cup.
8. All the usual Number Theorist Games Club rules apply.

I asked Ernie what rule 8) meant and he explained it just meant no use of calculators, slide-rules, or even pen and paper. “Each problem has to be solved entirely in your head”, he emphasized. “So, a game of skill?”, I asked Ernie. But he scoffed and told me that it was purely a game of chance. “I can guarantee any of the mathematicians here will find a solution if one exists.”. He then pointed at table North and explained that, of the twenty-four possible numbers, they had the six numbers with solutions for the most possible 4-digit goals. He then motioned to table West and told me that that, of the remaining eighteen numbers, they had the next best six. Then he waved at table East and said that they had the best of the remaining twelve numbers. “Unless lightning strikes one of the other tables, we can’t possibly win”.

The Chairman’s first target was 1944. One by one, each table (including ours) called out a solution. But I noticed one of the guests at table East had been tapping on their smart-phone – using a calculator app. The Chairman had apparently noticed too, as he announced, “One point for each of tables North, South, and West – East forfeits their point for using a mechanical aid.” I though that was a bit harsh, but Ernie told me that it was the responsibility of the mathematicians at the table to explain rule 8) to their guests and then added “Curiously enough" he murmured, "we now do have a chance of winning - although only a very small one”. But despite Ernie’s pessimism, after two more rounds our table was announced the winner and the large gold cup was filled to the brim with champagne and presented to table South.

This is where things get a bit hazy: I can clearly recollect Beryl asking me to call her later in the week, copying her phone number onto my phone, and mentioning that by an extraordinary coincidence as she did so, that her phone number was exactly equal to the concatenation of the four digit targets for the second and third rounds; I can vaguely recall us all sharing large gulps of champagne as the cup was passed around the table, and dropping my phone into it while attempting to take a photograph of the winning team; but I have no recollection of how I got home at the end of the evening.

Now here is my problem. My phone didn’t survive immersion in half a cup of champagne and, although I have wracked my brain, I can’t remember Beryl’s phone number, or the second and third target numbers. I am desperate to contact her but without her phone number what can I do? I would try asking Ernie, but he left town while I was sleeping things off and is currently uncontactable. Is there any information in the story that might help me recover Beryl's phone number?

Answer 1

First, we look at how many target numbers are reachable from each of the 134,596 possible starting sets. Each target number is formed from an expression with six terms. There are lots of different ways to combine six terms into an expression, but we can simplify things by looking only at the outermost operator. Here is an example expression:

$$ (1 + 2) + ((3 + 4) + (5 + 6)) $$

In this case the outermost operator is the second +, which combines a two-term expression (1 + 2) and a four-term expression ((3 + 4) + (5 + 6)).

To determine the possible values of the whole expression, it is enough to consider all the ways to split the starting values between the left- and right-hand sides, and the resulting combinations of the possible values of the left- and right-hand side expressions. Writing this in mathematical notation:

$$ \mathrm{possibleValues}(S) = \bigcup_{\substack{A\subset S \\ B = S \setminus A}}\left(\bigcup_{\substack{a\in\mathrm{possibleValues}(A)\\b\in\mathrm{possibleValues}(B)}}\{a+b,a-b,ab,a/b\}\cap\mathbb{N}\right) $$

This is a recursive function, whose base case is:

$$ \mathrm{possibleValues}(\{a\}) = \{a\} $$

I constructed this function as a series of maps, one for each size of input set, so that the construction of each map can re-use the values of the previous maps.

Finally, we take the last map and take the intersection with the range of four-digit numbers (1000 to 9999, inclusive), and sort by the number of reachable target numbers. The element in this map with the most reachable targets is the set of starting numbers for North. We then remove all elements that share any starting numbers with this set. The best element in the resulting map is West's numbers. This process is repeated until the map is exhausted, giving us the following four sets:

North's numbers:

11, 14, 15, 17, 20, 24 (6672 reachable targets)

West's numbers:

12, 13, 16, 19, 22, 23 (6636 reachable targets)

East's numbers:

5, 7, 8, 10, 18, 21 (4958 reachable targets); replacing the 7 with a 9 also yields 4958 targets, but that set cannot form 1944.

South's numbers:

1, 2, 3, 4, 6, 9 (65 goals)

Ernie is right when he says "Unless lightning strikes one of the other tables, we can't possibly win:"

The set of reachable targets for East is a superset of the reachable targets for South, so South can never gain any points over East.

Fun fact, it doesn't matter whether:

you define the natural numbers to include zero, the resulting reachable sets are the same.

---

Then, we look at which numbers are in South's reachable set, but not in North or West's reachable set. This lets us determine the second and third targets:

1314, which cannot be formed from North's numbers; and 1293, which cannot be formed from West's numbers.