Difference between the numbers in cells for a $n times n$ grid.

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

2

Each cell in an $n times n$ table is filled with an integer from 1 to $n^2$ without repetition. It is known that the number $1$ does not lie along the border. Prove that there exist two adjacent cells (cells with a common vertex or common side) such that the difference between the two numbers is at least $n+3$.

I was able to prove that the difference would be at least $n+1$, see below:

We assume that the difference between two adjacent cells is less than $n+1$.

If we place a counter on the cell numbered $1$, the counter will have to move through at most $n-1$ cells to reach the cell numbered $n$.

The difference between the numbers in adjacent squares is less than $n+1$. The counter moves through at most $n-1$ cells, and the difference between adjacent grids is less than $n+1$, therefore the difference between $n^2$ and $1$ would be appear to be less than $(n-1)(n+1) = n^2-1$. This is a contradiction, and therefore the difference between two adjacent cells has to be at least $n+1$

: I've proved that the difference between adjacent cells has to be at least $n+1$ (is the proof foolproof though), however, I need to prove that the there exist two adjacent cells such that the difference between the numbers in those two cells is $n+3$. Did I miss something in my proof? I do not know how to include the requirement that '$1$' does not lie along the border of the cell.

Thanks in advance

combinatorics

share|cite|improve this question

asked Aug 6 at 13:37

PETER SIAUW

83

add a comment | 

up vote
1
down vote

favorite

2

Each cell in an $n times n$ table is filled with an integer from 1 to $n^2$ without repetition. It is known that the number $1$ does not lie along the border. Prove that there exist two adjacent cells (cells with a common vertex or common side) such that the difference between the two numbers is at least $n+3$.

I was able to prove that the difference would be at least $n+1$, see below:

We assume that the difference between two adjacent cells is less than $n+1$.

If we place a counter on the cell numbered $1$, the counter will have to move through at most $n-1$ cells to reach the cell numbered $n$.

The difference between the numbers in adjacent squares is less than $n+1$. The counter moves through at most $n-1$ cells, and the difference between adjacent grids is less than $n+1$, therefore the difference between $n^2$ and $1$ would be appear to be less than $(n-1)(n+1) = n^2-1$. This is a contradiction, and therefore the difference between two adjacent cells has to be at least $n+1$

: I've proved that the difference between adjacent cells has to be at least $n+1$ (is the proof foolproof though), however, I need to prove that the there exist two adjacent cells such that the difference between the numbers in those two cells is $n+3$. Did I miss something in my proof? I do not know how to include the requirement that '$1$' does not lie along the border of the cell.

Thanks in advance

combinatorics

share|cite|improve this question

asked Aug 6 at 13:37

PETER SIAUW

83

add a comment | 

up vote
1
down vote

favorite

2

up vote
1
down vote

favorite

2

2

Each cell in an $n times n$ table is filled with an integer from 1 to $n^2$ without repetition. It is known that the number $1$ does not lie along the border. Prove that there exist two adjacent cells (cells with a common vertex or common side) such that the difference between the two numbers is at least $n+3$.

I was able to prove that the difference would be at least $n+1$, see below:

We assume that the difference between two adjacent cells is less than $n+1$.

If we place a counter on the cell numbered $1$, the counter will have to move through at most $n-1$ cells to reach the cell numbered $n$.

The difference between the numbers in adjacent squares is less than $n+1$. The counter moves through at most $n-1$ cells, and the difference between adjacent grids is less than $n+1$, therefore the difference between $n^2$ and $1$ would be appear to be less than $(n-1)(n+1) = n^2-1$. This is a contradiction, and therefore the difference between two adjacent cells has to be at least $n+1$

: I've proved that the difference between adjacent cells has to be at least $n+1$ (is the proof foolproof though), however, I need to prove that the there exist two adjacent cells such that the difference between the numbers in those two cells is $n+3$. Did I miss something in my proof? I do not know how to include the requirement that '$1$' does not lie along the border of the cell.

