Minimal Grouping in a Complete Graph

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Minimal Grouping in a Complete Graph

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Turkey TST P1

The post below has been deleted. Click to close.

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

15 posts

swynca

#1 h Tuesday at 6:10 AM • 1 Y

Y by sami1618

In a complete graph with $2025$ vertices, each edge has one of the colors $r_1$ , $r_2$ , or $r_3$ . For each $i = 1,2,3$ , if the $2025$ vertices can be divided into $a_i$ groups such that any two vertices connected by an edge of color $r_i$ are in different groups, find the minimum possible value of $a_1 + a_2 + a_3$ .

Z K Y

The post below has been deleted. Click to close.

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

15 posts

swynca

#2 h Tuesday at 8:36 AM • 1 Y

Y by sami1618

Answer

Z K Y

The post below has been deleted. Click to close.

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

874 posts

#3 h Tuesday at 1:29 PM • 3 Y

Y by MS_asdfgzxcvb, Kaimiaku, D.C.

The minimum possible value of $a_1 + a_2 + a_3$ is $38$ .

Bound: $a_1 + a_2 + a_3 \geq 38$

First, we claim that $a_1 a_2 a_3 \geq 2025$ . Assume otherwise. Each vertex of the graph has $a_1$ choices for the first partition, $a_2$ for the second, and $a_3$ for the third. Thus, there are a total of $a_1 a_2 a_3$ ways to assign a vertex across all three partitions.

Since we assumed $a_1 a_2 a_3 < 2025$ , the Pigeonhole Principle implies that there must exist two vertices $u$ and $v$ that are in the same group for all three partitions. However, this means the edge $uv$ is not colored with $r_1$ , $r_2$ , or $r_3$ , which is a contradiction.

To finish, we apply AM-GM:
$a_1 + a_2 + a_3 \geq \lceil 3\sqrt[3]{a_1 a_2 a_3} \rceil \geq \lceil 3\sqrt[3]{2025} \rceil \geq \lceil 30\sqrt[3]{2} \rceil \geq \lceil 30 \cdot \frac{5}{4} \rceil = 38.$

Construction: $a_1 + a_2 + a_3 = 38$

Consider the $12 \times 13 \times 13 > 2025$ lattice points $(x, y, z)$ with $1 \leq x \leq 12$ and $1 \leq y, z \leq 13$ . Arbitrarily assign the 2025 vertices to these coordinates. Any two vertices $u$ and $v$ must differ in at least one coordinate, say in position $i$ . Then assign the color $r_i$ to the edge connecting $u$ and $v$ .

For each $i = 1, 2, 3$ , group the vertices based on the value in position $i$ . Since two vertices sharing the same value in position $i$ would not have an edge colored with $r_i$ , this construction is valid.

Thus, we achieved $a_1 = 12$ , $a_2 = 13$ , and $a_3 = 13$ , yielding $a_1 + a_2 + a_3 = 38$ , as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a