# Problem of the Week Archive

### S25W15 (October 11 to October 15)

2021 random diameters of a circle $\Gamma$ are drawn.
Then, two points $A,B$ are independently and randomly chosen on $\Gamma$. What is the expected number of diameters that intersect the chord $\overline{AB}$?

### S25W14 (October 04 to October 08)

We have two coins: a fair coin that comes up heads with probability $\frac12$ when flipped, and a biased coin that comes up heads with probability $p$. If we pick a coin at random and flip it, it comes up heads with probability $2p$. Given that a randomly picked coin came up heads, what is the probability that the coin is fair?

The answer to last week’s problem as $\boxed{3/4}$. Saksham S. writes

The probability that a coin comes up heads when randomly chosen and then
flipped is $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2}\cdot p$, because either the fair coin is chosen or the biased
coin is chosen. For the first case, there is a $1/2$ chance that the fair coin will
get picked, and after getting picked, there is a $1/2$ chance it will come up heads.
For the second case, there is a $1/2$ chance that the biased coin will get picked,
and then a chance of $p$ that it will come up heads. We are given that this is $2p$,
so
\[\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot p =2p \implies 1+2p=8p \implies 6p=1 \implies p=\frac{1}{6}.\]

To finish, Saksham uses the fact that the probability of event $A$ conditioning on event $B$ is $\mathbf{P}(A \text{ and }B)/\mathbf{P}(B)$, where $\mathbf{P}(\bullet)$ denotes the probability of an event. Therefore the answer is
\[\frac{\mathbf{P}(\text{fair and heads})}{\mathbf{P}(\text{heads})} = \frac{1/4}{2p} = \frac{1/4}{1/3} = \frac{3}{4}.\]

Andrew L. takes a slightly different approach that doesn’t involve computing $p$ at all! The key realization is that
\[\frac{\mathbf{P}(\text{fair and heads})}{\mathbf{P}(\text{heads})} = 1 - \frac{\mathbf{P}(\text{not fair and heads})}{\mathbf{P}(\text{heads})} = 1 - \frac{p/2}{2p} = \frac{3}{4}.\]

### S25W13 (September 27 to October 01)

A lattice grid in the shape of an equilateral triangle consists of $55$ dots arranged in $10$ rows, with the largest row having $10$ dots. Determine the largest possible integer $N$ for which it is possible to select $N$ points such that no two points lie on a line parallel to a side of the grid.

(For an extra challenge, use a grid with $\frac{2021 \cdot 2022}{2}$ dots.)

This week’s problem was tough, and we did not receive any correct submissions. The answer is $\boxed{7}$; here is a valid construction:

To prove that 7 is maximal, we first observe the following interesting property of this triangular grid.
Suppose we associate with each point $P$ in the grid a triple
of numbers $x,y,z$, where $x$ is the number of layers parallel to the bottom of the triangle
that lie below the layer containing $P$, and $y$ and $z$ are defined similarly for the left and right sides, respectively. Then the top-most circled point in the diagram above, for example, is associated
with $(6,1,2)$. We can see that for all $P$, $0 \le x,y,z \le 9$ and $x + y + z = 9$.

By the constraints of the problem, we want to pick some set of $P_i$ such that all associated $x_i$ are pairwise distinct, as are all associated $y_i$ and $z_i$. Suppose we are able to select 8 such $P_i$; then we have that $\sum x_i \ge 0+1+2+3+4+5+6+7=28$, since all $x_i$ must be distinct. We likewise have that $\sum y_i \ge 28$ and $\sum z_i \ge 28$. It follows that $\sum x_i + \sum y_i + \sum z_i \ge 84$. But we also have $\sum x_i + \sum y_i + \sum z_i = \sum (x_i + y_i + z_i) = 8 \cdot 9 = 72 < 84$. Since this is a contradiction, it must be impossible to select 8 such $P_i$, and 7 must be optimal.

Can you extend the construction (and proof) to solve the problem for arbitrary $n$?

### S25W12 (September 20 to September 24)

Find the number of pairs of positive integers $(a, b)$ such that $a, b \leq 10^{12}$ and
\[
10a+10b + 99999999900\gcd(a, b) = \operatorname{lcm}(a, b).
\]

The answer is $\boxed{18}$.

