[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.

[Prime]

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".

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.

Ah... I remember now. That has a touch of nostalgia. I used to know those things. Long time ago, I wouldn't believe, I'd forget what it is. The O() we used to call "Order of". And binary search...

I shall post an old nice programming puzzle for all computer programmers on the forum. If I find a simple way to formulate it. And if I can figure out myself, how to solve it.

[Prime]

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.

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.

The part of filling out the infinite sheet is nicely done.

As far as the proof, my attention span is not good for more than 10 lines of text. But I happened to notice that your proof also relies on your particular method of filling out the sheet.

[k-man]

... 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"?

Suppose you give me a sheet pre-filled with all the numbers. I will start with an empty grid and will place the number 1 in the same square as on your sheet. Then I will place the number 2 in the same square as your sheet has it, and so on. It doesn't matter to me where the numbers on your sheet are located, I can "reproduce" any sheet with any number arrangement by placing numbers sequentially.

I think I proved that for any number "m" you give me I can find a finite number X that no matter how you place numbers 1 through X on the sheet there will be more than "m" empty neighboring squares. Once those squares are also filled there will be a pair of neighboring squares with the difference exceeding "m".

Spoiler for formula for X (for extra points) :

X=m²/8 - m/2 + 1.

[Guest]

I think I have it.

a) Create the grid. We'll assume the infinite spiral grid so nicely posted by flowstoneknight.

b) For any number "m" there must exist two adjacent squares who's difference is greater than m. This must be true because the smallest difference we can find in the spiral arrangement is 1 (2-1) and the differences increase from 1 to infinity, due to the infinite sheet.

There is no more efficient way to populate the infinite sheet to keep a difference of less than "m". The out and back method can have some constant difference, but by definition it would then have a "sheet boundry". To make the sheet truely infinite, you would have to populate numbers on either side of these boundries which would then satisfy our a-b>m requirement. Even if we went out to infinity and back, we would still have to populate our sheet on the "other side" of our first row, which would satisfy our requirement.

So what do we think?

[k-man]

There is no more efficient way to populate the infinite sheet to keep a difference of less than "m".

Can you prove this?

[Prime]

Several proofs posted on this topic zeroed in on the essence of the problem. I feel, however, that all of them rely on a method for filling out the infinite sheet.

Here is a solution that does not:

1). As number of posters have found, a spiral pattern may be used to fill the infinite sheet:

2). For a proof that there may not be a limit on a difference between two neighboring squares, let's take an arbitrary number m > 1. Than choose a square area 2m*2m anywhere on the infinite sheet.

In accordance with the OP conditions, there are 4m²different numbers in that area. The difference between the largest and the smallest number in that area is not less than 4m² – 1. Let's trace shortest path from the largest to the smallest number of the area along a path of neighbors. The furthest placement for two numbers is in the opposite corners of the area. The shortest path between opposite corners is 4m - 2 steps.

Thus the average difference between neighbors along a path from smallest to largest number is at least (4m² - 1)/(4m – 2). Which is greater than m for all positive m.

Since the average difference between neighbors along such path is greater than m, there must be one or more pair of neighbors with difference greater than m.

QED

[Guest]

The part of filling out the infinite sheet is nicely done.

As far as the proof, my attention span is not good for more than 10 lines of text. But I happened to notice that your proof also relies on your particular method of filling out the sheet.

Actually it doesn't. My proof is independent of where you start on the grid, what number you start with and how the numbers are filled in. The spiral formation was just for naming the cells, not for determining what number's inside each cell. It also works with an infinite grid that's already filled in, but I guess I didn't word my proof properly. I'll explain it again, with some corrections and rephrasing.

Let's suppose that the following is true: there exists a number m for which there exist no pairs of adjacent squares that have a difference not less than m. Basically, all pairs of adjacent squares have differences less than m.

