A standard observation is that when two performers meet and both reverse direction, this is equivalent to them simply passing each other without changing direction. In this model, a meeting occurs for a pair of performers if initially the one on the left walks to the right, and the one on the right walks to the left. Such a pair meets exactly once. Therefore, the total number of meetings is the number of such opposite-facing pairs.

To maximize this, place all right-moving performers to the left of all left-moving performers. If $k$ performers walk right and $25-k$ walk left, then the number of meetings is $k(25-k)=-k^2+25k$. Viewed as an $\mathbb R \to \mathbb R$ function, its graph is a downwards facing parabola with the tip positioned halfway between the two roots, at $k=12.5$, this is where $-k^2+25k$ is maximal. Restricting to $k \in \mathbb Z$, $k(25-k)$ is maximized when $k$ is as close as possible to $12.5$, i.e. $k=12$ or $k=13$, and both values give the number of meetings $12\cdot 13=156.$

At each meeting, both performers turn once, so each meeting contributes $2$ turns. Thus the maximum total number of turns is $2\cdot 156 = 312.$

Solution: 312.

First, consider what happens if we roll the die without moving the vertex aligned with the center of the table. Since the angles adjacent to this vertex add up to 180, the tetrahedron will roll over exactly twice and return to the same position. More precisely, if the faces of the die adjacent to the vertex at the enter are denoted $a,b,c$ (read clockwise), then as the die rolls around, these faces touch the table in six triangles forming a regular hexagon, reading $a,b,c,a,b,c$ anti-clockwise around the centre:

Whenever we roll the die over once on the table, one vertex (in fact, even two) is always fixed. So we can use the same principle to trace the position of the red face on the table as it rolls around (depicted below). In particular, the faces of the tetrahedron trace a grid of regular triangles, and if we track the position of the vertex which was centered (marked grey in the picture), these form the vertices of a larger triangular grid of side length 2. The red face of the triangle is the one opposite this vertex, so the triangles of the (smaller) grid that get stained red are exactly the ones not touching any marked vertices. Thus each face of the larger triangular grid contains exactly one red patch.

We need to count how many red patches we see inside a circle of radius 10 (marked green in the picture), centered at a vertex of the larger grid. The circle contains a regular hexagon of radius 10 aligned with the triangular grid (marked blue in the picture). We divide this hexagon into six identical regular triangles of side length 10, and count the number of red patches in each of these by counting the number of faces of the larger grid that fall inside the triangle. This is simply the number of regular triangles of side length 2 that tile a regular triangle of side length 10, given by the fifth $(5=10/2)$ triangular number $1+3+5+7+9=25$, so there are $6 \cdot 25$ red patches inside the hexagon.

What remains is to count how many red triangles we see inside the circle outside the hexagon. Again, by symmetry, we can focus on a single segment of the circle determined by two adjacent vertices of the radius 10 hexagon ($A,B$ in the picture below), and multiply by $6$. If one draws a sufficiently precise picture (note that the entire grid is constructable with a compass and a straight edge), the red triangles in the segment can be counted by looking: there are $3$ per segment, which makes the overall number of red triangles $6 \cdot (25+3)=168$.

We algebraically verify that the picture is accurate, i.e. the vertices of the grid that fall into the segment are exactly those depicted. Let us view the grid on the coordinate plane, where the $x$ axis contains two vertices of the radius 10 hexagon. Consider the vectors $\vec a=(-1/2, \sqrt 3/2),$ $\vec b=(0,1)$. These then line up with the (smaller) triangular grid (marked green in the picture above). Notice that every vertex of the grid can be obtained as $n \vec a + m \vec b$ for some integers $m,n$. This point falls within our circle if its distance from the origin is at most $10$. The square of the distance is $$\left|n \vec a + m \vec b\right|^2=\left|\left(m-\frac{n}{2}, \frac{\sqrt 3 n}{2}\right)\right|^2=\left(m-\frac{n}{2}\right)^2+\left(\frac{\sqrt 3 n}{2}\right)^2$$ which can be simplified to $m^2-mn+n^2$. This should be at most $10^2=100$.

Let us find the vertices of the grid in the segment of the circle determined by the vertices $A=10\vec a$ and $B=10(\vec a+\vec b)$ of the hexagon (pictured above). A point $n \vec a + m \vec b$ falls into the segment between the lines of the vectors $\vec a$ and $\vec a+\vec b$ whenever $n > m > 0$, and such a point falls outside the triangle formed by the origin, $A$ and $B$ if furthermore $n>10$. Thus we need to determine all integers $m,n$ with the properties: $$m^2-mn+n^2 \leq 100,\ 0 < m < n,\ 10 < n.$$ Solving the equality $m^2-mn+n^2-100=0$ for $m$, we obtain that the discriminant $n^2-4(n^2-100)$ is nonnegative exactly if $400 \geq 3n^2$. In particular, if $400 < 3n^2$, that is, if $12 \leq n$, then $m^2-mn+n^2-100$ is always positive, hence $m^2-mn+n^2 \leq 100$ is never satisfied.

Thus we only need to check what happens when $n=11$. In this case the inequality becomes $m^2-11n+21 \leq 0$. Solving for $m$, we obtain $$\frac{11-\sqrt{37}}{2}\leq m \leq \frac{11+\sqrt{37}}{2},$$ so the possible integer values for $m$ are $3, \ldots, 8$ (and these also satisfy $m < n$). The points of the triangular grid which are in the circle segment, but outside the hexagon, are thus $11\vec a+3 \vec b, \ldots, 11\vec a+8 \vec b$, which matches our picture.

Solution: 168.

