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: 
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
> 
> ```
> 
> 
> 
>
A quick intuitive answer:

For 16 students:

> 
>  6 weeks
> 
> 
> 

Reasoning (edited to account for the corner case, as pointed out by hexomino);

> 
> 2nd week: swap 1st and 3rd columns. 3rd week: swap 2nd and 4th columns. Do the same operations with the rows over the next two weeks. Before swapping, either the first or the preceding week's formation can be taken as the starting point. 5th week: swap the two middle columns. 6th week: swap the middle rows. At the beginning of the 7th week, each student would have been next to each other student.
> 
> 
> 

For 25 students:

> 
>  8 weeks
> 
> 
> 

Reasoning:

> 
>  Follow the above reasoning, except that the rows/columns to be swapped would be 1st/4th, 2nd/5th, 2nd/3rd, and 3rd/4th.
> 
> 
>