## TYI 39 : Can a coalition of children guarantees all being in the same class?

There is a class of children that have just finished elementary school. Now they all move from elementary school to high school and classes are reshuffled. Each child lists three friends, and the assignment of children into classes ensures that each child will have at least one of these three friends in his class.

One of the children heard from five of his schoolmates that they found that they can make their selections in a way that will ensure that all five will be assigned to the same class!

### Test your intuition: Is there a strategy for five of the children that will ensure that all five will be assigned to the same class?

Can a larger group of children coordinate their choices to ensure that they will all necessarily be assigned to the same class?

Bonus question: In case that every child lists only two friends and one of them is guaranteed to be in the same class. Is there a strategy of five children that will ensure they are in the same class?

Answer to Bonus question: Yes. For three children you let every one choose the other two. For the remaining children you let each one choose two among the three.

This entry was posted in Combinatorics, Economics, Mathematics to the rescue, Test your intuition and tagged . Bookmark the permalink.

### 3 Responses to TYI 39 : Can a coalition of children guarantees all being in the same class?

1. Joseph says:

Are you planning to post a spoiler eventually? I can’t test my intuition if I have nothing to test it against. 🙂

• Gil Kalai says:

Hi Joseph, yes I will post a solution.