Is there a strategy for five of the children that will ensure that all five will be assigned to the same class?

Poll choices
Posted 1 month.

4 Comments

  • Mark Bennet - 4 weeks ago

    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.

    Hence the answer is NO.

  • Martin Tran - 5 weeks ago

    Yes

Leave a Comment

0/4000 chars


Submit Comment