Choose any square, which we'll call c[1]. We will consider the four squares adjacent to c[1] as being "one square away from c[1]". These four squares will be put into a group called D[1] (for Distance 1). The eight "outside" squares adjacent to squares in D[1], we will call D[2]. We continue this to define groups D[3], D[4] and so on. Hereafter, when I refer to a square, I'm referring to the number inside, and not the position of the square.

Defining what group each square belongs to:

[color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#0000FF"]D[1][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#0000FF"]D[1][/color] c[1] [color="#0000FF"]D[1][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#0000FF"]D[1][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color]

Since adjacent squares have differences less than m, any square in D[1] must be (exclusively) within m of c[1].

|c[1] - c[D[1]]| < m

where c[D[1]] represents each square in D[1]

And since each square in D[2] must be within m of an adjacent square in D[1], we know that any square in D[2] must be within 2m of c[1].

|c[1] - c[D2]]| < 2m

We can generalize this to fit any group D[n], where n is some natural number.

|c[1] - c[D[n]]| < mn

Now we look at numbers of numbers. For any natural number, the number of other natural numbers within mn of it is always less than or equal to 2(m+1)n. I won't give examples here so you'll have to check it yourselves. So when looking at any group D[n], there are at most 2(m+1)n possible numbers. But since the set of numbers within mn of c[1] includes the sets of numbers within m(n-1), m(n-2) and so on until m (i.e. all the possible numbers within previous groups), there are actually at most 2(m+1)n possible numbers for all D groups up to and including D[n].

Now let's look at how many numbers exist in all D groups up to D[n]. In D[1], there are 4 numbers. In D[1] and D[2], there are 4+8=12. In D[1], D[2] and D[3], there are 4+8+12=24. The number of numbers that exist in all D groups up to D[n] can be given as 2(n+1)n.

So there exist 2(n+1)n numbers in all D groups up to D[n], and there are at most 2(m+1)n possible numbers for all D groups up to D[n]. Since n can be any natural number, for any m, there is always an n that's greater. So for any 2(m+1)n, there is always a 2(n+1)n that's greater. This means that for any m, there exists some group D[n], for which there are more numbers in all D groups up to D[n] than there are possible numbers for all D groups up to D[n]. This is obviously a contradiction.

Since the assumption of the opposite of the original statement results in an contradiction, the original statement must be true.

Edited August 28, 2008 by flowstoneknight

[Prime]

Actually it doesn't. My proof is independent of where you start on the grid, what number you start with and how the numbers are filled in. The spiral formation was just for naming the cells, not for determining what number's inside each cell. It also works with an infinite grid that's already filled in, but I guess I didn't word my proof properly. I'll explain it again, with some corrections and rephrasing.

Let's suppose that the following is true: there exists a number m for which there exist no pairs of adjacent squares that have a difference not less than m. Basically, all pairs of adjacent squares have differences less than m.

Choose any square, which we'll call c[1]. We will consider the four squares adjacent to c[1] as being "one square away from c[1]". These four squares will be put into a group called D[1] (for Distance 1). The eight "outside" squares adjacent to squares in D[1], we will call D[2]. We continue this to define groups D[3], D[4] and so on. Hereafter, when I refer to a square, I'm referring to the number inside, and not the position of the square.

Defining what group each square belongs to:

[color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#0000FF"]D[1][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#0000FF"]D[1][/color] c[1] [color="#0000FF"]D[1][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#0000FF"]D[1][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color] [color="#FF0000"]D[2][/color] [color="#00FF00"]D[3][/color]
[color="#00FF00"]D[3][/color]

Since adjacent squares have differences less than m, any square in D[1] must be (exclusively) within m of c[1].

|c[1] - c[D[1]]| < m

where c[D[1]] represents each square in D[1]

And since each square in D[2] must be within m of an adjacent square in D[1], we know that any square in D[2] must be within 2m of c[1].

|c[1] - c[D2]]| < 2m

We can generalize this to fit any group D[n], where n is some natural number.

|c[1] - c[D[n]]| < mn

