Equal area sum in regular n-gon triangulation

Art of Problem Solving

AoPS Online

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Equal area sum in regular n-gon triangulation

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USAMO 2024/3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#1 h Mar 20, 2024, 4:10 AM • 1 Y

Y by dolphinday

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

This post has been edited 2 times. Last edited by CyclicISLscelesTrapezoid, Mar 20, 2024, 10:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

497 posts

#2 h Mar 20, 2024, 4:22 AM

Y by

pretty sure the condition was $m|n$ and $m < n$ but im bad at math

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

33 posts

#3 h Mar 20, 2024, 4:36 AM • 1 Y

Y by Th3Numb3rThr33

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的多项式倍，这是代数整数.]

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

156 posts

Ritwin

#4 h Mar 20, 2024, 4:38 AM • 5 Y

Y by sixoneeight, TheHazard, EpicBird08, AtharvNaphade, LLL2019

Super clean.
answer
construction
necessity

This post has been edited 1 time. Last edited by Ritwin, Mar 20, 2024, 4:39 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1039 posts

#5 h Mar 20, 2024, 4:40 AM • 1 Y

Y by TheUltimate123

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.

This post has been edited 2 times. Last edited by Gogobao, Mar 20, 2024, 4:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23 posts

#6 h Mar 20, 2024, 4:41 AM

Y by

Don’t tell me this was a geo…

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#7 h Mar 20, 2024, 4:46 AM • 1 Y

Y by CyclicISLscelesTrapezoid

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] 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]$

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$ ) $.$

This post has been edited 4 times. Last edited by TheUltimate123, Mar 29, 2024, 6:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

96 posts

#8 h Mar 20, 2024, 6:21 AM

Y by

Is there a way to solve this without group theory?
I doubt the US would publish a problem without an elementary solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7351 posts

DottedCaculator

#9 h Mar 20, 2024, 11:43 AM • 1 Y

Y by Ritwin

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.

This post has been edited 1 time. Last edited by DottedCaculator, Mar 20, 2024, 11:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

#10 h Mar 20, 2024, 1:16 PM

Y by

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$ .

This post has been edited 3 times. Last edited by wzs26843545602, Mar 20, 2024, 3:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7585 posts

#11 h Mar 20, 2024, 2:15 PM

Y by

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)

This post has been edited 1 time. Last edited by asdf334, Mar 20, 2024, 2:41 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#12 h Mar 22, 2024, 9:32 PM • 2 Y

Y by ihatemath123, ike.chen

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] 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]$

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$

This post has been edited 3 times. Last edited by IAmTheHazard, Mar 22, 2024, 9:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#13 h Apr 15, 2024, 12:36 AM • 2 Y

Y by Sedro, soryn

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] 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]$
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$ .

This post has been edited 1 time. Last edited by v_Enhance, Aug 27, 2024, 12:04 AM
Reason: many missing factors of -1/2 zzz

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

500 posts

#14 h Apr 22, 2024, 4:05 PM • 1 Y

Y by soryn

This is def my favorite problem on this USAMO.
Solution

This post has been edited 5 times. Last edited by Mr.Sharkman, Apr 22, 2024, 5:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1324 posts

#15 h May 30, 2024, 7:55 PM • 3 Y

Y by cursed_tangent1434, bjump, soryn

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.

This post has been edited 2 times. Last edited by dolphinday, May 30, 2024, 8:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwerty123456asdfgzxcvb

1086 posts

qwerty123456asdfgzxcvb

#16 h May 31, 2024, 5:04 AM

Y by

Dude i have no idea how i got 1 point of partial for this,

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1739 posts

OronSH

#17 h Jan 25, 2025, 7:07 PM • 1 Y

Y by dolphinday

We claim $m\mid n,m\ne n$ .

First if $m\mid n$ draw all diagonals from one point $P$ , then color the triangles formed in a cycle. Then each color's triangles run from $P$ to equally-spaced edges. By generalized Viviani's theorem on the polygons formed by extending these edges, the sum of the distances from $P$ to the edges is the same, so multiplying by side length, so are the sums of the areas.

