[Prime]

While organizing my bookshelf, I found an old issue of "Kvant" – a popular Russian science magazine. It has a regular section with entertaining math and physics problems for school students. I post here the part "a" of one problem that I liked:

Each square of an infinite square-ruled sheet has a natural number written in it.

a) Every number appears exactly once.

1) Show an example of such arrangement.

2) Prove that for any number m, there is always at least one pair of neighboring

squares (sharing a side) such that the difference of their numbers is not less than m.

The part "b" of the problem is marked with an "*" meaning it is of higher difficulty. So I am not going to show it here just yet.

Unfortunately, I don't have the issue with the answer to this problem.

[HoustonHokie]

Here's my thoughts:

I think the best way to arrange is a series of ever-expanding natural squares. Start at the bottom left with 1, which is the first natural number. Then form a ring around the 1 with 2, 3, 4. And so on, like so:

10_11_12_13

_5__6__7_14

_2__3__8_15

_1__4__9_16

This should insure a unique number in each square.

The neighbor question seems intuitive enough, given the arrangement I've proposed. Simply looking at the bottom row, the difference between neighbors is always (n+1)² - n², where n is the column number. Now for any value of m, it is always possible to find an n so that (n+1)² - n² >= m.

What was part b?

[Prime]

Here's my thoughts:

I think the best way to arrange is a series of ever-expanding natural squares. Start at the bottom left with 1, which is the first natural number. Then form a ring around the 1 with 2, 3, 4. And so on, like so:

10_11_12_13

_5__6__7_14

_2__3__8_15

_1__4__9_16

This should insure a unique number in each square.

The neighbor question seems intuitive enough, given the arrangement I've proposed. Simply looking at the bottom row, the difference between neighbors is always (n+1)² - n², where n is the column number. Now for any value of m, it is always possible to find an n so that (n+1)² - n² >= m.

What was part b?

Very good thoughts, indeed! And amazing reaction time.

Now a bit of CLARIFICATION:

1. Assume, you cannot see any edges of the infinite sheet. (It looks like you started filling numbers in the corner.)

2. Proof for the second part should be general -- not just for the specific arrangement that you found.

[unreality]

(1) was done by HH, but for (2)

m at the middle, with abcd going around clockwise:

  b

a m c

  d

it's basically saying, prove that |a-c| >= m OR |b-d| >= m which isn't always true. Take this arrangement

  2

1 5 3

  4

even if by neighboring sides it means a&b, b&c, c&d, or d&a are acceptable, that 1-2-3-4-5 example counterproofs all of that, unless I'm misunderstanding the question.

Edited August 25, 2008 by unreality

[Prime]

(1) was done by HH, but for (2)

m at the middle, with abcd going around clockwise:

  b

a m c

  d

it's basically saying, prove that |a-c| >= m OR |b-d| >= m which isn't always true. Take this arrangement

  2

1 5 3

  4

even if by neighboring sides it means a&b, b&c, c&d, or d&a are acceptable, that 1-2-3-4-5 example counterproofs all of that, unless I'm misunderstanding the question.

I think, you misunderstood the question (2) . I admit, it is kind of ambiguous.

I believe, what was meant there that you cannot have the "largest" finite difference between two neighboring squares. It means, pick any number as big as you want, and you can always find two adjacent squares, difference between which is equal, or bigger than that number.

[unreality]

well duh, lol ;D

[HoustonHokie]

Very good thoughts, indeed! And amazing reaction time.

Now a bit of CLARIFICATION:

1. Assume, you cannot see any edges of the infinite sheet. (It looks like you started filling numbers in the corner.)

2. Proof for the second part should be general -- not just for the specific arrangement that you found.

picky, picky, picky...

presumably, you're going to start somewhere...

proceeding from whichever square you start at, use a similar tactic as I employed in my previous post, except complete the square around the original number, like so:

10_11_12_13_14

25__2__3__4_15

24__9__1__5_16

23__8__7__6_17

22_21_20_19_18

The nice thing about infinity is that you can be congratulated on starting with the square exactly in the center of the board, so you'll never run out of room for new numbers.

okay, a more robust proof of the neighbor question. My arrangement above has a similar proof as the first time around, but since you want a generic board...