Jonathan P. attacks this problem by letting $g = \gcd(a, b)$ and letting $a = gx$ and $b = gy$. Then $\operatorname{lcm}(a b) = gxy$ and $\gcd(x, y) = 1$. Given this substitution, the problem becomes
\[xy = 10x + 10y + 99999999900 \iff (x-10)(y-10) = 10^{11}.\]
At first, there might appear to be many solutions to this equation for $(x, y)$, but in fact there are only very few once we consider the condition $\gcd(x, y) = 1$. For instance, if $x-10$ and $y-10$ are both even, then $x$ and $y$ must then both be even, which is a contradiction. Therefore all the factors of $2$ in $10^{11}$ must be contained in exactly one of the terms. Similarly, if $x-10$ and $y - 10$ are both divisible by $5$, then $x$ and $y$ must also be divisible by $5$, again impossible.

There are now only two cases. We must either have $\{x-10, y-10\} = \{2^{11}, 5^{11}\}$ or $\{x-10, y-10\} = \{1, 10^{11}\}$. In the first case, we know that $\{x,y\} = \{2^{11}+10,5^{11}+10\}$. However, both $2^{11} + 10$ and $5^{11} + 10$ are divisible by $3$, so we can rule this case out. In the second case, $\{x,y\} = \{11, 10^{11} + 10\}$. Since $11$ is prime and $10^{11} + 10 \equiv (-1)^{11} - 1 \equiv -2 \pmod {11}$, these are relatively prime, so this is a valid solution.

It follows that the only solutions to the original equation are of the form $(11g, (10^{11} + 10) g)$ and $((10^{11} + 10) g, 11g)$ for any positive integer $g$. Each of these cases has $9$ solutions that fit the inequality $x,y\leq 10^{12}$, leading to $18$ solutions in total.

### S25W11 (September 13 to September 17)

Consider a unit square $S$. $A, B, C$ are vertices of a right triangle that has right angle at $A$, and points $B, C$ lie in $S$. Find the area of the region of possible locations of $A$.

The answer is $\boxed{1+\frac{\pi}{2}}$. The region in question consists of the square, joined with four semicircles of diameter $1$ on each side of the square:

To solve this, we shall do casework on where $A$ would be. There are three cases of regions where $A$ can be, which we will call Types I, II, and III, according to the above diagram. Let the square have vertices $WXYZ$.

The first case is when $A$ is inside the square (Type I region). In this case, observe that one can pick a very tiny right triangle with right angle $A$ that lies entirely in the square, so every point inside $A$ is possible.

Now, for the case where $A$ is in a Type II region. Let the side of the square closest to this point $A$ be $XY$. Then, if we can find points $B$ and $C$ inside the square such that $\angle BAC$ is right, it follows that $\angle XAY$ is strictly larger than $\angle BAC$ and is thus obtuse. Conversely, if $\angle XAY$ is obtuse, one can find two rays at right angles starting at $A$ that intersect the interior of the square, yielding choices for $B$ and $C$. The set of all such points with $\angle XAY$ obtuse is a semicircle.

Now for the case where $A$ is in a Type III region. Suppose that the vertex closes to $A$ is $X$. Then, note that since angle $\angle WAZ$ is acute, we cannot find two perpendicular rays starting at $A$ that both intersect the interior of the square, which means we cannot find $B$ and $C$ inside the square such that $\angle BAC$ is right.

Thus, the valid region includes the unit square and the four semicircles on the sides, which has a total area of $1+4\cdot \frac{\pi}{8} = \boxed{1+\frac{\pi}{2}}$.

For an extra challenge, what if we were to replace the unit square with some other regular polygon? What if we were to replace the square with a unit circle? And instead of looking for $\angle BAC = 90^{\circ}$, what if we looked for $\angle BAC = 60^{\circ}$, or any other angle?

### S25W10 (September 06 to September 10)

Find the number of positive integers $n$ for which
\[
2021^n +
2022^n + 2023^n +
\cdots +
2029^n
\]
is prime.

The main idea of this problem is considering the sum modulo 3. Daniel B. writes:

Reducing modulo $3$, each base can thus also be reduced modulo $3$. This gives us $3$ copies of $2^n$, $3$ copies of $1^n$, and $3$ copies of $0^n$.

