Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 USAMO Problems/Problem 3"

(Created page with "Let <math>m</math> be a positive integer. A triangulation of a polygon is <math>m</math>-balanced if its triangles can be colored with <math>m</math> colors in such a way that...")
 
 
Line 1: Line 1:
 
Let <math>m</math> be a positive integer. A triangulation of a polygon is <math>m</math>-balanced if its triangles can be colored with <math>m</math> colors in such a way that the sum of the areas of all triangles of the same color is the same for each of the <math>m</math> colors. Find all positive integers <math>n</math> for which there exists an <math>m</math>-balanced triangulation of a regular <math>n</math>-gon.
 
Let <math>m</math> be a positive integer. A triangulation of a polygon is <math>m</math>-balanced if its triangles can be colored with <math>m</math> colors in such a way that the sum of the areas of all triangles of the same color is the same for each of the <math>m</math> colors. Find all positive integers <math>n</math> for which there exists an <math>m</math>-balanced triangulation of a regular <math>n</math>-gon.
 
Note: A triangulation of a convex polygon <math>\mathcal{P}</math> with <math>n \geq 3</math> sides is any partitioning of <math>\mathcal{P}</math> into <math>n-2</math> triangles by <math>n-3</math> diagonals of <math>\mathcal{P}</math> that do not intersect in the polygon's interior.
 
Note: A triangulation of a convex polygon <math>\mathcal{P}</math> with <math>n \geq 3</math> sides is any partitioning of <math>\mathcal{P}</math> into <math>n-2</math> triangles by <math>n-3</math> diagonals of <math>\mathcal{P}</math> that do not intersect in the polygon's interior.
 +
 +
==Solution 1==
 +
The answer is if and only if <math>m</math> is a proper divisor of <math>n</math>.
 +
 +
We represent the vertices of the regular <math>n</math>-gon using complex numbers. Let <math>\omega = \exp(2\pi i/n)</math> be a primitive <math>n</math>-th root of unity, and label the vertices as <math>1, \omega, \omega^2, \ldots, \omega^{n-1}</math>.
 +
 +
Key Lemma:
 +
 +
The triangle with vertices <math>\omega^k, \omega^{k+a}, \omega^{k+b}</math> has signed area:
 +
 +
<cmath>T(a, b) := \frac{(\omega^a - 1)(\omega^b - 1)(\omega^{-b} - \omega^{-a})}{4i}</cmath>
 +
 +
Proof of Lemma:
 +
 +
We can rotate by <math>\omega^{-k}</math> to assume without loss of generality that <math>k = 0</math>. Then we apply the complex shoelace formula to the triangle with vertices <math>1, \omega^a, \omega^b</math>:
 +
 +
<cmath>\frac{i}{4} \det \begin{bmatrix} 1 & 1 & 1 \\ \omega^a & \omega^{-a} & 1 \\ \omega^b & \omega^{-b} & 1 \end{bmatrix} = \frac{i}{4} \det \begin{bmatrix} 0 & 0 & 1 \\ \omega^a - 1 & \omega^{-a} - 1 & 1 \\ \omega^b - 1 & \omega^{-b} - 1 & 1 \end{bmatrix}</cmath>
 +
 +
which simplifies to the expression for <math>T(a, b)</math> above.
 +
 +
Construction (Sufficiency):
 +
 +
To construct a valid triangulation and coloring when <math>m</math> divides <math>n</math>, we draw all the diagonals from vertex 1, and then color the resulting triangles with the <math>m</math> colors in cyclic order.
 +
 +
For example, when <math>n = 9</math> and <math>m = 3</math>, we get a coloring with red, green, blue as shown in the image, repeating cyclically.
 +
 +
To prove this works, we fix a residue <math>r \mod m</math> corresponding to one of the colors. Then the total area of triangles with this color is:
 +
 +
<cmath>\sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} \text{Area}(\omega^0, \omega^j, \omega^{j+1}) = \sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} T(j, j+1)</cmath>
 +
 +
After algebraic manipulation:
 +
 +
<cmath>= \frac{\omega - 1}{4i} \left(\frac{n}{m}(1 + \omega^{-1}) + \sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} (\omega^{-1-j} - \omega^j)\right)</cmath>
 +
 +
When <math>m</math> divides <math>n</math>, we can show that the inner sum vanishes, and the total area of each color equals:
 +
 +
<cmath>\sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} \text{Area}(\omega^0, \omega^j, \omega^{j+1}) = \frac{n}{m} \cdot \frac{\omega - \omega^{-1}}{4i}</cmath>
 +
 +
Since the right-hand side does not depend on the residue <math>r</math>, this shows all colors have equal area.
 +
 +
Necessity:
 +
 +
To prove that <math>m</math> must divide <math>n</math>, we note that if there were a valid triangulation and coloring, the total area of each color would equal:
 +
 +
<cmath>S := \frac{n}{m} \cdot \frac{\omega - \omega^{-1}}{4i}</cmath>
 +
 +
We then prove the following claim:
 +
 +
The number <math>4i \cdot S</math> is not an algebraic integer when <math>m \nmid n</math>.
 +
 +
This can be shown using the fact that <math>K = \mathbb{Q}(\omega)</math> is a number field with ring of integers <math>\mathcal{O}_K = \mathbb{Z}[\omega]</math>. We demonstrate that:
 +
 +
<cmath>\omega \cdot 4i \cdot S = \frac{n}{m}\omega^2 - \frac{n}{m}</cmath>
 +
 +
is not an algebraic integer when <math>m</math> doesn't divide <math>n</math> because <math>\frac{n}{m} \not\in \mathbb{Z}</math>.
 +
 +
