Olympiad Combinatorics

Exercises 
1. [Activity Selection Problem] 
On a particular day, there are n events (say, movies, classes, 
parties, etc.) you want to attend. Call the events E
1
, E
2
, …, E
n
and let E
i
start at time s
i
and finish at time f
i
. You are only 
allowed to attend events that do not overlap (that is, one 
should finish before the other starts). Provide an efficient 
algorithm that selects as many events as possible while 

---

Olympiad Combinatorics 
22 
satisfying this condition.
(Note: We have not defined what “efficient” here means. Note 
that this problem can be solved by simply testing all 2n 
possible combinations of events, and taking the best 
combination that works. However, this uses a number of steps 
that is exponential in n. By efficient, we mean a procedure that 
is guaranteed to require at most a number of steps that is 
polynomial in n).
2. [Weighted Activity Selection] 
Solve the following generalization of the previous problem: 
event E
i
has now weight w
i
and the objective is not to 
maximize the number of activities attended, but the sum of the 
weights of all activities attended.
3. [Russia 1961] 
Real numbers are written in an m × n table. It is permissible to 
reverse the signs of all the numbers in any row or column. 
Prove that after a number of these operations, we can make 
the sum of the numbers along each line (row or column) 
nonnegative. 
4. Given 2n points in the plane with no three collinear, show that 
it is possible to pair them up in such a way that the n line 
segments joining paired points do not intersect.