# Problem of the Week Archive

### 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!