Indeed, we find that

\[2021^n \equiv 2024^n \equiv 2027^n \equiv 2^n \pmod 3\]
\[2022^n \equiv 2025^n \equiv 2028^n \equiv 0^n \pmod 3\]
\[2023^n \equiv 2026^n \equiv 2029^n \equiv 1^n \pmod 3\]

So that \[2021^n + \cdots + 2029^n \equiv 3(2^n + 0^n + 1^n) \equiv 0 \pmod 3\]

So the sum is always divisible by 3, and no integers $n$ satisfy the requirement.

Aakash H. rigorously shows that $n \equiv (n + 3)^k \pmod 3$ for all positive integers $k$.

\[(n + 3)^k = \binom n 0 n^k + \binom n 1 3n^{k - 1} + \binom n 2 3^2n^{k - 2} + \cdots + \binom n n 3^k\]
Every term after the first contains 3 as a factor, so by taking modulo 3, we arrive at $x^n \equiv (x + 3)^n \pmod 3$

In general, many well-known properties of modular arithmetic can be invoked without proof on contests.
However, it is important to understand where these properties come from to use them effectively, and so deriving them for yourself can be a good exercise.
For example, the property that

\begin{equation}
a \equiv b \pmod n \implies a^k \equiv b^k \pmod n
\end{equation} is a consequence of a more general fact

\begin{equation}
a \equiv b \pmod n \text{ and } c \equiv d \pmod n \implies ac \equiv bd \pmod n.
\end{equation} Can you prove $(2)$?

### S25W9 (August 30 to September 03)

This week’s problem is an estimation problem! Submit both your best estimate and the reasoning by which you arrived at that estimate in lieu of a solution. You are not permitted to use calculators or computer software.

Let $\omega$ and $\Omega$ be two concentric circles with radii $1$ and $2$, respectively. Let $A$ and $B$ be two points chosen, independently and uniformly, at random on the boundary of $\omega$, and let $C$ and $D$ be two points chosen, independently and uniformly, at random on the boundary of $\Omega$. Estimate the probability that segments $AB$ and $CD$ intersect.

One way to approach the problem is by examining the chord $CD$. After plotting a few examples, one may notice that it is very common for $CD$ to miss the circle $\omega$ entirely, making it impossible that it intersect with chord $AB$. In order to calculate the probability of this occurring, Mainak C. sets $C$ to be some fixed point on $\Omega$, which is possible since the problem is rotationally symmetric. If we require that $CD$ intersects $\omega$, it must then be the case that $D$ lies in an arc bounded by the two lines through $C$ that are tangent to $\omega$.
After some computations, one finds that this arc is exactly $1/3$ of the circle, so the probability that $CD$ intersects $\omega$ is $1/3$.

To finish, we want to estimate the probability $p$ that $AB$ intersects $CD$ given that $CD$ intersects $\omega$. This probability is impossible to determine exactly, but one can estimate it with a few observations. For one, the maximum probability, if $CD$ is fixed, is $1/2$, achieved when $CD$ is a diameter of $\Omega$.
Roberto S. estimates $p \approx 1/3$, leading to a final answer of $1/9$.

We can get the true answer by evaluating the integral\[ \frac{4}{\pi^3}\int_{\frac\pi3}^{\frac\pi2}\arccos(2\cos x)(\pi - \arccos(2\cos x)) dx\]which Wolfram|Alpha tells us is $\approx$ $0.13365$.

### S25W8 (August 23 to August 27)

What is the volume of points $(x, y, z)$ in three-dimensional space so that
\[\lvert x\rvert + \lvert y\rvert + \lvert z\rvert + \lvert x+y\rvert + \lvert y+z\rvert + \lvert x+z\rvert + \lvert x-y\rvert + \lvert x-z\rvert + \lvert y-z\rvert \leq 1?\]

Last week’s problem of the week asked you to compute the volume of the region (which we will call $R$) of points $(x,y,z)$ that satisfy
\[\lvert x\rvert + \lvert y\rvert + \lvert z\rvert + \lvert x+y\rvert + \lvert y+z\rvert + \lvert x+z\rvert + \lvert x-y\rvert + \lvert x-z\rvert + \lvert y-z\rvert \leq 1.\]
(For simplicity, let $f(x,y,z)$ denote the left-hand side of the above inequality.)

