7
$\begingroup$

The matrix given as below where you are supposed to put number from 1 to 25 in it. But the condition is that, the difference between the neigbours (horizontal and vertical) will be at least $x$.

$\begin{bmatrix} a_{11} &a_{12} &a_{13} &a_{14} &a_{15} \\ a_{21}& a_{22} &a_{23} &a_{24} &a_{25} \\ a_{31} &a_{32} &a_{33} &a_{34} &a_{35}\\ a_{41} &a_{42} &a_{43} &a_{44} &a_{45} \\ a_{51} &a_{52} &a_{53} &a_{54} &a_{55} \\ \end{bmatrix}$

  1. What is the maximum value of $x$?
  2. Is it possible to generalize the maximum value of $x$ in terms of the dimension of the matrix ($n\times n$)?

Note: The first part is answered correctly, still looking for the general equation for $n$ in terms of $x$.

$\endgroup$
9
$\begingroup$

The maximum of value of $x$ is

10.

Grid:

$\begin{array}{|r|r|r|r|r|}\hline 1& 11& 21& 6& 16\\\hline 12& 22& 7& 17& 2\\\hline 23& 8& 18& 3& 13\\\hline 9& 19& 4& 14& 24\\\hline 20& 5& 15& 25& 10\\\hline \end{array}$

Numbers increase by 10 as you go right, and by 11 as you go down, wrapping around when this would make them exceed 25.

Proof of optimality

Suppose we have a labeling where adjacent numbers differ by at least eleven. Divide into cases based on where 13 is in the grid.

Note: I will repeatedly use the fact that diagonally adjacent numbers cannot differ by 22. This is because if $d=a+22$ in the below picture, then both $b$ and $c$ would be forced to be $a+11$.

ab
cd

Case 1: 13 is in the interior:

13 has only four possible neighbors: 1, 2, 24 and 25. You can't put 2 diagonally next to 24, so 2 is across from 24, leading to some rotation/reflection of the left picture. You are now forced to put 12 between 1 and 24, and 14 between 2 and 25.

Now, 12 has only four possible neighbors: 1, 23, 24 and 25. But 25 was already placed away from 12. With only three available neighbors, 12 must be on the border of the grid. Same goes for 14, leading to one of the two pictures on the right. In the left case, a 3 is forced above 14, leaving no options for *. The right grid has a similar contradiction.

                    *  3 |      +––––––––––
   25              25 14 |      |    25 14 
24 13  2  -->   24 13  2 |  or  | 24 13  2
    1           12  1    |      | 12  1    
              –––––––––––+      | 23  * 

Case 2: 13 is in on an edge, but not on a corner:

Say 13 is on the left edge. After possibly replacing each number $n$ in the grid with $25-n$, the number to the right of 13 is either 24 or 25.

2a. Assuming it is 24, then the other two neighbors must be 1 and 25 (neither can be 2). A 12 is forced next to the 1 and 24. Since 12 must be next to 1, 23, 24 or 25, and 25 is in use, 12 must be on the border as shown. But now there is nowhere to legally place 11 in the grid (since it must be surrounded by the numbers 22 through 25.)

  ___________
 |  1 12 23
 | 13 24
 | 25 

2b. Otherwise, there is a 25 to the right of 3. There are now to further subcases: either (i) one of 13's vertical neighbors is a 2, or (ii) it isn't.

2b(i). The first possibility is illustrated below. A 14 is forced between 2 and 25. There must be a 1 to the right of 14: if it was 3 to the right of 14, nothing could go above the 3. This forces a 12 above the 1, then a 23 or 24 to the right of 12, leaving a contradiction at *.

| 13 25 12 23/24
|  2 14  1  *

2b(ii) Otherwise, there must be a 1 vertically next to the 3, and a 24 on the other side. Following similar logic to case 2a leads to the picture below, which has no place to legally put an 11.

| 24
| 13 25
|  1 12 23
+–––––––––––

Case 3: 13 is in a corner.

Everything is similar to one of the three pictures below (omitting the case where the two neighbors are 2 and 24).

 ______       ______      _______
|13 25       |13 25      |13  1
| 1          | 2         | 2

Anyone following along diligently should be comfortable making deductions in this grid by now, so I'll just show all the forced decisions in the first two grids (the first one also has similar variation where 14 is replaced with 12).

 __________         ________________
| 13 25  *         | 13 25 12 23/24
|  1 14 2/3        |  2 14  1  *

For the last case, consider the location of the 14. If 14 is placed on a square marked #, then its other two sides must contain a 3 and 25, which differ by 22. Same goes if 14 is in one of the other corners. If 14 is placed anywhere else, then it will have 3 neighbors, which can't be covered by 3 and 25 alone.

 _________
|13 1 #
| 2 #
| #
$\endgroup$
  • $\begingroup$ In case 1 you say " You are now forced to put 12 between 1 and 24" but I'm not quite sure I can see why that is... $\endgroup$ – Chris Jul 26 '17 at 10:55
  • $\begingroup$ @Chris only two numbers are at least eleven away from both 1 and 24: 12 and 13, but 13 is already taken. $\endgroup$ – ffao Jul 27 '17 at 8:39
  • $\begingroup$ Ah, that makes sense. Since you were talking about where to put 12 I assumed we were looking at properties of 12 which of course could have gone in other places. May be worth considering whether it might be more clear to say "the space between 1 and 24 can only be filled by 12" making it clearer that its the space that is restricted, not the number 12. $\endgroup$ – Chris Jul 27 '17 at 8:45
1
$\begingroup$

Since no one could find the answer for the second part, I am going to share the answer:

First of all, while putting the numbers into the matrix;

  • You need to start from one end to the other end, such as $1$ to $n^2$,
  • While doing this, the distance between the numbers should be as close as possible.

For example, $5\times5$ case:

enter image description here

This is just an example, you could have put these differently but to get the maximum distance, this methodology seems optimal where you do not need to worry about the close numbers might get close to each other.

  • Lastly, with the same way, you just need to put the rest with the same order:

$5\times5$ case:

enter image description here

Since you put the numbers in the same order as before, the maximum difference happens between numbers which is $10$ as @MikeEarnest solved, but this time this methodology is applicable any size of matrix!

To form the formula, we can use the example above. as you will notice the maximum difference between numbers in $5\times5$ case is $(13+1)-4$ where $13$ is the last value you can put without any neighbor and $4$ is the first value on the second row where it has to be neigbour the next value after $13$ which is $14$. How do we get $13$ and $4$, if we can figure that out, the rest is just forming the formula!

  • $13$ case: It is simply $\left \lceil25\div2 \right \rceil$ which is the maximum value you can put into a $5\times5$ matrix without any neigbor.
  • $4$ case: It is simply $\left \lceil5\div2 \right \rceil+1$ which is the maximum value you can put on the row with the size of $5$ plus 1, first value on the second row.

So the formula becomes:

Maximum Difference= $\left \lceil n^2\div2 \right \rceil - \left \lceil n\div2 \right \rceil$

which is applicable for any size of square matrix! If you check the values of this series on the link over the formula via Wolfram Alpha. the well known series forms, Triangular numbers:

Maximum Difference = $\frac{n(n-1)}{2}$

$\endgroup$
  • $\begingroup$ Oh man, that's a super cool and simple construction! Do you know if it is possible to do better? $\endgroup$ – Mike Earnest Aug 5 '17 at 22:27

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.