Solution Set

Problem 1

a)

Let $2025=\frac{p}{q}$, where $p$ and $q$ are palindrome numbers.
Since $p=2025\times q$, $q$ must be an odd number because $p$ cannot end with 0
Then $p$ must begin with 5 and end with 5.
But for $p$ beginning with 5 divided by 2025, $\frac{p}{2025}$ must begin with 2, which leads to a contradiction.
$\boxed{\text{It is impossible to write 2025 as a ratio of two palindromes}}$

b)

Let $2026=\frac{p}{q}$, where $p$ and $q$ are palindrome numbers.
Since $p=2026\times q$, $p$ must end with 2, 4, 6, or 8 because 2026 is an even number.
Let us break down into 4 scenarios

• If $p$ begins with 2 and ends with 2, $q$ ends with 2 or 7. But for $p$ beginning with 2 divided by 2026, $\frac{p}{2026}$ must begin with 1 or 9, which leads to a contradiction.
• If $p$ begins with 4 and ends with 4, $q$ ends with 4 or 9. But for $p$ beginning with 4 divided by 2026, $\frac{p}{2026}$ must begin with 1 or 2, which leads to a contradiction.
• If $p$ begins with 6 and ends with 6, $q$ ends with 1 or 6. But for $p$ beginning with 6 divided by 2026, $\frac{p}{2026}$ must begin with 2 or 3, which leads to a contradiction.
• If $p$ begins with 8 and ends with 8, $q$ ends with 3 or 8. For $p$ beginning with 8 divided by 2026, $\frac{p}{2026}$ must begin with 3 or 4. Then $q$ must begin with 39 and end with 93 because $\frac{8}{2026}\ge 0.0039$. For $q$ ending with 93, $p$ must end with 18 and start with 81 because $2026\times 93=188418$ and the 2 last digits are not affected by $q$. So $q$ must begin with 399 and end with 993 because $\frac{81}{2026}\ge 0.0399$. For $q$ ending with 993, $p$ must end with 818 and start with 818 because $2026\times 993=2011818$ and the 3 last digits are not affected by $q$. But $q$ must begin with 4 and end with 4 because $\frac{818}{2026}\ge 0.4$, which leads to a contradiction.
  $\boxed{\text{It is impossible to write 2026 as a ratio of two palindromes}}$

Problem 2

a)

Base case: $k=3$ lines

When there are 3 subway lines, denoted $L_1,L_2,L_3$. Each pair of lines intersects at a station:

• $S_{1,2}$ is the intersection of $L_1$ and $L_2$
• $S_{1,3}$ is the intersection of $L_1$ and $L_3$
• $S_{2,3}$ is the intersection of $L_2$ and $L_3$
  In this configuration, the shortest path between any two stations requires at most 1 station:
• From $S_{1,2}$ to $S_{1,3}$, directly along $L_1$, 1 station
• From $S_{1,2}$ to $S_{2,3}$, directly along $L_2$, 1 station
• From $S_{1,3}$ to $S_{2,3}$, directly along $L_3$, 1 station
  Thus, for 3 lines, the distance between the furthest stations is 1 station.

Generalized hypothesis: $k$ lines

Suppose that for $k$ lines ($k\ge 3$), the distance between the furthest stations is $k-2$ stations. That is, the shortest path length between any two stations in a network of $k$ lines does not exceed $k-2$ stations.

Generalization Step: Adding to $k+1$ Lines

Now, we add a new line $L_{k+1}$ that intersects each of the existing $k$ lines at a new station. That is, there will be $k$ new stations:

