Suppose each point in the interval $[0,1]$ has some of a set of $N$ properties. The total length of the intervals with property $i$ is $x_i$ ($0\le x_i \le 1$).


  1. What is the maximum and minimum of the length of intervals of points with exactly $m$ properties?
  2. Is there some none-zero-length interval with $m$ properties? This second question may be seen as part of the first one.

Not sure about what is the proper name of such kind of problems.

An example:

In a school, 80% of the students play basketball, 60% play football, 60% play tennis, 60% play baseball.

Question: Is it true that, there must be some students play all four of the sports? What is the maximum and minimum fraction of students play three of the four sports?


1 Answer 1


Introduce $2^4=16$ nonnegative decision variables, one for each subset of the four sports. They must sum to $1$, and the given percentages imply four additional linear constraints.

To determine whether some students must play all four sports, minimize the corresponding decision variable by using linear programming. The minimum is positive if and only if some students must play all four sports.

The fraction that play three sports is a sum of four decision variables and hence a linear function. You can again use linear programming to minimize or maximize.


You must log in to answer this question.

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