2
$\begingroup$

There are 10 students in a class:

  1. Michael
  2. Michelle
  3. Jack
  4. Daniel
  5. James
  6. Jane
  7. Tom
  8. Thompson
  9. Chris
  10. Tracy

These are the pairs that like to talk together in class:

  1. Michael - Michelle
  2. Michael - Jack
  3. Michael - Daniel
  4. Michelle - James
  5. Michelle - Jane
  6. Jane - Tom
  7. Jane - Thompson
  8. Thompson - Chris
  9. Jack - Thompson
  10. Jack - Tracy
  11. Daniel - Tom
  12. Daniel - Chris
  13. James - Tracy
  14. James - Chris
  15. Tom - Tracy

Proof that there is no method to divide 10 students into 3 groups so that each group does not have a pair that likes to talk together.

I tried to use contradiction: Suppose that there are a way to do this. 10 students would be divided into 3 groups as such

3 - 3 - 4

I also notice that each student likes to talk to three other students

But i'm stuck here and don't know what to do next

$\endgroup$
1
  • $\begingroup$ Just checked that there are a total of 20 solutions. Four for each of the five groups of four people that we can group together. $\endgroup$
    – AnilCh
    Jul 26, 2021 at 9:20

1 Answer 1

1
$\begingroup$

How about:

  • Michael, Chris, Jane, Tracy
  • Michelle, Jack, Daniel
  • Tom, Thompson, James
$\endgroup$
2
  • $\begingroup$ Could you tell me how you got this answer $\endgroup$
    – Kain
    Jul 26, 2021 at 8:11
  • $\begingroup$ I forced a 4-group with Michael, and picked Chris because they both like Daniel. The rest was luck. $\endgroup$
    – JMP
    Jul 26, 2021 at 8:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .