Squares on a plywood

[BMAD]

Imagine a piece of plywood with an array of evenly spaced nails forming small squares and consider that each square has side lengths of 1 unit.  A simple closed shape is formed with a rubber band.  If you knew the number of nails used in the perimeter and the perimeter itself, how could you predict how many squares can be counted inside this rubber band shape?

for example say the rubber band shape is outlining these nails:

* -  * - * - * - *

|                  /

*   *   *   *

|           /

* - * - *

Perimeter = 8 + 2*sqrt(2)

Nails = 12

Squares: 6 squares (5 - 1x1 and 1 - 2x2)  --- the result of 6, at a minimum, is what we are trying to predict.

[CaptainEd]

We are not limited to convex figures, right?

[BMAD]

8 hours ago, CaptainEd said:

We are not limited to convex figures, right?

Hmmm, I only considered convex figures when making this problem.  Let us first solve the simple case (only convex) then we could consider the more complex case with the relaxed condition.

[CaptainEd]

Tricky enough as it is—here is my first cut

 

Caveat: I have no justification/derivation for my answer.

Area = Nails -Perimeter/2 -1

When counting perimeter, treat each diagonal nail-to-nail segment as 1, rather than root2, root5, root17, etc. (Absurd!!!)

This gives correct area for

* OP example: there are 2root2, that count as 2. (N=12, P=8+2, formula says 12-5-1=6)

* rectangles

* right trapezoids, and right triangles

Caveat #2: any nail-to-nail diagonal must be treated as a root, hence 1. This is needed to explain a 345 right triangle. This has a row of 5 nails, a row of 3 nails, a row of 2 nails and a row with 1 nail. If you correctly deduce that the hypotenuse is exactly 5, the formula would not work (N=11, P=12, formula = 11-6-1 = 4), but if you count the diagonal as root25, hence 1, formula works (N=11, P=7+1, formula=11-4-1=6). I told you this is an absurd formula!)

I look forward to a better answer :-)

 

Edited May 10, 2018 by CaptainEd
Corrected nails in 345

[bonanova]

Doctoring the figure a bit (while I think about solving it.)

o  -  o  -  o  -  o  -  o
|                    /
o     o     o     o
|              /
o  -  o  -  o