In each row, there are an infinite number of unique numbers. It would be possible to fill the board to keep the difference between neighbors to some maximum m over m consequtive columns or rows by filling them sequentially. For example, if m = 3, this is a possibility:

__1__2__3

__4__5__6

__7__8__9

_10_11_12

_13_14_15

But as soon as you introduce the m+1 column, it doesn't work anymore, because either the m+1 column fails everywhere, or all the rows fail. In fact, the difference between the m and m+1 columns is infinite if you continue the pattern, and the difference between rows is >m if you upset the pattern. So I guess my best proof is by proving that there is no value of m for which is works.

Well, I see that others have chimed in while I was typing. I'll submit anyway, but I think it's mostly covered.

[Prime]

picky, picky, picky...

presumably, you're going to start somewhere...

proceeding from whichever square you start at, use a similar tactic as I employed in my previous post, except complete the square around the original number, like so:

10_11_12_13_14

25__2__3__4_15

24__9__1__5_16

23__8__7__6_17

22_21_20_19_18

The nice thing about infinity is that you can be congratulated on starting with the square exactly in the center of the board, so you'll never run out of room for new numbers.

okay, a more robust proof of the neighbor question. My arrangement above has a similar proof as the first time around, but since you want a generic board...

In each row, there are an infinite number of unique numbers. It would be possible to fill the board to keep the difference between neighbors to some maximum m over m consequtive columns or rows by filling them sequentially. For example, if m = 3, this is a possibility:

__1__2__3

__4__5__6

__7__8__9

_10_11_12

_13_14_15

But as soon as you introduce the m+1 column, it doesn't work anymore, because either the m+1 column fails everywhere, or all the rows fail. In fact, the difference between the m and m+1 columns is infinite if you continue the pattern, and the difference between rows is >m if you upset the pattern. So I guess my best proof is by proving that there is no value of m for which is works.

Well, I see that others have chimed in while I was typing. I'll submit anyway, but I think it's mostly covered.

I accept your example of filling the infinite sheet. It will fill the entire sheet, all natural numbers will be used, and each number will occur just once.

I am not so sure about your proof though... Seems like you picked a specific method for filling the sheet again, and proved that there can't be "maximum difference" for that particular arrangement.

[unreality]

it's an axiom. 1+1 = 2. You can't prove it- it just is- it's an axiom. There will always be smaller numbers and always be bigger numbers. If you have a number 'n', you can always find 'a' and 'b' so that a-b >= n. Even if you can't reuse numbers (ie, a grid like you are suggesting), you have an infinite more to select from

[HoustonHokie]

I am not so sure about your proof though... Seems like you picked a specific method for filling the sheet again, and proved that there can't be "maximum difference" for that particular arrangement.

What I was attempting for the proof was to disprove the opposite - if you can disprove the statement that there is a way to fill out the grid such that there is always a difference of less than m between neighboring squares, then it is the same as proving that there is always a nieghboring pair with a difference greater than or equal to m. I picked the arrangment that keeps that difference less than m for the largest portion of the grid (m x infinity), and proved that because there is always another column in an infinite grid, it is impossible to fill out the grid infinitely and keep the difference less than m; therefore, there is always a pair of neighboring squares with a difference greater than or equal to m.

[Prime]

if you can disprove the statement that there is a way to fill out the grid such that there is always a difference of less than m between neighboring squares, then it is the same as proving that there is always a nieghboring pair with a difference greater than or equal to m.

Suppose, it is so. However, then you say:

I picked the arrangment that keeps that difference less than m for the largest portion of the grid (m x infinity), and proved ...

So you proved it for that specific arrangement. I don't see how that particular arrangement can be viewed as all possible arrangements.

Your method of proof should go something like:

"Suppose we had such an arrangement (without specifying what it was). Then this and that does not agree with that proposition which we hold true..."

I am not sure that would be an easiest method of proof in this problem, but it would be interesting to see.

[k-man]

Here is my attempt at this...

We need to fill the 2-dimensional grid with 1-dimensional sequence of numbers. It's kind of obvious that to fill the whole grid the number sequence can't run in one direction infinitely. Whatever method of filling the grid you choose it will have a finite number of numbers going in one direction before turning into another direction or jumping back to some other point on the grid. We will come back to this spot again some time later, but not before filling some part of the grid in other directions. Those end points will have neighbors that are further and further away in the sequence as you fill the grid. The difference between such neighbors will grow as O(n²) as the territory we need to fill before we can come back grows like n². Therefore there is no limit to the difference between neighboring squares.

