UW Challenge April 21 2008
April 20th, 2008 by erb
This week’s problem: Find the minimum number of squares that are required to draw a complete n x n grid. For example, when n = 2, the answer is 3, as three squares suffice: a 2×2 and two 1×1 squares (draw a picture!); moreover it is easy to see it can’t be done with fewer.
2(n-1), for n>3. For n=3, 5. I don’t have a complete proof, but logically it seems that my solution below is sound, based on both recursion and “minimal completeness” arguments. Further, I have comparisons of several other non-optimal “obvious” algorithmic techniques, which are less than optimal (See bottom).
Consider the first four cases, for n=2..5: See figure below. Note that 2 and 3 are special cases, but 4 and 5 reflect common solutions for all n ≥ 4, even and odd. Number of squares required using this method (which I claim is optimal, below): 2(n-1).
The algorithm shown above is one of two ways to achieve the same result, and is the first way I found it:
- Start with 2 squares of size (n-1)x(n-1).
- Continue adding squares of successively smaller size, in pairs, alternating the “diagonal”, until you get down to the smallest pair of size 1×1.
- For n odd, there is one crucial difference: When you reach the lower middle value, size s=⌊n/2⌋, do not alternate the diagonal! (See above, n=5, for s=⌊5/2⌋=2.) This is necessary for what should be obvious reasons on inspection: The previous pair of squares, of size s’=⌈5/2⌉=3, have already taken care of the interior sides associated with squares s=2 if we did alternate the diagonal, and worse we would miss the necessary interior sides actually needed.
- For n even, there is no such problem (middle size value for s=n/2 divides evenly, and further completely divides the entire grid of squares completely down the middle, horizontally and vertically).
The “alternate algorithm,” yielding identical results, shows why I think this is optimal. Instead of starting from the outside in, from size (n-1)x(n-1) down to 1×1, rather start from the center working your way out, following the diagonal intersections: For each step, add a total of 4 squares, in pairs of 2:
If n is odd, the center square is 1×1, and you will draw complementary squares (4 total, pairs of 2), of sizes s1=⌈n/2⌉ (overlapping, to create the center 1×1 square) and s2=n-s1. Each successive step, alternate diagonals used, with new sizes s1′=s1+1 and s2′=n-s1′. The final squares will have sizes s1=n-1 and s2=n-(n-1)=1. Total # algorithm steps = the first s2=n-⌈n/2⌉=⌊n/2⌋, and since we draw four squares per step, total # squares = 4⌊n/2⌋=4(n-1)/2=2(n-1).
If n is even, the center “square grid” is 2×2, and you follow the same algorithm as above (4 total squares per step, pairs of 2). First step s1=n/2, and there is no need for s2=n-s1=n/2, so you “save” 2 squares on first step for n even. Total # algorithm steps = first s1=s2=n/2, total # squares = 4(n/2)-2=2n-2=2(n-1).
Why is this optimal? We are working our way out from the center, covering as many line segments as possible (maximal coverage for minimal steps), using steps that are similar to the optimal coverage patterns used for n=2 and n=3 (expanded accordingly). E.g., for n odd, we are actually starting with an n=3-like pattern, and for n even, it is very similar to n=2 (without the outer square). In addition, it is clear that for ANY “intersection” point on the interior of the grid, a minimum of 4 squares MUST be used to accomplish the 4 line segments. This approach is “walking” the diagonals, from the center to the outermost corners, each step accomplishing completion of all 4 relevant intersections (using 4 squares) — in the minimal number of steps.
For comparison, some other possible approaches require more squares, with varying degrees of “efficiency”:
Cases:
- nxn 1×1 squares: Worst case, inefficient, simple
- non-overlapping 1×1 squares, subset of Case 1, plus 1 outer nxn (an obvious and straightforward optimization of Case 1; a standard checkerboard pattern)
- Expanding Diagonal, 2x squares “orthogonal” — i.e., starting from top left, 1×1, then 2×2, … nxn, as well as starting from bottom right, 1×1, 2×2, .. (n-1)x(n1)
- Expanding Diagonal, alternating — “optimal” algorithm described above
Efficiency Definitions: (Simple ratios, lower is “better”)
- (# Lines Needed) / (# Lines Total)
- (# Squares) / (# Lines Total)
- (# Squares) / (# 1×1 Squares in nxn Grid)
Case #Squares #Lines Eff1 Eff2 Eff3
-------- ---------- -------- ------------ ---------------- ------------
1 n^2 4n(n-1) (n+1)/2(n-1) n/4(n-1) 1
2 n Even (n^2+3)/2 2(n+1)^2 (n )/(n+1) (n^2+3)/4(n+1)^2 (n^2+3)/2n^2
2,n Odd (n^2+2)/2 2n(n+2) (n+1)/(n+2) (n^2+2)/4n(n+2) (n^2+2)/2n^2
3 2(n-1)+1 4n(n) (n+1)/(n ) (2n -1)/4n^2 (2n -1)/ n^2
4 n>3 2(n-1) 4n(n-1) (n+1)/2(n-1) 1/2n (2n -2)/ n^2It is particularly interesting to consider the limiting cases as n→∞:
Case #Squares #Lines Eff1 Eff2 Eff3
-------- -------- ------- ------- ------- -------
1 n^2 4n^2 1/2 1/4 1
2,n Even n^2/2 2n^2 1 1/4 1/2
2,n Odd n^2/2 2n^2 1 1/4 1/2
3 2n 4n^2 1 0 0
4 2n 4n^2 1/2 0 0
One Response to “UW Challenge April 21 2008”
Leave a Reply
-
My Visitors
-
My Calendar
erb
wrote on 04/28/08 at 11:25 am :
Obviously, in retrospect, I completely and carelessly dropped the ball on case n=3. That’s not a special case at all, and the minimum is in fact 2(n-1) — therefore the problem solution is 2(n-1), for n>2, not for n>3.
The posted solution has a simpler, more precise solution with a better “necessary and sufficient conditions” proof.