Let $n$ be such that $20$ divides $\sigma(n)$ and $26$ divides $\sigma(n+1)$. First, observe that, if the last $k$ digits of $n$ are $9$ (and the $(k+1)$-to-last is not a $9$, if it exists), then $n+1$ will have its last $k$ digits as $0$, with the $(k+1)$-to-last digit being $1$ more than it was before (or $1$, if $n$ only had $k$ digits to begin with). Hence, $$ \sigma(n+1) = \sigma(n) - 9k + 1,$$ Since $20$ and $26$ are both even, we know that $\sigma(n)$ and $\sigma(n+1)$ are also. Therefore, $9k-1 = \sigma(n) - \sigma(n+1)$ is even, meaning $k$ cannot be $0$. As $k>0$, and by considering the numbers whose digits are all $9$, $$\sigma(n+1)+8\leq\sigma(n)\leq 9d$$ where $d$ is the number of digits of $n$.

We are looking for the least $n$, so we require $d$ to be as small as possible. If $d\leq 7$, then $\sigma(n+1)<\sigma(n)\leq 63$. The positive multiples of $20$ up to $63$ are $20$, $40$, and $60$. The positive multiples of $23$ up to $63$ are $26$ and $52$. However, since $\sigma(n)$ must be at least $8$ more than $\sigma(n+1)$, the only pairs of multiples possible for $\sigma(n)$ and $\sigma(n+1)$ are $(26,40)$, $(26,60)$, and $(52,60)$.

Checking each of these in our equation $9k=\sigma(n)-\sigma(n+1)+1$, we see that $40-26+1=15$ and $60-26+1=35$ are not possible, since $15$ and $35$ are not multiples of $9$.

However, $60-52+1=9$, so if there is a solution having up to $7$ digits, then it must be one such that $\sigma(n)=60$, $\sigma(n+1)=52$, and $k=1$. Since $60>54$, we know that $d>6$, so there cannot be a solution with $6$ or fewer digits. The smallest number with exactly one $9$ at the end whose digit sum is $60$ is $7999989$. This works, since $7999989+1 = 7999990$ has digit sum $52$. By construction, this is minimal, so we know that $n=7999989$.

Denote the center of the circle by $A_0$, and the robot's position after $n$ steps by $A_n$ (see picture below). For all $n$, we have $d(A_n, A_{n+1})=1$. Observe furthermore the following:

1. $A_0, A_1, A_2$ fall on the same line and so $d(A_2,A_0)=2$
2. if $d(A_n, A_0)=d \notin \mathbb N$, then $A_0A_nA_{n+1}$ forms a right triangle (with the right angle at $A_n$), and so $d(A_{n+1}, A_0)=\sqrt{d^2+1}$
3. if $d(A_{n-1}, A_0) \notin \mathbb N$ and $d(A_n, A_0)=d \in \mathbb N$, then $A_0, A_n, A_{n+1}$ fall on the same line and $d(A_{n+1}, A_0)=d+1=\sqrt{(d+1)^2}$
4. if $d(A_{n-1}, A_0) \in \mathbb N$ with $n >1$, and $d(A_n, A_0)=d \in \mathbb N$, then again $A_0A_nA_{n+1}$ forms a right triangle (with the right angle at $A_n$), and so $d(A_{n+1}, A_0)=\sqrt{d^2+1}$

Consider the sequence $d_i=d(A_0,A_i)$ for $i \geq 1$. For any $i$, $d_i$ is of the form $\sqrt{n}$ for some positive integer $n$. Most of the times, $d_i$ is not an integer, so we increment it by the rule 2 above as $d_{i+1}=\sqrt{n+1}$. When $d_i$ reaches an integer value $n=\sqrt{n^2}$, then by rule 3 we have $d_{i+1}=n+1=\sqrt{(n+1)^2}$, and from this point onward, we increment as dictated in point 4 and then 2, until we reach the next integer value. In particular, all positive integers occur in the sequence $d_i$, and moreover they always occur in consecutive pairs. From $d_1=1$ and $d_2=2$ we can deduce that the first number of such a consecutive pair is odd, and the second is even. In between an even integer $2k=\sqrt{(2k)^2}$ and the next odd integer $2k=\sqrt{(2k+1)^2},$ $d_i$ takes all values $\sqrt{n}$ for $(2k)^2 < n < (2k+1)^2$.

To find the answer to the question, we need to determine the value $i$ such that $d_i=2026$ (we know that such an $i$ exists, because all positive integers occur in $d_i$), or in other words, how many different values are taken by $d_i$ by the time it reaches $2026$. We can compute this by grouping the sequence $d_i$ into consecutive blocks of $$2k=\sqrt{(2k)^2}, \sqrt{(2k)^2+1}, \sqrt{(2k)^2+2} \ldots, \sqrt{(2k+1)^2}=2k+1,$$ each of which has length $(2k+1)^2-(2k)^2+1=4k+2$, the first block given by $k=0$ and the last (within the circle) by $k=1012$. The first block has the first number missing, but this is compensated by the last block ending one number early, in $2025$.

This gives us $$\sum^{1012}_{k=0} (4k+2)=2\cdot 1013+4 \cdot \sum^{1012}_{k=0} k=2026+2 \cdot 1013\cdot 1012=2052338.$$

Solution: 2052338

Let us find the optimal strategy (i.e. the optimal sequence of $C$s and $D$s played) leading to the highest number of points in expected value.

Claim: An optimal strategy will necessarily have a form $\underbrace{C,\ldots, C}_{m},\underbrace{D,\ldots ,D}_{25-m}$.

We can prove this by contradiction: assume there is an optimal strategy $S$ not of the above form, then it will necessarily have a $D$ followed by a $C$, say in rounds $n$ and $n+1$, so we may write $S= S_0, D, C, S_1$ where $S_0$ and $S_1$ are (possibly empty) sequences of $C$ and $D$s, and the length of $S_0$ is $n-1$. Now consider the strategy $S'=S_0, C, D, S_1$. We claim that this achieves a higher number of points in expected value, contradicting the optimality of $S$. Note that the strategies don't differ until round $n$, so until then they both gather the same number of points. Similarly, they don't differ from round $n+2$ onward, and furthermore they both play the same number of $C$s and $D$s up to round $n+2$, so on average they also gather the same number of points in these rounds. Any difference must come from the scores in rounds $n$ and $n+1$.