To tackle this, Elias M. made the following observation: $f(x,y,z)$ is symmetric with respect to sign: in other words, $f(x,y,z) = f(-x,y,z)$, and similarly for the other variables. It is also symmetric with respect to reordering $x$,$y$, and $z$. Therefore, it suffices to consider the part of $R$ within the region $S = \{(x,y,z)\mid x \geq y \geq z \geq 0\}$. By symmetry, 3D space can be divided into $48$ regions equivalent to $S$ under the symmetries discussed above. Therefore, the volume $R$ is $48$ times the volume of $R \cap S$.

Now, observe that inside $S$, $f(x,y,z) = 5x + 3y + z$. Thus, $R \cap S$ defined by the four inequalities
\[
\begin{align*}
5x+3y+z &\leq 1 \\
x - y &\geq 0 \\
y - z &\geq 0 \\
z &\geq 0.
\end{align*}
\]
Therefore $R \cap S$ is bounded by four planes. Since it is bounded, it is a tetrahedron. The four points in space in which three of the above inequalities reach equality are $(0,0,0)$, $(1/9,1/9,1/9)$, $(1/8,1/8,0)$, and $(1/5,0,0)$, so these must be the vertices of our tetrahedron. Therefore, we can compute the volume of $R\cap S$ as
\[\frac{1}{6} \det
\begin{pmatrix}
1/5&0&0\\
1/8&1/8&0\\
1/9&1/9&1/9
\end{pmatrix}
= \frac{1}{2160}.\]
The final answer is $\frac{48}{2160} = \boxed{\frac{1}{45}}$.

An alternative way to calculate the volume of $R\cap S$ is to use the coordinate transformation $(x,y,z) \mapsto (u,v,w)$ given by
\[
\begin{align*}
x &= u + v + w \\
y &= v + w \\
z &= w.
\end{align*}
\]
This is a composition of two shears, so it preserves volume. Also, the region $R \cap S$ is now given by $u,v,w \geq 0$ and $9u + 8v + 5w \leq 1$, which is a tetrahedron with vertices $(0,0,0)$, $(1/9,0,0)$, $(0,1/8,0)$, and $(0,0,1/5)$. The volume of this is again $\frac{1}{6 \cdot 5 \cdot 8 \cdot 9} = \frac{1}{2160}$.

### S25W7 (August 16 to August 20)

The three roots of $x^3-4x^2+5x-p=0$ are positive and form the side lengths of a right triangle. Find the value of $p$.

This problem is an interesting application of Vieta’s formulas. Anh Danh Tran Phan writes

Let $x_1, x_2, x_3$ be the three roots of the cubic equation. By Vieta’s theorem for cubic polynomials, we have
\[
\begin{cases}
x_1 + x_2 + x_3 = 4 \\
x_1x_2 + x_2x_3 + x_3x_1 = 5.
\end{cases}
\]
Because the three roots form the side lengths of a right triangle, without loss of generality we have
\[x_1^2 + x_2^2 = x_3^2 \iff 2x_3^2 = x_1^2 + x_2^2 + x_3^2.\]
By manipulating with some algebra, we have
\[2x_3^2 = (x_1^2 + x_2^2 + x_3^2 + 2x_1x_2 + 2x_2x_3 + 2x_3x_1) - 10 = (x_1 + x_2 + x_3)^2 - 10 = 4^2 - 10 = 6.\]
Therefore, $x_3 = \sqrt{3}$ since every root of the equation is positive.
Because $x_3 = \sqrt{3}$ is a root of the cubic equation $x^3-4x^2+5x-p=0$, we have
\[p = x_3^3 - 4x_3^2 + 5x_3 = (\sqrt{3})^3 - 4(\sqrt{3})^2 + 5\cdot \sqrt{3} = \boxed{8\sqrt{3}-12}.\]
The needed value for $p$ is $p = 8\sqrt{3} - 12$.

