Getting everyone to meet everyone else

combinatorial-designscombinatoricsdiscrete mathematicsgraph theory

There are 25 students in a class who sit in five rows of five. Each week they sit in a different order.

After a number of weeks every student has sat next to every other student, next meaning side by side, one behind the other, or sitting diagonally together. What is the fewest number of weeks in which this can happen?

The case for 16 students sitting in four rows of four has been dealt with at:

https://puzzling.stackexchange.com/questions/83720/my-sixteen-friendly-students?noredirect=1#comment243063_83720

Best Answer

It can be done in 5 weeks:

  01 02 03 04 05       14 07 04 12 17
  06 07 08 09 10       25 18 22 01 20
  11 12 13 14 15       02 09 03 13 08
  16 17 18 19 20       16 23 06 21 24
  21 22 23 24 25       10 19 05 15 11

  09 19 02 14 17       02 22 23 12 24
  07 21 12 05 03       15 13 14 09 08
  23 25 01 24 11       10 18 11 01 17
  04 15 08 10 22       21 05 16 19 06
  13 16 18 06 20       07 20 03 25 04

  06 16 07 15 12
  14 24 17 10 03
  21 04 02 25 13
  18 20 11 22 05
  09 01 23 08 19

I used a relatively simple computer program to produce the last four seating arrangements. It used a "hill-climbing" optimisation, namely it repeatedly tried to swap to students at random, and if the total number of adjacent pairs increased then keep the swap or else put them back. To produce a seating arrangement, it runs the aforementioned optimisation a few times starting from a random seating, and then picks the best one it found (i.e. the one that introduces the most new pairs given any previous weeks' arrangements already chosen). I then had it produce sets of 5 seating arrangements until it found a set that contained all pairs.

I also set my program to find solutions for $N=6$. It found a 7-week solution:

  01 02 03 04 05 06      12 33 14 22 08 16
  07 08 09 10 11 12      05 23 35 04 06 36
  13 14 15 16 17 18      32 15 19 07 26 09
  19 20 21 22 23 24      01 24 11 28 17 25
  25 26 27 28 29 30      21 13 10 02 20 34
  31 32 33 34 35 36      29 31 30 27 18 03

  01 25 29 27 13 34      22 35 27 13 23 20
  14 03 05 16 02 06      31 14 36 03 12 21
  32 17 19 31 18 15      26 24 11 08 10 18
  35 21 33 09 36 07      15 34 25 07 19 06
  10 08 30 20 12 28      30 28 16 32 29 33
  23 26 11 22 04 24      09 01 04 02 05 17

  14 18 08 20 10 19      16 02 08 10 11 09
  28 05 32 29 01 34      20 34 14 33 21 35
  26 13 09 11 31 12      22 04 29 15 03 05
  03 22 35 23 27 15      36 19 31 07 30 18
  07 24 02 25 04 17      24 17 27 23 32 25
  16 33 36 21 06 30      13 26 01 06 28 12

  19 30 14 03 28 17
  02 12 16 06 31 08
  29 26 35 20 24 27
  04 18 01 05 07 09
  13 33 22 36 34 21
  15 25 10 32 23 11

There is a simple lower bound. There are $N^2$ students, so there are $N^2(N^2-1)/2$ pairs of students that need to sit adjacent to each other at some point. The number of adjacent pairs in one week's seating arrangement is $2N(N-1) + 2(N-1)^2 = 2(N-1)(2N-1)$. Divide them to get a lower bound on the number of weeks. Note that this grows quadratically in $N$.

For $N=5$ we get $300/72=4.167$ so $5$ weeks are necessary.
For $N=6$ we get $630/110=5.727$ so $6$ weeks are necessary.
However, given how hard it was to find a 7-week solution, it is almost surely not possible to attain a 6-week one.

Related Question