Sample problems for tutorial #1

1. The Stable Matching Problem we discussed in class was a simplified version of the more general Coop Student/Company Matching Problem that I mentioned initially. In this question, you will go back and consider the more general problem. Suppose that there are n students applying for jobs, and m companies where company i is looking for n_i COOP students. Suppose moreover that there are enough students to fill all of the positions, that every student has a ranking of companies in order of preference, and that each company has a ranking of students in order of preference. An assignment of students to companies is stable if neither of the following two situations arises:

   • There are two students s and s', and a company c such that s is assigned to c, s' is unemployed, and c prefers s' to s.
   • There are two students s and s', and companies c and c', such that s is assigned to c, s' is assigned to c', s prefers c' to c, and c' prefers s to s' (this is the usual type of instability we discussed in class).

   Describe an efficient algorithm that will produce a stable assignment of students to companies.

2. Prove or disprove each of the following two statements. That is, either prove that the statement is true, or give an example to show that it is false. Hint: exactly one of the statements is true.
   1. In every instance of the Stable Matching Problem, there is a stable matching containing a pair (w, m) such that w is ranked first on the preference list of m and m is ranked first on the preference list of w.
   2. Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (w, m) belongs to S.

3. (Induction review) Suppose you begin with a pile of n stones, and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r and s stones in them, respectively, you compute rs. Show that no matter how you split the pile, the sum of the products computed at each step equals n(n-1)/2. Here is an example that shows how the computation proceeds:

   

   The sum is 21+2+12+1+3+2+2+1+1 = 45, which is indeed 10 * 9 / 2.