Many submissions used an alternative finish. After deriving that $x_3 = \sqrt{3}$, they used Vieta again to find
\[p = x_1x_2x_3 = \sqrt{3}\cdot x_1x_2.\]
On the other hand, we know that $x_1 + x_2 = 4 - \sqrt{3}$ and $x_1x_2 + \sqrt{3}(x_1+x_2) = 5$, so
\[x_1x_2 = 5 - 4\sqrt{3} + 3 = 8 - 4\sqrt{3},\]
implying that $p = 8\sqrt{3} - 12$. While this is perfectly valid, it is considerably shorter to simply plug in $x = \sqrt{3}$ once one derives that it is a root.

As an interesting extension, one can try adding an extra degree of freedom to the problem. For example, let us assume that the roots of the polynomial $x^3 - 4x^2 + qx - p$ are all positive and the side lengths of a right triangle. There is no longer a unique solution for $p$ and $q$ in this case, but that doesn’t mean that they can be any real numbers. What are the possible values for $q$? What happens when $4$ is replaced with some other number?

### S25W6 (August 09 to August 13)

What is
\[\operatorname{lcm}(1, 6) + \operatorname{lcm}(2, 6) + \operatorname{lcm}(3, 6) + \cdots + \operatorname{lcm}(221, 6)?\]

The general plan for most of the solutions we received is to perform casework on $\gcd(x,6)$.
Shreyansh S. describes this approach:

To calculate the LCMs, the best approach would be to segregate the terms on the basis of the
first element. By segregating, the terms would be in Arithmetic Progression and it would be easy
to calculate the sum.

There end up being 4 cases, one for each factor of 6. If $\gcd(x, 6) = k$, then
$\operatorname{lcm}(x, 6) = \frac{6x}{k}$. Since $\frac{6}{k}$ is constant for $x$ from a given congruence class
mod 6, we can sum the six separate arithmetic progressions, multiplying each by $frac{6}{k}$. Another approach is to sum all multiples of 2 and subtract multiples of 6 for $k = 2$ (and, likewise, sum all multiples of 3 and subtract all multiples of 6 for $k = 3$). This approach is a little easier, since it only involves 4 arithmetic sums.

Let $S_k$ be the sum of positive integers $x \leq 221$ such that $k|x$. We have:
\[
\begin{align*}
S_1 &= \frac{222 \cdot 223}{2} - 222 = 24531 \\
S_2 &= \frac{222 \cdot 224}{4} - 222 = 12210 \\
S_3 &= \frac{222 \cdot 225}{6} - 222 = 8103 \\
S_4 &= \frac{222 \cdot 228}{12} - 222 = 3996
\end{align*}
\]

So for the final answer we compute:
\[
\begin{align*}
6(S_1 &- S_2 - S_3 + S_6) + 3(S_2 - S_6) + 2(S_3 - S_6) + S_6 = \\
&= 6 \cdot 24531 - 3 \cdot 12210 - 4 \cdot 8103 + 2 \cdot 3996\\
&= 86136.
\end{align*}
\]

Sambhu G. offers a solution where he instead groups the numbers $1,2,\dots,221$ into consecutive groups of $6$, rather than by residues modulo $6$. He notes that:

Note that
\[
\sum_{n=1}^ 6 \operatorname{lcm}(n,6) = 66, \quad
\sum_{n=7}^{12} \operatorname{lcm}(n,6) = 192, \quad
\sum_{n=13}^{18} \operatorname{lcm}(n,6) = 318,
\]
and so on and so forth. Aha! We see a pattern! We add $126$ to each sum [each time we increase $n$ by 6]. The problem now boils down to proving
\[\sum_{n=6k+1}^{6k+6} \operatorname{lcm}(n,6) = 66 + 126k.\]

The final claim can be proven just by checking the exact least common multiples for each of the terms $n=6k+1,\dots,6k+6$. Then, Sambhu sums the claim for $k=0,1,\dots,36$ and subtract the overcounted $\operatorname{lcm}(222,6)$ to get
\[66 + \dots + (66 + 126 \cdot 36) - 222 = \frac{66 + (66 + 126 \cdot 36)}{2} \cdot 37 - 222 = 86136.\]
Interestingly, it is possible to simplify this approach further—the key is to consider groups of six starting at $0$ instead of $1$. Then one only needs to compute
\[\sum_{k=0}^{36} \sum_{n=6k}^{6k+5} \operatorname{lcm}(n, 6) = \sum_{k=0}^{36} (126k + 60) = 37 \cdot (126 \cdot 18 + 60) = 86136.\]
In fact, the above solution further shows that
\[\lim_{n \to \infty} \frac{\operatorname{lcm}(1,6) + \operatorname{lcm}(2,6) + \dots + \operatorname{lcm}(n,6)}{1+2+\dots+n} = \frac{7}{2}.\]
Do you see why? How does the right-hand side change when we replace $6$ with a variable positive integer $m$?