• $S_{1,k+1}$ is the intersection of $L_1$ and $L_{k+1}$
• $S_{2,k+1}$ is the intersection of $L_2$ and $L_{k+1}$
• …
• $S_{k,k+1}$ is the intersection of $L_k$ and $L_{k+1}$
  Consider two stations: $S_{1,k+1}$ and $S_{k,k+1}$, and on $L_{k+1}$. Suppose the order of stations is $S_{1,k+1}-S_{2,k+1}-\cdots -S_{k,k+1}$. To get from $S_{1,k+1}$ to $S_{k,k+1}$ it is required to pass through a connection between $k-1$ stations,
  Attempting to go through other lines (e.g., from $L_1$ to some intermediate platform, then switching to other lines to end up at $L_k$ and $S_{k,k+1}$) does not result in a shorter path than $k-1$. This is because the direct paths on $L_{k+1}$ to $S_{1,k+1}$ and $S_{k,k+1}$ are $k-1$ stations, whereas the paths switched via other lines need to go through multiple additional stations and the path lengths do not decrease.
  Therefore, the shortest path from $S_{1,k+1}$ to $S_{k,k+1}$ is $k-1$ stations, i.e., the farthest distance of the entire network becomes $k-1$ stations (i.e., $k+1-2$) with the addition of $L_{k+1}$.

So for any $k$ subway line, the distance between the furthest stations is $k-2$ stations. Each time a subway line is added, the farthest distance of the network increases by one station.
For $k=15$, the distance between the furthest platforms is $15-2=13$ stations.
Angela can buy $\boxed{13}$ credits to guarantee that she can get from the airport to the museum.

b)

For curved subway lines, the structure of the subway system doesn’t essentially change (at worst it could just be that she passed the fewest number of stations but will spend more time). So the credits she buys $\boxed{\text{won’t change}}$

Problem 3

Notice that the binary tree cannot restore the order of greater than two numbers if the two numbers in all bottom pairs of leaf nodes are not consecutive numbers. This is because if three or more numbers can be restored in the correct order, they must contain a bottom pair.

(1)

So for every $n$, we only need to consider the arrangement $(1,2^{n-1}+1,2,2^{n-1}+\mathrm{2...}{2}^{n-1},2^{n-1}+2^{n-1})$to ensure that it can only restore the order of two numbers (e.g., for $n=3$: 1, 5, 2, 6, 3, 7, 4, 8 is one case). And it’s also easy to restore the order of two numbers, just by swapping the two numbers in the bottom left pair to restore the numbers 1 and 2.

(2)

First, for each arrangement of a height $n$ binary tree, it must be possible to place 2 consecutive numbers at the $2^{n-1}$ and $2^{n-1}+1$ places. That is, for a height $n-1$ binary tree, it must be possible to place a number at the first and the last place (except the two numbers are in a bottom pair, but if they are, it is already in order). Considering first the height 1 binary tree where the target number is located, we can place the number on the left or right by swapping it, then we consider the larger binary tree (height 2 binary tree), and it is also easy to place the number on the left or right again by swapping the larger binary tree, and keep this process, it is possible to place the numbers at the $2^{n-1}$ and $2^{n-1}+1$ places.

Therefore in the worst case scenario, for a perfect binary tree of height $n$, $\boxed{2}$ leaf nodes can be get into the correct position by shuffling

Problem 4

a)

According to the figure, we can prove that this 12-sided polyhedron exists by plotting the vertices.
First, we plot 8 points

$$A(1,1,1),B(1,-1,1),C(1,1,-1),D(1,-1,-1),$$ $$E(-1,1,1),F(-1,-1,1),G(-1,1,-1),H(-1,-1,-1),$$

Next, we plot 12 points

