## 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