### S25W5 (August 02 to August 06)

For how many triples of integers $(a, b, c)$ with $-2021 \le a, b, c \le 2021$ does the system of equations given by $ax = b$, $by = c$, and $cz = a$ have an integer solution in $x,y,z$?

We want to find all triples $(a,b,c)$ such that the following system has integer solutions for $x,y,$ and $z$: $$ax=b,$$ $$by=c,$$ $$cz=a.$$

Olivia X. starts by...

multiplying the three equations together [to give] $abcxyz = abc$. If one of $a$, $b$, $c$ is $0$, then all three are 0, so $(0, 0, 0)$ is a solution. We now assume $a, b, c \neq 0$, so $xyz = 1$.

In the case where $xyz=1$, we know that for $x,y,$ and $z$ to all be integers, we know that we must either have $x=y=z=1$ or two of the three are $-1$ while the other is $1$. In both cases, $|a| = |b| = |c| \neq 0$ (since we already counted the solution $(0, 0, 0)$).

Thus, in either case, there are $4042$ values to pick for $a$, and then the values for $x$, $y$ and $z$ determine the values for $b$ and $c$. Specifically, we must have $b = ax$ and $c = axy$ by the given equations, and the last equation $cz = a$ is satisfied since $xyz = 1$. So, we have $4 \cdot 4042 = 16168$ solutions. Adding back the triple $(0,0,0)$ gives us $16168+1 = \boxed{16169}$.

This problem demonstrates the importance of writing your proofs clearly and tackling every possible issue. For example, a common trap is to get to the step $abcxyz=abc$ and then divide both sides by $abc$ without checking if $abc=0$. As an interesting challenge, we left out a few minor details in our “proof”. Can you find what’s missing?

### S25W4 (July 26 to July 30)

The squares of the following figure are filled with the integers
$1, 2,\ldots , 64$, such that for each $1 \leq i < 64$,
the numbers $i$ and $i + 1$ are in adjacent squares.
What is the minimum possible sum of the $28$ numbers in the gray squares?
Note: This problem is challenging!
Feel free to submit any progress you find towards the solution.

The answer to last week's problem of the week was $\boxed{416}$. Congratulations to all who solved it!

A valid construction is the following:

The numbers in the gray squares consist of every integer from $1$ to $25$, along with $27$, $29$, and $35$. These have a sum of $416$, as desired.

To prove that this is optimal, suppose we have an example with a smaller sum.

