hmm I spent like 4 hours and 15 minutes. Got nowhere.

Okay, here is a solution that I found. I hope there are no major holes in it.

Denote $a_k$ to be the number of matches with the red points when you rotate the greens by $k$. Then $a_1+\cdots+a_{431}=108^2$. On average, each $a$ is $\frac{108^2}{431}>27$, so at least rotation gives $28$ matches. Then consider those $28$ points. Let $b_k$ be the number of matches with those with the blues when you rotate by $k$. Then $b_1+\cdots+b_{431}=28*108$. On average, each $b$ is $\frac{28\cdot 108}{431}>7$, so at least one is $8$. Then, we do the same action again and get that we can rotate each of the colors to get a group of $3$ that is the same, because $\frac{108\cdot 8}{431}>2$.

Yongyi781 wrote: Okay, here is a solution that I found. I hope there are no major holes in it. Basically the exact same way I did it. I couldn't make any progress forever, and when this general idea to do rotations hit it was solved almost instantly

The way I tried was pigeonholing quadrilaterals which have one vertex of each color. It doesn't work, probably because it assumes the four triangles have the same orientation.

ftong wrote: The way I tried was pigeonholing quadrilaterals which have one vertex of each color. It doesn't work, probably because it assumes the four triangles have the same orientation. It doesn't work because you're not being greedy enough; you need to be super-greedy to eek out as much detail as you can. You'll get the same asymptotic but the numbers were pretty much chosen to be maximum-greediness.

I bet half the people got #1 and then spent the rest of the time thinking pidgeonhole over and over again till time ran out. Oh like me.

benjamin7xx wrote: I bet half the people got #1 and then spent the rest of the time thinking pidgeonhole over and over again till time ran out. Oh like me. and me

Why do people word stuff in terms of pigeonhole instead of probabilistic method D:

pythag011 wrote: ftong wrote: The way I tried was pigeonholing quadrilaterals which have one vertex of each color. It doesn't work, probably because it assumes the four triangles have the same orientation. It doesn't work because you're not being greedy enough; you need to be super-greedy to eek out as much detail as you can. You'll get the same asymptotic but the numbers were pretty much chosen to be maximum-greediness. Also note that with rotations, all 4 triangles do have the same orientation in the end, so the problem can be strengthened to include the same orientation.

andersonw wrote: Also note that with rotations, all 4 triangles do have the same orientation in the end, so the problem can be strengthened to include the same orientation. Darn, I decided the problem would be too easy if this were the case, so I looked for tricker strategies. Guess I just need to be dumber. Glad I only spent two hours on this one.

.... Oh. So... I did have the right method after all, and I just fail at common sense? This makes me feel somewhat better. So if I got the right method of the problem but didn't realize that not rotating the points doesn't cause overlaps, then do I get a 1 or a 6?

benjamin7xx wrote: I bet half the people got #1 and then spent the rest of the time thinking pidgeonhole over and over again till time ran out. Oh like me. ha that was me but I was smart and moved on to question 3 after 2 1/2 hours of failing number 2, and I got it! well... assuming they understand my solution.

I wonder how much stronger we can make this, seeing as $n_1$ and $n_{-1}=n_{431}$ only hit at most one good point. And $n_2$ and $n_{-2}=n_{430}$ only hit at most two good points. (And so on.)

Gah, i had the rotation idea and had gotten 27, but i didnt know where to go from there

The idea of the solution to this problem is that rotation preserves angles and side lengths, and 432 points is the best you can reduce this problem to if you use this method of proof. But while I was stuck on this problem, I realized that reflection also preserves angles and side lengths, so I thought that the problem had something to do with reflections as well, and I started toying with the idea of reflecting the 108 red points across the center of the circle and rotating that, but I couldn't get anywhere with this idea. My question is: given the reflection idea, can you improve 432 to 428, or possibly less?

What would even be the motivation to think about applying rotations?

Congruent triangles that are oriented similarly are just rotations of one another, so it makes sense to consider rotations of some kind.

