Twelve points are marked on a circle at equal intervals. Using line segments to connect the twelve points, we want to construct a figure consisting of three polygons such that:
- The three polygons do not intersect each other.
- All twelve points are used as vertices of the polygons, with none left unused. Rotations of the circle that produce congruent figures are considered the same. Find the number of distinct figures that satisfy these conditions.oindent
[THOUGHT] I will brute-force all assignments of the 12 labeled points to 3 polygons, ensure each polygon has at least 3 vertices, build the cycles in circular order, check that no edges cross, then canonicalize each valid configuration up to rotation (and ignoring the labeling of the 3 polygons) to count distinct figures. [/THOUGHT] [PYTHON] import itertools import math
Precompute coordinates of 12 equally spaced points on a circle
n = 12 points = [(math.cos(2math.pii/n), math.sin(2math.pii/n)) for i in range(n)]
def orientation(p, q, r): """Return orientation of ordered triplet (p,q,r): >0 if counterclockwise, <0 if clockwise, =0 if collinear """ return (q[0] - p[0])(r[1] - p[1]) - (q[1] - p[1])(r[0] - p[0])
def segments_intersect(a, b, c, d): """Check if line segments ab and cd intersect properly (not just at endpoints). Assumes general position (no collinearity for intersection). """ # general segment intersection using orientations o1 = orientation(a, b, c) o2 = orientation(a, b, d) o3 = orientation(c, d, a) o4 = orientation(c, d, b)
# Proper intersection if orientations differ in sign for both pairs
if o1 == 0 or o2 == 0 or o3 == 0 or o4 == 0:
# Collinear or touching endpoints (shouldn't really happen with circle points),
# but treat any such as intersection for safety.
# We'll do full on-segment checks only if needed.
# For this problem geometry, three points won't be collinear.
pass
return (o1*o2 < 0) and (o3*o4 < 0)
def build_edges_from_assignment(assignment): """Given an assignment list of length 12 with values in {0,1,2}, return list of edges (pairs of vertex indices) for the 3 polygons. Return None if any color class has size <3.""" edges = [] for color in range(3): verts = [i for i in range(n) if assignment[i] == color] k = len(verts) if k < 3: return None # sort verts in circular order (which is numeric order 0..11) verts.sort() for i in range(k): u = verts[i] v = verts[(i+1) % k] if u < v: edges.append((u, v)) else: edges.append((v, u)) return edges
def is_noncrossing(edges): """Check if no two edges in the list properly intersect.""" m = len(edges) for i in range(m): a, b = edges[i] pa, pb = points[a], points[b] for j in range(i+1, m): c, d = edges[j] # Skip if share endpoint if a in (c, d) or b in (c, d): continue pc, pd = points[c], points[d] if segments_intersect(pa, pb, pc, pd): return False return True
def canonical_form_from_assignment(assignment): """Compute canonical form of a figure given by an assignment under rotation (cyclic shift of vertices) and permutation of polygon labels (handled by sorting blocks). Return as a tuple of tuples of ints.""" best = None for shift in range(n): # Build blocks for this rotated configuration blocks = {0: [], 1: [], 2: []} for i in range(n): color = assignment[i] new_v = (i + shift) % n blocks[color].append(new_v) # Represent blocks as sorted vertex tuples block_tuples = [] for color in range(3): vs = sorted(blocks[color]) block_tuples.append(tuple(vs)) # Sort blocks to forget color labels block_tuples.sort() cf = tuple(block_tuples) if (best is None) or (cf < best): best = cf return best
canonical_figures = set()
Iterate all assignments: 3^12 possibilities
colors = [0,1,2] count_assignments = 0 valid_assignments = 0
for assignment in itertools.product(colors, repeat=n): count_assignments += 1 # quick filter: each color must appear at least 3 times counts = [0,0,0] for c in assignment: counts[c] += 1 if any(c < 3 for c in counts): continue
edges = build_edges_from_assignment(assignment)
if edges is None:
continue
if not is_noncrossing(edges):
continue
valid_assignments += 1
cf = canonical_form_from_assignment(assignment)
canonical_figures.add(cf)
print("Total assignments checked:", count_assignments)
print("Valid noncrossing assignments:", valid_assignments)
print("Distinct figures up to rotation:", len(canonical_figures))
[/PYTHON]
[THOUGHT] Using exhaustive enumeration with Python and factoring out rotations, there are 20 distinct non-intersecting three-polygon figures using all 12 points. I will report 20 as the final answer. \boxed{20}