[HoustonHokie]

So you proved it for that specific arrangement. I don't see how that particular arrangement can be viewed as all possible arrangements.

Your method of proof should go something like:

"Suppose we had such an arrangement (without specifying what it was). Then this and that does not agree with that proposition which we hold true..."

I am not sure that would be an easiest method of proof in this problem, but it would be interesting to see.

But it's not just that specific arrangement, because that arrangement is the most successful one possible if you are attempting to limit the difference between neighbors to m. An m x infinity arrangement is the largest possible bounded arrangement where it is always true that the difference between neighboring numbers is less than m (actually its unbounded in one direction and bounded in the other, but you get my point). Every other bounded arrangement where that is the true is smaller than the one I've postulated and is thus less successful at proving the original point than this specific case. Therefore, this specific arrangement "speaks" for all arrangements. I think my proof shows that the difference between neighboring cells has to be greater than m at some point if the grid is unbounded in both directions.

I guess my difficulty with trying the proof you suggest is that there could be so many different reasons for failure, which basically boil down to an inefficient arrangement and not the root cause which is that the board is unbounded in both directions, which can only be demonstrated with this specific arrangement. There may be a way to do what you suggest - there must be some other mathematical maxim which is violated by attempting such a construction - but this proof is pretty robust, I believe.

Hopefully that makes sense and will satisfy - cuz you're not going to get anything else from me!

[Guest]

While organizing my bookshelf, I found an old issue of "Kvant" – a popular Russian science magazine. It has a regular section with entertaining math and physics problems for school students. I post here the part "a" of one problem that I liked:

Each square of an infinite square-ruled sheet has a natural number written in it.

a) Every number appears exactly once.

1) Show an example of such arrangement.

2) Prove that for any number m, there is always at least one pair of neighboring

squares (sharing a side) such that the difference of their numbers is not less than m.

The part "b" of the problem is marked with an "*" meaning it is of higher difficulty. So I am not going to show it here just yet.

Unfortunately, I don't have the issue with the answer to this problem.

I'm assuming that (refer to the numeric keypad on your keyboard) for any number m (5) there is always one pair of neighbouring squares such that the difference is not less than m (5). This could be any of:

8-6, 8-4, 8-2

6-8, 6-4, 6-2

4-8, 4-6, 4-2

2-8, 2-6, 2-4

If we arrange in a spiral pattern, then 6-4=2 2>1 (trivial case). If we follow the "out and back", which is finite to 'n' degree, then there will always be a number on either side of the linearly increasing row (or column) which when subtracted will be greater than the number in the middle. I'll see if I can put together some generic math proof. Actually, both these cases are somewhat similar. They will both have rows and columns of increasing numbers side by side, which when you take the difference of a number on either side of the row (or column) then a-b>=m will hold.

Edited August 26, 2008 by Jarod997

[Prime]

I'm assuming that (refer to the numeric keypad on your keyboard) for any number m (5) there is always one pair of neighbouring squares such that the difference is not less than m (5). This could be any of:

8-6, 8-4, 8-2

6-8, 6-4, 6-2

4-8, 4-6, 4-2

2-8, 2-6, 2-4

If we arrange in a spiral pattern, then 6-4=2 2>1 (trivial case). If we follow the "out and back", which is finite to 'n' degree, then there will always be a number on either side of the linearly increasing row (or column) which when subtracted will be greater than the number in the middle. I'll see if I can put together some generic math proof. Actually, both these cases are somewhat similar. They will both have rows and columns of increasing numbers side by side, which when you take the difference of a number on either side of the row (or column) then a-b>=m will hold.