The idea is also extremely natural if you think about combinatorics problems probabilistically. I'm rather puzzled by how so few people know probabilistic method, when it is 1. easier than the random lemmas they know how to use 2. is at the same time arguably the most fundamental thing in all of combinatorics (Fundamental as in it shows up EVERYWHERE) and 3. this the third USAMO in a row with a probabilistic method problem, and this USAMO had two probabilistic method problems. Yes, in theory for most of the applications of probabilistic method on USAMO, it can be converted into pigeonhole; but the probabilistic perspective is both massively cleaner and a much more insightful perspective. Pigeonhole is a very attractive framework for direct applications and has a number of interesting generalizations (Van de Waerdan) but probabilistic method tends to be a much nicer framework for the problems that aren't direct applications and don't need the generalizations.

Here for storage, sorry for an typos, etc. For more clarity, many of the above posts use the same solution. Let $\mathbb{E}[R]$ be the expected number of red points that will coincide with green points on any of the $431$ rotations that do not place the red points back onto themselves. To compute $\mathbb{E}[R],$ we note that there are $108^2$ ways that the redpoints will map onto the green. However, there are $431$ possible rotations. So, $$\mathbb{E}[R] = \frac{108^2}{431} > 27.$$Thus, there must exist a red $28$-gon such that a certain rotation will map it onto $28$ green points. Now let $\mathbb{E}[G]$ be the expected number of these $28$ green points that will overlap with the blue points in the $431$ possible rotations. There are $108 \times 28$ ways this can happen, and $430$ possible rotations (no all red/green), so $$\mathbb{E}[G] = \frac{108 \times 28}{430} > 7.$$So, there exists a blue $8$-gon such that it can be rotated to map onto a blue $8$-gon. Lastly let $\mathbb{E}[B]$ be expected number of points that the blue $8$-gon maps onto yellow points in the $429$ possible rotations. Then, $$\mathbb{E}[B] = \frac{108 \times 8}{429} > 2.$$Thus, we have $4$ same colored triangles of each color, and we are done by Pigeonhole. $\blacksquare$

The key idea here is to notice that triangles on the circle are congruent if and only if they are rotations of one another. Thus, we can consider all possible rotations of the 108 points and see if at least 3 of them overlap with the other 3 colors. Let us deal with the blue points. Considering an arbitrary rotation, the probability a red point has been rotated onto a blue is $\frac{1}{4}$. Thus, the expected value of overlapping blue-red points is " on average" $108 \cdot \frac{1}{4}=27$. Now, take any rotation with at least 27 points. Rotating these points, we want to find the expected number of red-green overlaps. The expected value is $27 \cdot \frac{1}{4}=\frac{27}{4}=6.75$. Thus, there certainly \textit{exists} a rotation with at least 7 red-green overlaps. Take these 7 points. Then, we count the number of red-yellow overlaps. The expected number is $\frac{7}{4}=1.75$. However, this only guarantees there \textit{exists} 2 overlapping red-yellow points. However, we need 3! However, we can slightly improve this lower bound to 3 through a nice trick. Notice that there are on average 27 red-blue overlaps. However, the only way it is 27, and not anything lower or higher, ist that every single rotation has 27 overlapping red-blue points. However, we know that this is not true. For example, take the identity rotation for the red points. There are 0 red-blue overlaps. Therefore, there must be some rotation with over 27 overlapping points to "balance out" these lower values. That is, we are in fact guaranteed a rotation with 28 red-blue overlaps, 8 red-green overlaps and 2 red-yellow overlaps. Once again, using the same trick, since the identity rotation has 0 overlaps, there certainly exists a rotation with 3 red-yellow overlaps. Thus, we have found 4 triangles which are rotations of each other, as desired.

