18
$\begingroup$

Let $P$ be a $2016$ sided polygon with all its adjacent sides perpendicular to each other, i.e., all its internal angles are either $90$°or $270$°. If the lengths of its sides are odd integers, prove that its area is an even integer.

I think visualising what this polygon might look like would more or less be the key to getting started on the problem, but I'm having quite a hard time doing so. Since the internal angles are all $90$° or $270$°, I think the shape would look like a rectangle or a square with smaller squares or rectangles protruding out from each side — but mini rectangles protruding from sides would not be possible because degrees of $180$° are not allowed. And to prove that the area is an even integer, if there are mini squares protruding from the sides there will have to be even number of those squares in total. And then I also need to make sure that at least the width or length of 'bigger' square or rectangle is even. But I seem to get stuck trying to draw a possible diagram...

$\endgroup$
  • 3
    $\begingroup$ Hint: use the shoelace formula. $\endgroup$ – Théophile Jun 19 '18 at 4:02
  • 1
    $\begingroup$ The appearance of $2016$ makes it sound like this is from a contest two years ago. Source? $\endgroup$ – Jyrki Lahtonen Jun 19 '18 at 4:16
  • 1
    $\begingroup$ Maybe Pick's theorem. Area = i + $\frac{b}{2}$ - 1. The 90 degree turns mean that all the sides can be aligned to be on the grid. $b$ is definitely even as the length of the sides are odd. Not sure how to calculate i. Off to bed now! $\endgroup$ – user625 Jun 19 '18 at 4:21
  • 1
    $\begingroup$ @JyrkiLahtonen Yes, I realize this. If I am not mistaken, the proof is exactly the one given by achillehui, but phrased as a sum rather than appealing to calculus. $\endgroup$ – Théophile Jun 19 '18 at 5:08
  • 1
    $\begingroup$ For example, it is easy to construct examples of polygons with 2012 or 2020 edges, all perpendicular to the adjacent ones, all of odd length, such that the area is also odd. Consider the following comb shape: start with a $1\times (2m+1)$ rectangle, lying horizontally. Add $m$ "teeth", $1\times1$ squares, with 1 unit spacing from the ends. Altogether there will be $4(m+1)$ edges, one of length $2m+1$, the rest of length $1$. The area is $(2m+1)+m=3m+1$. If $m$ is even, then the area is odd, and the number of edges is $\equiv4\pmod8$. $\endgroup$ – Jyrki Lahtonen Jun 19 '18 at 8:04
4
$\begingroup$

Not a complete proof.

However, maybe you can visualize the polygon like this: enter image description here

All the internal angles are either $90^\circ$ or $270^\circ$.


Another way of visualizing: enter image description here

Observe that you have a $12$-sided polygon here, comprised of $5$ squares. The next acceptable polygon would be this: enter image description here Notice that $2$ sides are lost and $6$ more sides are added, thus we have a $16$-sided polygon. Notice too that there are $3$ more additional squares.

Therefore, for a polygon in this form, the number sides can be expressed as: $$12+4x \Rightarrow 12+4x=2016\iff x=501$$ Using $x$, the number of squares that compose this polygon will be: $$5+3x\Rightarrow 12+3\cdot501=1508$$ Therefore, we have an even number of squares therefore the area is an even integer.

$\endgroup$
  • 4
    $\begingroup$ This can get one specific polygon, but we are asked for a proof for all polygons meeting the requirements. $\endgroup$ – Ross Millikan Jun 19 '18 at 3:52
  • 1
    $\begingroup$ @RossMillikan that's why it's not a complete proof, but only to fuel OP's intuition. $\endgroup$ – John Glenn Jun 19 '18 at 3:53
  • 5
    $\begingroup$ I agree that it is essential that the number of sides is divisible by eight, but you are studying an awfully limited class of polygons. To wit, why do you insist on side lengths equal to one unit only? $\endgroup$ – Jyrki Lahtonen Jun 19 '18 at 4:14
  • $\begingroup$ This hints at a viable approach: Proving that every 4m-sided polygon with the specific angle constraints can be reduced to a 4(m-1)-sided polygon with the same constraints and a smaller area, by repeatedly chopping off blocks that point outwards or filling in dents. In every step, the difference is a rectangle with an area that's an odd integer, and the final diamond has an odd integer area. Since 2016 is 8*252, this means the original area must be even. $\endgroup$ – MSalters Jun 19 '18 at 16:47
  • $\begingroup$ @MSalters If you just add a or remove a rectangle with odd sides, you can reduce any $4+2(m)$-sided polygon of that form to a $4+2(m-1)$-sided polygon by picking any vertex ($V1$), following lines ($L1$ and $L2$) from there until their other vertices ($V2$ and $V3$), then extending/retracting the new lines ($L3$ and $L4$) that the $L1$ and $L2$ meet at $V2$ and $V3$ until they intersect at new vertex $V4$. The added or subtracted rectangle will have area $|L1|*|L2|$ (depending on the vertex chosen the newly formed shape may have "negative" area). The rest of your conjecture then holds. $\endgroup$ – Chronocidal Jun 19 '18 at 20:26
18
$\begingroup$