First suppose that $n=1$. Then one round 1, the opponent Cooperates or Defects with probability $1/2$, so the Defecting $S$ gets $\frac{5}{2}+\frac{1}{2}=3$ points on average, and the Cooperating $S'$ gets $\frac{3}{2}$. Now in round 2, when playing $S$, the opponent will definitely Defect, and $S$, who Cooperates, gets no points. When playing $S'$ however, the opponent Cooperates and $S'$ gets $5$ points against them. So $S'$ gains an average of 6.5 points versus the 3 points of $S$.

Now assume $n \geq 2$. Let the number of Cooperations in $S_0$ be $k$. Then in round $n$, the opponent plays $C$ with probability $\frac{k}{n-1}$ and $D$ with probability $\frac{n-k-1}{n-1}$. In this round, the expected value of points gained by strategy $S$, which Defects, is $$5\cdot \frac{k}{n-1}+\frac{n-k-1}{n-1},$$ and by strategy $S'$, which Cooperates, is $$3\cdot \frac{k}{n-1}.$$ Now by round $n+1$, strategy $S'$ will have cooperated $k+1$ times, whereas startegy $S$ only $k$ times. So when playing $S$, the opponent will Cooperate with probability $\frac{k}{n}$, but when playing $S'$, it will Cooperate with probability $\frac{k+1}{n}$. In round $n+1$, this gives $S$ (who now Cooperates) the expected value of $$3\cdot \frac{k}{n},$$ whereas $S'$ who Defects gains $$5\cdot \frac{k+1}{n}+\frac{n-k-1}{n}$$ points on average. So over the two rounds, $S$ gets $$P=\frac{5k}{n-1}+\frac{n-k-1}{n-1}+\frac{3k}{n}=1+\frac{4k}{n-1}+\frac{3k}{n}=1+\frac{7kn-3k}{n(n-1)}$$ points on average, and $S'$ gets $$P'=\frac{3k}{n-1}+\frac{5k+5}{n}+\frac{n-k-1}{n}=1+\frac{3k}{n-1}+\frac{4k+4}{n}=1+\frac{7kn+4n-4k-4}{n(n-1)}$$ points on average. So, keeping in mind that $0 \leq k \leq n-1$, we have $$P'-P=\frac{4n-k-4}{n(n-1)}= \frac{4(n-1)-k}{n(n-1)} \geq \frac{3k}{n(n-1)} \geq 0$$ furthermore at least one of the two inequalities is strict since $n-1 \neq 0$, so we obtain $P'-P > 0$, and thus $P' > P$.

This completes the proof of our claim. What therefore remains is comparing the strategies $S_m:=\underbrace{C,\ldots, C}_{m},\underbrace{D,\ldots ,D}_{25-m}$ for different $m$ and determine which of them is optimal.

Let us calculate the expected number of points $P_m$ gained by the strategy $S_m$. If $m=0$, then $S_0$ gets an average of $3$ points in round $1$ and no points afterwards, so $P_0=3$. If $m \geq 1$, then in the first round, $S_m$ gets $1.5$ points on average, followed by $3$ points for the next $m-1$ rounds. On round $n+1$, where $n \geq m$, the average number of points gained is $$\frac{5m}{n}+\frac{n-m}{n}=1+\frac{4m}{n},$$ which makes \begin{align*} P_m &= \frac{3}{2}+3(m-1)+\sum_{n=m}^{24} \left(1+\frac{4m}{n}\right)\\ &= \frac{3}{2}+3(m-1)+(25-m)+4m\sum_{n=m}^{24} \frac{1}{n}\\ &=23.5+2m\left(1+2\sum_{n=m}^{24} \frac{1}{n}\right) \end{align*}

We need to determine which $m$ $P_m$ is maximal for. This can be done by analysing the difference $P_{m+1}-P_{m}$. We have \begin{align*} \frac{P_{m+1}-P_m}{2} &= (m+1)\left(1+2\sum_{n=m+1}^{24} \frac{1}{n}\right)-m\left(1+2\sum_{n=m}^{24} \frac{1}{n}\right)\\ &=\; \not{\!\!m}+1+2m\sum_{n=m+1}^{24} \frac{1}{n}+2\sum_{n=m+1}^{24} \frac{1}{n}-\not{\!\!m}-2m\sum_{n=m}^{24} \frac{1}{n}\\ &=1+2m\sum_{n=m+1}^{24} \frac{1}{n}+2\sum_{n=m+1}^{24}\frac{1}{n}-\frac{2m}{m}-2m\sum_{n=m+1}^{24}\frac{1}{n}\\ &=2\sum_{n=m+1}^{24}\frac{1}{n}-1 \end{align*} If $P_m$ is maximal, then either $m=1$ or $m=25$, or we must have $P_m-P_{m-1} \geq 0$ and $P_{m+1}-P_{m} \leq 0$, which is equivalent to $$\sum_{n=m}^{24}\frac{1}{n} \geq \frac{1}{2},\ \sum_{n=m+1}^{24}\frac{1}{n} \leq \frac{1}{2}.$$ Let $H_m=\sum_{n=m}^{24}\frac{1}{n}$. It is clear that $H_m$ is strictly decreasing, so there can be at most one $m$ with $H_m \geq 1/2$ and $H_{m+1} \leq 1/2$. Clearly $H_1 >1$ and $H_{25}=0$, so such $m$ exists. We can find this value by iteratively computing $H_{25}, H_{24}, ...$ using that $H_{k-1}=H_k+\frac{1}{k-1}$. We obtain $$ H_{16} \approx 0.4577,\ H_{15} \approx 0.5244$$ so we find that $m=15$ has the desired property. In particular, $$H_1 < H_2 < \ldots < H_{15} < \frac12 < H_{16} < \ldots < H_{25}$$ and thus $$P_1 < P_2 < \ldots < P_{15} > \ldots > P_{25}$$ so the best strategy has $15$ Cooperations and $10$ Defections, and the corresponding expected value of points is $P_{15} \approx 84.9638$.

