It took me longer than I thought, and the outcome is slightly disappointing: I failed to solve two of the problems, and I solved the remaining ones way too slowly, so in a real exam conditions I probably would have solved just one or two…
Exam Problems
4 Pegs Tower of Hanoi
First, it helps to see that the indices of the recurrence are actually $S_n$:
And of course, $S_n = S_{n-1} + n$.
Setting $m=S_{n-1}$, we try to show:
Now, obviously, if we have $m+n$ discs, we can move the $m$ top ones from $A$ to $C$ using $B$ and $D$ as transfer pegs, then move the bottom $n$ ones from $A$ to $B$ using $D$ as transfer peg, and finally move the top $m$ ones from $C$ to $B$.
The first step takes $W_m$ moves, the second one is the classic Tower of Hanoi problem (as we can no longer use peg $C$, we only have three pegs), so it takes $T_n$ moves, and the last step takes $W_m$ moves again.
This is only one possible solution; the optimal one must be equal or better, so we have
This is true for any $m+n$ discs, and in particular for $S_n = S_{n-1} + n$ ones.
Specific Zigs
I could not solve this problem. I had found that the half-lines did intersect, but then I failed to show that their intersections were all distinct.
Even with the solution from the book, it took me a while before I finally had a complete understanding.
One problem I had was that lines in a graph are basic college level mathematics, but college was a long, long time ago. I pretty much had to work from first principles.
Following the book in writing the positions as $(x_j, 0)$ and $(x_j - a_j, 1)$, I need to find $\alpha$ and $\beta$ such that $y=\alpha x + \beta$ is true for both points above.
With this given, I can try to find the intersection of lines from different zigs, $j$ and $k$:
Now, still following the book, I replace $x$ by $t$ with $x=x_j - t a_j$:
Somehow, I have a faint memory of such a result; I need to check a college math book.
To complete, I need to show that $y = t$:
So the intersection of any two pair of half-lines from different zigs is $(x_j - t a_j, t)$. Note that $t$ has the same value whether $j \gt k$ or $k \gt j$. To simplify further computations, I set $j \gt k$.
There are two remaining steps: show that $t$ is different for different pairs of $j$, $k$ (with $j \ne k$); and then show that the four intersections for a pair $j$, $k$ are also distinct.
$a_j$ can be of two forms: $n^j$ and $n^j + n^{-n}$. So $a_j - a_k$ can be one of
So there are three different forms for $a_j - a_k$, which I will simply write $n^j - n^k + \epsilon$ where $|\epsilon| \lt 1$.
Let’s show that $n^j+n^k - 1 \lt t \lt n^j+n^k + 1$: multiply the whole inequality by $n^j - n^k + \epsilon$. As
so $n^j - n^k + \epsilon \gt 0$. Defining
the left and right inequalities become
Subtracting $N_{jk}N'_{jk} = (n^j-n^k)(n^j+n^k)$ from the original inequality:
I need to prove the following inequality
We already know $|\epsilon| \lt 1$, so looking at the second term (and assuming $\epsilon \ne 0$, as this case is trivial)
and we have
So the inequalities are established. $N_{jk}$ can be seen as a number in based $n$ where the digits are all zeroes except the $j$ and $k$ ones, $N_{jk} = N_{j'k'} \implies j=j', k=k'$, and therefore $t$ uniquely defines $j$ and $k$ or, two pairs of zigs must have different $t$.
I still need to show that for a given pair, when $t$ is the same, the intersections are different. There are three different values of $t$, so two intersections points have the same height. This happens for
which happens when $a_j = n^j$, $a_k = n^k$ and $a_j = n^j + n^{-n}$, $a_k = n^k + n^{-n}$. But the $x = x_j - t a_j$ value for intersections is different: $t n^j$ and $t (n^j + n^{-n})$, so there are indeed four distinct intersection points.
30 degrees Zigs
I could not solve this problem. Once again, my lack of intuition with geometry was to blame.
But if we have two zigs with half-lines angles $\phi$, $\phi + 30^{\circ}$ and $\theta$, $\theta + 30^{\circ}$, then for any two pairs of half-lines from the two zigs to intersect, their angles must be between $0^{\circ}$ and $180^{\circ}$. Taken together, these constraints give $30^{\circ} \lt |\phi - \theta| \lt 150^{\circ}$.
Update: The original version of this post had a lower bound of $0$. Thanks to Tailshot for pointing out the error
This means there cannot be more than $5$ such pairs (and to be honest, I would have said 4, but the book says it’s indeed 5).
Recurrence Equations
Using the repertoire method, solve the recurrence equations
The general form of $h(n)$ is
We get three of these functions directly by solving
So we have a solution for $A(n)$, $B_0(n)$ and $B_1(n)$.
Setting $h(n) = n$
which gives the equation $n = A(n) + B_1(n) -2(C_0(n) + C_1(n))$.
Setting $h(n) = n^2$
which gives the equation $n^2 = A(n) + B_1(n) + 4C_1(n)$
The latest gives us $C_1(n) = (n^2 - A(n) - B_1(n))/4$. To solve for $C_0$, one can either replace the value of $C_1$ in the equation for $h(n) = n$ above, or, equivalently, add twice that equation to the one for $h(n) = n^2$, which eliminates $C_1(n)$:
Good and Bad Persons in Josephus Problem
It took me a while, as I was trying to find a recurrence equation of some sort which would help me with this problem and the bonus one (where Josephus’ position is fixed but he can pick $m$). Eventually I found one, which did not help me with the bonus problem, but led me to a solution for this problem.
Obviously, if we have $k$ persons and want to remove the last one in the first round, we can choose $m=k$ and that will work. Actually, any multiple $m=ak$ works as well.
This shows that at each round, if we have $k$ persons left, and we start counting on the first one, when $m=ak$ we will remove the $k^{th}$ person then start counting from the first one again.
Back to the original problem: there are $2n$ persons, and we want to get rid of the $n+1, \cdots, 2n$ first. If we take $m=lcm(n+1,\cdots, 2n)$, then for the first $n$ rounds the last (bad) person will be remove, leaving only the good ones at the end.
When first solving the problem, I picked $m=\prod_{i=1}^n (n+i)$, which has the same property as the least common multiple, but is larger. Perhaps a smaller number is better for the nerves of the participants.
Bonus Problems
I tried to solve the bonus questions, but after repeatedly failing, I had a glimpse at the solutions: they obviously require either knowledge of later chapters, or other concepts I know nothing about, so I will get back to these bonus problems after I finish the book.
I am now working through Chapter 2. It is a much larger chapter than the first, so it will take me some time.