Help with Problem!

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

Help with Problem!

G H J

Reveal topic tags

Three-Year Mathcounts Marathon

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

1103 posts

#1 h Mar 22, 2025, 3:07 PM

Y by

There are 51 senators in a Senate. The Senate needs to be divided into $n$ committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If A hates B, then B does not necessarily hate A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee.

Z K Y

The post below has been deleted. Click to close.

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

1103 posts

#2 h Mar 22, 2025, 3:12 PM

Y by

I found this problem while skimming over my books and then I was kind of stuck on this problem for an while so I need help and I have gotten nowhere. I solved every other problem in the chapter except this MOP problem.

Z K Y

The post below has been deleted. Click to close.

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

909 posts

#4 h Mar 31, 2025, 5:15 PM

Y by

$\textbf{Definition: }$ We say that the senators $A$ and $B$ are $\textbf{enemies}$ if occurs one of the situations:
$\bullet\quad A$ hates $B$ and $B$ doesn't hate $A$ ;
$\bullet\quad B$ hates $A$ and $A$ doesn't hate $B$ ;
$\bullet\quad A$ hates $B$ and $B$ hates $A$ .

Using the initial conditions, we construct $2$ graphs:

$\textbf{The graph G}_{\textbf{1}}:$ We construct a directed graph with $51$ vertices (the senators) and $3\cdot51=153$ arrows (an arrow from $A$ to $B$ means " $A$ hates $B$ "). From each vertex go exactly $3$ arrows.

$\textbf{The graph G}_{\textbf{2}}:$ Using the previous graph, we construct an undirected graph:
a) We keep the $51$ vertices;
b) We transform the arrows from $\textbf{G}_{\textbf{1}}$ into edges in $\textbf{G}_{\textbf{2}}$ . An edge connects two vertices $A$ and $B$ if and only if the corresponding senators are $\textbf{enemies}$ .
Hence, an edge in $\textbf{G}_{\textbf{2}}$ replaces one or two arrows from $\textbf{G}_{\textbf{1}}$ .
If two vertices $C$ and $D$ in the first graph are not connected by an arrow, then they are not connected by an edge in the second graph.
Results:
$\bullet$ the graph $\textbf{G}_{\textbf{2}}$ contains at most $153$ edges;
$\bullet$ in the graph $\textbf{G}_{\textbf{2}}$ , each vertex has the degree at least $3$ (in the graph $\textbf{G}_{\textbf{1}}$ , from each vertex start $3$ arrows).

$\textbf{An evaluation of the minimum value of \textit{n}}$
1) If the graph $\textbf{G}_{\textbf{2}}$ contains a clique (complete subgraph) with $r$ vertices, then $n\ge r$ .
The conclusion results immediately: any two vertices of the clique are connected by an edge, hence the corresponding senators cannot be members of the same committee.

2) The graph $\textbf{G}_{\textbf{2}}$ can contain cliques with at most $7$ vertices.
A subgraph $\textbf{S}\subset\textbf{G}_{\textbf{1}}$ with $r$ vertices can contain at most $3r$ arrows: from each vertex of $\textbf{S}$ start at most $3$ arrows with the endpoints in $\textbf{S}$ . Results: the number of arrows in $\textbf{S}$ is maximum $3r$ .
The number of edges in a clique with $r$ vertices in $\textbf{G}_{\textbf{2}}$ is $\dfrac{r(r-1)}{2}$ .
We proved previously: the number of edges in a subset of $\textbf{G}_{\textbf{2}}$ is less or equal to the number of arrows in the corresponding subgraph from $\textbf{G}_{\textbf{1}}$ .
Results: $\dfrac{r(r-1)}{2}\le 3r\Longrightarrow r\le7$ .