Solution: 84.9638

Let us imagine that there is a guard standing at every floor of every tower. The goal is to find the shortest sequence of instructions which, given to all guards simultaneously, will lead them all to the ground floor of tower one.

Let $(t,l)$ denote the location of tower $t$ on level $l$, so $1 \leq t \leq 17$ and $0 \leq l \leq 20$. The instructions then correspond to the following movements:

$(t,l) \xrightarrow{A} (t+1,l)$, where $17+1$ is identified with $1$.

$(t,l) \xrightarrow{B} \begin{cases} (t,l+1) &\hbox{if } t \neq 17, l\neq 20 \\ (1,l+1) &\hbox{if } t =17, l\neq 20\\ (t,l) &\hbox{if } l=20 \end{cases}$

$(t,l) \xrightarrow{C} \begin{cases} (t,l-1) &\hbox{if } l\neq 0 \\ (t,l) &\hbox{if } l=0 \end{cases}$

We will call a sequence of instructions "synchronizing" if they send all guards to the same position. Note in particular that the solution is a synchronizing sequence (namely one sending everyone to position $(1,0)$), and also a tower synchronizing sequence. Notice that only instructions $A$ and $B$ change towers.

Let us for the moment ignore that the towers have different levels and focus on just the instructions $A$ and $B$. The effect of the moves $A$ and $B$ on the towers $1-17$ are depicted in the diagram below. (For now we disregard the fact that a guard on level $20$ cannot execute $B$.)

We define a sequence of $A$s and $B$s "tower synchronizing" if it sends all guards to the same tower (ignoring the problem about level $20$), i.e. if following the instructions from any node of the graph above leads to the same node.

Let us determine how many steps we need to synchronize the towers -- this is in fact the most difficult part of the question.

Observe the following:

• the sequence $A^{16}$ (which denotes $16$ consecutive $A$s) has the effect of sending everyone "back" one tower, i.e. $17 \to 16 \to 15 \ldots \to 1 \to 17$,
• the sequence $BA^{16}$ sends everyone "back" one tower, except tower $17$ which it fixes, i.e. $16 \to 15 \ldots \to 1 \to 17 \to 17$

In particular, after executing $BA^{16}$, no guard can be in tower $16$. After executing another $BA^{16}$, no guard can be in tower $15$ either because they would have needed to be in tower $16$ after the first execution of $BA^{16}$. Iterating, it is easy to see (by a formal induction) that the instruction $(BA^{16})^{15}$ sends everyone to towers $17$ and $1$, and another $B$ synchronizes to tower $1$.

It also turns out that $(BA^{16})^{15}B$ is a minimal length tower synchronizing sequence -- the proof of that is more tricky, and we leave it to the end. For now let us accept this claim, according to which no sequence shorter than $17\cdot 15+1=16^2$ can synchronize the towers.

Now suppose that $S$ is a minimal solution to the problem, i.e. a synchronizing sequence sending everyone to position $(1,0)$. Recall that $B$ has no effect on a guard on level $20$ -- a problem we have so far ignored. If $S$ contained a $B$-instruction that some guards could not execute, then omitting this instruction from $S$ has the same effect on these guards as $S$. In particular, this shorter sequence still synchronizes towers to $1$, and certainly does not leave anyone above level $0$ since it has one less "up" instruction than $S$. But this contradicts the minimality of $S$.

It means that any $B$-instruction in $S$ is executed by all guards. Let $c$ and $b$ denote the number of $C$s and $B$s in $S$ respectively. It follows that a guard reading $S$ from level $20$ cannot go below level $20-c+b$ after reading $S$, therefore we must have $c \geq 20+b$. Observe furthermore that a single $B$-move can only merge two towers at a time, therefore we must have $b \geq 16$ and thus $20+b \geq 20+16=36$, so the overall number of $C$-moves we need is at least $36$. The $C$-moves do not contribute to synchronizing towers, so by the previous claim we need at least $16^2$ further steps to synchronize these. This gives a lower bound of $16^2+36=292$ on the shortest synchronizing sequence.

This is achievable: $(CBA^{16})^{15}CB C^{20}$ is a solution. Observe that since all $B$-instructions are preceded by a $C$, no guard encounters a $B$ standing on level $20$, and thus the subsequence $(CBA^{16})^{15}CB$ (as we have already seen) sends everyone to tower $1$. Then $C^{20}$ sends everyone to the ground floor. This solution has length 292, which coincides with our lower bound, so it must be a minimal length solution.

The minimality of the tower synchronizing sequence. What remains is to show that no tower synchronizing sequence shorter than $16^2$ exists. This in fact was first observed by the computer scientist Jan Cerny, who came up with the graph above as an example which takes a long sequence of instructions to synchronize. (It is a long standing open problem, called the Cerny conjecture, whether there are any graphs where synchronization is possible but takes even longer -- more than $(v-1)^2$ steps where $v$ is the number of vertices.) The proof we provide below is due to Mikhail V. Volkov.

Suppose $S$ is a tower synchronizing sequence of minimal length, our aim is to show that $S$ has length at least $16^2=256$. Notice the following:

• since only $B$ merges towers together, $S$ must end in $B$ (otherwise we could obtain a shorter tower synchronizing word by dropping any trailing $A$s)
• putting $S=S'B$, since $S'$ is not tower synchronizing, it must send everyone to either tower $1$ or $17$, who all go to tower $1$ upon following $B$
• the instruction $BB$ has identical effect to the instrution $B$, therefore (by minimality) no two consecutive $B$s occur in $S$

It follows that every occurrence of $B$ in $S'$ is followed by $A$. In particular, $S'$ can be viewed as a sequence of instructions of the form $A$ and $D:=BA$. The effect of the moves $A$ and $D$ on the towers is depicted below.

