Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a class of 17 students, at the start students are to be paired each week with a new partner. This is done for 2 weeks, then on the third week they are to be put into a group of 4 which consists of students who haven't been partnered together before. How would I prove that this is impossible/possible?

EDIT: Sorry, I left out the most important info, allow a team of 3 for first 2 weeks and a team of 5 for the last.

share|improve this question
    
Well, one problem would be that 17 is odd... –  Zev Chonoles Apr 21 '11 at 12:38
    
Perhaps I'm being too literal, but with an odd number of students (17), how do you propose to pair each with a partner for even one week? –  hardmath Apr 21 '11 at 12:39
    
To prove it possible, one way is to exhibit an arrangement that satisfies the constraints. As each student is only paired with 5 or 6 others out of 16, this should be easy to accomplish. joriki has given an explicit general construction. –  Ross Millikan Apr 21 '11 at 13:23
add comment

1 Answer

up vote 1 down vote accepted

First off, it's trivially impossible since you can't pair 17 students (much less group them in 4). Assuming that you somehow deal with that problem (say, by letting one of them play games while the others work) and get to a multiple of $4$, you can show that this is possible if you have at least $8$ students as follows: Divide the students into groups of $4$, and arrange the groups in a cycle. Choose $2$ students from each group to pair with the preceding group in the cycle, and $2$ to pair with the following group in the cycle. In the first two weeks, form the $2$ possible pairs of students from the pairs of adjacent groups in the cycle with the students who have been designated to be thus paired. Then in the third week put them in the groups you formed.

[Edit in response to the edit to the question:] If you have $4n+1$ students and allow teams of $3$ and $5$, respectively, then it's no longer possible for $n=2$ (i.e. $9$ students), but possible for $n>2$ (i.e. $13, 17, \ldots$ students).

To see that it's impossible for $9$ students, note that the $5$ students in the team of $5$ would have to have had $5$ different partners in the first week, but there are only $4$ other students.

To see that it's possible for $13, 17, \ldots$ students, use the same grouping as in the $4n$ case, but designate one student as the "extra" student and put her in some team of $5$. Then in the first week, add her to arbitrary pairings between two adjacent teams of $4$ (which exist since there are at least $8$ students other than the $5$).

share|improve this answer
    
Awesome explanation. Now I have to translate that for my marketing tutorial. –  meiryo Apr 22 '11 at 2:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.