Maths Olympiad Prep

Library / /602 of 740

, 2023

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Compute the number of ways to color the vertices of a regular heptagon red, green, or blue (with rotations and reflections distinct) such that no isosceles triangle whose vertices are vertices of the heptagon has all three vertices the same color.

Solution

Solution:

Number the vertices 11 through 77 in order. Then, the only way to have three vertices of a regular heptagon that do not form an isosceles triangle is if they are vertices 1,2,41,2,4, rotated or reflected. Thus, it is impossible to have four vertices in the heptagon of one color because it is impossible for all subsets of three vertices to form a valid scalene triangle. We then split into two cases:

Case 1: Two colors with three vertices each, one color with one vertex. There is only one way to do this up to permutations of color and rotations and reflections; if vertices 1,2,41,2,4 are the same color, of the remaining 44 vertices, only 3,5,63,5,6 form a scalene triangle. Thus, we have 77 possible locations for the vertex with unique color, 33 ways to pick a color for that vertex, and 22 ways to assign the remaining two colors to the two triangles, for a total of 4242 ways.

Case 2: Two colors with two vertices each, one color with three vertices. There are 33 choices of color for the set of three vertices, 1414 possible orientations of the set of three vertices, and (42)\binom{4}{2} choices of which pair of the remaining four vertices is of a particular remaining color; as there are only two of each color, any such assignment is valid. This is a total of 3146=2523 \cdot 14 \cdot 6 = 252 ways.

Thus, the final total is 42+252=29442 + 252 = 294.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.