Since $S'$ sends everyone tower $1$ or $17$, $S'D$ is a tower synchronizing sequence (of $A$s and $D$s) sending everyone to tower $2$. Let $n$ denote the length of $S'D$ considered as an $A-D$ sequence. Then $S'$ has length $n-1$. To count the length of $S'$ as an $A-B$ sequence, we need to count the number of occurrences of $D$s (which is the same as the number of occurrences of $B$s) twice. Since $S$ contains at least $16$ $B$s, $S'$ must contain at least $15$ $B$s and thus the length of $S'$ (as an $A-B$ sequence) is at least $n-1+15$, and so the length of $S$ is at least $n+15$. Therefore to prove our claim, it suffices to show that $n \geq 256-15=241$. This is our goal for the rest of the proof.

Observe that if a guard, starting in tower $2$, takes an arbitrary number $k$ of moves, and then follows the $n$ moves of $S'D$, they again arrive in tower $2$. It follows that the graph above has directed cycles of length $n+k$ around $2$ for any $k \in \mathbb N$.

The graph only has two kinds of directed simple cycles (i.e. cycles which visit every tower at most once): those visiting all towers in sequence (these are of length $17$), and those visiting towers in sequence but skipping $1$ (these are of length $16$). Any cycle can be decomposed into simple cycles, so in particular any cycle has length $16x+17y$ for some positive integers $x,y$. It follows that for any $k \in \mathbb N$, there exist positive integers $x,y$ such that $n+k=16x+17y$. We can use this to find a lower bound for $n$.

Indeed, we claim that $17\cdot 16-17-16=239$ cannot be expressed as $16x+17y$ where $x,y$ are positive integers, that is, the graph contains no cycle of this length. Suppose for contradiction that $$16x+17y=17\cdot 16-17-16.$$ Rearranging, we have $$16(x+1)+17(y+1)=17 \cdot 16,$$ in particular we must have $16 \mid 17(y+1)$ and $17 \mid 16(x+1)$ and thus (since $16$ and $17$ are coprime) $16 \mid y+1$ and $17 \mid x+1$, which (since $x,y$ are positive) implies $16 \leq y+1$ and $17 \leq x+1$. But substituting back we have $$17 \cdot 16=16(x+1)+17(y+1) \geq 16\cdot 17+17\cdot 16=2\cdot17\cdot16$$ which is a contradiction.

We can deduce that $n \geq 240$. Now suppose that $n=240$, that is, $S'D$ is a tower synchronizing sequence of length $n$, sending every guard to tower $2$. Suppose we follow $S'D$ from tower $1$ -- after the first step, we must be in tower $2$ (since there are no other ways out of tower $1$), and so the remaining $n-1$ instructions result in a cycle around tower $2$. But we have just seen that there is no cycle in the graph of length $239$. Thus we must have $n \geq 241$, which is what we had to prove.

Solution: 292

To solve this problem, the mass and centre of mass of the water bottle and the water (as a function of water depth) must be calculated. These can then be combined to find the total centre of mass a function of water depth, of which the minimum can then be found by standard analysis techniques. We treat each of the three parts of the bottle separately at first, then combine them at the end. Note that by symmetry, the centre of mass of each part falls on the vertical centre line of the bottle, hence we only need to determine its height measured from the base of the bottle. The mass of the circular base portion of the bottle is clearly the area times the surface density: $$m_{\text{base}}=\pi(5\text{cm})^2\cdot 0.2\text{g}\cdot\text{cm}^{-2}=5\pi\text{ g}.$$ The centre of mass is obviously $$c_{\text{base}}=0\text{cm}.$$ The mass of the middle cylindrical portion can be calculated similarly: $$m_{\text{mid}}=\pi(10\text{cm})30\text{cm}\cdot0.2\text{g}\cdot\text{cm}^{-2}=60\pi\text{ g}.$$ Again, the centre of mass is obvious from symmetry: $$c_{\text{mid}}=15\text{cm}.$$ For the conical portion, we use the standard formula for the area of the frustum of a truncated cone, which is $$(R+r)s\pi,$$ where $s=\sqrt{h^2+(R-r)^2}$ is the side length of the cone, $h=5\text{cm}$ is the height, $R=5\text{cm}$ is the radius of the base, and $r=0.5\text{cm}$ is the radius of the top opening. Thus $$m_{\text{cone}}=0.2\text{g} \cdot \text{cm}^2\cdot 5.5\cdot \sqrt{4.5^2+5^2}\pi\text{cm}^2=\frac{11\sqrt{181}}{20}\pi\text{g}.$$

Calculating the centre of mass is a bit more tricky, but can be reduced to a one-dimensional integral. The idea is to replace the cone with a thin $5\text{cm}$ long rod (running along its vertical axis) which has the same centre of mass. This involves two steps: we first shrink the side length $s$ of the cone down to $h=5\text{cm}$ preserving mass, i.e. replace the truncated cone with one that has the same base and top, but has height $5\cdot \frac{5}{s}\text{cm}$, and density $0.2\text{g} \cdot \frac{s}{5}$ to preserve the same mass. Then replace the circular cross-section of the new cone which has distance $d$ (measured along the frustum) from the base with a single point on the $5\text{cm}$ long rod at height $d$ (preserving mass). This means that the mass distribution of the of the rod, as a function of the height $h$, is given by the function $0.2\text{g}\cdot \text{cm}^{-2} \cdot 2r(h)\pi\cdot \frac s5$, where $r(h)$ is the radius of the original cone at height $h$, and this coincides with the mass distribution of the original cone as a function of $h$.

