A 21-day solution - Kindergarten problem

(found by VE2IQ 2012.8.24)


  1: 1-2-3 4-5-6 7-8-9 10-11-12 13-14-15 16-17-18 19-20-21 22-23-24 25-26-27 28-29-30 
  2: 3-1-5 2-4-6 9-7-11 8-10-12 15-13-17 14-16-18 21-19-23 20-22-24 27-25-29 26-28-30 
  3: 4-3-5 1-6-2 10-9-11 7-12-8 16-15-17 13-18-14 22-21-23 19-24-20 28-27-29 25-30-26 
  4: 4-1-8 6-3-10 2-5-12 14-7-16 18-9-20 21-11-22 23-13-24 25-15-26 27-17-28 29-19-30 
  5: 1-21-3 5-23-7 9-25-11 12-27-13 14-29-15 16-2-17 18-4-19 20-6-22 24-8-26 28-10-30 
  6: 1-12-2 3-14-4 5-16-6 7-18-8 10-20-11 9-22-13 15-24-17 19-26-29 21-28-25 23-30-27 
  7: 9-1-10 8-6-11 2-22-3 4-16-12 14-23-15 17-26-18 20-5-21 24-7-25 29-13-30 27-19-28 
  8: 7-2-13 16-3-17 20-4-21 5-8-19 6-9-23 18-10-22 1-11-24 25-12-29 26-14-27 28-15-30 
  9: 1-17-4 2-18-3 7-20-8 6-21-9 5-24-26 10-25-19 11-27-15 12-28-13 16-29-23 14-30-22 
 10: 7-1-14 5-11-8 10-21-15 9-2-19 6-12-17 16-22-18 20-3-24 25-13-26 27-23-28 29-4-30 
 11: 9-5-10 1-15-2 3-25-4 13-6-14 11-16-19 12-26-20 21-7-22 23-17-29 18-27-24 28-8-30 
 12: 3-9-4 2-10-6 5-14-8 1-26-7 13-19-15 23-20-27 12-24-25 11-28-16 18-29-22 17-30-21 
 13: 17-6-18 3-7-4 16-9-19 23-10-27 26-11-29 20-12-21 1-13-5 25-14-28 8-15-22 2-30-24 
 14: 22-1-23 8-2-11 12-3-13 10-4-15 7-5-25 26-16-27 9-17-21 24-18-28 6-19-14 29-20-30 
 15: 4-8-13 2-21-14 12-22-19 11-23-26 1-24-6 16-25-17 15-18-30 3-27-5 7-28-20 9-29-10 
 16: 16-1-20 14-2-25 15-3-19 13-4-23 17-5-18 6-26-10 7-27-9 22-28-24 8-29-21 11-30-12 
 17: 29-7-30 24-9-28 3-11-4 10-13-12 5-15-6 8-17-14 1-19-18 26-21-27 2-23-16 20-25-22 
 18: 7-6-28 3-8-27 15-10-17 19-12-23 9-14-11 21-16-30 1-18-25 2-20-13 5-22-26 4-24-29 
 19: 23-3-29 27-6-30 17-7-19 16-8-25 13-9-15 12-14-22 11-18-20 10-24-21 2-26-4 1-28-5 
 20: 28-2-29 7-10-14 15-12-18 20-16-24 11-19-17 8-21-13 6-25-23 3-26-5 4-27-22 1-30-9 
 21: 25-1-27 28-3-30 13-7-15 12-9-26 16-10-19 11-17-20 21-18-23 4-22-8 2-24-14 5-29-6 

Pairings still available:
  1: [29]  [1]
  2: [27]  [1]
  4: [12,28]  [2]
  5: [19,30]  [2]
  6: [23]  [1]
  8: [23]  [1]
 11: [13,15]  [2]
 12: [4]  [1]
 13: [11,16]  [2]
 14: [20]  [1]
 15: [11,20]  [2]
 16: [13]  [1]
 17: [22]  [1]
 19: [5]  [1]
 20: [14,15]  [2]
 21: [25]  [1]
 22: [17]  [1]
 23: [6,8]  [2]
 25: [21]  [1]
 27: [2]  [1]
 28: [4]  [1]
 29: [1]  [1]
 30: [5]  [1]

Here is the problem: -------------------- A kindergarten class has 30 children. Every day at recess they go out for a walk. To keep them all safe and discourage straying the teacher has them form 10 rows of 3 across on the sidewalk. In each row the kid in the middle holds hands with those on either side. They decide to play a game: no one may hold hands with the same partner more than once. How many days could they keep this up without breaking the rule? There ought to be a solution for 21 days per the following reasoning: In any group of 30 individuals there are 30x29/2=435 unique pairings. With each day's walk, a row of 3 kids uses up 2 pairings so the 10 rows use up 20 pairings. Thus maximum days = 435/20 = 21.75. Since all kids have to participate to make up a complete day's walk, that means the upper bound is 21 days. The above solution is just one of many that are possible but I don't need to give them all, even one will prove it can be done. I can now definitely answer the question and state with confidence the kids can walk for 21 days. Now it's time to move on to something more challenging, hi!

See here for an 18-day solution