To show this must hold, assume the polygon vertices are the $n$ th roots of unity. Then the area is $\tfrac n2\sin\tfrac{2\pi}n$ . If a triangle in the triangulation has vertices with arguments $\alpha,\beta,\gamma$ then its area is $\tfrac12|\sin(\alpha-\beta)+\sin(\beta-\gamma)+\sin(\gamma-\alpha)|$ by Shoelace. The key idea is that this is always $\tfrac14$ times an algebraic integer. Thus we must have $\tfrac nm2\sin\tfrac{2\pi}n$ is an algebraic integer.

Writing $2\sin\tfrac{2\pi}n=i(e^{-\frac{2\pi i}n}-e^{\frac{2\pi i}n})$ we see that we want $\tfrac nm(\omega-1)$ to be an algebraic integer, where $\omega=e^{\frac{4\pi i}n}$ . If $\omega$ is a primitive $k$ th root of unity, then notice $\tfrac nm(\omega-1)$ has minimal polynomial $\Phi_k(\tfrac mnx+1)$ . If $k=2$ then $\omega=-1$ and $n=4$ which is easily checked. Otherwise the product of the roots is $(\tfrac nm)^{\varphi(k)}$ times $\varphi(k)$ terms of the form $(\omega^i-1)$ , all of which have magnitude value $<2$ . Thus if $m\nmid n$ then $(\tfrac nm)^{\varphi(k)}$ has denominator at least $2^{\varphi(k)}$ , but the product of the other terms is an integer less than it. Thus the product of the roots is not an integer, so the minimal polynomial is not monic, so $\tfrac nm(\omega-1)$ is not an algebraic integer, contradiction.

Finally $m\ne n$ by size, done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3369 posts

#18 h Feb 9, 2025, 7:16 PM • 2 Y

Y by OronSH, megarnie

The answer is $m \mid n$ , and $m \neq n$ . It is obvious that $m \ge n > n-2$ would not work, so here on we assume $m < n$ . Without loss of generality, assume the polygon has circumradius $1$ .

Construction: Let the vertices of $\mathcal{P}$ be $\{A_0, A_1, \dots, A_{n-1}\}$ . We claim the triangulation in which you take all diagonals containing $A_0$ is $m$ -balanced for all $m \mid n$ and $m < n$ . Assign the triangle $A_0A_iA_{i+1}$ to group $k$ if and only if $i \equiv k \pmod m$ . Note that $[\mathcal{P}] = \tfrac{\sin(2\theta)}{2} \cdot n$ where $\theta = \tfrac{\pi}{n}$ , so it suffices to show that each group has combined area $\tfrac{\sin(2\theta)}{2} \cdot \tfrac{n}{m}$ . We have that $\begin{align*} \sum_{i \equiv k \pmod{m}} [A_0A_iA_{i+1}] = \sum_{i \equiv k \pmod{m}} A_0A_i \cdot A_0A_{i+1} \cdot \frac{\sin \theta}{2} \\ = \sum_{i \equiv k \pmod m} \left [ 4\sin(i\theta)\sin((i+1)\theta) \right ] \cdot \frac{\sin \theta}{2} \\ = \sum_{i \equiv k \pmod m} (\omega^{-i} - \omega^{i})(\omega^{i+1} - \omega^{-i-1}) \cdot \frac{\sin \theta}{2} \\ = \sum_{i \equiv k \pmod m} \left [ 2\cos \theta - \omega^{-2i-1} - \omega^{2i+1} \right] \cdot \frac{\sin \theta}{2} = \frac{\sin 2\theta}{2} \cdot \frac{n}{m} \end{align*}$ where $\omega = e^{i\theta}$ . Therefore, the construction is valid.

