All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Absolute Adjacent Cell Difference (Posted on 2010-01-02) Difficulty: 4 of 5
The cells of a 5x5 square grid is numbered by the positive integers from 1 to 25 inclusively, with each number occurring in a cell exactly once.

Prove that there must exist two adjacent cells with common edge (not including diagonally) whose numbers have an absolute difference of at least 5.

In general with the numbers 1, 2,...., n2 written on the cells of a nxn square grid in a random order such that each number occurs in a cell exactly once, will there always exist two adjacent cells with common edge (not including diagonally) whose numbers have an absolute difference of at least n, for every value of n ≥ 2?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Almost a solution Comment 1 of 1
The problem Close Neighbors is very similar, but it has the addition of diagonal neighbors.  I tried adapting the relatively simple solution to that problem and got this almost-a-solution.

Find the cells with 1 and n^2.  If they are in the same row or column then the solution to Close Neighbors applies and resolves this case.

Otherwise there are two rows and two columns to examine.  Call the row and column with '1' r1 and c1.  Similarly, call the row and column with 'n^2' r2 and c2.

Traveling along a row there are two ways to go from c1 to c2, when wraparound is included.  Choose the shorter way, the number of steps is at most n/2.  Similarly there is a way to step from r1 to r2 in at most n/2 steps.

The combination of these two paths is a path from 1 to n^2 in at most n steps.  If the largest difference is at most n-1 then the increments could total at most n^2-n, which is less than the n^2-1 needed.  Therefore there must be a difference of at least n along this path.

I call this an almost-a-solution because of the clause when wraparound is included.  The problem as stated does not allow for this variation.

  Posted by Brian Smith on 2016-07-17 15:11:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information