Now we look at numbers of numbers. For any natural number, the number of other natural numbers within mn of it is always less than or equal to 2(m+1)n. I won't give examples here so you'll have to check it yourselves. So when looking at any group D[n], there are at most 2(m+1)n possible numbers. But since the set of numbers within mn of c[1] includes the sets of numbers within m(n-1), m(n-2) and so on until m (i.e. all the possible numbers within previous groups), there are actually at most 2(m+1)n possible numbers for all D groups up to and including D[n].

Now let's look at how many numbers exist in all D groups up to D[n]. In D[1], there are 4 numbers. In D[1] and D[2], there are 4+8=12. In D[1], D[2] and D[3], there are 4+8+12=24. The number of numbers that exist in all D groups up to D[n] can be given as 2(n+1)n.

So there exist 2(n+1)n numbers in all D groups up to D[n], and there are at most 2(m+1)n possible numbers for all D groups up to D[n]. Since n can be any natural number, for any m, there is always an n that's greater. So for any 2(m+1)n, there is always a 2(n+1)n that's greater. This means that for any m, there exists some group D[n], for which there are more numbers in all D groups up to D[n] than there are possible numbers for all D groups up to D[n]. This is obviously a contradiction.

Since the assumption of the opposite of the original statement results in an contradiction, the original statement must be true.

Now, that is a general proof. It takes an arbitrary reference square and shows that you can construct an area around it for which requirement to keep the difference of less than "m" between any two neighboring squares fails.

Small correction: there are at the most 2mn - 1 available numbers for the area, not 2(m+1)n as you estimated. But that is even better for your proof.

Here is an illustration and slight re-wording:

Again, we pick an arbitrary number "m" and show that there always will be differences of more than "m" between some neighboring squares.

Select square X (named after the number it holds) anywhere on the grid. Construct an area arond X, so that the squares at the perimeter are exactly n steps from X (if we trace a shortest path to them through a sequence of neighbors.)

The number of squares inside that area is 2n*(n+1) not counting the origin square X. The largest number insided that area must be less than X+n*m. (We can construct a path of n steps or less to it from X. Thus any larger number would average more than m distance between the neighbors in that path.) Similarly, the smallest number must be greater than X - n*m. Thus we have less than (X+n*m) - (X - n*m) = 2nm - 1 numbers available to fill the area. (Excluding X.)

Comparing that to the number of squares in the area: 2n(n+1) => 2nm-1, we find that for n+1 >= m, we cannot keep the difference between all neghbors less than m. (Omitting fractions, since we deal with natural numbers only.)

[Guest]

I new that was the path to the solution... (looking at the averages in a given area) but I've been away from pens and computers for a couple of days and couldn't make it work in my head. Wd Prime.

Now... what was the more difficult part of the question?

[Prime]

I new that was the path to the solution... (looking at the averages in a given area) but I've been away from pens and computers for a couple of days and couldn't make it work in my head. Wd Prime.

Now... what was the more difficult part of the question?

Thanks.

And I am a little hesitant to post part "B" here. It is more difficult, and I can't see the proof yet. I will not be able to follow 3-page long proofs, which people may submit. But since so many people got interested in the problem, here it is, part B, but without any warranty from me, or obligation to follow up.

PART B

Now let each natural number n on the infinite square-ruled sheet occur exactly n times. Find the largest k such that there always will be neighboring squares with the difference not less than k.

Show an example of an arrangement, where the difference between any two neighboring squares does not exceed k+1.

[HoustonHokie]

PART B

Now let each natural number n on the infinite square-ruled sheet occur exactly n times. Find the largest k such that there always will be neighboring squares with the difference not less than k.

Show an example of an arrangement, where the difference between any two neighboring squares does not exceed k+1.

Clarity question: Doesn't "Find the largest k such that there always will be neighboring squares with the difference not less than k." mean that the difference between neighbors is greater than k, but "the difference between any two neighboring squares does not exceed k+1" means the difference is less than or equal to k? I'm probably misreading something - the brain's just not working this afternoon...

