43
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ please comment why did you vote negative? I believe this is a good question. $\endgroup$ – Oray Aug 1 '17 at 14:27
  • $\begingroup$ I didn't downvote but I think it comes from the fact explained in Forklift's answer, where your first assumption is contradicting the second paragraph you have. Unless that IS the intended answer, which will makes the question less interesting $\endgroup$ – Alex Aug 1 '17 at 14:29
  • 11
    $\begingroup$ You asked a question that was not quite defined, then rejected the correct answer and changed the question. A new answer appeared which satisfied the new parameters, you have changed the question again. This is a likely cause of downvotes. $\endgroup$ – Forklift Aug 1 '17 at 14:35
  • 27
    $\begingroup$ The reason for the downvotes should be obvious. It's right there, in the title. :) $\endgroup$ – Rubio Aug 1 '17 at 14:38
  • $\begingroup$ I think I found the misunderstanding - "The principal summons some of the students from this class and somehow no one hates anyone in the summoned group." is interpret as no one hates anyone in the summoned group, which is impossible $\endgroup$ – Alex Aug 1 '17 at 14:39
62
$\begingroup$

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.

$\endgroup$
  • 14
    $\begingroup$ pretty good graph you drew :) $\endgroup$ – Oray Aug 1 '17 at 15:53
  • 2
    $\begingroup$ If you like to think of it as a graph, then you are looking for the maximum possible independent set in a 3 regular 20 vertices graph. In 1964 Rosenfeld showed this to be <= min (20/2,n-3) =10 $\endgroup$ – lPlant Aug 1 '17 at 18:02
  • $\begingroup$ @MikeEarnest, well, "..The principle summons the A and C families, along with Sarah, Vanessa, Xavier and Yolanda..." Makes the number 6 rather than 10. As A family can be represented by only one person ... not more than one ...(if more than one is summnoned from A family, we viloate the problem's condition). Similarly with the family of 'C' thereby leading to the max. number as 6. Oray ... please check ! $\endgroup$ – Mea Culpa Nay Aug 2 '17 at 5:47
  • $\begingroup$ @MeaCulpaNay he calls for all 3 members of family A (who all 3 hate the members of family B) and all 3 members of family C (who hate D). Then the 4 from the cube. This is 10. $\endgroup$ – Forklift Aug 2 '17 at 5:52
  • $\begingroup$ @Forklift...hmmm ..then the question is invalid ..as it speaks about individual student hating another individual student... not a group hating another group ... If the requirement is like that ...it should have been mentioned in the problem clearly ! Definitely -1 from my side... if that is the case ...:-) $\endgroup$ – Mea Culpa Nay Aug 2 '17 at 5:56
11
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Yes indeed. We must prove that no more than $n/2$ students can be summoned (which Mike Earnest did). To prove that the bound $n/2$ can be attained, it is enough to prove that among balanced bipartite 20-node graphs, at least one is cubic, as you showed. $\endgroup$ – Rosie F Aug 2 '17 at 9:10
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ They all mutually hate exactly 3 students. Therefore all students are hated but not by everyone. Each student is hated by 3 others $\endgroup$ – BMS21 Aug 1 '17 at 14:18
  • $\begingroup$ If ALL students hate, and ALL hate is mutual, then ALL student MUST be hated as well. $\endgroup$ – Forklift Aug 1 '17 at 14:19
  • $\begingroup$ ALL students are hated by 3 people exactly which are the people they hate therefore there will be 17 students they don't hate and who don't hate them! $\endgroup$ – BMS21 Aug 1 '17 at 14:21
  • 3
    $\begingroup$ I think you are misunderstanding. Since every students hates at least one student, and all hate is returned, it is mathematically impossible for any student not to be hated. When you hate, you are hated. All hate, therefore all must be hated. $\endgroup$ – Forklift Aug 1 '17 at 14:24
  • 1
    $\begingroup$ Yes but each person hates 3 people so they are hated by THOSE 3 PEOPLE ONLY. Therefore there are 17 people they get along with fine. All students are hated yes but NOT BY EVERYONE. $\endgroup$ – BMS21 Aug 1 '17 at 14:28
7
$\begingroup$

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$enter image description here

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$enter image description here

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$enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ by outer 9 im assuming you don't mean the 9 on the edge which are all connected $\endgroup$ – BMS21 Aug 8 '17 at 16:16
  • $\begingroup$ sorry to burst your bubble XD $\endgroup$ – BMS21 Aug 8 '17 at 16:22
  • $\begingroup$ It needed to be bursted. $\endgroup$ – user39732 Aug 8 '17 at 16:24
4
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you think all the graph have to be connected each other? there could not be some seperated graphs? $\endgroup$ – Oray Aug 1 '17 at 14:47
  • $\begingroup$ @Oray My attempts at separate groups seems to lower the number possible of summoning at once $\endgroup$ – BMS21 Aug 1 '17 at 15:07
  • $\begingroup$ @Marius I can add a net to show visually if you want? $\endgroup$ – BMS21 Aug 1 '17 at 15:08
  • $\begingroup$ @Oray. Oooo. I see what you mean. Will post a slightlly changed answer when i reach a computer. But the idea is similar. On the phone now. $\endgroup$ – Marius Aug 1 '17 at 15:36
  • $\begingroup$ The dodecahedral graph having chromatic number 3 does not imply that there does not exist a cubic 20 vertex graph with chromatic number 2. In fact, other answer disprove this assertion. $\endgroup$ – Jared Goguen Aug 2 '17 at 16:13
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.