Question: I have sixteen students in my class who sit in four rows of four. 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?

How many if my students were 25?

Answer: 
Partial answer to Question 1.

> 
> First, the average number of friends a student gets per week is
> $$\frac{4\times 3 +8\times 5+4\times 8}{16}=5.25$$
>  (there are $4$ corners each of which has $3$ friends, and so on).  
> 
>   
> 
> At the end of the day, we want each student to have had $15$ different friends, so this has to take **at least $3$ weeks.**
> Moreover, in three weeks at most $12$ students can be in the center once:
>  [![enter image description here](https://i.stack.imgur.com/RaUDE.jpg)](https://i.stack.imgur.com/RaUDE.jpg)  
> 
>   
> 
>  Those who are never in the center will need to be on an edge all three times to get $3\times 5$ friends.  
> 
>   
> 
>  The scheme above is therefore the only way to get 15 friends for everyone in 3 rounds. It is very rigid - there is no room for redundancy for the all-edgers, and there can be one redundancy for the others. Yet I can't prove yet that the constraints are too heavy to be met.
> 
> 
>
As a starting point for Question 2, here it is done in

> 
>  7 weeks
> 
> 
> 

Solution

> 
> 
> ```
> 
> 01234   IG968   HCFA1   97HEP   BA92H   HDCE0   EB095
> 56789   B1HKJ   3P4JD   MF8AK   L3CJ8   8K1F2   GN46H
> ABCDE   P4307   E20BM   N3LI4   KDGN7   GMBNI   3IACK
> FGHIJ   D5MAL   7698K   J50D6   50461   P6LJA   DF712
> KLMNP   NF2CE   GILN5   1CG2B   IEMPF   93475   JM8PL
> 
> ```
> 
> 
> 
>