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 years 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 years 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.
Hence the answer is NO.
Martin Tran - 5 years ago
Yes
Leave a Comment
Create your own.
Opinions! We all have them. Find out what people really think with polls and surveys from Crowdsignal.
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.
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.
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.
Hence the answer is NO.
Yes