justin1228 wrote: The key idea here is to notice that triangles on the circle are congruent if and only if they are rotations of one another. Thus, we can consider all possible rotations of the 108 points and see if at least 3 of them overlap with the other 3 colors. Let us deal with the blue points. Considering an arbitrary rotation, the probability a red point has been rotated onto a blue is $\frac{1}{4}$. Thus, the expected value of overlapping blue-red points is " on average" $108 \cdot \frac{1}{4}=27$. Now, take any rotation with at least 27 points. Rotating these points, we want to find the expected number of red-green overlaps. The expected value is $27 \cdot \frac{1}{4}=\frac{27}{4}=6.75$. Thus, there certainly \textit{exists} a rotation with at least 7 red-green overlaps. Take these 7 points. Then, we count the number of red-yellow overlaps. The expected number is $\frac{7}{4}=1.75$. However, this only guarantees there \textit{exists} 2 overlapping red-yellow points. However, we need 3! However, we can slightly improve this lower bound to 3 through a nice trick. Notice that there are on average 27 red-blue overlaps. However, the only way it is 27, and not anything lower or higher, ist that every single rotation has 27 overlapping red-blue points. However, we know that this is not true. For example, take the identity rotation for the red points. There are 0 red-blue overlaps. Therefore, there must be some rotation with over 27 overlapping points to "balance out" these lower values. That is, we are in fact guaranteed a rotation with 28 red-blue overlaps, 8 red-green overlaps and 2 red-yellow overlaps. Once again, using the same trick, since the identity rotation has 0 overlaps, there certainly exists a rotation with 3 red-yellow overlaps. Thus, we have found 4 triangles which are rotations of each other, as desired. I understand this solution " and almost the solutions above " but i have a question , why we can use the expected value in the proofs ? i mean expected value means on average " as i have understood" , so may there are values more or less than it for example , we have found that the expected value of overlapping blue-red points is $108 \cdot \frac{1}{4}=27$ but may there are just 26 overlapped blue-red points can any one explain this for me please

raghoodah1m wrote: I understand this solution " and almost the solutions above " but i have a question , why we can use the expected value in the proofs ? i mean expected value means on average " as i have understood" , so may there are values more or less than it for example , we have found that the expected value of overlapping blue-red points is $108 \cdot \frac{1}{4}=27$ but may there are just 26 overlapped blue-red points can any one explain this for me please Yes, these are some very good questions. It is true that there may be a rotation with only 26 overlapping points. But... who cares? There is even a rotation with only 0 overlapping points (identity rotation). If it has less than 27 overlapping points, we don't care about that rotation. We only care about a rotation which has at least 27 overlapping points, and this is guaranteed by expected value. Also, all we need is just one rotation to satisfy 27 overlapping points, no need for more than that.

justin1228 wrote: raghoodah1m wrote: I understand this solution " and almost the solutions above " but i have a question , why we can use the expected value in the proofs ? i mean expected value means on average " as i have understood" , so may there are values more or less than it for example , we have found that the expected value of overlapping blue-red points is $108 \cdot \frac{1}{4}=27$ but may there are just 26 overlapped blue-red points can any one explain this for me please Yes, these are some very good questions. It is true that there may be a rotation with only 26 overlapping points. But... who cares? There is even a rotation with only 0 overlapping points (identity rotation). If it has less than 27 overlapping points, we don't care about that rotation. We only care about a rotation which has at least 27 overlapping points, and this is guaranteed by expected value. Also, all we need is just one rotation to satisfy 27 overlapping points, no need for more than that. oh , i get it now ! thank you very much

mr.clock wrote: This is very likely wrong, but I can't seem to find the mistake. Can someone please check this? There are exactly $108^4$ quadrilaterals with all 4 vertices of different colour. Notice that we can assign to each of them a 3 letter word which gives the order in which we meet vertices when we start moving from the red vertice in the clockwise direction(for example BYG). Since there are only 6 combinations one must appear in at least $108^4/6$ quadrilaterals. The number of quadrilaterals with vertices in the $432$ points so that no two are congruent is no more than $\frac{\binom{432}{4}}{432}$. Since $\frac{108^4}{6}>2\frac{\binom{432}{4}}{432}$ we must have 3 congruent quadrilaterals with vertices appearing in the same order in each of them. Taking these points gives the desired triangles. Now I'm confused, because I tried something very similar and it failed. Allow quadrilaterals to self-intersect, and suppose vertices are distinguishable. Then there are clearly $108^4$ quads will all 4 vertices of a different color. Now clearly there are also $431\cdot 430\cdot 429$ equivalence classes of quads (where quads that differ by a rotation are in the same class), which comes from fixing vertex 1 and then picking vertices 2, 3, 4. But $108^4$ is not greater than $2\cdot 431\cdot 430\cdot 429$, so the approach fails... Could someone explain the difference between what I did and what mr.clock did?