$$O\left(\frac{3-\sqrt{5}}{2},\frac{\sqrt{5}-1}{2},0\right),P\left(\frac{3-\sqrt{5}}{2},-\frac{\sqrt{5}-1}{2},0\right),$$ $$M\left(-\frac{3-\sqrt{5}}{2},\frac{\sqrt{5}-1}{2},0\right),N\left(-\frac{3-\sqrt{5}}{2},-\frac{\sqrt{5}-1}{2},0\right),$$ $$I\left(0,\frac{3-\sqrt{5}}{2},\frac{\sqrt{5}-1}{2}\right),J\left(0,\frac{3-\sqrt{5}}{2},-\frac{\sqrt{5}-1}{2}\right),$$ $$K\left(0,-\frac{3-\sqrt{5}}{2},\frac{\sqrt{5}-1}{2}\right),L\left(0,-\frac{3-\sqrt{5}}{2},-\frac{\sqrt{5}-1}{2}\right),$$ $$R\left(\frac{\sqrt{5}-1}{2},0,\frac{3-\sqrt{5}}{2}\right),Q\left(-\frac{\sqrt{5}-1}{2},0,\frac{3-\sqrt{5}}{2}\right),$$ $$T\left(\frac{\sqrt{5}-1}{2},0,-\frac{3-\sqrt{5}}{2}\right),S\left(-\frac{\sqrt{5}-1}{2},0,-\frac{3-\sqrt{5}}{2}\right),$$

We know that:

$$d=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2+(z_2-z_1{)}^2}$$

So:

$$\begin{array}{rl}AO& =\sqrt{\frac{3-\sqrt{5}}{2}+\frac{7-3\sqrt{5}}{2}+1}\\ & =\sqrt{6-2\sqrt{5}}\\ & =\sqrt{5}-1\end{array}$$

Similarly, all the edges of this polyhedron are calculated and all equals to $\sqrt{5}-1$

We use $A、B、O$ to construct a plane. We know that $\overrightarrow{AB}=(0,-2,0)$ and $\overrightarrow{AO}=(\frac{1-\sqrt{5}}{2},\frac{\sqrt{5}-3}{2},-1)$
So $\overrightarrow{n}=\overrightarrow{AB}\times \overrightarrow{AO}=(2,0,1-\sqrt{5})$ and the plane equation is:
$2x+(1-\sqrt{5})z+(\sqrt{5}-3)=0$
Then substitute the coordinate of point $P$ $\left(\frac{3-\sqrt{5}}{2},-\frac{\sqrt{5}-1}{2},0\right)$ into the equation：

$$2\cdot \frac{3-\sqrt{5}}{2}+(1-\sqrt{5})\cdot 0+(\sqrt{5}-3)=0$$

And substitute the coordinate of point $R$ $\left(\frac{\sqrt{5}-1}{2},0,\frac{3-\sqrt{5}}{2}\right)$：

$$2\cdot \frac{\sqrt{5}-1}{2}+(1-\sqrt{5})\cdot \frac{3-\sqrt{5}}{2}+(\sqrt{5}-3)=0$$

Therefore we proved that the five points $A,B,O,P,R$ are coplanar.
Similarly, all the faces can be proved that are coplanar.

According to the figure, we know that $\angle A=\angle C=36°$, $\angle D=\angle E=108°$ and $\angle B=252°=108°$.
Connect $EB$ and $DB$, we know that $\angle AEB=108°-\angle BED$ and $\angle ABE=180°-\angle A-\angle AEB=\angle BED+36°$. So $C,B,E$ are on a line, $CD=DE$ and $AB=AE$.
Similar on the other side, we got $AE=ED=DC=CB=BA$.

Back to the polyhedron, the faces are all crescents instead of pentagons considered by the coordinates. So the polyhedron $\boxed{\text{exists}}$.

b)

When we consider how to make a net of a polyhedron, the first thing to consider is which edge it unfolds from. In this case we can start with a face, and assuming that each point of this face is labeled the same as the part a). We first consider unfolding from AB to the next face, and then again from AB to the next face. Such a step can only be performed twice because the AB of the last face unfolded connects to the first face which we start from. So let’s switch and expand twice from BC and then again from AB. Repeat these steps until all faces have been unfolded. The complete net is shown above, and the polyhedron can be obtained by folding with the black lines.
Therefore, the net of the polyhedron $\boxed{\text{exists}}$.

Problem 5

a)

Assuming that each field in Infina is a coordinate, for all $k$, $k\in \mathbb{Z}$, $(0,k)$ is the farmer’s territory.
For $n=1$, only this infinitely long territory is needed.
For $n\ge 2$, it is only necessary to add $n-1$ “ray territories” to the $n=1$ territories. That is, there are $n-1$ different values of $r$, $r\in \mathbb{Z}$ , and $m$, where $m\in {\mathbb{Z}}^{+}$, $(m,2r)$ is also the farmer’s territory.