We can calculate the centre of mass of the rod by taking the weighted average of the points of the rod weighted by their masses. Since the mass distribution is continuous, this is exactly the integral \begin{align*} c_{\text{cone}}&=\frac{0.2\text{g}\cdot \text{cm}^{-2} \cdot 2\pi\frac{s}5\int_{30}^{35} h r(h)\; dh}{m_{\text{cone}}}\\ &=\frac{0.2\text{g}\cdot \text{cm}^{-2} \cdot 2\pi\frac{s}5\int_{30}^{35} h r(h)\; dh}{0.2\text{g}\cdot \text{cm}^{-2}\cdot (R+r)s\pi}\\ &=\frac{2\int_{30}^{35} h r(h)\; dh}{R+r}. \end{align*}

Let us calculate $r(h)$. Clearly it is a linear function that interpolates the points $(h,r(h))=(30\text{cm},10\text{cm}),(35\text{cm},1\text{cm})$. We can construct it by the linear interpolation formula: $$r(h)=r_0+\frac{r_1-r_0}{h_1-h_0}(h-h_0)=10\text{cm}+\frac{1\text{cm}-10\text{cm}}{35\text{cm}-30\text{cm}}(h-30\text{cm})=64\text{cm}-\frac{9}{5}h.$$

So we calculate \begin{align*} \int_{30}^{35} hr(h)\; dh & =\int_{30}^{35} 64h\;\text{cm}-\frac{9}{5}h^2 \; dh\\ &=\left[32h^2\text{ cm}-\frac{3}{5}h^3\right]_{30\text{cm}}^{35\text{cm}}\\ &=\left(32(35\text{cm})^2\text{cm}-\frac{3}{5}(35\text{cm})^3-32(30\text{cm})^2\text{cm}+\frac{3}{5}(30\text{cm})^3\right)\\ &= 875\text{cm}^3, \end{align*} and thus the height of the center of mass is $$c_{\text{cone}}=\frac{2}{55}\text{cm}^{-2}\cdot 875\text{cm}^3=\frac{350}{11}\text{cm}.$$

Finally we need the mass and centre of mass of the water itself as a function of its depth, $x$. So long as the water is at most $30\text{cm}$ deep, these calculations are quite simple. When $x>30\text{cm}$, the water itself must be split up into two portions. It can perhaps already be estimated, based on physical intuition, that the optimal water depth is far below the $30\text{cm}$ mark, so treating the case where $35\text{cm}\geqslant x>30\text{cm}$ is (thankfully) unnecessary. For now we proceed with finding the minimum in the range $[0\text{cm},30\text{cm}]$ that we sense intuitively should be a unique local minimum and relatively close to $0\text{cm}$, then afterwards we will show more rigorously that there are no smaller minima hiding near the top of the bottle. Let $x\in[0\text{cm},30\text{cm}]$. Then clearly the mass is just given by the volume of the cylinder times the density of water: $$m_{\text{water}}(x)=\pi\cdot (5\text{cm})^2\cdot x\cdot 1\text{g}\cdot\text{cm}^{-3}=\left(25\pi \text{ g}\cdot\text{cm}^{-1}\right)x.$$ The centre of mass is obvious: $$c_{\text{water}}(x)=\frac{x}{2}.$$ Now that we have all necessary masses and centres of mass, we can find the total centre of mass, the weighted mean of the centres of masses of all four parts: \begin{align*} c(x)&=\frac{m_{\text{base}}c_{\text{base}}+m_{\text{mid}}c_{\text{mid}}+m_{\text{cone}}c_{\text{cone}}+m_{\text{water}}(x)c_{\text{water}}(x)}{m_{\text{base}}+m_{\text{mid}}+m_{\text{cone}}+m_{\text{water}}(x)}\\ &=\frac{5\pi\text{ g}\cdot 0\text{cm}+60\pi\text{ g}\cdot 15\text{cm}+\tfrac{11\sqrt{181}}{20}\pi\text{g}\cdot\tfrac{350}{11}\text{cm}+\left(25\pi \text{ g}\cdot\text{cm}^{-1}\right)x\cdot\tfrac{x}{2}}{5\pi\text{ g}+60\pi\text{ g}+\frac{11\sqrt{181}}{20}\pi\text{g}+\left(25\pi \text{ g}\cdot\text{cm}^{-1}\right)x} \\ &=\frac{900\,\text{cm}+\frac{35}{2}\sqrt{181}\,\text{cm}+\frac{25}{2}\,\text{cm}^{-1}x^2} {65+\frac{11\sqrt{181}}{20}+25\,\text{cm}^{-1}x}. \end{align*}

Setting $A=900\,\text{cm}+\frac{35}{2}\sqrt{181}\,\text{cm}$, $B=65+\frac{11\sqrt{181}}{20}$, we may write $c(x)=\frac{A+\frac{25}{2}x^2}{B+25x}.$ We take the first derivative to analyse the function on $0\text{cm}\leqslant x\leqslant 30\text{cm}$, using the quotient rule. \begin{align*} c'(x)&=\frac{f'g-fg'}{g^2},\quad f=A+\frac{25}{2}x^2,\quad g=B+25x\\ c'(x)& =\frac{25x(B+25x)-\left(A+\frac{25}{2}x^2\right)\cdot 25} {(B+25x)^2}\\ &=\frac{25\left(Bx+\frac{25}{2}x^2-A\right)}{(B+25x)^2}. \end{align*}

Since the denominator is always positive, the sign of $c'(x)$ is determined entirely by $Bx+\frac{25}{2}x^2-A$. Substituting $A$ and $B$ and multiplying by $20$, we obtain the following equation for $x$: $$250x^2+(1300+11\sqrt{181})x-(18000 +350\sqrt{181} )=0.$$ Solving for $x$, we obtain two roots, only one of which is positive: $$x_0=\frac{-(1300+11\sqrt{181}) +\sqrt{(1300+11\sqrt{181})^2+1000(18000+350\sqrt{181})}} {500} \text{cm} \approx 7.0653\text{cm}.$$ In particular we have that $c'(x_0)=0$ and $c'(x)$ is negative for $0\leq x < x_0$ and positive for $x > x_0$, hence $x_0$ is the global minimum on the positive axis. Furthermore since $x_0 \leq 30$, it is in the cylindrical part of the bottle as assumed. If the level of the water in the bottle is higher than $x_0$, then clearly the combined centre of mass is also higher, so we won't achieve a lower center of mass with water levels in the conical part.