I think the solution follows super naturally from the ideas this problem embodies, which I'll state briefly below (and which I believe is more useful for my own storage anyways), so I'll leave out a full solution. The idea is that the bound is not tight enough. Summing/expecting/pigeonholing/whatever in the obvious way yields a bound of $\frac{108^4}{432^3-\varepsilon} < 2$ expected intersections between all four points. Upon inspection, however, this is a pretty loose bound: there are many cases where *things don't intersect* (i.e. the EV is 0) but they are counted in the numerator. Replacing $432^3$ with $431 \cdot 430 \cdot 429$ doesn't do much, either. The piecemeal Pigeonhole application is simply to encode this emptiness as much as possible. Notice that at every step, the difference between 432 and 431 makes a critical difference: otherwise, we wouldn't have been able to construct the 28-gon (instead a 27-gon), 8-gon (instead a 7-gon), and so on; ignoring these slight non-identity irregularities turns this solution into essentially the global case (with only segments found), but taking advantage of the small alterations forms the crux of the solution. I don't usually like writing explicit motivations, but I find this problem to be a perfect example of the importance of intermediate steps especially in global problems; the idea shines through without any other difficulty to cloud the problem.

Did I do something wrong? I was thinking about probabilities and the probabilistic method, but I have yet to be that advanced. I'm going to post it. Here goes nothing! Let $R, B, Y, G$ denote the set of all points that are red, blue, yellow, and green respectively. Denote the vertices as $v_1, v_2, \dots, v_{12n}$. We define the distance between two vertices $v_i$ and $v_j$ as $|i - j|$. Denote by $N_R$ the set of all the differences from $R$. We then make the following observations: $\bullet$ $|N_R| \geq 3n - 1$; $\bullet$ $|N_R \cap N_B| \leq 3n - 1$; $\bullet$ $|N_R \cap N_B \cap N_Y| \geq n$; $\bullet$ $|N_R \cup N_B \cup N_Y \cup N_G| < 4n - 1 \implies |N_R \cup N_B \cup N_Y \cup N_G| \leq 4n - 2$. Also notice that if for three red vertices and three blue vertices $(v_i, v_j, v_k)$ and $(v_{i'}, v_{j'}, v_{k'})$ are such that $d(v_i, v_k) = d(v_{i'}, v_{j'}), d(v_i, v_k) = d(v_{i'}, v_{k'})$, then $d(v_j, v_k) = d(v_{j'}, v_{k'})$. Therefore it would suffice to show $|N_R \cap N_B \cap N_Y \cap N_G| \geq 2$. By inclusion-exclusion, we have that $$|N_R \cap N_B \cap N_Y \cap N_G| = |N_R| + |N_B| + |N_Y| + |N_G| - (|N_R \cap N_B| + |N_R \cap N_Y| + |N_R \cap N_G| + |N_B \cap N_Y| + |N_B \cap N_G| + |N_Y \cap N_G|)$$$$+ (|N_R \cap N_B \cap N_Y| + |N_R \cap N_B \cap N_G| + |N_R \cap N_Y \cap N_G| + |N_B \cap N_Y \cap N_G|) - |N_R \cup N_B \cup N_Y \cup N_G|$$$$\geq 4(3n - 1) - 4(3n - 1) + 4n - (4n - 2) = 2, $$as desired. $\blacksquare$

The idea is to rotate the points of one color so that they overlap onto another color. Our goal is to rotate the colored points such that we can get three stacks of all four colors, which would imply that there is a congruent (in fact, rotationally congruent) triangle. First, fix $108$ of the red points. We first rotate the blue points. Consider the $108$ rotational states of the blue points. Then the expected value of the number of overlapping blue and red points is $\frac{108}{4} = 27$ because there is a one fourth chance for a given point that it is blue. However, we know there is a state (the original) for which there are $0$ overlapping points. This means there must exist $28$ points that overlap for some rotation. Now we fix those $28$ points and rotate the yellow points. The logic is the same, one fourth chance of overlapping, but a $0$ state exists, so we have a rotation that has $8$ points with red, blue, and yellow overlapping. Then, we can rotate green and we'll have $\frac{8}{4} + 1 = 3$ points overlapping, resulting in a congruent triangle as desired.