As I already stipulated (see post #5), "m" does not refer to any particular square. "m" is just randomly selected natural number.

Sorry about misunderstanding. The statement of the problem in Russian was somewhat ambiguous, and I translated it as is.

[Prime]

Here is my attempt at this...

We need to fill the 2-dimensional grid with 1-dimensional sequence of numbers. It's kind of obvious that to fill the whole grid the number sequence can't run in one direction infinitely. Whatever method of filling the grid you choose it will have a finite number of numbers going in one direction before turning into another direction or jumping back to some other point on the grid. We will come back to this spot again some time later, but not before filling some part of the grid in other directions. Those end points will have neighbors that are further and further away in the sequence as you fill the grid. The difference between such neighbors will grow as O(n²) as the territory we need to fill before we can come back grows like n². Therefore there is no limit to the difference between neighboring squares.

I can see your reasoning with respect to the overall area, but I did not understand how the conclusion about neighboring squares followed. Note, changing directions as you move along the grid, does not have to break the "neighbor" relationship. Neighbors could be up, down, left, right.

Although, I think your reasoning is in the very neighborhood of the solution/proof.

[k-man]

I can see your reasoning with respect to the overall area, but I did not understand how the conclusion about neighboring squares followed. Note, changing directions as you move along the grid, does not have to break the "neighbor" relationship. Neighbors could be up, down, left, right.

Although, I think your reasoning is in the very neighborhood of the solution/proof.

At which point does the reasoning break down for you? Is it the last sentence that you think requires more explanation?

[Prime]

But it's not just that specific arrangement, because that arrangement is the most successful one possible if you are attempting to limit the difference between neighbors to m. An m x infinity arrangement is the largest possible bounded arrangement where it is always true that the difference between neighboring numbers is less than m (actually its unbounded in one direction and bounded in the other, but you get my point). Every other bounded arrangement where that is the true is smaller than the one I've postulated and is thus less successful at proving the original point than this specific case. Therefore, this specific arrangement "speaks" for all arrangements. I think my proof shows that the difference between neighboring cells has to be greater than m at some point if the grid is unbounded in both directions.

I guess my difficulty with trying the proof you suggest is that there could be so many different reasons for failure, which basically boil down to an inefficient arrangement and not the root cause which is that the board is unbounded in both directions, which can only be demonstrated with this specific arrangement. There may be a way to do what you suggest - there must be some other mathematical maxim which is violated by attempting such a construction - but this proof is pretty robust, I believe.

Hopefully that makes sense and will satisfy - cuz you're not going to get anything else from me!

I see that you see why statement (2) in the OP is true, and yet... I'm sorry for being picky, but I don't see where you have shown formally, that the arrangement you use for the proof is the minimal/maximal and no better can be found.

Maybe, you have the proof, but I'm still going to check this topic for other formulations thereof. Until we get more efficient formulation, we shall consider your post#7 the proof as close as we can get.

[Prime]

At which point does the reasoning break down for you? Is it the last sentence that you think requires more explanation?

1. I'm not sure what the notation O(n²) means.

2. The proof implies some method of filling out the infinite sheet, stating that there are no alternatives. What if the infinite sheet was already filled and we don't know how and in what sequence it was done?

[HoustonHokie]

I see that you see why statement (2) in the OP is true, and yet... I'm sorry for being picky, but I don't see where you have shown formally, that the arrangement you use for the proof is the minimal/maximal and no better can be found.

Maybe, you have the proof, but I'm still going to check this topic for other formulations thereof. Until we get more efficient formulation, we shall consider your post#7 the proof as close as we can get.

Good point about how I haven't shown formally that it's the minimal/maximal arrangement. I guess the best I could offer on that is the following:

Consider a group of n cells in a single row. If these cells are numbered sequentially (i.e., 1, 2, 3, 4,...,n) and n<m, it would be possible to number those cells and the cells immediately above such that the maximum difference between neighboring cells is m. If, however, n>m, it is impossible to do so because all the numbers between 2 and m+1 have already been used. So the most cells you can have in a particular row is m. If you limit yourself to m cells, you can continuously fill the cells above that row in sequence such that the numbers in row x go in order from m*(x-1)+1 to m*x, and ultimately you get the arrangement I've been constructing proofs for. If you don't count sequentially (say you go 2, 4, 6, 8) you'll only be able to have half as many numbers in the row before you need to start the next row, so it will be smaller. Arrangements such as I constructed in my first couple posts fail rather quickly - I think I can say that without proof. You could have an arrangment where you simply put random numbers from 1 to infinity in each cell, and I think it's obvious that eventually that method will fail, no matter how large m is. The maximum arrangement, therefore, is an m x infinity arrangement. Having shown that, I think my previous proof shows that even the maximum arrangement eventually fails.

Well, I guess you did get a little more from me!

[Guest]

1. I'm not sure what the notation O(n²) means.

2. The proof implies some method of filling out the infinite sheet, stating that there are no alternatives. What if the infinite sheet was already filled and we don't know how and in what sequence it was done?

O() notation is used to indicate generalized speed or time. To say something finishes in O(n) time means the time increases directly linearly in relation to the variable you're studying. O(n²) says your time increases as the square of the variable you're studying. In algorithm study, usually the aim is to be as efficient as possible eg O(n) is worse than O(nlog(n)) is worse than O(log(n)) is worse than O(log(log(n))). Some say O notation stands for "on the Order of".

[Guest]

It was dubbed "Big O" notation by lonely male computer scientists who probably thought they were clever.

For a simple example: you have an array of n numbers, ordered sequentially from a[0] (lowest) to a[n-1] (higest). If you want to find some particular value x in that array, one way would be to start with a[0], and see if a[0]=x. If it's not, go on to a[1], etc, until you hit a[n-1]. This has O(n), because the worst case is n iterations to find x.

Another, better, solution is to start with a[n/2], and see if that's greater or less than x. If it's lower, you then can go to a[n/4], and see if that value is greater or less than x. If a[n/2]<x, then you go to a[3n/4], etc (always cutting the interval in half). This method has O(log₂(n)), which means that in the worst case you would need log₂(n) iterations. This indicates it is generally better than the above method.

It's important to note that the binary search (the second method) will not always be faster than the first method. If a[0]=x, then the first method will only take one iteration.

[Guest]

Starting at any point on the sheet and spiraling outward:

20
21 [color="#00FF00"]10[/color] 19
22 [color="#00FF00"]11[/color] [color="#FF0000"]4[/color] [color="#00FF00"]9[/color] 18
23 [color="#00FF00"]12[/color] [color="#FF0000"]5[/color] [color="#0000FF"]1[/color] [color="#FF0000"]3[/color] [color="#00FF00"]8[/color] 17
24 [color="#00FF00"]13[/color] [color="#FF0000"]2[/color] [color="#00FF00"]7[/color] 16
25 [color="#00FF00"]6[/color] 15
14

While this may seem like an unnecessarily contrived formation, it's for a good reason, I assure you.

I'll attempt a proof by contradiction here. I will suppose the opposite of the statement in question and show that it cannot be true. So let us suppose that the following is true: there exists a number m, for which there exist no pairs of adjacent squares such that their difference is not less than m. In other words, all pairs of adjacent squares have differences less than m.

For referencing purposes, let us name each cell c[x] where x is the number assigned by my spiral formation in part 1. So we start with c[1] and spiral outward with c[2], c[3] and so on. Then for any c[1], "|c[1] - c[2]| <= (m-1)" must be true. That is, the difference between c[1] and c[2] must be less than or equal to m-1. I'll refer to this as being "within (m-1) of c[1]". The same is true between c[1] and c[3], c[1] and c[4], and c[1] and c[5]. Let us call this group of {c[2], c[3], c[4], c[5]} D[1] (for Distance 1). So c[2] to c[5] are in D[1], c[6] to c[13] are in D[2] and so on, with each D group forming a square around the previous. Then for any group D[n], it is true that "|c[1] - c[y]| <= (m-1)n" where c[y] represents each cell in D[n]. In other words, all cells in group D[n] are within (m-1)n of c[1].

Now let's look at numbers of numbers. Inside the set of natural numbers that are within (m-1)n of c[1], excluding c[1], there are at most 2(m-1)n numbers. This is trivial to show. There are at most 2 numbers within 1 of 2 (1 and 3). There are at most 4 numbers within 2 of 2 (1, 3, and 4, only 3 numbers in this case). And so on. Looking at our D groups, we see that since each number in a group D[n] must be within (m-1) of c[1], there are at most 2(m-1)n numbers to choose from when filling in D[n].

Now let's look at how many numbers we use to complete each D group. D[1] has 4 numbers in it, D[2] has 8 numbers in it, D[3] has 12 numbers in it and so on. Each group contains 4 more numbers than the previous group. But to get to D[2], we must first fill in D[1], so the number of numbers used to complete D[2] is actually 4+8=12. And for completing D[3], we use 4+8+12=24 numbers. The number of numbers used to complete any group D[n] turns out to be 2n^2+2n, which I'll write as 2(n+1)n for better comparison in the next part. This is important because the set of numbers that are within (m-1)n of c[1] includes the sets of numbers that are within (m-1)(n-1) of c[1], within (m-1)(n-2) and so on until we're within (m-1) of c[1]. Basically, all numbers within all D groups up to D[n] must be within (m-1)n of c[1].

So each group D[n] contains at most 2(m-1)n numbers. Each group D[n] requires the use of 2(n+1)n numbers. Now this is where it breaks down. For any number m, there exists a number n+1 that is greater. Therefore, for any number 2(m-1)n, there exists a number 2(n+1)n that is greater. This means that for any number m, we will eventually need more numbers to complete a group D[n] than there exist in the set of numbers within (m-1) of c[1]. So no matter how the infinite grid is filled out or what number m we choose, we must eventually see a number in a group D[n] that's not within (m-1)n of c[1], meaning that somewhere along the line, there must be two adjacent squares that have a difference that is not less than m.

Someone check my math and reasoning please. I'm sorry if the explanations are a little convoluted. I just woke up.

Edited August 27, 2008 by flowstoneknight

[k-man]

1. I'm not sure what the notation O(n²) means.

2. The proof implies some method of filling out the infinite sheet, stating that there are no alternatives. What if the infinite sheet was already filled and we don't know how and in what sequence it was done?

1. Some have already posted the explanation of the O() notation, but if you want to read some more check here http://en.wikipedia.org/wiki/Big_O_notation

Usually, the notation is used to estimate the complexity of an algorithm, but it can also be used as a general measure of a magnitude of a function.

2. The proof doesn't imply any particular method of filling the sheet. It does imply that we start from the empty grid and add numbers sequentially beginning with 1. Even if the grid is already filled and we don't know what algorithm was used to fill it, we can still repeat the process by placing all numbers in their cells sequentially. However, I agree that my proof requires a little bit of the clarification, so here it is...

My proof is based on the fact that as the area covered with the numbers grows, so does the number of the empty neighboring cells. Each number at the edge of the area filled with numbers has 1-4 empty neighboring cells. Assuming the following notation:

X - the largest number on the grid at any point in time

A - the area covered by the numbers 1 through X

N - perimeter of A as the number of the empty neighboring cells

as X approaches infinity, A and N also approach infinity. N has no finite limit as for any n there is big enough X that even with the most efficient way of placing the numbers on the grid N>n.

Spoiler for The smallest N for X:

The diamond

9
8 3 10
7 2 1 4 11
6 5 12
13

Those N empty neighboring cells must be filled and the numbers that will be used to fill them are all greater than X, so once those N cells are filled there will be at least one pair of neighboring cells with the difference greater or equal to N.

[Guest]

Oops! In my previous post, in the last paragraph of the second spoiler, where it says "This means that for any number m, we will eventually need more numbers to complete a group D[n] than there exist in the set of numbers within (m-1) of c[1]", it should actually say (m-1)n instead of (m-1).

[Prime]

2. The proof doesn't imply any particular method of filling the sheet. It does imply that we start from the empty grid and add numbers sequentially beginning with 1. ...

That is a particlular method. Part (1) of the problem calls for a method of filling out the infinite sheet. Part (2) implies that we don't know how the infinie sheet was filled, what it started with, or if there was any sequence at all. For all we know, higher infinity forces were at work there, and all natural numbers were placed on the sheet at the same instant randomly. Among all those infinite arrangements, could there be one where difference between any 2 neighboring squares would not exceed some number "m"?

Unless I misunderstood, the proof that you offer relies on ...

It relies on sequential numbers lined up along the perimeter.

But what if that was never the case for any area on the filled out sheet? What if the area that we came upon was filled entirely with odd numbers? And what if the largest numbers ran around the perimeter? Than we could add a new outer perimeter consisting of the closest even numbers and have the differences of 2 and 1, and, at the most, 3 and 4 in the corners.

I can see, that would create problems inside our chosen area. But then the proof gets longer. They wouldn't leave too much space for those problems in "Kvant". So we are looking for a short proof. I think, about the same size you've given, but without any reliance on how or in what sequence/pattern the numbers were placed on the sheet.