The question asks for the volume of water required to give this depth $x_0$, which can clearly be found by multiplying by the area of the base of the bottle: $$v=x_0\cdot\pi\cdot(5\text{cm})^2\approx 554.8864\text{cm}^3.$$

Solution: $554.8864$.

We first consider the more general problem: given $n$ bulbs, what is the smallest number $f(n)$ of bulbs that can always be lit? The question then is to determine $f(2026)$.

It is convenient to view the $n$ bulbs (numbered $1$ through $n$) as an $n$-tuple, where each component can be either $0$ or $1$, $0$ corresponding to the respective bulb being off, and $1$ to it being on.

Similarly, we can also consider a switch as an $n$-tuple of $0$s and $1$s, where the $i$th component is $1$ exactly if the switch is connected to the $i$th bulb.

Let us denote the set $\{0,1\}$ by $\mathbb Z_2$, and the set of $n$-tuples of $0$s and $1$s by $\mathbb Z_2^n$. Observe that if $s_1, \ldots, s_j$ are switches (viewed as tuples in $\mathbb Z_2^n$), then the tuple $s_1 \oplus \ldots \oplus s_j$, where $\oplus$ denotes componentwise modulo $2$ addition (i.e. $1 \oplus 1 =0$), is exactly the bulb configuration obtained after toggling the switches $s_1, \ldots, s_j$. In particular, toggling the same switch twice (even if other switches are toggled in between) does not change the configuration. The set of all possible lightbulb configurations obtainable given some set $S \subseteq \mathbb Z_2^n$ of switches is $$\{s_1 \oplus \ldots \oplus s_j \colon \{s_1, \ldots, s_j\}\subseteq S\}.$$ We are going to call that $V \subseteq \mathbb Z_2^n$ a configuration space if it occurs as the set of all possible lightbulb configurations associated to some switches. If furthermore every bulb is connected to some switch (equivalently: if for every position $1 \leq i \leq n$, $V$ contains some tuple that has $1$ in position $i$), we call the configuration space non-degenerate. Observe that configuration spaces are closed under the addition $\oplus$.

Given a tuple $v \in \mathbb Z_2^n$, we define the brightness of $v$, denoted by $|v|$, as the number of $1$s, i.e. the number of bulbs that are on in the configuration $v$. We define the brightness of a configuration space $V$ as $$|V|:=\max\{|v| \colon v \in V\},$$ i.e. the maximal number of bulbs that can be on at the same time. Using this notation, the definition for $f(n)$ can be rephrased as follows: $$f(n)=\min\{|V|\colon V \subseteq \mathbb Z_2^n \hbox{ is a non-degenerate configuration space}\}.$$ It is possible, but difficult to write down a formula directly for $f(n)$. Instead, it turns out to be easier to look at the function $$N(m)=\max\{n \in \mathbb N\colon \exists V \subseteq \mathbb Z_2^n \hbox{ is a non-degenerate configuration space with } |V|\leq m \}.$$ In words, $N(m)$ is the largest integer $n$ such that there exists non-degenerate configuration space $V \subseteq \mathbb Z_2^n$ where at most $m$ lightbulbs can be turned on at once. We define $N(0)$ to be $0$. It is easy to see that $$f(n)=\min\{m \colon N(m)\geq n\}.$$ We will show that for every integer $m\ge 0$, $$N(m)=\sum_{i\ge 0}\left\lfloor \frac{m}{2^i}\right\rfloor.$$ Note that if $m < 2^k$, then $\left\lfloor \frac{m}{2^k}\right\rfloor=0$ so the above sum is finite.

From the formula, obtaining $f(2026)$ is not difficult. Observe that $N(m) \leq \sum_{i\ge 0} \frac{m}{2^i}=2m$. So we have $N(1012)\leq 2024$, in particular $f(2026) \geq 1013$. We can thus compute $N(1013), N(1014), \ldots$ until we find the first value reaching $2026$ (observe that $N(m)$ is, by definition, monotonous). This first happens at $N(1017)=2026$.

We now proceed to proving the formula.

The upper bound. We begin by showing the inequality "$\leq$". It suffices to show that $$N(m)\le m+N(\lfloor m/2\rfloor),$$ then by a formal induction we obtain $$N(m)\le \sum_{i= 1}^{\lfloor\log_2(m)\rfloor}\left\lfloor \frac{m}{2^i}\right\rfloor+N(0)=\sum_{i\ge 0}\left\lfloor \frac{m}{2^i}\right\rfloor.$$ So let $V \subseteq \mathbb Z_2^n$ be a non-degenerate configuration space, and suppose that $V$ has brightness at most $m$. We must show that $$n\le m+N(\lfloor m/2\rfloor).$$ Choose a configuration $v\in V$ of maximum brightness, say $|v|=m'$. Then $m'\le m$.

Let $A \subseteq \{1, \ldots, n\}$ be the set of lighbulbs $i$ which are on in the configuration $v$, and $B= \{1, \ldots, n\} \setminus A$. (So we have $m'$ bulbs in $A$ and $n-m'$ in $B$.)