[Prime]

Clarity question: Doesn't "Find the largest k such that there always will be neighboring squares with the difference not less than k." mean that the difference between neighbors is greater than k, but "the difference between any two neighboring squares does not exceed k+1" means the difference is less than or equal to k? I'm probably misreading something - the brain's just not working this afternoon...

In problem A (the OP) we proved that there may not be any finite limit for the difference between two neighboring squares.

This problem (part B) specifies a different kind of population of the infinite sheet. It implies that for that type of population, there is a finite number k such that it is possible to populate sheet and keep the difference between any two members less or equal to k+1.

The tasks are:

1) Find k.

2) Show an arrangement for populating the sheet, such that the difference between any two neighbors does not exceed k+1.

[HoustonHokie]

In problem A (the OP) we proved that there may not be any finite limit for the difference between two neighboring squares.

This problem (part B) specifies a different kind of population of the infinite sheet. It implies that for that type of population, there is a finite number k such that it is possible to populate sheet and keep the difference between any two members less or equal to k+1.

The tasks are:

1) Find k.

2) Show an arrangement for populating the sheet, such that the difference between any two neighbors does not exceed k+1.

Thanks for the reply. The question seemed to imply that we were looking for a maximum k (and perhaps we still are) and therefore it would be possible for all values of k from 1 to whatever this number is. I think I could show that for 1 it does not work.

[Guest]

In problem A (the OP) we proved that there may not be any finite limit for the difference between two neighboring squares.

This problem (part B) specifies a different kind of population of the infinite sheet. It implies that for that type of population, there is a finite number k such that it is possible to populate sheet and keep the difference between any two members less or equal to k+1.

The tasks are:

1) Find k.

2) Show an arrangement for populating the sheet, such that the difference between any two neighbors does not exceed k+1.

k is not 0, as the number 1 must have four neighbours, and with only two 2s the minimum difference must be 2

So... can we construct a sheet with differences less than or equal to 2?

The old spiral seems to work:

9 7 7 9
9 7 5 5 7 9
9 7 5 3 3 5 7 9
9 7 5 3 1 2 4 6 8 10
8 6 4 2 4 6 8
8 6 4 6 8
8 6 8
8

         9 9

A sketch proof would be:

The length of the sides of the diamond increases by 2 each time.... but so do the number of numbers available. So we will have exactly the right amount of numbers to maintain the pattern unto infinity.

But you can see it works, and hence k=1

NB... this part of the question asks about a specific arrangement, not the general arrangement in the first part.

[Prime]

k is not 0, as the number 1 must have four neighbours, and with only two 2s the minimum difference must be 2

So... can we construct a sheet with differences less than or equal to 2?

The old spiral seems to work:

9 7 7 9
9 7 5 5 7 9
9 7 5 3 3 5 7 9
9 7 5 3 1 2 4 6 8 10
8 6 4 2 4 6 8
8 6 4 6 8
8 6 8
8

         9 9

A sketch proof would be:

The length of the sides of the diamond increases by 2 each time.... but so do the number of numbers available. So we will have exactly the right amount of numbers to maintain the pattern unto infinity.

But you can see it works, and hence k=1

NB... this part of the question asks about a specific arrangement, not the general arrangement in the first part.

That's the way! There are enough numbers to keep the difference at a minimum.

[Guest]

PART B

Now let each natural number n on the infinite square-ruled sheet occur exactly n times. Find the largest k such that there always will be neighboring squares with the difference not less than k.

Show an example of an arrangement, where the difference between any two neighboring squares does not exceed k+1.

There appears to be two problems, the first one where the difference is not less than k, and the second where the difference is not greater than k+1. This is for the second part.

As k increases from 1, the largest difference we can get between any two squares is k-1, which is always less than k+1. As for a graphical proof, try any random or organized layout.