Area 10 Squares – Proof & Additional Musings

Additional musings on the problem of Area 10 Squares:

Thanks, again to Dave Gale‘s inspirations and comments on my initial post. For some initial clarifications, what I was asking in Question 3 was whether these square areas ultimately can all be found after a certain undetermined point, thereby creating a largest area that could not be drawn on a square grid. I’m now convinced that the answer to this is a resounding NO–there is no area after which all integral square areas can be constructed using square grid paper. This is because there is no largest un-constructable area (proof below). This opens a new question.

Question 4:
Is there some type of 2-dimensional grid paper which does allow the construction of all square areas?

The 3-dimensional version of this question has been asked previously, and this year in the College Math Journal, Rick Parris of Exeter has “proved that if a cube has all of its vertices in then the edge length is an integer.”

Dave’s proposition above about determining whether an area 112 (or any other) can be made is very interesting. (BTW, 112 cannot be made.) I don’t have any thoughts at present about how to approach the feasibility of a random area. As a result of my searches, I still suspect (but haven’t proven) that non-perfect square multiples of 3 that aren’t multiples of pre-existing squares seem to be completely absent. This feels like a number theory question … not my area of expertise.

Whether or not you decide to read the following proof for why there are an infinite number of impossible-to-draw square areas using square grids, I think one more very interesting question is now raised.

Question 5:
Like the prime numbers, there is an infinite number of impossible-to-draw square areas. Is there a pattern to these impossible areas? (Remember that the pattern of the primes is one of the great unanswered questions in all of mathematics.)

THE PROOF
My proof does not feel the most elegant to me. But I do like how it proves the infinite nature of these numbers without ever looking at the numbers themselves. It works by showing that there are far more integers than there are ways to arrange them on a square grid, basically establishing that there is simply not enough room for all of the integers forcing some to be impossible. I don’t know the formal mathematics name for this principle, but I think of it as a reverse Pigeonhole Principle. Rather than having more pigeons than holes (guaranteeing duplication), in this case, the number of holes (numbers available to be found) grows faster than the number of pigeons (the areas of squares that can actually be determined on a square grid), guaranteeing that there will always be open holes (areas of squares that cannot be determined on using a square grid).

This exploration and proof far exceeds most (all?) textbooks, but the individual steps require nothing more than the ability to write an equation for an exponential function and find the sum a finite arithmetic sequence. The mathematics used here is clearly within the realm of what high school students CAN do. So will we allow them to explore, discover, and prove mathematics outside our formal curricula? I’m not saying that students should do THIS problem (although they should be encouraged in this direction if interested), but they must be encouraged to do something real to them.

Now on to a proof for why there must be an infinite number of impossible-to-draw square areas on a square grid.

This chart shows all possible areas that can be formed on a square grid. The level 0 squares are the horizontal squares discussed earlier. It is lower left-upper right symmetric (as noted on Dave’s ‘blog), so only the upper triangle is shown.

From this, the following can be counted.
Level 1 – Areas 1-9: 6 of 9 possibilities found (yellow)
Level 2 – Areas 10-99: 40 of 90 possibilities found (orange)
Level 3 – Areas 100-999: 342 of 900 possibilities found (blue)

The percentage of possible numbers appears to be declining and is always less than the possible number of areas. But a scant handful of data points does not always definitively describe a pattern.

Determining the total number of possible areas:
Level 1 has 9 single-digit areas. Level 2 has 90 two-digit areas, and Level 3 has 900 three-digit areas. By this pattern, Level M has M-digit areas. This is the number of holes that need to be filled by the squares we can find on the square grid.

Determining an upper bound for the number of areas that can be accommodated on a square grid:
Notice that if a horizontally-oriented square has area of Level M, then every tilted square in its column has area AT LEAST of Level M. Also, the last column that contains any Level M areas is column where floor is the floor function.

In the chart, Column 1 contains 2 areas, and every Column N contains exactly (N+1) areas. The total number of areas represented for Columns 1 through N is an arithmetic sequence, so an upper bound for the number of distinct square areas represented in Columns 1 to N (assuming no duplication, which of course there is) is .

The last column that contains any Level M areas has column number . Assuming all of the entries in the data chart up to column are Level M (another overestimate if is not an integer), then there are

maximum area values to fill the Level M area holes. This is an extreme over-estimate as it ignores the fact that this chart also contains all square areas from Level 1 through Level (M-1), and it also contains a few squares which can be determined multiple ways (e.g., area 25 squares).

Conclusion:
Both of these are dominated by base-10 exponential functions, but the number of areas to be found has a coefficient of 9 and the number of squares that can be found has coefficient 1/2. Further, the number of squares that can be found is decreased by an exponential function of base , accounting in part for the decreasing percentage of found areas noted in the data chart. That is, the number of possible areas grows faster than the number of areas that actually can be created on square grid paper.

While this proof does not say WHICH areas are possible (a great source for further questions and investigation!), it does show that the number of areas of squares impossible to find using a square grid grows without bound. Therefore, there is no largest area possible.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s