All that is needed to separate to $n$ territories is $n-1$ fences that separates the “straight line territory” from all “ray territories”.

b)

First, consider a $1\times 2$ finite territory that can be separated into at most 2 sub-territories, and the partitioning operation requires 1 fence.

We assume that any finite territory requires at least $n-1$ fences to be split into n sub territories.
Now consider a finite-area territory that has been separated into n sub-territories. Extend a $1\times 1$ territory adjacent to this territory, and we want this extended territory to have only one common edge with the original territory, so that only one additional fence is needed to split the extended territory again. So at least $n-1+1=n$ fences are needed to split the new territory into $n+1$ sub territories. For any other way of adjacency or any other size of extended territory, at least one fence is needed to separate them.

After we proved this, the theory is true for an infinite territory, so if a territory needs to be split into infinite parts, infinite fences are needed. So this operation cannot be complete.

c)

A territory is un-splittable if it has one end, as any finite fence cannot separate it into two infinite pieces (e.g., half-plane). In any partition of the grid (one end) into $k\ge 2$ infinite connected territories, each territory has finitely many ends. Territories with one end cannot split; those with $\ge 2$ can.

In the 2D grid, consider large squares $|m|,|n|\le N$. Territories intersecting the boundary extend to infinity. As N grows, at least two territories reach opposite “sides” (e.g., left and right), each with one end, while others between them have $\ge 2$ ends (separating role).

Thus, at least two farmers have territories with one end, unable to split.

Problem 6

a)

For each $n$, $H_n=4\times H_{n-1}+3$, where $H_0=3$. We can derive the generalized formula:
The length of $H_n$ is

$$\boxed{H_n=4^{n+1}-1}$$

b)

For $n=2^k-1$, it can be considered as each step of generating Hilbert Curve dividing each previous grid (consider as a block) into 4 sub-grids (blocks). And getting to the top right corner requires walking through all the grids from the previous path (except the top right corner one), as well as 3 sub-grids of the previous top right grids. Let $L_n$ be the length get to the top right corner, we can conclude that:
$L_{2^{k+1}-1}=4\times (L_{2^k-1}+1)-2$
(we have to subtract 1 because it counts the length of the path traveled between blocks)
Then we can derive the generalized formula:

$$L_{2^k-1}=\frac{2\times 4^k+1}{3}-1$$

Who’s simplified form is:

$$L_{2^k-1}=\frac{2(4^k-1)}{3}$$

For $n=2^k$:

$$L_n=\frac{2(4^k-1)}{3}+L_{2^{k+1}-1}-2L_{2^k-1}$$

Who’s simplified form is:

$$\begin{array}{rl}{L}_n& =\frac{2(4^{k+1}-1)}{3}-\frac{2(4^k-1)}{3}\\ & =\frac{2(4^{k+1}-4^k)}{3}\\ & =2\times 4^k\end{array}$$

Or we can write like this:

$$2\times 4^{{\log }_{2}n}$$

For every $n$, we suggest $n=2^k+m$, where $m\le n^{k-1}$:

$$L_n=2\times 4^{\lfloor {\log }_{2}n\rfloor }+L_m$$

It can be simplified as:
Each iteration decomposes $n$ into $2^k+m$, where $k$ is the largest integer such that $2^k\le n$. In this case, $m=n-2^k$, and it satisfies $m\le n^{k-1}$ (which automatically holds when $k\ge 2$). Each recursion contributes a term of $2\times 4^k$, and ultimately, $L_n$ is the sum of these terms across all decomposition steps. Consider the binary representation of $n$ as a quaternary (base-4) number and multiply by 2, then $L_n$ can be represented by:

$$L_n=2\times \text{decimal value of the quaternary representation of binary }n$$

Or the generalized form:

