Importance: Low ✭
 Subject: Combinatorics » Matrices
 Keywords:
 Posted by: Vadim Lioubimov on: May 20th, 2013
 Solved by: Daniel Soltész
Conjecture   Any matrix with different integer entries has two neighboring entries with .

Only neighbors in the same row or column are considered. Given a matrix , let be the maximum difference between two neighboring entries of . Given integers , let be the smallest possible value of among all matrices with different integer entries. Thus the conjecture asserts that .

Consider the matrix defined by . The entries of is and . Thus . Consequently the conjecture is equivalent to the assertion .

It can be easily seen that for any matrix with different integer entries, there exists a matrix with the entries such that . Therefore, in the definition of , we may assume that the entries of each matrix is . Consequently the conjecture reduces to the case when the entries of the matrix is .

I have proved the conjecture for . The proof is separate for each of the 4 cases and pretty elementary. However, I am not so sure at the moment whether the conjecture is true for all . If it turns out to be generally false, it would be an interesting problem to evaluate . I wonder if there are any related results.

## Bibliography

* indicates original appearance(s) of problem.