In any of these situations where the number of options is greater than two, and pupils are required to use all their options, if two pupils choose each other, you can make them a pair and put all the others in a separate group (provided there are no constraints on the maximum number of pupils who can go into a class).

If pupils are not required to use all their options, they can guarantee to stay together (just make a directed chain for a minimal solution, or a directed cycle if each must use at least one choice)

The minimum number which can guarantee to stay together in the case where each pupil has three choices they must use is 7. For larger numbers, a group of seven can stick together and any others can choose three out of the seven.

So in similar problems with more choices, if there is a group which can hold together, so can any larger group, using a similar strategy.

The problem with $n$ pupils having $m$ choices of which $r$ must be satisfied looks interesting.

Lior Gishboliner - 5 weeks ago

5 children cannot guarantee they are assigned to the same class. Since there are 15 pairs (a,b) such that b is on a's list, and since there are 10 unordered pairs of children, there must be at least 5 pairs (a,b) s.t. a is on b's list and b is on a's list. A graph with 5 vertices and 5 edges must contain a matching of size 2, say (a,b) and (c,d). Suppose (wlog) that the fifth kid, e, has a on his list. Then putting a,b,e in one class and c,d in another is a legal assignment.

Seven kids have a strategy for being all put in the same class, by identifying themselves with the vertices of the 7-vertex Paley tournament and letting i be on j's list iff i-->j.

Gerhard - 5 weeks ago

There must be two kids A and B so that (A lists B) and (B lists A).
Otherwise the underlyng undirected 3-regular graph would be simple and
have an odd number of vertices; impossible.

The school assigns A and B to one class, and tyhe remainng three children C,D,E to another class.
Since each of C,D,E lists three friends, at least one must be different from A and B.

Mark Bennet- 4 weeks agoIn any of these situations where the number of options is greater than two, and pupils are required to use all their options, if two pupils choose each other, you can make them a pair and put all the others in a separate group (provided there are no constraints on the maximum number of pupils who can go into a class).

If pupils are not required to use all their options, they can guarantee to stay together (just make a directed chain for a minimal solution, or a directed cycle if each must use at least one choice)

The minimum number which can guarantee to stay together in the case where each pupil has three choices they must use is 7. For larger numbers, a group of seven can stick together and any others can choose three out of the seven.

So in similar problems with more choices, if there is a group which can hold together, so can any larger group, using a similar strategy.

The problem with $n$ pupils having $m$ choices of which $r$ must be satisfied looks interesting.

Lior Gishboliner- 5 weeks ago5 children cannot guarantee they are assigned to the same class. Since there are 15 pairs (a,b) such that b is on a's list, and since there are 10 unordered pairs of children, there must be at least 5 pairs (a,b) s.t. a is on b's list and b is on a's list. A graph with 5 vertices and 5 edges must contain a matching of size 2, say (a,b) and (c,d). Suppose (wlog) that the fifth kid, e, has a on his list. Then putting a,b,e in one class and c,d in another is a legal assignment.

Seven kids have a strategy for being all put in the same class, by identifying themselves with the vertices of the 7-vertex Paley tournament and letting i be on j's list iff i-->j.

Gerhard- 5 weeks agoThere must be two kids A and B so that (A lists B) and (B lists A).

Otherwise the underlyng undirected 3-regular graph would be simple and

have an odd number of vertices; impossible.

The school assigns A and B to one class, and tyhe remainng three children C,D,E to another class.

Since each of C,D,E lists three friends, at least one must be different from A and B.

Hence the answer is NO.

Martin Tran- 5 weeks agoYes