There is a natural map $$\pi_B:\mathbb Z_2^n\to \mathbb Z_2^{n-m'},$$ which deletes the lightbulbs in $A$ (i.e. projects onto the $B$-components). Let $W=\pi_B(V)$. Observe that if $V$ was associated to some set of switches $S$, then $W$ is the configuration space of the set of switches $\pi_B(S)$, and $W$ inherits the non-degeneracy of $V$.

We claim that $W$ has brightness at most $\lfloor m'/2\rfloor$. Fix $w\in W$, and choose $x\in V$ with $\pi_B(x)=w$. Suppose for contradiction that $w$ has brightness at least $\lfloor m'/2\rfloor+1>m'/2$. Since $x$ has at most $m'$ lighbulbs on, and more than $m'/2$ of those fall into the set $B$, we must have strictly less that $m'/2$ of on bulbs in $A$. But consider the configuration $x \oplus w$, where a lightbulb is on if it is on in precisely one of the configurations $x$ and $w$. These are the bulbs in $A$ where $x$ is off -- there are more than $m'-m'/2=m'/2$ of these; and the bulbs in $B$ where $x$ is on -- there are again more than $m'/2$ of these, so $x \oplus v \in V$ has brightness greater than $m$, which is a contradiction.

Since $w \in W$ was arbitrary, we obtain $|W| \leq \left\lfloor m'/2\right\rfloor \leq \left\lfloor m'/2\right\rfloor$. Since $W \subseteq \mathbb Z_2^{n-m'}$ is a non-degenerate configuration space, by definition we must have $$N\left(\left\lfloor \frac m2\right\rfloor\right) \geq n-m' \geq n-m,$$ we obtain the desired inequality by rearranging to $n$.

The lower bound. We now construct, for each $m$, a non-degenerate configuration space on exactly $\sum_{i\ge 0}\left\lfloor \frac{m}{2^i}\right\rfloor$ lightbulbs, with brightness at most $m$.

We begin by explaining the construction for a 2-power $m=2^{k-1}$. The number of lightbulbs will be $$\sum_{i\ge 0}\left\lfloor \frac{2^k}{2^i}\right\rfloor=2^{k-1}+2^{k-2}+\ldots +1=2^{k}-1.$$ We denote the set $\{1, \ldots n\}$ by $[n]$. In $\mathbb Z_2^{2^{k}-1}$, it will be convenient to identify the indexing set $2^k-1$ with the set of nonempty subsets of $[k]$, i.e. fix any bijection $$f\colon [2^k-1] \to \mathcal P([k]) \setminus \emptyset,$$ where $\mathcal P(\cdot)$ denotes the power set. We define $k$ switches $s_1, \ldots, s_{k}$, where the $i$th switch switches exactly those bulbs whose associated set contains $i$. Observe that every bulb is controlled by some switch. Let $U$ be the configuration space associated to these switches. We claim that for all configurations $u \in U$, either $|u|=0$ or $|u|=2^{k-1}$. Take a configuration $u$, and suppose $u$ was obtained by flipping the switches $s_{j_1}, \ldots s_{j_n}$, and let $I=\{j_1, \ldots, j_n\} \subseteq [k]$. Recall that the brightness of $u$ is the sum of the bulbs that are on in $u$, and a bulb is on exactly if there were an odd number of switches in $I$ affecting it. It follows that $|u|=\left|\{S \subseteq [k] \colon |S \cap I| \hbox{ is odd}\}\right|.$ We claim that if $I \neq \emptyset$, this is exactly $2^{k-1}$. First observe that $$2^k=|\mathcal P([k])|=\left|\{S \subseteq [k] \colon |S \cap I| \hbox{ is even}\}\right|+\left|\{S \subseteq [k] \colon |S \cap I| \hbox{ is odd}\}\right|,$$ and notice that there is a bijection between the two summands, namely fixing some $i \in I$, the odd sets containing $i$ are in bijection with the even sets not containing $i$; and the even sets containing $i$ are in bijection with the odd sets not containing $i$. The claim follows. We have thus shown that every $u \in U$ has either brightness $0$ (when $I=\emptyset$) or $2^{k-1}$ (when $I \neq \emptyset$).

Now for a general $m$, write the binary expansion of $m$ as $$m=2^{k_1}+2^{k_2}+\cdots+2^{k_r} \qquad (k_1>k_2>\cdots>k_r\ge 0).$$ Take the previous construction on $2^{k_i}-1$ lightbulbs for each $i$, and take the disjoint union of these constructions (i.e. of the bulbs and associated switches). This results in a nondegenerate configuration $V$. Note that within any block, we can either light $2^{k_i}$ bulbs or no lightbulbs at all, in particular every configuration has brightness at most $m=2^{k_1}+2^{k_2}+\cdots+2^{k_r}$, and this upper bound is reached by switching one switch in every block.

The total number of lightbulbs is $$ \sum_{j=1}^r (2^{k_j+1}-1)=2\sum_{j=1}^r 2^{k_j}-r=2m-r. $$ But $r$ is exactly the number of $1$s in the binary expansion of $m$, denoted $b_1(m)$. We also claim that $$ F(m):=\sum_{i\ge 0}\left\lfloor \frac{m}{2^i}\right\rfloor=2m-b_1(m), $$ which is easy to verify by induction. Indeed, for $m=0$ the claim is clearly true. Now suppose it holds up to $m$, then $$F(m)=m+\sum_{i\ge 1}\left\lfloor \frac{m}{2^i}\right\rfloor=F\left(\left\lfloor \frac{m}{2}\right\rfloor\right)= \begin{cases} F\left(\frac{m}{2}\right)=m+b_1(m/2) &\hbox{if $m$ is even}\\ F\left(\frac{m-1}{2}\right)=m-1+b_1((m-1)/2) &\hbox{if $m$ is odd}. \end{cases}$$ Now if $m$ is even, then $b_1(m)=b_1(m/2)$, and if $m$ is odd, then $b_1(m)=b_1((m-1)/2)+1$, which yields the claim.

Hence our construction shows that $$N(m)\ge \sum_{i\ge 0}\left\lfloor \frac{m}{2^i}\right\rfloor$$ which gives the lower bound we needed.

Solution: $1017$.

Remark: we did not derive a formula for the function $f(n)$, but a recursion exists: https://oeis.org/A046699.

Mathsbombe Competition 2026 is organised by the The Department of Mathematics at The University of Manchester.
© The University of Manchester 2012–2026, All Rights Reserved
Contact us | Privacy notice