$$\boxed{L_n=2\times \sum _{k=0}^{\lfloor {\log }_{2}n\rfloor }\left(\lfloor \frac{n}{2^k}\rfloor \mathrm{mod}2\right)\cdot 4^k}$$

c)

We consider positions on the track to be quadratic numbers. Position $s=a_0+a_1\cdot 4+a_2\cdot 4^2+\dots$ ($a_i\in \{0,1,2,3\}$) and each quadratic bit corresponds to the choice of which sub-quadrant ($H_{n-1}$) of $H_n$ is chosen. It is known that Anna and Benny and Benny and Charlotte’s speed difference is $1m/s$, distance $\Delta s=t$. Anna and Charlotte’s speed difference is $2m/s$, distance $\Delta s=2t$.

When the distance along the track between the two person $\Delta s=4^n$, they are each in a neighboring sub-quadrant of the $H_n$. At the $H_1$ level (covering the $3\times 3$ region), two people may be located in the adjacent $1\times 1$ sub-quadrant ($H_0$) with a net distance of $\le 1$ meters when the difference in their positions is 4 meters. At the $H_2$ level (covering the $7\times 7$ region), with a difference of 16 ($4^2$) meters , it may be located in the adjacent $3\times 3$ sub-quadrant, with a net distance of $\le 3$ meters, and the distance will be considered agin within the smaller sub-quadrant.

They enter a neighboring sub-quadrant of $H_n$, at which point the coordinate difference corresponds to 1 meter at the bottom ($H_0$) level. As $n\to \infty$, this happens infinitely often, so they will approach within 1 meter an infinite number of times.
But for Anna and Charlotte, the position difference $\Delta s=2t$. When $t=4^n$, $\Delta s=2\cdot 4^n$. They go into different sub-quadrants of the $H_n$, but since $\Delta s$ is not a power of 4, the two people cannot be within neighboring sub-quadrants.
The $2\cdot 4^n$ distance would cause them to be in sub-quadrants that are further apart (e.g., diagonal positions), with net distances of at least $\sqrt{2}\cdot 2^n>1$ meters.

So $\boxed{\text{Anna and Benny}}$ and $\boxed{\text{Benny and Charlotte}}$ will pass within 1 meter infinitely often.

d)

Since the difference in distance traveled is always the same for two people, we only need to find a difference in distance traveled and there are no shapes can construct a path of that length (since the question doesn’t ask me to solve for the generalized solution, which is doable but will not go into it, the goal is just to find some solutions).

First we look at $H_0$ and $H_1$. In $H_0$ the difference in distance traveled is 3 meets the statement; In $H_1$ the difference in distance traveled is 3, 5, 11, 13 meets the statement. Here we already be able to see that the composition of the new conforming distances is a composite of the previous constructions.
As shown in the figure, for the 3 in $H_1$, the distance composed by the two $H_0$s’ edge form a new shape (we call it form A). For 5 in $H_1$, it is the composition of two differently oriented $H^0$s’ that forms a new shape (we call it form B). For the last two cases, 11 and 13, it is a new shape made up of two $H^0$s’ in the same orientation (we call it form C).

For each step $H_n$, we can figure out how many new forms A, B, and C it generates.

• For form A, each step generates $3\times 2^{n-2}$ shapes
• For form B, each step generates $2^{n-1}$ shapes
• For form C, each step generates $2^n$ shapes.
  Each form gradually generates a larger distance than the previous ones’, so we just need to find a number that is not covered by all the forms A, B, and C within a certain range.

By enumeration, as of $H_3$, the numbers generated by form A are, 3, 7, 9, 11, 29, 31, 33, 39, 41, 43; the numbers generated by form B are, 5, 19, 21, 75, 79, 81, 85; and the numbers generated by form C are, 11, 13, 43, 45, 51, 53,… (a bit many, omitted here).
We can immediately see that the numbers $\boxed{15,17,23,25,27,35,37,...}$are not covered. These numbers are part of the answer (I’m sure there must be a generalized formula, but only some answers are listed here).