Let $m = 504$ and $p_0, p_1, \ldots, p_{4m-1}$ be the $2016$ vertices of the polygon $\Delta$ ordered in counterclockwise manner. Let $p_{4m} = p_0$ and $(x_k,y_k)$ be the coordinates of $p_k$. WOLOG, we will assume all $x_k, y_k$ are integers and the edges are either horizontal or vertical.

Cyclic reordering if necessary, we will assume $y_0 = \min \{ y_k \}$ and $x_0 = \min \{ x_k : y_k = y_0 \}$.
Shift the origin so that $p_0 = (0,0)$. It is easy to see for all $k$, the parity of coordinates satisfy:

$$p_k = (x_k,y_k) \equiv \begin{cases} (0,0), & k \equiv 0 \pmod 4\\ (1,0), & k \equiv 1 \pmod 4\\ (1,1), & k \equiv 2 \pmod 4\\ (0,1), & k \equiv 3 \pmod 4 \end{cases}$$

Using Green's theorem, we can evaluate the area of $\Delta$ as a line integral over its boundary $\partial \Delta$:

$$\verb/Area/(\Delta) = \int_\Delta dx dy = \int_{\partial \Delta} x dy$$

Since $\partial\Delta$ are a bunch of horizontal or vertical segments, we can convert the last integral to a sum over corresponding edges${}^{\color{blue}{[1]}}$.

We can split the 2016 edges of the polygon into $4$ groups.

  • $p_{4\ell} \to p_{4\ell+1}$ : doesn't contribute because this is a horizontal edge.
  • $p_{4\ell+1} \to p_{4\ell+2}$ : $x$ is constant and an odd number. Since $y_{4\ell+2} - y_{4\ell+1}$ is also odd, this contributes an odd number to area.
  • $p_{4\ell+2} \to p_{4\ell+3}$ : doesn't contribute because this is a horizontal edge.
  • $p_{4\ell+3} \to p_{4\ell+4}$ : $x$ is constant and an even number. Since $y_{4\ell+4} - y_{4\ell+3}$ is an integer, this contributes an even number to the area.

This means in general, we have

$$\int_{p_{k} \to p_{k+1}} xdy \equiv \begin{cases} 1 \pmod 2, & k \equiv 1 \pmod 4\\ 0 \pmod 2, & k \not\equiv 1 \pmod 4 \end{cases}$$ Summing $k$ from $0$ to $4m-1$, we obtain

$$\verb/Area/(\Delta) = \sum_{k=0}^{4m-1} \int_{p_{k} \to p_{k+1}} xdy \equiv m \pmod 2$$

Since $m$ is an even integer, so does the area of original polygon $\Delta$.

Notes

  • $\color{blue}{[1]}$ - For those who don't want to use calculus, one can replace the line integral by following specific form of shoelace formula: $$\verb/Area/(\Delta) = \left|\sum_{k=0}^{4m-1} \frac{x_k + x_{k+1}}{2}(y_{k+1} - y_k)\right|$$ The rest of arguments will be exactly the same.
$\endgroup$
  • $\begingroup$ From your parity observations, one could go straight to the shoelace formula to observe that the contribution of each group of four consecutive vertices makes an even contribution to the area, without regard to the specific value of that contribution or the orientations of the segments. The number of vertices being divisible by 4 then yields the conclusion. $\endgroup$ – John Bollinger Jun 20 '18 at 13:03
  • $\begingroup$ @JohnBollinger each group of 4 vertices give an odd contribution to the area. not even. $\endgroup$ – achille hui Jun 20 '18 at 13:42
  • $\begingroup$ Looking more closely, I see that you are right. But this, too, leads to the conclusion, because there is an even number of groups. $\endgroup$ – John Bollinger Jun 20 '18 at 14:13
3
$\begingroup$

Consider the following structure $A$:

  1. Every axis-parallel rectangle whose side lengths are odd integers is in $A$.

  2. Let $a \in A$ be an arbitrary element and $b \in A$ be an rectangle. The union $a \cup b$ is in $A$ if it satisfies the following properties:

    • The intersection $a \cap b$ is a subset of exactly one side of $a$ and $b$ respectively.
    • The length of the intersection $a \cap b$ is an even integer. (The intersection needs to be a line segment by the first property.)
    • Note: If created in this way $a \cup b$ has:

      • odd area
      • #(sides of $a$) + #(sides of $b$) sides
      • $4n$ sides, where $n$ is the total number of rectangles used in the process of creating $a \cup b$

It is easy to check that this structure contains only polygons with perpendicular adjacent sides where all side lengths are odd.

Now consider a arbitrary polygon with perpendicular adjacent sides where all side lengths are odd. Wlog. assume all sides are axis-parallel (rotate otherwise). We can now slice the polygon into axis-parallel rectangles the following way:

  • "Sweep" the polygon with a line parallel to an axis (e.g. x-axis)
  • Whenever the line contains a side of the polygon, extend that side into the interior of the polygon until you hit another side. Cut the polygon along the extended side into parts (one part is a rectangle).

One can check that after a complete sweep the resulting parts are axis-parallel rectangles whose side lengths are odd integers which can be combined following the procedure of structure $A$. Thus every (axis-parallel) polygon with perpendicular adjacent sides where all side lengths are odd is in $A$.

Thus the given polygon is (after rotating) in $A$ and can be created by $2016/4 = 504$ non-overlapping "base rectangles". Each of those rectangles has odd area. Thus the area of the polygon is the sum of 504 odd numbers which is an even number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.