However, for any triangle in our construction, <math>4i \cdot T(a,b)</math> is always an algebraic integer. Since a finite sum of algebraic integers is also an algebraic integer, the sum of expressions of the form <math>4i \cdot T(a,b)</math> can never equal <math>4i \cdot S</math> unless <math>m</math> divides <math>n</math>.
 +
 +
We can also show this directly by noting that <math>T(a,b)</math> is always divisible by <math>\frac{\omega - \omega^{-1}}{4i}</math>, which means we need <math>\frac{n}{m}</math> to be an algebraic integer. A rational number is an algebraic integer if and only if it's a rational integer, so <math>\frac{n}{m}</math> is an algebraic integer exactly when <math>m</math> divides <math>n</math>.
 +
 +
Therefore, a valid triangulation and coloring exists if and only if <math>m</math> is a proper divisor of <math>n</math>.
 +
 +
~ brandonyee

Latest revision as of 16:41, 7 March 2025

Let $m$ be a positive integer. A triangulation of a polygon is $m$-balanced if its triangles can be colored with $m$ colors in such a way that the sum of the areas of all triangles of the same color is the same for each of the $m$ colors. Find all positive integers $n$ for which there exists an $m$-balanced triangulation of a regular $n$-gon. Note: A triangulation of a convex polygon $\mathcal{P}$ with $n \geq 3$ sides is any partitioning of $\mathcal{P}$ into $n-2$ triangles by $n-3$ diagonals of $\mathcal{P}$ that do not intersect in the polygon's interior.

Solution 1

The answer is if and only if $m$ is a proper divisor of $n$.

We represent the vertices of the regular $n$-gon using complex numbers. Let $\omega = \exp(2\pi i/n)$ be a primitive $n$-th root of unity, and label the vertices as $1, \omega, \omega^2, \ldots, \omega^{n-1}$.

Key Lemma:

The triangle with vertices $\omega^k, \omega^{k+a}, \omega^{k+b}$ has signed area:

\[T(a, b) := \frac{(\omega^a - 1)(\omega^b - 1)(\omega^{-b} - \omega^{-a})}{4i}\]

Proof of Lemma:

We can rotate by $\omega^{-k}$ to assume without loss of generality that $k = 0$. Then we apply the complex shoelace formula to the triangle with vertices $1, \omega^a, \omega^b$:

\[\frac{i}{4} \det \begin{bmatrix} 1 & 1 & 1 \\ \omega^a & \omega^{-a} & 1 \\ \omega^b & \omega^{-b} & 1 \end{bmatrix} = \frac{i}{4} \det \begin{bmatrix} 0 & 0 & 1 \\ \omega^a - 1 & \omega^{-a} - 1 & 1 \\ \omega^b - 1 & \omega^{-b} - 1 & 1 \end{bmatrix}\]

which simplifies to the expression for $T(a, b)$ above.

Construction (Sufficiency):

To construct a valid triangulation and coloring when $m$ divides $n$, we draw all the diagonals from vertex 1, and then color the resulting triangles with the $m$ colors in cyclic order.

For example, when $n = 9$ and $m = 3$, we get a coloring with red, green, blue as shown in the image, repeating cyclically.

To prove this works, we fix a residue $r \mod m$ corresponding to one of the colors. Then the total area of triangles with this color is:

\[\sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} \text{Area}(\omega^0, \omega^j, \omega^{j+1}) = \sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} T(j, j+1)\]

After algebraic manipulation:

\[= \frac{\omega - 1}{4i} \left(\frac{n}{m}(1 + \omega^{-1}) + \sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} (\omega^{-1-j} - \omega^j)\right)\]

When $m$ divides $n$, we can show that the inner sum vanishes, and the total area of each color equals:

\[\sum_{\substack{0 \leq j < n \\ j \equiv r \mod m}} \text{Area}(\omega^0, \omega^j, \omega^{j+1}) = \frac{n}{m} \cdot \frac{\omega - \omega^{-1}}{4i}\]

Since the right-hand side does not depend on the residue $r$, this shows all colors have equal area.

Necessity:

To prove that $m$ must divide $n$, we note that if there were a valid triangulation and coloring, the total area of each color would equal:

\[S := \frac{n}{m} \cdot \frac{\omega - \omega^{-1}}{4i}\]

We then prove the following claim:

The number $4i \cdot S$ is not an algebraic integer when $m \nmid n$.

This can be shown using the fact that $K = \mathbb{Q}(\omega)$ is a number field with ring of integers $\mathcal{O}_K = \mathbb{Z}[\omega]$. We demonstrate that:

\[\omega \cdot 4i \cdot S = \frac{n}{m}\omega^2 - \frac{n}{m}\]

is not an algebraic integer when $m$ doesn't divide $n$ because $\frac{n}{m} \not\in \mathbb{Z}$.

However, for any triangle in our construction, $4i \cdot T(a,b)$ is always an algebraic integer. Since a finite sum of algebraic integers is also an algebraic integer, the sum of expressions of the form $4i \cdot T(a,b)$ can never equal $4i \cdot S$ unless $m$ divides $n$.

We can also show this directly by noting that $T(a,b)$ is always divisible by $\frac{\omega - \omega^{-1}}{4i}$, which means we need $\frac{n}{m}$ to be an algebraic integer. A rational number is an algebraic integer if and only if it's a rational integer, so $\frac{n}{m}$ is an algebraic integer exactly when $m$ divides $n$.

Therefore, a valid triangulation and coloring exists if and only if $m$ is a proper divisor of $n$.

~ brandonyee

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_USAMO_Problems/Problem_3&oldid=244496"