We first color the squares red and blue in a checkerboard pattern (this is normally black and white, but we'll use red and blue here to avoid confusion with gray), so that the lower left corner is blue. Then, the gray staircase consists of $16$ red squares and $12$ blue squares. A key observation is that the numbers must alternate colors. In other words, we have two cases:

- Case 1. All odd numbers are on blue squares and all even numbers are on red squares. In this case, it is easy to show that the minimum sum is \[1 + 2 + \cdots + 23 + 24 + 26 + 28 + 30 + 32 = 416.\] But we assumed that we had an arrangement that did strictly better than $416$, so this is a contradiction. (In fact, I'm pretty sure that there are no examples in this case that achieve $416$, but I haven't thought about it too much---it's irrelevant to the answer of the problem.)
- Case 2. All odd numbers are on red squares and all even numbers are on blue squares. The minimum possible sum under these restrictions is \[1 + 2 + \cdots + 23 + 24 + 25 + 27 + 29+ 31 = 412.\] Therefore, if we are to do better than $416$, our possibilities are very limited. In fact, one can show that the set of numbers (call this $S$ from now on) on gray squares must be one of the following three cases: \[ \begin{align*} &\{1, 2, \ldots, 23, 24, 25, 27, 29, 31\} \tag{A} \\ &\{1, 2, \ldots, 23, 25, 26, 27, 29, 31\} \tag{B}\\ &\{1, 2, \ldots, 23, 24, 25, 27, 29, 33\}. \tag{C} \end{align*} \]

We will now prove that each of these are impossible. Cases A and B are not too difficult to disprove, but Case C is a bit trickier. In fact, Jeffrey H. points out that if we ignore the restriction we must be able to continue the labeling all the way up to $64$, we can actually achieve case C, as follows:

Here, we will present a neat argument which will rule out all three cases simultaneously.

Of the two white corners immediately adjacent to the staircase, one of them must not be labeled $64$; without loss of generality let it be the top right. If this is labeled with $x$, then observe that exactly one of $x+1$ and $x - 1$ must be in $S$. In cases A and B, this forces $x = 32$, while in case C this forces $x$ to be one of $30$, $32$, or $34$. It's pretty easy to show that in case C we must in fact have $x = 34$, but we will not use this fact.

Now we turn our attention to the lower left corner. Define $a, b, c$ to be the following labels:

Since we know $x \in \{30,32,34\}$, it follows that $a, b, c$, which are a minimum distance of $10$ from the label $x$, are either at most $24$ or at least $40$. Since $a, b, c \notin S$, the only way for the first case to be true is if $x = 34$ and we are in case B, but this is impossible since we know $x = 32$ in case B. Therefore $a, b, c \geq 40$.

However, all numbers in $S$ are strictly less than $39$, so the numbers adjacent to $a, b, c$ must all be on white squares. Since there is exactly one white square adjacent to $a$, we must have $a = 64$. The rest must have two adjacent numbers in adjacent squares, so we can deduce the following:

However, there is now no way to handle the square marked with a question mark. This is a contradiction, concluding the proof.

Personally, we (the HMMT problems staff) think this problem is hard enough as is, but if you're up for an extra challenge you can try solving the problem with the $8 \times 8$ board replaced by an $n \times n$ board. If you do manage to solve this case, please do let us know!

Since it's the first week of August, we are returning to the easier part of the monthly cycle.

### S25W3 (July 19 to July 23)

Consider the following $4 \times 4$ grid of unit squares. What is the radius of the dotted circle?

The answer to last week's problem of the week was $\boxed{\frac{5\sqrt{26}-7}{14}}$.

One method, used by several submissions, was to convert the entire problem into algebra. If we introduce a coordinate system on the diagram so that the lower left corner is $(0,0)$ and $(4,4)$, we need to solve
\[(x-0.5)^2+(y-0.5)^2 = (x-1.5)^2+(y-3.5)^2=(x-3.5)^2+(y-2.5)^2.\]
While not particularly elegant, it is possible to deduce $(x, y) = (13/7, 12/7)$ and solve the problem.

Viraj S. from Kent School, Connecticut submitted a slick solution, which observes that if we let $\Omega$ be the circle that we are interested in, $\Omega_1, \Omega_2, $ and $\Omega_3$ be the three smaller circles, and $\Omega '$ be the circle that passes through the centers of the small circles, then

Since the radius of $\Omega_1$, $\Omega_2$, and $\Omega_3$ are all $0.5$, the radius of $\Omega$ is simply $R' = R + 0.5$ and both $\Omega$ and $\Omega '$ share the same center (this is true since $\Omega$ is tangent to $\Omega_1$, $\Omega_2$, and $\Omega_3$).

Here's a handy diagram to visualize this:

From there, one can finish the problem using the property
\[
[ABC] = \frac{AB \cdot BC \cdot AC}{4R'}
\]

Using Pythagoras theorem we get that, $BC = \sqrt 5$, $AC = \sqrt{13}$, and $AB = \sqrt{10}$... Now, we will find the area of triangle ABC... The easiest method [is] to subtract [from] the area of the square DEFA the areas of the triangles DBA, BEC, and CFA.
$[ABC] = 3 \cdot 3 - \frac{3 \cdot 1}2 - \frac{2 \cdot 1}{2} - \frac{3 \cdot 2}2 = \frac7 2$

Here's another diagram to help understand how we found the area of this triangle:

Rearranging the triangle-area expression and inserting these values gives
\[R = R' - \frac{1}{2} = \frac{\sqrt{5} \sqrt{13} \sqrt{10}}{4 \cdot \frac{7}{2}} - \frac{1}{2} = \frac{5\sqrt{26}}{14} - \frac{1}{2}.
\]

### S25W2 (July 12 to July 16)

Adele and Beyoncé are playing a game with a biased coin that comes up heads with probability $p$. They alternate flipping the coin, with Adele going first. Adele wins if they flip heads, while Beyoncé wins if they flip tails. If the probability of Adele winning is $\frac{1}{2021}$, find $p$.

The answer to last week's problem of the week was $\boxed{1011 -
2\sqrt{255530}}$. Bo S. from
Great Valley High School submitted two correct solutions, one of which
observes that

The probability that Adele wins is the sum of the probabilities that
she wins on the 1st turn, 3rd turn, 5th turn, etc.

This yields the infinite sum
\[
\frac1{2021} = p + p(1 - p) + p^2(1 - p)^3 + \cdots
\]

We can note that the sum is geometric with common ratio $p(1 - p)$,
giving
\[
\frac1{2021} = \frac p{1 - p(1 - p)}
\]

Solving the resulting quadratic gives that answer (and an extraneous
solution that is greater than 1).

On the other hand, Jeffrey H.
gives a shortcut to the above method. Specifically, he notes:

Adele wins if H comes up first, with probability $p$. Beyoncé wins the
first time if TT shows up, or $(1-p)^2$. Otherwise, the game goes back
to where it started.

Thus, we know the winning odds for Adele are precisely $p : (1-p)^2$.
The finish is then easy;

Adele wins with probability $1/2021$, we need for Beyonce to have 2020
times a winning chance as Adele, so $(1-p)^2=2020p$. Solving for $p$,
we get $p^2-2022p+1=0$, or $p=1011-\sqrt{1011^2-1}$ since
$0 < p < 1$.

Instead of using the quadratic formula, we can also compute $p$ by
rewriting the quadratic $p^2 - 2022p + 1 = 0$ as $p = \frac{1}{2022 -
p}$. Iterating this gives us
\[
p = \cfrac{1}{2022
-\cfrac{1}{2022
-\cfrac{1}{2022
-\cfrac{1}{2022
-\cdots}}}}
\]
Trying to evaluate this fraction is a quick way to approximate the
answer. For example, we can tell immediately that $p$ is slightly
greater than $\frac{1}{2022}$, but only by a tiny amount.

The existence of this continued fraction raises an interesting
question: is there a way to get this answer form directly from the
problem statement?

### S25W1 (July 05 to July 09)

How many ways are there to select one brick from each of the rows of the following figure so that no two bricks are adjacent?

The answer to last week's POTW was $\boxed{550}$. Chrissy J. from the Bronx High School of Science submitted a solution which uses a clever use of recursion to calculate the answer without having to do casework on all the possibilities.

The number of ways to select one brick from each of the rows so that no two bricks are adjacent
can be computed by finding the number of valid possibilities of picking each brick, considering
the cases of the bricks picked from the row above.

In order to accomplish this, Chrissy writes in each brick the number of possible ways to select the bricks, under the condition that (1) the current brick must be selected, and (2) only the rows above the current brick are considered in addition to the current brick. By recursion, the number to be written in a brick $b$ is the sum of all the numbers written in bricks that are in the row immediately above and also not adjacent to $b$.

Filling in the numbers yields the following diagram:
The answer can be read off the bottom row as $140 + 108 + 105 + 104 + 93 = 550$.

In general, this technique is related to the idea of "dynamic programming" in computer science. Instead of brute-forcing through all possibilities, dynamic programming recognizes that certain subtasks are performed multiple times in an naïve calculation, and so stores the results of these subtasks so that they only need to be computed once.

On the other hand, Jeffrey H. used symmetry to reduce the problem from five rows to two pairs of rows by performing...

casework on the brick in the middle row; notice that we only need to count either the top or the bottom since there are the same number of ways to [select bricks] on [either side of the middle row]. Going from left to right [along the middle row], we get $13\cdot13+10\cdot10+10\cdot10+10\cdot10+9\cdot9=550$ ways.

In fact, note that in Chrissy's diagram, the sum of the squares of the middle row entries is the sum of the entries in the bottom row! As a challenge, can you use this idea to simplify the expression
\[\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2?\]

There aren't any archived problems of the week yet!