10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts on the problem? $\endgroup$ – Servaes May 8 '19 at 12:58
  • 3
    $\begingroup$ @Servaes: Far more difficult than it seems! $\endgroup$ – Bernardo Recamán Santos May 8 '19 at 13:02
  • 4
    $\begingroup$ Each student must sit together with $24$ other students, so $\tfrac{24\times25}{2}=300$ pairs must be made. Each day a total of $$\frac{8\times9+3\times4+5\times12}{2}=72,$$ pairs are made, which shows that we will need at least $5$ weeks for every student to have sat next to every other student. In $5$ weeks a total of $5\times72=360$ pairs are made, so this gives quite a bit of leeway to make the necessary $300$ pairs. A bit of trial and error would go a long way? Perhaps some affine transformations will do the trick? $\endgroup$ – Servaes May 8 '19 at 13:03
  • $\begingroup$ @Servaes Why did you delete your answer? I checked your solution, it worked! $\endgroup$ – Mike Earnest May 9 '19 at 1:14
  • $\begingroup$ @MikeEarnest Ha! It was late last night, I was tinkering with it a bit more in an attempt to get it down to six weeks (to no avail), and then reverted to the wrong configuration, apparently, so I believed I made a mistake. Thanks for checking :) I'll recheck it for myself as well later today. $\endgroup$ – Servaes May 9 '19 at 11:21
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I have now found a 5-week set that uses $299$ pairs, missing out only one. It really looks like a 5-week solution should be possible. $\endgroup$ – Jaap Scherphuis May 9 '19 at 13:45
  • $\begingroup$ I'm looking forward to seeing it! $\endgroup$ – Servaes May 9 '19 at 13:45
  • 1
    $\begingroup$ @Servaes I have edited my answer to show the $299$ pair near-solution. $\endgroup$ – Jaap Scherphuis May 9 '19 at 13:57
  • 1
    $\begingroup$ +1 and am I the only person visualizing this solution as: every student goes to school for only $5$ weeks, except for students $12$ and $21$ who "failed" the class and had to attend during the extra $6$th week, sitting side by side in an otherwise empty classroom? :D $\endgroup$ – antkam May 9 '19 at 14:35
  • 1
    $\begingroup$ @BernardoRecamánSantos Given that it takes only one week for $4$ students, the growth is not quite linear. $\endgroup$ – Servaes May 9 '19 at 18:31
1
$\begingroup$

The following are sittings for seven weeks that allow everyone to meet everyone else:

 Week 1            Week 2            Week 3
 [ 0  1  2  3  4]  [18 16 19 15 17]  [ 7  9  5  8  6]
 [ 5  6  7  8  9]  [ 8  6  9  5  7]  [ 2  4  0  3  1]
 [10 11 12 13 14]  [23 21 24 20 22]  [17 19 15 18 16]
 [15 16 17 18 19]  [ 3  1  4  0  2]  [12 14 10 13 11]
 [20 21 22 23 24]  [13 11 14 10 12]  [22 24 20 23 21]

 Week 4            Week 5            Week 6
 [ 8 15  1 20 13]  [20 12  1 19  7]  [22 14  7  0 12]
 [11 22 19  3 18]  [11  9  5 10 21]  [20 16 21  4  3]
 [ 4  6 17 24  5]  [17  8 22 14 23]  [17  1  6  5 23]
 [ 2 14 10  9 16]  [24 13  4  3 15]  [13 18  8  2 15]
 [21 12 23  7  0]  [ 2 18  0 16  6]  [ 9 19 10 11 24]

 Week 7
 [ 1 10 21  7  4]
 [ 3 19 17 18 24]
 [15 11  0 22  5]
 [12 16 23 20 13]
 [19  2  8  6  9]
$\endgroup$
  • $\begingroup$ This validates via the python script I wrote. $\endgroup$ – TemporalWolf May 8 '19 at 23:31
  • $\begingroup$ @TemporalWolf: Thank you! I updated my answer for seven weeks. $\endgroup$ – Freddy Barrera May 9 '19 at 4:40
1
$\begingroup$

This is only a partial answer, which shows that the fewest number of weeks in which this can happen is either $5$ or $6$. I suspect the number is $5$, but I do not have a proof.

To see that at least $5$ sittings are required, note that we require a total of $\tbinom{25}{24}=300$ meetings between students. A quick count shows that there are $$\frac12(4\times3+12\times5+9\times8)=72,$$ meetings for each sitting, so we will need at least $5$ weeks for all students to meet.

Here is a series of six sittings in which every student meets every other student, which I have constructed and checked by hand, so there may be a mistake. The time spent constructing this convinces me that it is very likely possible in only five sittings; without (too) much effort, the first five sittings miss only $20$ pairs of students.

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

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

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

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

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

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

Here is an earlier series of seven sittings in which every student meets every other student:

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

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

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

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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