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 \ge 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. Proposed by Krit Boonsiriseth
Problem
Source: USAMO 2024/3
Tags: AMC, USA(J)MO, USAMO, geometry
20.03.2024 07:22
pretty sure the condition was $m|n$ and $m < n$ but im bad at math
20.03.2024 07:36
I saw a quick solution in math puzzle [多边形面积形如 n/2(w-1/w);每一个小块的面积都是(w-1/w)/2 的代数整数倍,因此n/m 是代数整数,也是整数.n=m 显然不行.每一块面积形如(w^x-w^(-x))/2的和,每一个都是(w-1/w)/2的w的多项式倍,这是代数整数.]
20.03.2024 07:38
Super clean.
20.03.2024 07:40
If $m < n, m | n$ take a vertex-centered triangulation and label the triangles $1, 2, ... m$ repeating in clockwise order. If $m \not | n$ then problem reduces to showing $\frac{2n}{m} \sin \frac{2\pi}{n}$ algebraic integer implies $\frac{n}{m}$ is an integer, easy by citing that the ring of integers of $Q(\omega)$ is $Z[\omega]$, where $\omega$ is a primitive $n$th root of unity.
20.03.2024 07:41
Don’t tell me this was a geo…
20.03.2024 07:46
Solved with mira74 and Th3Numb3rThr33. The answer is all \(m\mid n\) with \(m<n\). Construction: Assume \(m\mid n\) but \(m<n\). Let the polygon be \(V_0V_1\cdots V_{n-1}\), and let \(O\) be its center. Take the triangulation in which every diagonal passes through \(V_0\). [asy][asy] size(5cm); defaultpen(fontsize(10pt)); int n=12; for (int i=2; i<n; i+=3) { fill(dir(90)--dir(90+360/n*i)--dir(90+360/n*(i+1))--cycle,cyan+white+white); } for (int i=0; i<n; i+=1) { dot(dir(90+360/n*i)); draw(dir(90+360/n*i)--dir(90+360/n*(i+1))); draw(dir(90)--dir(90+360/n*i)); } [/asy][/asy] Then we can check that taking every \(m\)th triangle in this triangulation gives \(1/m\)th of the area, which suffices. Indeed, for each \(a\), \begin{align*} \sum_{i\equiv a\bmod m}\operatorname{Area}(\triangle V_0V_iV_{i+1}) &=\sum_{i\equiv a\bmod m}\operatorname{Area}(\triangle V_0V_1V_{i+1})\\ &=\frac{V_0V_1}2\sum_{i\equiv a\bmod m}\operatorname{dist}(V_{i+1},\overline{V_0V_1})\\ &=\frac{V_0V_1}2\cdot\frac nm\operatorname{dist}(O,\overline{V_0V_1})\\ &=\frac1m\operatorname{Area}(V_0\cdots V_{n-1}). \end{align*} Proof of necessity: Let the circumradius be 1. Assume an \(m\)-balanced configuration exists. Claim: For any \(i\), \(j\), the area of \(\triangle OV_iV_j\) is \(\frac12\sin\frac{2\pi}n\) times an algebraic integer. Proof. Let \(\omega=e^{2\pi i/n}\). We have \begin{align*} \operatorname{Area}(\triangle OV_iV_j) &=\frac12\sin\frac{2\pi(j-i)}n=\frac1{4i}\left( \omega^{j-i}-\omega^{i-j} \right)\\ &=\frac1{4i}\left( \omega-\omega^{-1} \right) \left( \omega^{j-i-2}+\omega^{j-i-4} +\cdots+\omega^{i-j+2}\right)\\ &=\frac12\sin\frac{2\pi}n \left( \omega^{j-i-2}+\omega^{j-i-4} +\cdots+\omega^{i-j+2}\right). \end{align*}\(\blacksquare\) Claim: For any \(i\), \(j\), \(k\), the area of \(\triangle V_iV_jV_k\) is \(\frac12\sin\frac{2\pi}n\) times an algebraic integer. Proof. We have \[\operatorname{Area}(\triangle V_iV_jV_k) =\pm\operatorname{Area}(\triangle OV_iV_j) \pm\operatorname{Area}(\triangle OV_jV_k) \pm\operatorname{Area}(\triangle OV_kV_i).\]\(\blacksquare\) Assuming the existence of an \(m\)-balanced triangulation, we know from the above claim that every \(m\)-balanced triangulation must have area \(\frac12\sin\frac{2\pi}n\alpha\) for some algebraic integer \(\alpha\), so \[\frac n2\sin\frac{2\pi}n=\operatorname{Area}(V_1\cdots V_n)=\frac m2\sin\frac{2\pi}n\alpha.\]It follows that \(n/m=\alpha\). But \(n/m\) is rational, so it is an integer. This finishes (since of course \(m\ne n\))\(.\)
20.03.2024 09:21
Is there a way to solve this without group theory? I doubt the US would publish a problem without an elementary solution.
20.03.2024 14:43
bhan2025 wrote: I doubt the US would publish a problem without an elementary solution. Why? I think algebraic integers are fair game, and even kind of standard.
20.03.2024 16:16
Alternate proof for necessity which I found during exam. (dammit how did i not find construction?? how many points will this get) Inscribe the regular $n$-gon in a circle of radius $\sqrt2$. For a triangle $ABC$, let $\angle BOC = \frac{2a\pi}n$ and similarly for $\angle BOC$ and $\angle COA$. Let $\zeta_n = e^{2\pi i/n}$, then we obtain \[[ABC] = \sin \frac{2a\pi}n + \sin \frac{2b\pi}n + \sin \frac{2c\pi}n = \Im (\zeta_n^a + \zeta_n^b + \zeta_n^c).\]That is, the sum of areas of triangles will always be the imaginary part of some number in the ring $\mathbb Z[\zeta_n]$. The total area of the polygon is $\Im (n\zeta_n)$, so it follows that $\frac nm \zeta_n + k$ is in $\mathbb Z[\zeta_n]$ for some real number $k$. We complex conjugate it to obtain $\frac nm \zeta_n^{-1} + k\in \mathbb Z[\zeta_n]$, therefore $\frac nm (\zeta_n^2 - 1)\in \mathbb Z[\zeta_n]$. Observe that $\mathbb Z[\zeta_n]$ is a free $\mathbb Z$-module with basis $\{1,\zeta_n,\dots,\zeta_n^{\varphi(n)-1}\}$, and if $\varphi(n) > 2$, then it immediately follows that $m$ divides $n$. If $\varphi(n) = 2$, then $n=3,4,6$, and we can also quickly verify that $m\mid n$.
20.03.2024 17:15
wrote something about n/m = integer polynomial in $\cos \frac{2\pi}{n}$ how many points? raging bc i definitely could have solved this if i had known about algebraic integers ;-; i think this is just because i have zero polynomial experience in general usa stop putting trivial poly p3s on tests please (2021 USAMO 3, 2024 TST 3, 2024 USAMO 3)
23.03.2024 00:32
The answer is all $m \mid n$, except for $m=n$ which obviously fails. Construction: Let our polygon $\mathcal{P}$ be $V_0V_1\ldots V_{n-1}$, and take indices modulo $n$. Draw every diagonal through $V_0$ and then color the triangles $1,\ldots,m$ in order and extend this periodically. If the side length of $\mathcal{P}$ is WLOG $1$, then the sum of areas of the triangles of color $k$ is $\tfrac{1}{2}(d(V_0,\overline{V_kV_{k+1}})+d(V_0,\overline{V_{k+m}V_{k+m+1}})+\cdots)$. Now extend $\overline{V_kV_{k+1}},\overline{V_{k+m}V_{k+m+1}},\ldots$ to form either a regular $\tfrac{n}{m}$-gon $\mathcal{Q}_k$ or two parallel lines (if $n=2m$). In the former case, note that all the $\mathcal{Q}_k$ are clearly congruent, and the sum of the distances from a point in the interior of a regular polygon $\mathcal{Q}$ to its sides is constant, since it's equal to the area of $\mathcal{Q}$ divided by half its side length by splitting into triangles. In the latter, note that the sum of the distances from two parallel lines to a point between them is obviously constant. Since $V_0$ lies in the interior of all $\mathcal{Q}_k$ or between each pair of parallel lines, it follows that $d(V_0,\overline{V_kV_{k+1}})+d(V_0,\overline{V_{k+m}V_{k+m+1}})+\cdots$ is constant as well. [asy][asy] size(5cm); defaultpen(fontsize(10pt)); path s1=(10*dir(90+40*4)-9*dir(90+40*5))--(10*dir(90+40*5)-9*dir(90+40*4)); path s2=(10*dir(90+40)-9*dir(90+40*2))--(10*dir(90+40*2)-9*dir(90+40)); path s3=(10*dir(90+40*7)-9*dir(90+40*8))--(10*dir(90+40*8)-9*dir(90+40*7)); pair[] X = intersectionpoints(s1,s2); pair[] Y = intersectionpoints(s2,s3); pair[] Z = intersectionpoints(s3,s1); dot(X[0]); dot(Y[0]); dot(Z[0]); draw(X[0]--Y[0]--Z[0]--cycle,blue+white); int n=9; for (int i=1; i<n-1; i+=3) { fill(dir(90)--dir(90+360/n*i)--dir(90+360/n*(i+1))--cycle,red+white+white); } for (int i=0; i<n; i+=1) { dot(dir(90+360/n*i)); draw(dir(90+360/n*i)--dir(90+360/n*(i+1))); draw(dir(90)--dir(90+360/n*i)); } draw(dir(90)--foot(dir(90),X[0],Y[0]),green+white); draw(dir(90)--foot(dir(90),Z[0],Y[0]),green+white); draw(dir(90)--foot(dir(90),X[0],Z[0]),green+white); dot(dir(90)); [/asy][/asy] Necessity: We prove that $m \mid n$ is necessary. Suppose that some $m$-balanced triangulation of $\mathcal{P}$ exists. WLOG let $\mathcal{P}$ be inscribed in the unit circle and let its center be $O$, with its vertices at the $n$-th roots of unity, and let $\omega=e^{2\pi i/n}$. By the sine area formula we have $[OV_0V_1]=\tfrac{1}{2}\sin \tfrac{2\pi}{n}$, so $[\mathcal{P}]=\tfrac{n}{2}\sin \tfrac{2\pi}{n}$ and the sum of triangle areas of any given color is $\tfrac{n}{2m}\sin \tfrac{2\pi}{n}$. On the other hand, each triangle in a triangulation has vertices at roots of unity, and we have $$4i[V_iV_jV_k]=-\begin{vmatrix}\omega^i&\omega^{-i}&1\\\omega^j&\omega^{-j}&1\\\omega^k&\omega^{-k}&1\end{vmatrix} \in \overline{\mathbb{Z}},$$since $\overline{\mathbb{Z}}$ is closed under addition and multiplication and $\omega^\bullet \in \overline{\mathbb{Z}}$. Hence we require $\tfrac{n}{m}2i\sin \tfrac{2\pi}{n} \in \overline{\mathbb{Z}}$. Note that $2i\sin \tfrac{2\pi}{n}=\omega-\omega^{-1} \in \overline{\mathbb{Z}}$. Consider the monic polynomial with roots $2i\sin \tfrac{2k\pi}{n}=\omega^k-\omega^{-k}=\omega^k-\omega^{(n-1)k}$ for $0 \leq k \leq n-1$; I claim it is in $\mathbb{Z}[x]$. Indeed, note that every elementary symmetric sum of the $\omega^k-\omega^{(n-1)k}$ can be thought of as a symmetric integer polynomial in $\omega^0,\ldots,\omega^{n-1}$, which by the fundamental theorem of symmetric polynomials can be written as an integer polynomial in the elementary symmetric sums of $\omega^0,\ldots,\omega^{n-1}$, and is therefore an integer by Vieta's on $x^n-1$, so by Vieta's again the claim follows. This implies that the minimal polynomial $P$ of $2i\sin \tfrac{2\pi}{n}$ has only roots of the form $2i\sin \tfrac{2k\pi}{n}$. Since $|2i \sin \tfrac{2k\pi}{n}| \leq 2$ for all $k$, and equality holds only when $k=\tfrac{n}{4},\tfrac{3n}{4}$, it follows that its constant term $c$ has absolute value at most $2^{\deg P}$, with equality only when $n=4$; also note that it is clearly nonzero, since minimal polynomials are irreducible. We now prove the following. Lemma: Let $z \in \overline{\mathbb{Z}}$ and let $0 \neq q \in \mathbb{Q}$ such that $qz \in \overline{\mathbb{Z}}$ as well. If $A$ is the minimal polynomial of $z$ then $q^{\deg A}A(\tfrac{x}{q}) \in \mathbb{Z}[x]$. Proof: Obviously we have $q^{\deg A}A(\tfrac{x}{q}) \in \mathbb{Q}[x]$. Let $B$ be the minimal polynomial of $qz$. Then $B(x)$ and $q^{\deg A}A(\tfrac{x}{q})$ share a root—namely $qz$—but should both be irreducible, hence they are constant multiples of each other. Since $A$ is monic, so is $q^{\deg A}A(\tfrac{x}{q})$, so we conclude $A \equiv B \in \mathbb{Z}[x]$, done. $\blacksquare$ The lemma implies that $(\tfrac{n}{m})^{\deg P}P(\tfrac{m}{n}) \in \mathbb{Z}[x]$, so $c(\tfrac{n}{m})^{\deg P}$ should be an integer. If $m \nmid n$, this implies some prime $p$ with $\nu_p(\tfrac{n}{m})<0$ has $p^{\deg P} \mid c$, but if $0<|c|<2^{\deg P}$ this is absurd. Finally, if $n=4$ then we evidently require $m \in \{1,2\}$, so we have $m \mid n$ always. $\blacksquare$
15.04.2024 03:36
The answer is if and only if $m$ is a proper divisor of $n$. Throughout this solution, we let $\omega = \exp\left( 2 \pi i / n \right)$ and let the regular $n$-gon have vertices $1$, $\omega$, \dots, $\omega^{n-1}$. We cache the following frequent calculation: Lemma: The triangle with vertices $\omega^k$, $\omega^{k+a}$, $\omega^{k+b}$ has signed area \[ T(a,b) \coloneqq \frac{(\omega^a-1)(\omega^b-1)(\omega^{-b}-\omega^{-a})}{4i}. \]Proof. Rotate by $\omega^{-k}$ to assume WLOG that $k=0$. Apply complex shoelace to the triangles with vertices $1$, $\omega^a$, $\omega^b$ to get \[ \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 equals the above. $\blacksquare$ Construction. It suffices to actually just take all the diagonals from the vertex $1$, and then color the triangles with the $m$ colors in cyclic order. For example, when $n = 9$ and $m = 3$, a coloring with red, green, blue would be: [asy][asy] size(6cm); pair A(int i) { return dir(40*i); } pen[] fillcolors = {palered, palegreen, palecyan}; pen[] labelcolors = {brown, darkgreen, deepblue}; string[] labels = {"R", "Green", "Blue", "Red", "Green", "Blue", "R"}; for (int i=0; i<=6; ++i) { filldraw(A(0)--A(i+1)--A(i+2)--cycle, fillcolors[i-3*(i#3)], black+1.5); label(labels[i], incenter(A(0),A(i+1),A(i+2)), labelcolors[i-3*(i#3)] + fontsize(14pt)); } [/asy][/asy] To see this works one can just do the shoelace calculation: fix a residue $r \bmod m$ corresponding to one of the colors. Then \begin{align*} \sum_{\substack{0 \le j < m \\ j \equiv r \bmod m}} \operatorname{Area}(\omega^0, \omega^j, \omega^{j+1}) &= \sum_{\substack{0 \le j < m \\ j \equiv r \bmod m}} T(j, j+1) \\ &= \sum_{\substack{0 \le j < m \\ j \equiv r \bmod m}} \frac{(\omega^j-1)(\omega^{j+1}-1)(\omega^{-(j+1)}-\omega^{-j})}{4i} \\ &= \frac{\omega-1}{4i} \sum_{\substack{0 \le j < m \\ j \equiv r \bmod m}} (\omega^{-j}-1)(\omega^j-\omega^{-1}) \\ &= \frac{\omega-1}{4i} \left( \frac{n}{m} \left( 1 + \omega^{-1} \right) + \sum_{\substack{0 \le j < m \\ j \equiv r \bmod m}} (\omega^{-j}-\omega^j) \right). \end{align*}(We allow degenerate triangles where $j \in \{0,m-1\}$ with area zero to simplify the notation above.) However, if $m$ is a proper divisor of $m$, then $\sum_j \omega^j = \omega^r(1+\omega^m+\omega^{2m}+\dots+\omega^{n-m}) = 0$. For the same reason, $\sum_j \omega^{-j} = 0$. So the inner sum vanishes, and the total area of this color equals \[ \sum_{\substack{0 \le j < m \\ j \equiv r \bmod m}} \operatorname{Area}(\omega^0, \omega^j, \omega^{j+1}) = \frac nm \frac{(\omega-1)(\omega^{-1}+1)}{4i} = \frac nm \cdot \frac{\omega-\omega^{-1}}{4i} . \]Because the right-hand side does not depend on the residue $r$, this shows all colors have equal area. Proof of necessity. It's obvious that $m < n$ (in fact $m \le n-2$). So we focus on just showing $m \mid n$. Repeating the same calculation as above, we find that if there was a valid triangulation and coloring, the total area of each color would equal \[ S \coloneqq \frac nm \cdot \frac{\omega-\omega^{-1}}{4i}. \]However: Claim: The number $4i \cdot S$ is not an algebraic integer when $m \nmid n$. Proof. This is easiest to see if one knows the advanced result that $K \coloneqq {\mathbb Q}(\omega)$ is a number field whose ring of integers is known to be $\mathcal{O}_K = {\mathbb Z}[\omega]$, in which case it follows right away. $\blacksquare$ Remark: We spell out the details in the proof a bit more explicitly here. It's enough to show that $\omega \cdot 4i \cdot S = \frac nm \omega^2 - \frac nm$ is not an algebraic integer for completeness. Take $K = \mathbb Q(\omega)$ of degree $d \coloneqq \varphi(n) \ge 2$; as a $\mathbb Q$-module, it obeys $K = \mathbb Q \oplus \omega \mathbb Q \oplus \dots \oplus \omega^{d-1} \mathbb Q$. The theorem we are quoting is that, as ${\mathbb Z}$-modules, we have $\mathcal{O}_K = \mathbb Z[\omega] = \mathbb Z \oplus \omega \mathbb Z \oplus \dots \oplus \omega^{d-1} \mathbb Z$ i.e.\ $\mathcal{O}_K$ contains exactly those numbers in $K$ for which the canonical $\mathbb Q$-coefficients happen to be integers. And $\omega \cdot 4i \cdot S$ fails this criteria, since $\frac nm \notin {\mathbb Z}$. However, for any $a$ and $b$, the number \[ 4i \cdot T(a,b) = (\omega^a-1)(\omega^b-1)(\omega^{-b}-\omega^{-a}) \]is 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)$ will never equal $4i \cdot S$. Remark: If one wants to avoid citing the fact that $\mathcal{O}_K = {\mathbb Z}[\omega]$, then one can instead note that $T(a,b)$ is actually always divisible by $(\omega-1)(\omega^{-1}+1) = \omega - \omega^{-1}$ over the algebraic integers (at least one of $\{\omega^a-1, \omega^b-1, \omega^{-a} - \omega^{-b}\}$ is a multiple of $\omega+1$, by casework on $a,b \bmod 2$). Then one using $\frac{4i}{(\omega-1)(\omega^{-1}+1)}$ as the scaling factor instead of $4i$, one sees that we actually need $\frac nm$ to be an algebraic integer, which happens only when $m$ divides $n$.
22.04.2024 19:05
This is def my favorite problem on this USAMO.
30.05.2024 22:55
The answer is all $m$ so that $m < n$(which is clearly necessary) and $m \mid n$. Label all vertices of the polygon $\mathcal P$ as $X_1, X_2, \dots, X_n$ with its circumcenter as $O$. WLOG, $\mathcal P$ has circumradius $1$. Note that the area of any triangle $\triangle X_aX_bX_c$ can be written as $[X_aX_bX_c] = \pm[OX_aX_b] \pm [OX_bX_c] \pm [OX_cX_A]$. Our goal is to show that for any $j$, $k$ with $j > k$ we have $OX_jX_k$ is $\frac{1}{2} \cdot \sin\left( \frac{2\pi}{n}\right)$ multiplied by an algebraic integer which would imply $X_aX_bX_c$ is $\frac{1}{2} \cdot \sin\left( \frac{2\pi}{n}\right)$ times an algebraic integer since $\overline{\mathbb Z}$ is a ring(closed under addition/subtraction). By Sine Area formula we have $[OX_jX_k] = \frac{1}{2} \cdot \sin\left(\frac{2\pi(|j-k|)}{n}\right)$. Let $\zeta$ be an $n$th root of unity. So then from $\sin(\theta) = \frac{e^{{\theta}i} - e^{{-\theta}i}}{2i}$ we get that $[OX_jX_k] = \frac{\zeta^{j-k} - \zeta^{k-j}}{4i} = \frac{1}{4i}(\zeta + \zeta^{-1})(\zeta^{j-k-1} + \zeta^{j-k-3} + \dots + \zeta^{k-j+1}) = \frac{1}{2} \cdot \sin\left(\frac{2\pi}{n}\right) \cdot (\zeta^{j-k-1} + \zeta^{j-k-3} + \dots + \zeta^{k-j+1})$. Since $\zeta$ is an root of $x^n - 1$ it follows that all powers of $\zeta$ are also algebraic integers since $\overline{\mathbb Z}$ is closed under multiplication which implies that $[OX_jX_k]$ is $\frac{1}{2} \cdot \sin\left(\frac{2\pi}{n}\right)$ times an algebraic integer which implies that this is also true for any triangle with vertices in $\mathcal P$. We also have $[\mathcal{P}] = \frac{n}{2} \cdot \sin\left(\frac{2\pi}{n}\right)$ from which it follows that all triangles with a given color have a total area of $\frac{[\mathcal{P}]}{m} = \frac{n}{2m} \cdot \sin\left(\frac{2\pi}{n}\right)$ which as we know is $\frac{1}{2} \cdot \sin\left(\frac{2\pi}{n}\right)$ times an algebraic integer by closure under addition so it follows that $\frac{n}{m} \in \overline{\mathbb Z}$. However $\frac{n}{m} \in \mathbb Q$ and $\mathbb Q \cap \overline{\mathbb Z} = \mathbb Z$ so $\frac{n}{m} \in \mathbb Z \implies m \mid n$. For our construction for $m \mid n$, our triangulation will just be all possible diagonals stemming from one vertex(WLOG let the vertex be $X_1$) and we will color the triangles so that every $m$th triangle is colored(see other post's diagrams for examples). Now WLOG the side length of $\mathcal{P} = 2$ and let the $m$ colors be labeled $c_1$, $c_2$, $\dots$, $c_{m}$. Then it follows that the sum of the triangles with color $c_p$ is equal to the sum of the altitudes from $X_1$ to sides $X_{p}X_{p+1}$, $X_{m + p}X_{m+p+1}$, $\dots$, $X_{n-m+p}X_{n-m+p+1}$. Note that the extensions of these sides form a regular $\frac{n}{m}$-gon and since $X_1$ is a point in its interior, the sum of its altitudes to the sides are constant regardless of its position relative to the $\frac{n}{m}$-gon. This is also true in the case of $\frac{n}{m} = 2$ where the two sides are two parallel lines. So we get that the sum of the triangles with color $c_p$ are constant regardless of $p$, as desired.
31.05.2024 08:04
Dude i have no idea how i got 1 point of partial for this,