This is a linearity of expectation problem, which was fairly obvious as there aren't any other obvious approaches. Trying smaller cases seems to suggest the the numbers hold some bearing, most likely to force the expectation to work. Now rather than attempt to look at triangles, we instead consider rotating segments of a specific color. Indeed consider rotating all red arcs about the center of the circle, such that they map to some other arcs. Now if any $3$ red arcs coincide with any $3$ arcs of a different color, then connecting those arcs we find a congruent triangle shared by the two colors. Thus it suffices to show the expected value of arc overlaps shared amongst all colors is bounded between $2$ and $3$. Consider the expected number of arc overlaps for two specific colors, say red and blue. A specific red segment lies on any other blue segment with probability $\frac{1}{431}$ over a random rotation. Thus the expected number of overlaps is $108 \cdot \frac{108}{431} >108 \cdot \frac{1}{4} = 27$. Thus for two specific colors we are guarenteed at least $28$ overlaps. A similar process allows us to find we are guarenteed an expected $8$ arcs overlapping amongst $3$ colors, and at least $3$ overlapping arcs amongst $4$, as desired. Remark: The rotation idea also appears in a certain Canda problem in a walkthrough of D-Global.

The expected number of yellow points that the red $108$-gon will coincide with when rotated is $108\cdot \frac{108}{431}$ which is a little bit more than $27$ so there exists a $28$-gon that coincides with red and yellow. Then, this $28$-gon is expected to coincide with $28\cdot\frac{108}{431}$ green points which is a little bit more than $7$ so there exists a $8$-gon that coincides with red, yellow, and green. Then, this $8$-gon is expected to coincide with $8\cdot \frac{108}{431}$ blue points which is a little bit more than $2$ so there exists a triangle that coincides with red, yellow, green, and blue after rotation, as desired.

Take two copies and fix one and rotate the other. Over all $432$ rotations, a red dot overlaps a blue one $108^2$ times, and the initial rotation has $0$ overlaps. Thus there is some rotation where red overlaps blue $\left\lceil\frac{108^2}{431}\right\rceil=28$ times. Consider the $28$ red dots. As they rotate, one of these red dots overlaps a green one $28\cdot 108$ times, and the initial rotation has $0$ overlaps, so there is some rotation where this overlaps green $\left\lceil\frac{28\cdot 108}{431}\right\rceil=8$ times. Consider the $8$ red dots. As they rotate, one of these red dots overlaps a yellow one $8\cdot 108$ times, and the initial rotation has $0$ overlaps, so there is some rotation where this overlaps yellow $\left\lceil\frac{8\cdot 108}{431}\right\rceil=3$ times. This set of $3$ red points can be rotated to $3$ blue, green or yellow points.

Start by only considering the two colors red and green. Consider the $431$ non-identity rotations of the red points. Note that there are $108^2$ total intersections with the green points (each pair of points intersects once). Therefore (by Pigeonhole), there exists a rotation of the red points so that at least $$\frac{108^2}{431}>27$$red points match up with the green points. In particular, there exists a red $28$-gon that can be rotated to form a green $28$-gon. Now, we repeat the process! Consider intersections with the blue points. Consider the $430$ rotations of the red $28$-gon that aren't the identity and don't send it to the green $28$-gon. There are $28\cdot 108$ intersections with the blue points, and at least $$\frac{28\cdot 108}{430}>7$$red points match up with the blue points. In particular, there exists a red $8$-gon that can be rotated to form a green $8$-gon and a blue $8$-gon. Now, we need to add yellow points. Consider the $429$ rotations of the red $8$-gon that aren't the identity and don't send it to the green or blue $8$-gons. There are $8\cdot 108$ intersections with the blue points, and at least $$\frac{8\cdot 108}{429} > 2$$points match up. Therefore, there exists a red $3$-gon (triangle) that can be rotated to form triangles in each of the other colors.

It suffices to show that some 3 red points can be rotated to overlap with 3 points of each of the other colors. Suppose that we rotate the 108 red points in one of 431 ways. Then the expected overlap with the green points is \[\frac{108}{431} \cdot 108 = 27 + \epsilon,\] so there exist 28 points which can rotate to overlap with some 28 green points. Continuing with this process, we see that of these 28 red points, at least 8 can also be rotated to match with 8 blue points, and of these 8 red points, at least 3 can also be rotated to match with 3 yellow points. $\blacksquare$