Haters gonna hate

Question

In a classroom, there are $20$ students and every student mutually hates exactly $3$ other students in the class. (If X hates Y, Y hates X as well.)

The principal summons some of the students from this class and somehow within this group of student, no one hates each other.

What could be the maximum number of students the principal summoned?

For example, let say there are 6 students in the class, the student hate graph is somehow like below;

• A hates B,C,D
• B hates A,C,E
• C hates A,B,F
• D hates A,E,F
• E hates B,D,F
• F hates C,D,E

so if principal called A, for the maximum number of students, B,C,D cannot be in this group, then E could be the other student, and since E hates F as well. there could be only 2 people in this setup.

Answer 1

The greatest number of students that could be summoned is

ten.

Proof you cannot summon more:

Suppose $n$ people are summoned. Imagine everyone summoned sent a hate letter to the three people they hated. Then $3n$ hate letters are sent, and the $20-n$ people not summoned each receive at most $3$ letters apiece. Therefore, $3(20-n)\ge 3n$, proving $n\le 10$.

Here is a situation where the principle can summon that many:

The first 12 students are divided into four families A, B, C and D, with three students per family. The A family hates the B family, and the C family hates the D family.

The remaining eight students are named Sarah, Tommy, Ursula,..., Zach, and they are arranged like a cube so edges correspond to pairs which hate each other.

    S–––T
   /|  /|
  U–––V |
  | W–|–X
  |/  |/
  Y––-Z

The principle summons the A and C families, along with Sarah, Vanessa, Xavier and Yolanda.

Answer 2

Accepted answer nailed it, but here's another combination that works:

Put the students in two groups: 1 to 10, and 11 to 20. Student 1 hates 11, 12 and 13; Student 2 hates 12, 13, 14; etc... Then roll over when you hit 20: Student 9 hates 19, 20, 11, Student 10 hates 20, 11, 12.

Answer 3

Answer:

It's 10.

Explanation:

Essentially what you are saying is that there exists a group of 20 nodes where all nodes have degree 3. My initial chicken scratch of the problem was to fill up the nodes with degree 3 most efficiently to get something like this for the first 6 students:

$\hskip2in$

Here, a double-sided arrow means "mutual hate". Once you get to the seventh student he/she can't hate anyone in this group because that would mean a student from this group has degree 4, so you start optimally finding degrees again, which just makes another group like this:

$\hskip2in$

And again for the remaining students:

$\hskip2in$

However, there are two left (S & T). They cannot hate anyone in these three groups (degree 3 constraint), so either one hate bond between any two people in EACH group is broken to give S three people to hate and T as well, like so:

$\hskip1.5in$

or S and T hate one another and one hate bond between any two people in TWO groups is broken to give S two more people to hate and T as well, like so:

$\hskip2in$

Now, in either case, circle the disjoint students, i.e., circle students in such a way that no two students share the same edge color (double arrow). Circling them in this way ensures that you're picking students that don't hate one another, as they don't share a hate bond. It's also what's known as the independent set. Notice that the maximum is 10 for both scenarios. :-)

For example:

$\hskip2in$

Interestingly, it turns out this problem is in fact a case of a larger generalized notion. Mathematically speaking, what is being asked is "What is the maximum size of the independent set on any $d$-regular graph on $v$ vertices?" Where, here, $d=3$ and $v=20$. Moshe Rosenfeld has discovered this to follow the below equation:

$$F(v,d) = \min\{\lfloor v/2\rfloor, v-d\}$$

So, for $F(20,3)$ we get the following:

$$F(20,3) = \min\{\lfloor 20/2\rfloor, 20-3\}=\min\{10,17\}=10$$

Which is cool because now you can generalize for any number of students and any number (one less than the number of students) of mutual hate bonds, which isn't really all that practical because who in a room of other people hates exactly the same amount of people?

By the way, there are 500,000+ connected graphs like this (the fourth one in this post). They all look something like this:

All the red students can be chosen and they'll all like each other. Notice how they're not all 10. Some have 9. Some have 8.

---

Notes:

_{Erick Wong (math se) found the above linked thesis.}

_{$\lfloor \hspace{0.25cm} \rfloor$ is the floor function.}

_{$\min\{\}$ is the min function.}

Answer 4

The answer is:

0. If every student hates 3 students and the feeling is mutual, all students are hated.

EDIT: After a series of edits to the question, this formerly correct answer has been invalidated. Leaving for posterity.

Answer 5

10 is achievable

Arbitrarily divide the students into two teams, $A$ and $B$, of size 10. We'll make sure students from the same team never hate each other. That way the principle can summon 10 mutually non-hating students by calling every member of a team.

Arbitrarily number the students within each team from $0$ to $9$. To satisfy the "everyone hates 3 people" constraint, make student $A_k$ hate student $B_{k+j \pmod{10}}$ for every $k \in [0, 9]$ and every $j \in [0, 2]$.

Note that this approach trivially generalizes to any even number $2n$ of students who must hate $d \leq n$ people. There will always be two teams of $n$ people who don't hate any of their teammates.

10 is the best possible

Suppose there are 11 people who don't hate each other. Each must hate 3 people, which means we have 33 hate-tokens to distribute over all the players. But there's only 9 players outside of the group of 11 players, and each of them can only accept 3 hate-tokens for a total of 27. That leaves 6 hate-tokens, and the only people who can claim them are in the group of 11 players. This contradicts our assumption that no one in the group of 11 players hates each other.

This proof generalizes to any number of students larger than 10. It also generalizes to the case of an even number $2n$ students who must all hate $d \leq n$ people. For this subset of the possible cases, the maximum group size is $n$.

Answer 6

Partial:

Let's turn the students into a graph. because we hate students but we love graphs.
each vertex is a student and each edge is the "hate".
This will make a cubic graph with 20 vertices.
Like anyone of those presented here.
just pick one.

Now I'm stuck.

What is left to do is color the graph with as few colors as possible and pick the dominant color.

I'm not stuck anymore.

Just found the answer below int he same page.
This graph has the chromatic number 3.
since colors can be switched among each other, it means the color distribution has to be 7,7,6. This means that the max number is 7.
I know, I know...lousy proof. I'm working on a better explanation.

Answer 7

11 cannot be selected

Construct a graph with 20 vertices and 3 edges connected to each vertex. This leads to 30 total edges. If 11 students were selected, there would be 33 edge beginnings, meaning that at least one edge is counted twice.

10 can be selected

Consider the complete bipartite graph with M=N=10. In this graph, there are two groups of 10 students that hate every member in the other group. Remove edges from this graph until each student hates 3 members of the other group. (This can be done, arrange each group of 10 into circles with the same normal vector. Then keep only the edges to the three closest nodes in the other circle.)

Note that this last observation proves that each student could hate 10 other students and the answer would be the same.

Answer 8

The maximum size of such group can be

5

And the explanation is :

Let us take student #1, who hates 2,3,4 and student # 5 who hates 6,7,8 and so on till student # 17 who hates 18,19,20.

With this, we get

5 groups and the 'heads' of each group cannot hate each other thereby leaving the maximum size of the summoned group to be FIVE