%MathLeagueQuizSol.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf  Solutions of the Quiz  for Doron Zeilberger's Lecture at Math Leagues Camp, 
}
\centerline
{\bf TCNJ, July 23, 2018, 1:30-2:20pm}
\bigskip



{\bf 1.} China played Soccer against Japan, and the score was 

China: 5; \quad Japan:4 \quad . 

How many possible game histories are there?

\bigskip
{\bf Sol. of 1}:
$$
{{5+4} \choose {4}} \, = \, {{9} \choose {4}} \, =  \, \frac{ 9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1}\,= \, 126 \quad .
$$


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

\bigskip
{\bf Sol. of 2}: Recall that a game is boring if the winning team was always {\bf 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
$$
FCFFFC \quad,
$$
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} \, {{2n+1} \choose {n}} \quad .
$$
In this problem $n=4$, so the number of boring histories is
$$
\frac{1}{2\cdot 4+1} \, {{2 \cdot 4 +1 } \choose {4}} \, = \,
\frac{1}{9} \, {{9 } \choose {4}} \, = \, \frac{1}{9} \cdot 126 \, =  \, 14 \quad.
$$
Hence the number of {\bf boring} game-histories is $14$ and the number of exciting ones is $126-14=112$.

{\bf 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) \rightarrow (0,2) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (4,3) \rightarrow (5,3) \rightarrow (5,4)
$$

\bigskip

{\bf Sol. of 3:} We look at the portion until it hits the diagonal (the line $y=x$) for the {\bf first} time
$$
(0,1) \rightarrow (0,2) \rightarrow (1,2) \rightarrow (2,2)  \quad,
$$
and reflect it , by changing $(a,b)$ to $(b,a)$, getting
$$
(1,0) \rightarrow (2,0) \rightarrow (2,1) \rightarrow (2,2)  \quad,
$$
After that first encounter, we just keep it, as is, getting
$$
(1,0) \rightarrow (2,0) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (4,3) \rightarrow (5,3) \rightarrow (5,4) \quad .
$$



{\bf 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.

$$
A A B B B A B A B A A A B \quad ,
$$
\bigskip

{\bf Sol. of 4}: After every goal, we write the {\bf 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) \quad ,
$$
(note that it must always end at $1$, since there $7$ As and $6$ Bs). The {\bf lowest} difference is $-1$, but it shows up {\bf three} times,
so we look at the {\bf 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
$$
 A A A B A A B B B A B A B \quad .
$$


{\bf 5.} In a circular track, there are stations where the amount of gasoline (in km) is indicated in {\bf boldface},
and the distances between them are written in {\it italic}.
$$
{\bf 1} \quad {\it 3} \quad {\bf 4} \quad {\it 4} \quad {\bf 3} \quad {\it 3} \quad {\bf 2} \quad {\it 6}  \quad {\bf 10} \quad {\it 4}  \quad ,
$$
where would you start so that you will never run out of gas?

\bigskip
{\bf Sol. of 5}: We first do a {\bf 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.

{\bf But} in real life, you can't have a negative amount of gasoline, so in order to be able to drive
this track, we {\bf start} at the station where, right before it, we had the {\bf 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
$$
{\bf 10} \quad {\it 4}  \quad {\bf 1} \quad {\it 3} \quad {\bf 4} \quad {\it 4} \quad {\bf 3} \quad {\it 3} \quad {\bf 2} \quad {\it 6}  \quad  \,
$$
and you will never have a negative amount in your gas tank.

\end








