Keep The Difference Small
Filling a 5 × 5 grid with distinct integers from 1 to 25, what is the minimum of the maximum of the differences between 2 squares that share a common side?
Hint:
As an explicit example, for the naive arrangement below
the maximum of the differences between 2 squares sharing a common side is equal to 5. This is because, in the above table which is one of all 2 5 ! possible arrangements, the maximum never exceeds 5, as can be seen by the differences between many neighboring cells: 6 − 1 = 7 − 2 = ⋯ = 2 4 − 1 9 = 2 5 − 2 0 , which are all equal to 5. Hence, the minimum of the maximum we are looking for is at most 5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
@Alex Li I've added in how to deal with this problem in a way that is independent of "strategy consideration". You can see that it highlights the essence of your proof in a much clearer manner.
@Daniel Berger You can see how this solution also easily generalizes to the N × N case, so we're not required to find the corresponding value of "7".
Log in to reply
Thanks for the solution, I could not figure out any way to formalize what made intuitive sense so i kind of gave up, sorry.
I think this question is poorly worded - even after looking at the comments it took me a while to understand what was being asked for. When you talk about squares sharing a common side, I had understood that to mean a side of the large 5 × 5 square.
Log in to reply
How do you think the phrasing can be improved?
Log in to reply
Update: I've added more lines to the last paragraph...
Log in to reply
@Pi Han Goh – I still think it's really unclear. Is it the minimum of max difference between any two adjacent squares? The answer is 1.
Any two squares on one side (i.e. any two squares in row 1, row 5, column 1, or column 5)? The answer is 4.
Or is there an assumption that limits how the grid can be filled, more than just a 5x5 arrangement of the integers 1-25?
Log in to reply
@Alex Peirce – Please read the last paragraph of the question again. Your configuration shows that you have found a minimum of 5 too.
Please help me to parse what the problem statement means. This is how I understand it, so far, (1) every square in a 5x5 grid is uniquely filled by an integer from the set of integers 1 to 25. (2) every square has an adjacent square (i.e. the two squares have a common side). (3) Nine interior squares will have four differences: up, down, left and right. The four squares in the extreme corners will only have two differences and the three interior squares along each of the four sides will have three differences. So each of the 25 squares has a set of 2, 3 or 4 differences with its adjacent neighbors. (4) Of the set of differences that each square has with its adjacent neighbors, one of those differences will be a maximum, creating a set of 25 maximum differences. (5) Of the set of 25 maximum differences, one of those will be a minimum. Given my interpretation, why can't the minimum maximum be 2, which would be the case if "1" was in the upper left corner and "2" was to its right and "3" was below it. The differences for the "1" square would be the set {1 and 2}. The maximum difference would be 2. No other square could have a smaller maximum difference, so the minimum maximum difference would be 2.
So, if I've misunderstood what the problem is asking, please help.
Log in to reply
You don't look at the differences of each square. You look at all the differences (there are 40 of them) and take the maximum among them. Now, among all possible ways of filling the grid, you want to minimize this maximum.
This is actually related to the outer boundary of a subset of vertices in a graph: given a graph G = ( V , E ) and a subset S ⊆ V , the outer boundary ∂ out ( S ) is the set of all vertices in V ∖ S that is adjacent to some vertex in S . For a given labeling of the vertices of G by { 1 , 2 , 3 , … , n } where n = ∣ V ∣ and no two vertices have the same label, if S k is the set of all vertices of G with labels { 1 , 2 , 3 , … , k } , the maximum difference is at least max 0 ≤ k ≤ n ∣ ∂ out ( S k ) ∣ .
Thus, to minimize the maximum difference, we want to bring this value as low as possible and then show that it's achievable. Conversely, to prove a lower bound, we want to find a lower bound for this value over all possible labelings; this is exactly your hint of considering labeling the graph from 1 to n sequentially. Finally, this also allows us to generalize the problem to arbitrary graphs, not only grid graphs.
5 is possible according to the example.
4 is not possible, I'm trying to show that the number block with 1-7 has at least 5 neighbors greater 7.
The numbers 1-7 will be either in 5 different rows, 4 different rows, 3 different rows or 2 different rows. Imagine the boxes with 1-7 to be black, the others white.
5 rows: there are at least 5 white boxes adjacent to the black boxes. At least the ones below (above) each black box. That means there will be a difference of at least 5 as the numbers 8-25 only contain 4 numbers with difference 4 or less to the numbers 1-7. So the five white boxes can not be filled with max difference 4.
Note that 7 boxes in 5 rows means max 3 columns with black boxes.
4 rows: same again, 4 white boxes adjacent below (above) and additionally at least 1 in the completely white row left or right to a black box. At least 5 adjacent white and therefore difference of at least 5.
Note that 7 boxes in 4 rows means max 4 columns with black boxes.
3 rows: in case there are 4 columns, rotate 90 degrees and you have the case above.
For 3 rows in max 3 columns: 3 above (below) plus 2 from the white columns adjacent, again at least 5.
2 rows: rotate 90 degrees and you have 4 or 5 rows
Yes, we know that 5 is possible. But is that the optimal configuration?
First, I will prove that we require a minimum difference of 4. Consider if we had a minimum difference of 3. If we put the 1 in the bottom left and 25 in the top right, as far from each other as possible, we would need every 'route' between them to have a difference of 3 between each square to make it.
However, there are several routes, not just the one shown. For example, going all the way up, and then to the right. Each would need to have these exact numbers in them, so 3 or less is not possible.
Now, how about a difference of 4? By the route logic above, we can see that either the 1 or 25 must be in the corner opposite the other. So we will put the 1 in the bottom left corner. This is a bit of a heuristic leap, but I can't come up with anything better, so we know we want to bunch up numbers that are closer. Placing the 2 or 3 later will hurt us. So we place the 2 and 3 next to the 1. On the next diagonal, we follow this logic and place a 4,5,6. The next column gets 7,8,9,10 and the next gets 11,12,13,14,15. However, There is no way to do this without putting the 11 next to a 7, so the difference must be 5 or more, and we can see that that is possible by the diagram above.
By the route logic above, we can see that either the 1 or 25 must be in the corner opposite the other.
Not quite yet. Since 4 2 5 − 1 = 6 , we can only conclude that they must be at distance 6 away from each other. Distance 6 gives the unique path 1 − 5 − 9 − 1 3 − 1 7 − 2 1 − 2 5 , and so we can conclude that we need distance at least 7. It's not immediately apparent to me why it must be distance 8.
The idea of "bunch up numbers that are closer" is good. Think about what numbers can be bunched, and how/why.
Log in to reply
I am saying distance 7 is okay, it's just that with distance 7 either the 25 or 1 has to be in the corner. By symmetry, I put the 1 in the corner.
Log in to reply
I agree that WLOG 1 is in the corner.
I read the statement "must be in the corner opposite the other" as "both must be in opposite corners".
I added a hint on how to exploit "bunch up numbers that are closer".
(I spent a lot of time trying to figure out a nice fancy method like counting the number of ways from bottom right to top left and showing that it was more than the total number of ways to add 8 (not necessarily positive) numbers less than or equal to 4 and reach 24. Unfortunately it isn't, but that would be a cool proof. The proof I eventually found is significantly less cool, but hey, I'm just happy I found something rigorous.)
Let's place our numbers in ascending order. 1, then 2, then 3, etc. Start with 1 in the bottom left corner. Assuming you require a distance of <=4, every time that you add a number next to a number, you must cover each adjacent space within 4 turns. Therefore, all I need to prove is that the number of spaces that need to be covered at a time will eventually exceed 4, regardless of your strategy.
First, let's consider the strategy of placing each number next to an already placed one. Starting at 1, we see that every time we move to the next diagonal, the number of spaces to be covered increases by 1 when we place a number. (If we stay on a diagonal, the number of spaces to be covered does not change). This effect stops once we reach the largest diagonal.
(By the way these are the diagonals I'm talking about)
Next, consider the strategy of not placing a number next to an already placed one. If this eventually joins with the other numbers into 1 body, it is effectively the same in terms of the number of nearby empty spaces. However, if it does not, than it will only add spaces and therefore be an inferior strategy to the other.
We can also generalize this to a N by M grid. The answer will be the size of the largest diagonal, which is just the minimum of N and M.
Log in to reply
Great! The generalized answer is indeed min ( N , M ) .
There is a very simple, cool and rigorous proof. You essentially touched on the key point of "all I need to prove is that the number of spaces that need to be covered at a time will eventually exceed N − 1 , regardless of your strategy". How can we make this independent of strategy consideration?
Note: The reason why I want to avoid the "consider best case scenario first", is because we do not know for certain that "strategy of placing each number next to an already placed one + staying on a diagonal" is indeed the best.
Log in to reply
Hmm. I'm not sure what you're going for. Independently of strategy, it can be shown that any 10 points will have 5 white spaces next to them. Or you could say that there will eventually be a point where all 5 columns xor all 5 rows will have 1 space that needs to be filled. But these would still require strategy considerations.
Log in to reply
@Alex Li – You're getting hotter.
There is an argument that is independent of strategy considerations in the sense that we do not have to control how they place down the numbers. E.g. If it is indeed true that "any 10 points will have 5 white spaces next to them", then this is independent of any strategy considerations. It doesn't matter whether the squares are filled next to an already placed one, or that we backtrack and fill in the gap.
(In particular, you can see that this argument is bringing you further away from the "minimum step difference of 3/4". While that is a nice initial approach, it turns out to be a red herring.)
The question does not state that the numbers have to fill the grid in order, does it? If we enter the 25 numbers in any order, the minimum of maximum differences between adjoining numbers is 2.
The other combinations in this grid(other than the one given) can be achieved by swapping pair of digits in the given arrangement(i.e., 12345...) at least once such that no arrangement is repeated that have been encountered before during this process(avoiding those swaps which would get us to a previously discovered arrangement). You can now observe it easily that any swap would result to change the Max difference over 5.( Prove it yourself)
Can you add in more details? I do not understand what you are trying to say.
Also, how do you know that there isn't a swap that first brings the max to 6, but a subsequent swap that allows us to bring a max to 4? IE What you have found is a local extrema (by swaps), but it need not be a global extrema.
[This is not a complete solution. It provides some hints]
The hardest part of the proof is explaining why 4 is not possible.
Proof by contradiction. Suppose such a solution exists.
Hint: Prove that if the numbers from 1 to k are filled in sequentially, then there will come a point in time when there are 5 blank spaces neighboring already filled squares.
Hint: Prove the generalized case of an N × M rectangle.
[Here is the actual solution.]
We will show that given any way of filling in the grid with numbers from 1 to 25, then there will always be 2 numbers which differ by at least 5.
Given any configuration, pretend that we write in the numbers from 1 to 25 in an increasing sequence. Let k be the smallest number in which we have completely filled in a row or column. In the example, we have k = 5 .
Consider the squares filled in with the numbers from 1 to k − 1 . We will count the number of neighbours to these squares which are currently empty. WLOG, let square k complete a row. Then
Thus, there are at least 5 neighboring squares. Each of these squares will be filled in with a number from k , k + 1 , k + 2 , … . Since there are 5, we are guaranteed that one of these neighboring squares is at least k + 4 . Then, the filled square that it is next to is at most k − 1 . Hence, there is a difference of at least ( k + 4 ) − ( k − 1 ) = 5 .
Thus, in any configuration, there are 2 squares which differ by at least 5. It remains to find a configuration where this is possible (which has already been done).
Note: Now generalize it to the N × M rectangle. What is the answer? (Be careful, some parts of the solution need to be rephrased when N = M .)