Claim: The sum of the areas of all triangles in a group is $\tfrac{\sin(\theta)}{2} \cdot z$ , where $z$ is an algebraic integer.
Proof. It suffices to show that the area of any triangle $A_iA_jA_k$ satisfies such property, because the set of algebraic integers is closed under addition. Note that we can decompose $[A_iA_jA_k]$ with the following:
$\begin{align*} [A_iA_jA_k] = \epsilon_{1} [OA_iA_j] + \epsilon_{2} [OA_jA_k] + \epsilon_{3} [OA_iA_k] \end{align*}$ where $O$ is the center and $\epsilon_{n} \in \{ -1, 1 \}$ . Now, the claim is reduced to only proving that $[OA_iA_j]$ satisfies such property. Observe that $\begin{align*} [OA_iA_j] = \frac{\sin((j-i)\theta)}{2}\end{align*}$ so we can reduce this even further to showing that $\tfrac{\sin((j-i)\theta)}{\sin \theta}$ is an algebraic integer. Finally, note that $\begin{align*} \frac{\sin((j-i)\theta)}{\sin \theta} = \frac{\omega^{j-i} - \omega^{i-j}}{\omega - \omega^{-1}} \\ = (\omega^{j-i-1} + \omega^{j-i-3} \dots + \omega^{i-j+1})\end{align*}$ which is clearly an algebraic integer. $\square$

This implies that $z = \tfrac{n}{m}$ must be an algebraic integer, which can only occur if $m \mid n$ . Therefore we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

623 posts

#19 h Apr 23, 2025, 4:12 AM

Y by

Let $\omega = e^{\frac{2\pi i}{n}}.$
Claim: The area formed by $1, \omega^a, \omega^b$ is $\frac{(\omega^a-1)(\omega^b-1)(\omega^{-b}-\omega^{-a})}{4i}$
Proof: Using complex shoelace, we have
$\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} = \frac i4 \frac{(\omega^a-1)(\omega^b-1)(\omega^{-b}-\omega^{-a})}{4i}$ Claim: $m\mid n, m < n$ is necessary
Proof: Obviously, $m < n$ is necassary.
Clearly note that the area of each color is necessarily $\frac nm\frac{\omega - \omega^{-1}}{4i}.$ Thus, there exists some sequence $(a_1, b_1), \dots, (a_k, b_k)$ such that $\sum_{j = 1}^k \frac{(\omega^{a_j}-1)(\omega^{b_j}-1)(\omega^{-b_j}-\omega^{-a_j})}{4i} = \frac nm \frac{\omega - \omega^{-1}}{4i}$ Canceling, $\frac{\omega}{1-\omega^2}\sum_{j = 1}^k (\omega^{a_j}-1)(\omega^{b_j}-1)(\omega^{-b_j}-\omega^{-a_j}) = \frac nm$ However, note that every term in the summation is divisible by $\frac1{1-\omega^2}$ via casework on $a, b \pmod 2.$ Thus, the LHS is an algebraic integer. Hence, the right needs to be an algebraic integer, finishing.

Now, we show that all of $m \mid n$ work.

Do the triangulation about one vertex, and then we can alternate between colors in the fashion of $0, 1, \dots, m - 1, 0, 1, \dots, m, \dots.$ This actually works. We will include a degenerate area of 0 in our calculations to make them easier. If we are working with color $r,$ then:
$\begin{align*} \sum_{\stackrel{d\equiv r\pmod m}{0\leq d < n}} \frac{(\omega^d - 1)(\omega^{d + 1} - 1)(\omega^{-(d + 1) - \omega^{-d}})}{4i} & = \frac{\omega^{-1} - 1}{4i} \sum_{\stackrel{d\equiv r}{0\leq d < n}}(\omega^d - 1)(\omega - \frac1{\omega^d}) \\ & = \frac{\omega^{-1} - 1}{4i} \sum_{\stackrel{d\equiv r\pmod m}{0 \leq d < n}} \omega^{d + 1} - \omega- 1 + \frac1{\omega^d} \\ & = \frac{\omega^{-1} - 1}{4i}\left(-\frac mn(\omega + 1) + \sum_{\stackrel{d\equiv r\pmod m}{0\leq d < n}} \omega^{d + 1} + \frac1{\omega^d}\right) \end{align*}$ However, clearly note that the sum must evaluate to zero as they form a full polygon centered at 0. Thus, the sum is $\frac mn\frac{\omega - \omega^{-1}}{4i} = \frac mn \frac{\sin\left(\frac{2\pi }{n}\right)}{2}.$ Indeed, if we were to compute the area of the polygon by splitting it into iscoceles triangles, we get the desired value.

This post has been edited 1 time. Last edited by Ilikeminecraft, Apr 23, 2025, 4:12 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a