Home » Subject » Combinatorics » Matrices
Importance: Low ✭
Author(s): Vadim Lioubimov
Subject: Combinatorics
» Matrices
Keywords:
Recomm. for undergrads: yes
Posted by: Vadim Lioubimov
on: May 20th, 2013
Solved by: Daniel Soltész
Conjecture   Any $ n\times n $ matrix with different integer entries has two neighboring entries $ a,b $ with $ |a-b|\ge n $.

Only neighbors in the same row or column are considered. Given a matrix $ A $, let $ v(A) $ be the maximum difference between two neighboring entries of $ A $. Given integers $ n,m\ge2 $, let $ \xi(n,m) $ be the smallest possible value of $ v(A) $ among all $ n\times m $ matrices $ A $ with different integer entries. Thus the conjecture asserts that $ \xi(n,n)\ge n $.

Consider the $ n\times m $ matrix $ B:=\{b_{i,j}\} $ defined by $ b_{i,j}:=i + (j-1)n $. The entries of $ B $ is $ [nm] $ and $ v(B)=n $. Thus $ \xi(n,m)\le\min\,\{n,m\} $. Consequently the conjecture is equivalent to the assertion $ \xi(n,m)=\min\,\{n,m\} $.

It can be easily seen that for any $ n\times m $ matrix $ A $ with different integer entries, there exists a matrix $ A^* $ with the entries $ [nm] $ such that $ v(A^*)\le v(A) $. Therefore, in the definition of $ \xi(n,m) $, we may assume that the entries of each matrix is $ [nm] $. Consequently the conjecture reduces to the case when the entries of the matrix is $ [n^2] $.

I have proved the conjecture for $ n\le5 $. The proof is separate for each of the 4 cases $ n=2,3,4,5 $ and pretty elementary. However, I am not so sure at the moment whether the conjecture is true for all $ n\ge6 $. If it turns out to be generally false, it would be an interesting problem to evaluate $ \xi(n,m) $. I wonder if there are any related results.

Bibliography



* indicates original appearance(s) of problem.
4 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options