Suppose that there are 51 students in a preschool. The students need to be divided into groups in order to play games. However, each student hates 3 other students, and if A hates B, they cannot be in the same group. What is the smallest number of groups to ensure it always works?
Asked
Active
Viewed 115 times
0
-
Welcome to MSE. Can you show your attempt? – Culver Kwan Aug 13 '19 at 03:43
-
I think that in the worst case: 1 hates 2 3 4, 2 hates 3 4 5 and so on. I can split it into 7 groups, although I am not sure. Group 1 = 1,5,9,13...,45 Group 2 = 2,6,10,14...,46 Group 3 = 3,7,11,15...,47 Group 4 = 4,8,12,16...,48 Group 5 = 49 Group 6 = 50 Group 7 = 51. I don't know if can do better. – user690234 Aug 19 '19 at 09:51
1 Answers
1
The answer is 2 since if everyone hates persons 1, 2, 3 and 1, 2, 3 don't hate one another it works.
aerupons
- 37
-
The question says that you have to make sure that it can always work, no matter who hates who – user690234 Aug 25 '19 at 09:16