3) We can form a clique with $7$ vertices in the graph $\textbf{G}_{\textbf{2}}$ .
Denote the vertices $1,2,3,4,5,6,7$ .
Consider in $\textbf{G}_{\textbf{1}}$ the $21$ arrows:
$1\to2\to3\to4\to5\to6\to7\to1$ ;
$1\to3\to5\to7\to2\to4\to6\to1$ ;
$1\to4\to7\to3\to6\to2\to5\to1$ .
Each pair of vertices is connected by exactly one arrow and results the number of edges $E=21=\dfrac{7\cdot6}{2}$ , hence exactly the number of edges in the clique with $7$ vertices.

From 1), 2), 3) results: $n\ge7$ .

$\textbf{The minimum value of \textit{n} is 7. The construction of the 7 committees.}$
We will prove: it is always possible to divide the Senate into $7$ committees so that no senator hates another senator on his or her committee.

$\textbf{Step A: }$ The graph $\textbf{S}_{\textbf{0}}=\textbf{G}_{\textbf{2}}$ contains $M_0=51$ vertices. Denote $m_v$ the degree of the vertex $v\in\{1,2,...,50,51\}$ in the graph $\textbf{S}_{\textbf{0}}$ .
The number of edges in $\textbf{S}_{\textbf{0}}$ is $E_0=\dfrac{1}{2}\cdot \sum_{v=1}^{51}m_v\le153$ .
Let be $M_1$ the number of vertices with the degree $m_v\ge7$ in $\textbf{S}_{\textbf{0}}$ and $51-M_1$ the number of vertices with the degree $3\le m_v\le6$ .
Results: $7M_1+3(51-M_1)\le2\cdot E_0\le2\cdot153\Longrightarrow M_1\le 38$ . Denote $\textbf{S}_{\textbf{1}}$ the set which contains the $M_1$ vertices with the degree $m_v\ge7$ .

$\textbf{Step B: }$ For $k=1,2,...$ and the subset $\textbf{S}_{\textbf{k}}\subset\textbf{G}_{\textbf{2}}$ with $M_k$ vertices, we apply successively the algorithm: we select the $M_{k+1}$ vertices with the degree $m_v\ge7$ in $\textbf{S}_{\textbf{k}}$ . These vertices form a new subset $\textbf{S}_{\textbf{k+1}}\subset\textbf{S}_{\textbf{k}}$ .
a) the number of edges in the subgraph $\textbf{S}_{\textbf{k}}$ is $E_k\le 3M_k$ .
b) the number of vertices with the degree $m_v\ge7$ in $\textbf{S}_{\textbf{k}}$ is $M_{k+1}$ .
c) results: $7M_{k+1}\le 2E_{k}\le 2\cdot3M_k\Longrightarrow M_{k+1}\le\dfrac{6}{7}\cdot M_k<M_k$ .

After a finite number of steps, we obtain a subset $\textbf{S}_{\textbf{N}}$ with $M_{_{N}}$ vertices such that $M_{_{N}}\le 7$ and $M_{_{N-1}}>7$ .

$\textbf{Step C: }$ The construction of the committees.
We obtain a succession of subsets of $\textbf{S}_{\textbf{0}}:\;\textbf{S}_{\textbf{N}}\subset \textbf{S}_{\textbf{N-1}}\subset...\textbf{S}_{\textbf{1}}\subset\textbf{S}_{\textbf{0}}$ and
$M_{_{N}}\le 7<M_{_{N-1}}<...<M_1<M_0=51$ .
1) The $M_{_{N}}$ senators from $\textbf{S}_{\textbf{N}}$ are "chiefs of committees" (the first member in committee). We complete the remaining $7-M_{_{N}}$ "chiefs of committees" with senators from the set $\textbf{S}_{\textbf{N-1}}$ .
2) We place in committees the remaining senators from $\textbf{S}_{\textbf{N-1}}$ , then the senators from $\textbf{S}_{\textbf{N-2}}$ and we continue the process until we distribute all senators.
This step is always possible: any vertex $V\in\textbf{S}_{\textbf{k}}\setminus\textbf{S}_{\textbf{k+1}}\ne\phi$ has the degree $m_{_V}\le6$ in the subgraph $\textbf{S}_{\textbf{k}}$ . The vertices from $\textbf{S}_{\textbf{k}}$ connected with $V$ by an edge belong to $n_{_V}\le m_{_V}\le6$ committees and we can place the vertex $V$ in one of the remaining $7-n_{_V}$ committees.