Question: You mention the number of nails (12) and also the number of nails in the perimeter (here that's 10.) So for this example, would we be given N=12 or N=10? I'm thinking the latter, but would like to confirm.

[BMAD]

1 hour ago, bonanova said:

Doctoring the figure a bit (while I think about solving it.)

o  -  o  -  o  -  o  -  o
|                    /
o     o     o     o
|              /
o  -  o  -  o

Question: You mention the number of nails (12) and also the number of nails in the perimeter (here that's 10.) So for this example, would we be given N=12 or N=10? I'm thinking the latter, but would like to confirm.

nails are 12

perimeter are the side lengths, 8+sqrt(2)

Forgive my english, i think i see the confusion.  When I say the number of nails in the perimeter what I am really trying to say is the number of nails throughout the shape.

[CaptainEd]

Hah! It’s exactly right!

The formula A = N – P/2 -1 is exact for any connect figure composed of sticks, rectangles, and triangles, whether concave or convex, but with no holes. We can compute the Area of any such construction as long as we are given N and P, where P is the sum of the lengths of foursquare segments (NS,EW) plus a square root for each diagonal.

First, construct the figure.

The Null figure consists of a nail with a rubber band around it. N=1, P=0, A=0. Note that the formula (F) is observed, A = N – P/2 -1.

Now, append a stick, rectangle, or triangle.

·         Stick: append a foursquare “stick” of M nails to the outside of any nail in the perimeter of the existing figure. Stretch the rubber band to the end of the stick and back. This adds M to the N count, and adds 2M to the P count, but adds 0 to the area.  The formula still obtains, because it adds M-2M/2=0 to A.

·         Rectangle: append a  rectangle of size PxQ to share one side of an existing foursquare line segment. If the existing side is not long enough, append one or two sticks collinear with the existing side. For generality, assume the shared side of the new rectangle  is of length P. (the existing side of existing figure can be longer). Since the shared side already contains P+1 nails, we are adding Q(P+1) nails. Since we are essentially sliding the P side perimeter out to the outside of the rectangle, we are only adding 2Q to the perimeter.  We are adding PQ to the area. The formula still obtains, because we add Q(P+1) to N, we add 2Q to P, and we add PQ to area. Q(P+1) – 2Q/2 = PQ.

·         Triangle: append a triangle with base P and altitude Q to share one or two foursquare sides of the figure. If the existing sides are not long enough, append or two sticks collinear with the existing sides.

·         For this proof, if P and Q are not relatively prime, then break it down into a succession of rectangles and triangles, each of which the same size. For example, to add a 3x6 triangle, add a 1x3 triangle, then a 1x3 rectangle, then the other 1x3 triangle. Similarly, to add a 2x6 triangle, append a 1x2 triangle, a 1x2 rectangle, a 1x2 triangle, a 2x2 rectangle, and the last 1x2 triangle.

·         For generality, assume the shared side of the new triangle is of length P. (once again, the existing sides can be longer). Since the shared sides already contains the necessary P+Q+1 nails, we are only adding nails necessary for the interior of the triangle.

·         (Asserted without proof) the number of nails INSIDE a PxQ triangle where P and Q are relatively prime is (P-1)(Q-1)/2

·         The added area is clearly PQ/2

·         What impact does this action have on N, P, and A?

·         deltaN is (P-1)(Q-1)/2

·         deltaA is PQ/2

·         deltaP: we are removing P+Q from the perimeter and adding a side of length root(Psq+Qsq). So deltaP = -(P+Q) + root…

·         Does the Formula show deltaA = deltaN – deltaP/2?

·         PQ/2  ?= (P-1)(Q-1)/2 +(P+Q)/2

·         PQ/2 ?= PQ/2 –P/2 –Q/2 +1/2 +(P+Q)/2

·         PQ/2 ?= PQ/2 –(P+Q)/2 +(P+Q)/2 +1/2

·         So, interestingly enough, the only discrepancy is ½.

·         My proposal, count the square root (regardless of its contents) as contributing 1 to the delta perimeter

·         In other words, PRETEND that we remove P+Q from the perimeter and add 1 to the perimeter

·         Now deltaA = PQ/2, deltaN = (P-1)(Q-1)/2, deltaP is –(P+Q-1), and F still holds.

·         Notice that we need to have hypotenuses identified by square roots, even if they happen to be integers (as in a 345 right triangle)

So this construction (informally) shows that any figure constructed this way obeys the Formula A=N-P/2-1, as long as we carry around the square roots, one per triangle.

Given such a figure, including the square roots, first take a triangle (represented by a square root), identify the P and Q, add P+Q-1 to the perimeter, subtract PQ/2 from A (accumulate this A contribution in a separate counter for later use) and (P-1)(Q-1)/2 from N. Once all the triangles are out of the figure, compute A from the existing adjusted N and P values, and add the accumulated A. This is the A of the original figure.

[CaptainEd]

Sorry, proof was right, but method for calculation was confusing

 

given N, the number of nails on or inside the perimeter of the figure,

given P, in two components: total of NSEW segment lengths  and

D, number of diagonal segments, (that is, six diagonals => D=6)

A = N -(P+D)/2-1

so, treating any diagonal as adding 1 to Perimeter is actually right!

 

Edited May 11, 2018 by CaptainEd

[BMAD]

On 5/11/2018 at 2:03 PM, CaptainEd said:

Sorry, proof was right, but method for calculation was confusing

  Hide contents

given N, the number of nails on or inside the perimeter of the figure,

given P, in two components: total of NSEW segment lengths  and

D, number of diagonal segments, (that is, six diagonals => D=6)

A = N -(P+D)/2-1

so, treating any diagonal as adding 1 to Perimeter is actually right!

 

If I am not mistaken, you found a way to calculate the area every time; which is wonderful,  However, I wanted to know if it could be extended to know the amount of nxn squares that were defined within the shape not the precise area.

Edited May 14, 2018 by BMAD

[CaptainEd]

Ooh, now I see what you mean. Much different problem. Sorry

[CaptainEd]

I question whether the information given about a figure is sufficient to uniquely determine the number of included squares:

If I understand right, these two figures have the same N and P, but don’t have the same number of squares.

    o o o o
 o o o o o
 o o o
Nails = 12, perimeter = 7+sqrt2 + sqrt5
Squares =5

 o o o o
 o o o o o
 o o o
nails=12, perimeter = 7 + sqrt2 + sqrt5
Squares = 6

[BMAD]

On 12/12/2018 at 4:52 PM, CaptainEd said:

I question whether the information given about a figure is sufficient to uniquely determine the number of included squares:

  Hide contents

If I understand right, these two figures have the same N and P, but don’t have the same number of squares.

    o o o o
 o o o o o
 o o o
Nails = 12, perimeter = 7+sqrt2 + sqrt5
Squares =5

 o o o o
 o o o o o
 o o o
nails=12, perimeter = 7 + sqrt2 + sqrt5
Squares = 6

 

 

So then if we know N and P we should be able to bound  squares x by a two values. Are those values always consecutive?

[CaptainEd]

I think not: please check my counting

 

In what follows, the rubber band’s path goes on the outside of the nails marked “x

 o o o o o o o
 o o o o o o o o x
 o o o o o o o o
 o o o o o o o
 o o o o o o
 o o o o o x
N = 43
P = 21 + sqrt(5)
S = 62: (5x5:1, 4x4:4, 3x3:10, 2x2:18, 1x1:29)

Compare with

       o o o o o o o 
 o o o o o o o o x
 o o o o o o o o
 o o o o o o o
 o o o o o o
 o o o o o x
N = 43
P = 21 + sqrt(5)
S = 56: (4x4:2, 3x3:8, 2x2:17, 1x1:29)

 

Edited December 15, 2018 by CaptainEd
Correct a row

[BMAD]

On 12/15/2018 at 4:16 PM, CaptainEd said:

I think not: please check my counting

  Hide contents

In what follows, the rubber band’s path goes on the outside of the nails marked “x

 o o o o o o o
 o o o o o o o o x
 o o o o o o o o
 o o o o o o o
 o o o o o o
 o o o o o x
N = 43
P = 21 + sqrt(5)
S = 62: (5x5:1, 4x4:4, 3x3:10, 2x2:18, 1x1:29)

Compare with

       o o o o o o o 
 o o o o o o o o x
 o o o o o o o o
 o o o o o o o
 o o o o o o
 o o o o o x
N = 43
P = 21 + sqrt(5)
S = 56: (4x4:2, 3x3:8, 2x2:17, 1x1:29)

 

All you showed is the bound is wider than one thought.