19
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Perhaps the second 25 student puzzle (which presumably has five rows of five) should be a new question after this is solved? $\endgroup$ – Weather Vane May 7 at 18:27
  • 2
    $\begingroup$ @WeatherVane: Following your suggestion, I have now posted the case for 25 students at: math.stackexchange.com/questions/3218384/… $\endgroup$ – Bernardo Recamán Santos May 8 at 12:41
  • 1
    $\begingroup$ I made a solution validator some may find useful. $\endgroup$ – TemporalWolf May 8 at 23:30
  • 2
    $\begingroup$ I found an optimal solution to the 25 student problem (5 weeks), or rather, my computer program did. The solution can be found over on Mathematics SE. $\endgroup$ – Jaap Scherphuis May 9 at 15:59
10
$\begingroup$

Continuing from Arnaud Mortier's observations,

I noticed that each student in the always-on-the-edge group will sit by one student from each rotating group while the rotating students are in the corners, and two more students from each rotating group while they are in the center. So each student in the always-on-the-edge group needs to sit by exactly one student in each rotating group while it is on the edge. Since each edge seat is adjacent to two other edge seats, this means that each student in the always-on-the-edge group will sit by one other student in the always-on-the-edge group each week.

Using that knowledge and a bit of trial and error,

I was able to find a solution for 3 weeks.

 Week 1            Week 2            Week 3

  1  2  3  4       9 11 10 12        10  2 14  6
  5  6  7  8       2  4  1  3        16  8 12  4
  9 10 11 12      15 13 16 14         1  9  5 13
 13 14 15 16       8  6  7  5         7 15  3 11
Here's a table which show which weeks the students sit by each other.
Student   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
       -----------------------------------------------------------------
  1   |   -   1   2   2   1   1   3   3   3   2   2   2   2   2   3  2,3
  2   |   1   -   1   2   1   1   1   3   2   3   2   3   2   3   2   3
  3   |   2   1   -   1   3   1   1   1   3   2   3   2   3   2   3   2
  4   |   2   2   1   -   3   3   1   1   2   2   2   3  2,3  3   2   2
  5   |   1   1   3   3   -   1   2   3  1,3  1   3   3   3   2   3   2
  6   |   1   1   1   3   1   -  1,2  2   1   1   1   3   2   3   2   2
  7   |   3   1   1   1   2  1,2  -   1   3   1   1   1   2   2   3   2
  8   |   3   3   1   1   3   2   1   -   3   3   1  1,3  2   3   2   3
  9   |   3   2   3   2  1,3  1   3   3   -   1   2   3   1   1   3   3
 10   |   2   3   2   2   1   1   1   3   1   -  1,2  2   1   1   1   3
 11   |   2   2   3   2   3   1   1   1   2  1,2  -   1   3   1   1   1
 12   |   2   3   2   3   3   3   1  1,3  3   2   1   -   3   3   1   1
 13   |   2   2   3  2,3  3   2   2   2   1   1   3   3   -   1   2   2
 14   |   2   3   2   3   2   3   2   3   1   1   1   3   1   -   1   1
 15   |   3   2   3   2   3   2   3   2   3   1   1   1   2   1   -   1
 16   |  2,3  3   2   2   2   2   2   3   3   3   1   1   2   1   1   -

$\endgroup$
  • 2
    $\begingroup$ Well done! I was waiting for this answer to be re-posted after it was deleted: beat me to the solution, but I too was working on the idea that 4 students rotate around two pairs of centre-edge seats, and each meets 5+5+5 others, and the other 12 students meet 3+5+8 others, having been at the corner-edge-middle positions. $\endgroup$ – Weather Vane May 8 at 19:17
11
$\begingroup$

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

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.

$\endgroup$
6
$\begingroup$

Here's 16 students in

4

weeks.

0123 A8B9 CAD0 135E
4567 2031 B179 A2BC
89AB ECFD 58E4 94D0
CDEF 6475 F263 7F68

$\endgroup$
  • $\begingroup$ I can confirm this works! Good job. How did you find it? $\endgroup$ – Dr Xorile May 8 at 1:29
  • $\begingroup$ @DrXorile Nothing special, just filled out the grids using some symmetries, trying to maximize new pairs. On my first attempt, the last grid fit together perfectly to finish off the pairs. $\endgroup$ – noedne May 8 at 1:56
  • 2
    $\begingroup$ It may be possible with 3. Tricky to find though. $\endgroup$ – Dr Xorile May 8 at 1:58
  • $\begingroup$ Are you Helium_1s2 by any chance? $\endgroup$ – greenturtle3141 May 27 at 22:20
  • $\begingroup$ @greenturtle3141 No. $\endgroup$ – noedne May 27 at 22:28
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice! I found one for nine weeks. $\endgroup$ – Freddy Barrera May 8 at 19:20
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Won't students who are originally in opposite corners stay in opposite corners? $\endgroup$ – hexomino May 7 at 15:14
  • $\begingroup$ hmm. Guess, I'd need to add a few extra steps for the corner cases. Not sure if this would be the optimum solution. $\endgroup$ – Mazurka Fahr May 7 at 15:17
  • 1
    $\begingroup$ In the new version, students in the original first column never sit next to students in the original third column. $\endgroup$ – hexomino May 7 at 15:31
  • $\begingroup$ :(. Can't avoid the extra steps. $\endgroup$ – Mazurka Fahr May 7 at 15:32
-2
$\begingroup$

The first question i believe it's

256


and the second one it's

625

I think the solution of this one is to multiply the two numbers given. An other example is:find all the combinations of these words PANEL(wich i'll use the same equation).

$\endgroup$
  • $\begingroup$ it's a math logic that my teacher told me, we have 16 students (in the first question) and 16 chairs, 16x16 = 256. Like, we need to repeat the same process 16 times for all of the 16 students $\endgroup$ – riki481 May 7 at 13:03
  • $\begingroup$ This seems more like the total number of combinations, rather than how quickly you can get each student to have sat next to every other 8 directions $\endgroup$ – Smock May 7 at 13:56
  • $\begingroup$ Guess there is another step i need to do, but i don't remember $\endgroup$ – riki481 May 7 at 14:00
  • 1
    $\begingroup$ After actually looking into the question, these numbers are way too large. $\endgroup$ – Arnaud Mortier May 7 at 14:28

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.