$\textbf{Final answer:}$
The smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee is $n_{min}=7$ .

$\textbf{Observation: }$ Applying this method, results $n_{min}=7$ for any value $M_0\ge7$ .

$\textbf{Example with M}_{\textbf{0}}\textbf{=12 vertices and E}_{\textbf{0}}\textbf{=36 edges}$
Consider the graph $\textbf{G}_{\textbf{1}}$ with $12$ vertices numbered $\{1,2,...,11,12\}$ :
a) the vertices $1,2,3,4,5,6,7$ form a clique with $21$ arrows
$1\to2\to3\to4\to5\to6\to7\to1$ ;
$1\to3\to5\to7\to2\to4\to6\to1$ ;
$1\to4\to7\to3\to6\to2\to5\to1$ .
b) $8\to\{1,2,12\};\;9\to\{3,4,12\};\;10\to\{5,6,12\};\;11\to\{6,7,12\}$ ;
c) $12\to\{1,2,3\}$ .

The corresponding graph $\textbf{S}_{\textbf{0}}=\textbf{G}_{\textbf{2}}$ contains $12$ vertices and $36$ edges.

$\textbf{Step A: }$ We identify in $\textbf{S}_{\textbf{0}}$ the vertices $v$ with degree $m_v\ge7:\;\textbf{S}_{\textbf{1}}=\{1,2,3,4,5,6,7,12\}$ , hence $M_1=8$ .

$\textbf{Step B: }$ We identify the vertices $v$ with degree $m_v\ge7$ in $\textbf{S}_{\textbf{1}}:\;\textbf{S}_{\textbf{2}}=\{1,2,3\}$ , hence $M_2=3$ .

$\textbf{Step C: }$
We construct the committees $C_1,C_2,...,C_7$ :

a) The first $3$ chiefs of committees from $\textbf{S}_{\textbf{2}}:\quad 1\in C_1;\;2\in C_2;\;3\in C_3$ ;

b) The next $4$ chiefs of committees from $\textbf{S}_{\textbf{1}}\setminus\textbf{S}_{\textbf{2}}:\quad 4\in C_4;\;5\in C_5;\;6\in C_6;\;7\in C_7$ ;

c) We place the remaining senators from $\textbf{S}_{\textbf{1}}\setminus\textbf{S}_{\textbf{2}}:\quad 12\in C_4$ ;

d) We place the remaining senators from $\textbf{S}_{\textbf{0}}\setminus\textbf{S}_{\textbf{1}}:\quad 8\in C_3;\;9\in C_1;\;10\in C_1;\;11\in C_1$ .

Result the committees:

$C_1=\{1,9,10,11\};\quad C_2=\{2\};\quad C_3=\{3,8\};\quad C_4=\{4,12\}$ ;

$C_5=\{5\};\;C_6=\{6\};\;C_7=\{7\}$ .

Of course, the distribution of the senators is not unique. In the previous example, we placed each senator in the first free committee. But are possible other more equilibrated distributions, for example:

$C_1=\{1,9\};\quad C_2=\{2,10\};\quad C_3=\{3,8\};\quad C_4=\{4,12\}$ ;

$C_5=\{5,11\};\;C_6=\{6\};\;C_7=\{7\}$ .

Attachments:

This post has been edited 1 time. Last edited by WallyWalrus, Mar 31, 2025, 5:24 PM

Z K Y

The post below has been deleted. Click to close.

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

221 posts

#5 h Mar 31, 2025, 5:32 PM

Y by

sadas123 wrote:

There are 51 senators in a Senate. The Senate needs to be divided into $n$ committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If A hates B, then B does not necessarily hate A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee.

I was confused on this problem too in the Three year mathcounts marathon, thanks so much for the solution!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a