1998-09 Solution
See if you can see the pattern from the example of 20 students. This
matrix shows the people in the columns and rows (1 means student
number 1, etc) and the day they meet inside the matrix. E.g., On day
#1, the students are paired as such ([x y] means student x is paired
with student y): [1 2] [3 19] [4 18] ... [10 12] [11 20]. Here's
C code
that generated the matrix.
unix% ./partners
./partners v1.0 by Dan Garcia
Enter the number of students to be paired up (must be even): 20
Partner Table (people on rows and columns, matrix contains day they meet)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
+---------------------------------------------------------
1| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
2| 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2
3| 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 4
4| 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 6
5| 9 10 11 12 13 14 15 16 17 18 19 1 2 3 8
6| 11 12 13 14 15 16 17 18 19 1 2 3 4 10
7| 13 14 15 16 17 18 19 1 2 3 4 5 12
8| 15 16 17 18 19 1 2 3 4 5 6 14
9| 17 18 19 1 2 3 4 5 6 7 16
10| 19 1 2 3 4 5 6 7 8 18
11| 2 3 4 5 6 7 8 9 1
12| 4 5 6 7 8 9 10 3
13| 6 7 8 9 10 11 5
14| 8 9 10 11 12 7
15| 10 11 12 13 9
16| 12 13 14 11
17| 14 15 13
18| 16 15
19| 17
Parsing the table into a useful form:
Day 1:[1-2][3-19][4-18][5-17][6-16][7-15][8-14][9-13][10-12][11-20]
Day 2:[1-3][2-20][4-19][5-18][6-17][7-16][8-15][9-14][10-13][11-12]
Day 3:[1-4][2-3][5-19][6-18][7-17][8-16][9-15][10-14][11-13][12-20]
Day 4:[1-5][2-4][3-20][6-19][7-18][8-17][9-16][10-15][11-14][12-13]
Day 5:[1-6][2-5][3-4][7-19][8-18][9-17][10-16][11-15][12-14][13-20]
Day 6:[1-7][2-6][3-5][4-20][8-19][9-18][10-17][11-16][12-15][13-14]
Day 7:[1-8][2-7][3-6][4-5][9-19][10-18][11-17][12-16][13-15][14-20]
Day 8:[1-9][2-8][3-7][4-6][5-20][10-19][11-18][12-17][13-16][14-15]
Day 9:[1-10][2-9][3-8][4-7][5-6][11-19][12-18][13-17][14-16][15-20]
Day 10:[1-11][2-10][3-9][4-8][5-7][6-20][12-19][13-18][14-17][15-16]
Day 11:[1-12][2-11][3-10][4-9][5-8][6-7][13-19][14-18][15-17][16-20]
Day 12:[1-13][2-12][3-11][4-10][5-9][6-8][7-20][14-19][15-18][16-17]
Day 13:[1-14][2-13][3-12][4-11][5-10][6-9][7-8][15-19][16-18][17-20]
Day 14:[1-15][2-14][3-13][4-12][5-11][6-10][7-9][8-20][16-19][17-18]
Day 15:[1-16][2-15][3-14][4-13][5-12][6-11][7-10][8-9][17-19][18-20]
Day 16:[1-17][2-16][3-15][4-14][5-13][6-12][7-11][8-10][9-20][18-19]
Day 17:[1-18][2-17][3-16][4-15][5-14][6-13][7-12][8-11][9-10][19-20]
Day 18:[1-19][2-18][3-17][4-16][5-15][6-14][7-13][8-12][9-11][10-20]
Day 19:[1-20][2-19][3-18][4-17][5-16][6-15][7-14][8-13][9-12][10-11]
WWW Maven: Dan
Garcia (ddgarcia@cs.berkeley.edu)
Send me feedback
