Solutions of the Quiz for Doron Zeilberger’s Lecture at Math Leagues Camp, TCNJ, July 23, 2018, 1:30-2:20pm

1. China played Soccer against Japan, and the score was

China: 5; Japan:4 .

How many possible game histories are there?

Sol. of 1:

\binom{5 + 4}{4} = \binom{9}{4} = \frac{9 · 8 · 7 · 6}{4 · 3 · 2 · 1} = 126 .

2. Out of these game-histories , how many were boring? How many exciting ones?

Sol. of 2: Recall that a game is boring if the winning team was always ahead, i.e. there was not even a time when there was a temporary tie, like in the 2018 World Cup Final game between France and Croatia

F CF F F C ,

where after the second goal both teams had one goal. In the lecture we proved that the number of such totally boring games, with score (n + 1, n) is

\frac{1}{2n + 1} \binom{2n + 1}{n} .

In this problem n = 4, so the number of boring histories is

\frac{1}{2 · 4 + 1} \binom{2 · 4 + 1}{4} = \frac{1}{9} \binom{9}{4} = \frac{1}{9} · 126 = 14 .

Hence the number of boring game-histories is 14 and the number of exciting ones is 126−14 = 112.

3. What ‘bad’ walk in the Manhattan lattice from (1, 0) to (5, 4) corresponds to the following walk from (0, 1) to (5, 4) ?

(0, 1) → (0, 2) → (1, 2) → (2, 2) → (3, 2) → (3, 3) → (4, 3) → (5, 3) → (5, 4)

Sol. of 3: We look at the portion until it hits the diagonal (the line y = x) for the first time

(0, 1) → (0, 2) → (1, 2) → (2, 2) ,

and reflect it , by changing (a, b) to (b, a), getting

(1, 0) → (2, 0) → (2, 1) → (2, 2) ,

After that first encounter, we just keep it, as is, getting

(1, 0) → (2, 0) → (2, 1) → (2, 2) → (3, 2) → (3, 3) → (4, 3) → (5, 3) → (5, 4) .

4. What is the unique cyclic shift in the following game history between team A and team B, where team A scored 7 goals and team B scored 6 goals, that is boring.

AABBBABABAAAB ,

Sol. of 4: After every goal, we write the difference between the number of As and the number of Bs (possibly a negative integer)

A(1)A(2)B(1)B(0)B(−1)A(0)B(−1)A(0)B(−1)A(0)A(1)A(2)B(1) ,

(note that it must always end at 1, since there 7 As and 6 Bs). The lowest difference is −1, but it shows up three times, so we look at the last time it showed up, so the unique boring cyclic shift must start with AAAB followed by the part that came in front of it.

The answer is

AAABAABBBABAB .

5. In a circular track, there are stations where the amount of gasoline (in km) is indicated in boldface, and the distances between them are written in italic.

1 3 4 4 3 3 2 6 10 4 ,

where would you start so that you will never run out of gas?

Sol. of 5: We first do a dry run, allowing for negative amount of gasoline in our gas tank.

At the start, the first station, we have gasoline for 1 km.

after traveling 3 km, right before the second station, we have −2 km of gasoline.

We add 4 km of gasoline, so now our gas tank has enough for −2 + 4 = 2 km.

We travel 4 km to the third station, and right before the third station, we have 2 − 4 = −2 km of gasoline.

At the third station we add 3 km of gasoline, yielding −2 + 3 = 1 km of gasoline. We travel 3 km to the fourth station, leaving us 1 − 3 = −2 km of gasoline. At the fourth station, we add the available 2 km of gasoline, leaving us −2 + 2 = 0 km of gasoline in our gas tank. We travel 6 km to the fifth station, leaving us 0 − 6 = −6 km of gasoline. At the fifth station, we add the available 10 km of gasoline, leaving us −6 + 10 = 4 km of gasoline. The distance between the fifth station to the starting point is 4 km, so we arrive safely with an empty gas tank. But in real life, you can’t have a negative amount of gasoline, so in order to be able to drive this track, we start at the station where, right before it, we had the lowest amount, in this problem it is the fifth (last) station. So the answer is: Start at the fifth station (where the amount of gasoline is 10). Now the track is

10 4 1 3 4 4 3 3 2 6

and you will never have a negative amount in your gas tank.