Thanks in advance

combinatorics

share|cite|improve this question

asked Aug 6 at 13:37

PETER SIAUW

83

Each cell in an $n times n$ table is filled with an integer from 1 to $n^2$ without repetition. It is known that the number $1$ does not lie along the border. Prove that there exist two adjacent cells (cells with a common vertex or common side) such that the difference between the two numbers is at least $n+3$.

I was able to prove that the difference would be at least $n+1$, see below:

We assume that the difference between two adjacent cells is less than $n+1$.

If we place a counter on the cell numbered $1$, the counter will have to move through at most $n-1$ cells to reach the cell numbered $n$.

The difference between the numbers in adjacent squares is less than $n+1$. The counter moves through at most $n-1$ cells, and the difference between adjacent grids is less than $n+1$, therefore the difference between $n^2$ and $1$ would be appear to be less than $(n-1)(n+1) = n^2-1$. This is a contradiction, and therefore the difference between two adjacent cells has to be at least $n+1$

: I've proved that the difference between adjacent cells has to be at least $n+1$ (is the proof foolproof though), however, I need to prove that the there exist two adjacent cells such that the difference between the numbers in those two cells is $n+3$. Did I miss something in my proof? I do not know how to include the requirement that '$1$' does not lie along the border of the cell.

Thanks in advance

combinatorics

share|cite|improve this question

asked Aug 6 at 13:37

PETER SIAUW

83

share|cite|improve this question

share|cite|improve this question

asked Aug 6 at 13:37

PETER SIAUW

83

asked Aug 6 at 13:37

PETER SIAUW

83

asked Aug 6 at 13:37

PETER SIAUW

83

83

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote



accepted

This construction is exactly the right idea, but your bounds can be further refined. You know the cell containing $1$ is not on the edge, so only $n-2$ cells will need to be traversed. You can therefore assume the difference between adjacent cells is no more than $n+2$ and arrive at a contradiction.

share|cite|improve this answer

answered Aug 6 at 13:46

Kajelad

1,893619

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873877%2fdifference-between-the-numbers-in-cells-for-a-n-times-n-grid%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote



accepted

This construction is exactly the right idea, but your bounds can be further refined. You know the cell containing $1$ is not on the edge, so only $n-2$ cells will need to be traversed. You can therefore assume the difference between adjacent cells is no more than $n+2$ and arrive at a contradiction.

share|cite|improve this answer

answered Aug 6 at 13:46

Kajelad

1,893619

add a comment | 

up vote
1
down vote



accepted

This construction is exactly the right idea, but your bounds can be further refined. You know the cell containing $1$ is not on the edge, so only $n-2$ cells will need to be traversed. You can therefore assume the difference between adjacent cells is no more than $n+2$ and arrive at a contradiction.

share|cite|improve this answer

answered Aug 6 at 13:46

Kajelad

1,893619

add a comment | 

up vote
1
down vote



accepted

up vote
1
down vote



accepted

This construction is exactly the right idea, but your bounds can be further refined. You know the cell containing $1$ is not on the edge, so only $n-2$ cells will need to be traversed. You can therefore assume the difference between adjacent cells is no more than $n+2$ and arrive at a contradiction.

share|cite|improve this answer

answered Aug 6 at 13:46

Kajelad

1,893619

This construction is exactly the right idea, but your bounds can be further refined. You know the cell containing $1$ is not on the edge, so only $n-2$ cells will need to be traversed. You can therefore assume the difference between adjacent cells is no more than $n+2$ and arrive at a contradiction.

share|cite|improve this answer

answered Aug 6 at 13:46

Kajelad

1,893619

share|cite|improve this answer

share|cite|improve this answer

answered Aug 6 at 13:46

Kajelad

1,893619

answered Aug 6 at 13:46

Kajelad

1,893619

answered Aug 6 at 13:46

Kajelad

1,893619

1,893619

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873877%2fdifference-between-the-numbers-in-cells-for-a-n-times-n-grid%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email