‌পি‌কের সূত্র

Pick's Theorem

What is Pick's Theorem? Pick's Theorem expresses the area of a polygon, whose vertices are lattice points in the coordinate plane, using the number of lattice points inside and outside of the polygon. In other words, the area of a polygon can be expressed as $$A=I+\dfrac{B}{2}-1,$$ where $I$ is the number of lattice points inside the polygon and $B$ is the number of lattice points lying on the boundary of the polygon. This theorem is similar to the Shoelace Theorem.

Let's try an example:

$\text{Given polygon ABCDEF, find [ABCDEF].}$

Note: The distance between two adjacent points is 1

We count that there are $6$ interior points (colored red) and $6$ boundary points (lettered A to F). Therefore, the area of the polygon is $$A=I+\dfrac{B}{2}-1=6+\dfrac{6}{2}-1=\boxed{8},$$ by Pick's Theorem. We can check our answer by splitting the polygon into easier shapes that we know how to deal with:

We calculate the area of each of the triangles to get $$[ABCDEF]=[ABC]+[GCD]+[AGE]+[AFE]$$ $$=\dfrac{1}{2}\cdot3\cdot1+\dfrac{1}{2}\cdot1\cdot1+\dfrac{1}{2}\cdot2\cdot2+\dfrac{1}{2}\cdot2\sqrt{2}\cdot2\sqrt{2}$$ $$=\dfrac{3}{2}+\dfrac{1}{2}+2+4=8,$$ as desired.

So, as you can see, Pick's Theorem is just a matter of counting dots :)

Pick's Theorem - Proof

Thanks to Kevin for that wonderful introduction! I can't think of any motivation for the conclusion in the theorem except by experimentation, so let's jump to proving it!

Remind me of the statement of Pick's theorem.

For any polygon with all vertices on lattice points, if $I$ represents the number of points inside the polygon and $B$ the number of points on the boundary, then the area of the polygon is $I+\frac{B}{2}-1$.

The area of this figure would be $4+\frac{7}{2}-1$. Let's begin!

What would be a simpler result about polygons?

One thing we can use to inspire something is that if $n$ is the number of vertices of the polygon, then the sum of the interior angles is $180(n-2)$. How did we prove this?

Triangulation?

Can you triangulate a concave polygon?

You can't easily partition a concave polygon into $n-2$ triangles. Can you find 1 triangle, though?

There should always be at least 1 triangle... What method do we want to use?

Induction!

Let's do the same thing with this diagram!

We want to prove Pick's theorem by induction. What's the base case?

A triangle!

What rectangle should we draw, containing $\triangle AEF$?

What do we have to find the area of now?

We must find the areas of $XYZF$, $XAF$, $YAE$, and $ZEF$. What formulas do we use?

We already used the box one. If there's nothing more basic, let's look at what we're trying to prove.

That's it - any triangle isn't the simplest base case. What would be simpler?

A right triangle!

Where does the area formula for a right triangle come from?

A rectangle. And we recall that we still need the area of $XYZF$, so we're going to prove Pick's theorem for a rectangle first.

What are the easiest things to express the area of a rectangle in terms of?

We express it in terms of length and width. If the length were $m$ and width were $n$, what would be the area?

The area would be $mn$. What are we trying to prove again?

We're trying to prove Pick's theorem, that the area is $I+\frac{B}{2}-1$, for a rectangle. How do you express it in terms of $m$ and $n$?

How do you express the number of interior points in terms of $m$ and $n$?

The interior is a grid with length $m-1$ and width $n-1$ and thus there are $(m-1)(n-1)$ interior points. How do you express the number of boundary points in terms of $m$ and $n$?

There are $m+1$ boundary points at the top, $n+1$ boundary points to the right, $m+1$ boundary points to the bottom, and $n+1$ boundary points to the left, but four boundary points that we double-counted for a total of $2m+2n$ boundary points. Or we can shift each unit length to the point nearest to its left for a bijection from $2m+2n$ to the number of boundary points.

What do we get?

$$\begin{align*} I+\frac{B}{2}-1&=(m-1)(n-1)+\frac{2m+2n}{2}-1\\ &=mn-m-n+1+m+n-1\\ &=mn, \end{align*}$$

as desired.

Now what do we want to find?

We want to find the area of a right triangle, such as this one.

What do we need to find its area?

We need its length, which we'll call $m$, and width, which we'll call $n$ (we already proved the result for the rectangle, so we can reuse these variable names).

What is its area?

$\frac{mn}{2}$. What are we trying to show again?

We're trying to show Pick's theorem, that the area is $I+\frac{B}{2}-1$, for right triangles.

How many boundary points are there?

There are $m+1$ to the top, $n+1$ to the left, and - how many on the hypotenuse?

What best describes the hypotenuse?

We're going to use a linear equation. What can we do with it?

Shift it so that it contains $(0,0)$. Where it intersects axes isn't going to make much of a difference, so why not take advantage of it? So what would the equation look like?

What is the value of $\frac{a}{b}$?

$\frac{a}{b}=\frac{n}{m}$. What are the first few possible values of $(x,y)$?

$(x,y)$ can be $(0,0)$, $(b,a)$, $(2b,2a)$, and so on, until $(m,n)$. What are we trying to do?

We're trying to count them. How many are there, with the information we have so far?

There are $\frac{n}{a}+1$ of them. Let's take note that this is also $\frac{m}{b}+1$. What's special about $a,b$? What's different from $n,m$?

$\gcd(a,b)=1$, and $\gcd(n,m)$ is not necessarily 1. What can we do to $n,m$ to get $a,b$?

$a,b$ is basically the same as $n,m$ except for all the divisors are not there. The divisors are taken out. So if we take out all of the divisors, what are $a$ and $b$?

$a=\frac{n}{\gcd(n,m)}$. So how many possible values of $(x,y)$ are there?

There are $\frac{n}{a}+1=\frac{n}{\frac{n}{\gcd(n,m)}}+1=\gcd(n,m)+1$ possible values of $(x,y)$. How do we use this?

We were trying to count the boundary points. How many are there?

Recall that we counted $m+1$ and $n+1$ horizontally and vertically.

There are three points overcounted for a total of $m+1+n+1+\gcd(m,n)+1-3=m+n+\gcd(m,n)$ points on the boundary. What do we do now?

We count the number of interior points. We want our formula to equal the area. But is there anything about greatest common divisor in our formula?

Nope, so we could've set the number of points on the hypotenuse to any variable. Anyways, let's count the number of interior points given the number of lattice points on the hypotenuse.

Is there an clear way using a lonely triangle?

The number of lattice points on the hypotenuse had a number theory form. The hypotenuse is getting annoying. What should we do?

How should we place the new triangle to get rid of the annoying hypotenuse?

Reflectional Symmetry:

Rotational Symmetry:

What can we easily count?

How many lattice points are in the interior?

As with our rectangle from earlier, there are $(m-1)(n-1)$ lattice points.

Can we count the number of points inside each triangle now?

No, or else our work completing the figure would be for nothing.

What can we count?

We can't count the number of points inside each triangle in a straightforward way.

We don't count the points inside each triangle. What do we count?

We have the number of points inside the rectangle, so don't be afraid.

We count the number of points inside the rectangle and not inside each triangle. What can we say about these points?

These are the boundary points, except the endpoints. How many are there?

From earlier, there were $\gcd(m,n)+1$ points on the boundary, and we're not counting the two endpoints.

There are $\gcd(m,n)-1$ points here. What did we want at first?

The number of points inside each triangle.

Can we get there immediately?

No, we need an intermediate step.

What can we get immediately, considering we have $(m-1)(n-1)$ interior points of the rectangle, of which $\gcd(m,n)-1$ are on the boundary and not to be counted?

Since $\gcd(m,n)-1$ of $(m-1)(n-1)$ are not to be counted, we subtract them to get $(m-1)(n-1)-\gcd(m,n)+1$. What is this number?

This is the number of points inside a triangle. So what's the number of points inside each triangle?

By symmetry, there are half of these, or $\frac{(m-1)(n-1)-\gcd(m,n)+1}{2}$ points inside each triangle. What do we do now?

We have everything for our theorem. Now calculate $I+\frac{B}{2}-1$, and recall that we want it to be $\frac{mn}{2}$

$I+\frac{B}{2}-1=\frac{(m-1)(n-1)-\gcd(m,n)+1}{2}+\frac{m+n+\gcd(m,n)}{2}-1=\frac{mn}{2}$. We're finally done with the right triangle case! What case were we using this and the rectangle for?

We were using this for the base case, any triangle.

What did we want to show?

We wanted to show that if $I$ was the number of interior points and $B$ was the number of boundary points, then $I+\frac{B}{2}-1$ was the area. What do we know about the area?

Let's just find the area. What is it?

We can subtract the areas of the triangles from the area of the rectangle. What area forms do we use?

Which forms of areas do we use?

The product of base and height?

That would make up one side of the Pick's theorem equation we want to prove. How do you get the other side?

What is the other side?

The other side is made of interior and boundary points. Is it really worth it, now?

Not for this solution. But there's no harm in trying.

What about our proven cases of Pick's theorem?

Yes! Recall that the formula is $I+\frac{B}{2}-1$ and we have proved it for rectangles and right triangles.

What is the area?

The area is the sum of the number of interior points of $XYZF$, half the number of boundary points of $XYZF$, and -1, minus the sum of the number of interior points of $XAF$, half the number of boundary points of $XAF$, -1, the number of interior points of $YAE$, half the number of boundary points of $YAE$, -1, the number of interior points of $ZEF$, half the number of boundary points of $ZEF$, and -1.

What do you want to do with that expression? Doesn't it bug you?

OMG it is sooo long! How do we simplify it?

Is it a good idea to express it over each rectangle and right triangle? That is, for each rectangle or right triangle, sum the stuff specific to that figure, and then add and subtract based on our expression.

What's our goal?

Our goal is to show that it is equal to $I+\frac{B}{2}-1$ for $I$ and $B$ taken from $\triangle AEF$. There's a better way.

The area is the number of interior points of $XYZF$ minus the number of interior points of $XAF$ minus the number of interior points of $YAE$ minus the number of interior points of $ZEF$ plus half of the following terms having to do with boundary points - the number of boundary points of $XYZF$ minus the number of boundary points of $XAF$ minus the number of boundary points of $YAE$ minus the number of boundary points of $ZEF$ - plus two.

It's still pretty long. What do we do?

Cancel some stuff.

How can we express the number of interior points of $XYZF$ minus the number of interior points of $XAF$ minus the number of interior points of $YAE$ minus the number of interior points of $ZEF$?

What are these such points?

How would you describe these points?

Our goal is to relate them to $\triangle AEF$.

They're in the interior or boundary of $AEF$ besides $A$, $E$, and $F$.

How can we express the number of boundary points of $XYZF$ minus the number of boundary points of $XAF$ minus the number of boundary points of $YAE$ minus the number of boundary points of $ZEF$?

What do you notice about it?

It's negative! What would be easier to count?

We count the number of boundary points of $XAF$ plus the number of boundary points of $YAE$ plus the number of boundary points of $ZEF$ minus the number of boundary points of $XYZF$. What are these points?

How do you describe them?

Try your best to relate them to $\triangle AEF$.

Everything on the boundary of $\triangle AEF$ is counted once.

So what is our area?

Our area is the number of interior or boundary points besides the vertices minus half the number of boundary points plus two.

What do we want to show?

We want to show that this is equal to the number of interior points plus half the number of boundary points minus one.

How do we relate them?

Which one should we deal with?

What can we do first? Which parts can we simplify immediately?

What are we trying to use to prove our theorem?

We're trying to use induction. What case are we working on?

We're working on the base case.

How many vertices?

There are three vertices. What is our expression now?

The area is the number of interior or boundary points minus three minus half the number of boundary points plus two. Simplify this a bit more.

The area is the number of interior or boundary points minus half the number of boundary points minus one.

Simplify this further.

What is simplification often associated with in expressions?

You can combine terms.

Now what does our expression look like?

The area is the number of interior points plus half the number of boundary points minus one.

What do we want to show?

Wait what?

This is the base case of Pick's Theorem. Yay!

What next?

Now we must show the inductive step. What can we use as our inductive step?

If you've done induction, don't think too hard about it. For those who haven't, I'll try to get out something motivating induction sometime soon. It's a powerful technique, so I wouldn't want to miss out on self-discovery.

The base case has three vertices, so...

The inductive step assumes that there are $n$ vertices, and tries to prove that the same result holds for $n+1$ vertices.

What's different about $n+1$ vertices than $n$?

There's an extra one. How can we reduce it to $n$?

We do something with the extra one. What do we do?

Ok, the base case is a triangle...

We take out the triangle with the extra one as a special point.

How should the extra one be special in our triangle?

The extra one should be in between the other two vertices on the polygon.

Which triangle do we choose, though?

We choose one that, when removed, lies outside the rest. Let's just continue assuming that it exists. The proof shouldn't be too different otherwise.

What from earlier can we relate this to, in order to inspire our proof?

We can relate this to how we removed the right triangles from the rectangle. Refer to this if you want. It's just possible inspiration.

Let's set the notation first. How will we refer to everything?

Anything's fine. For below, we'll use the following notation. For any polygon $P$, let $I_P$ be the number of interior points of polygon $P$ and $B_P$ be the number of boundary points of polygon $P$. Sometimes it'll just refer to the set of such points.

What do we want to show?

We want to show that the area of $ABCDEF$ is $I_{ABCDEF}+\frac{B_{ABCDEF}}{2}-1$. What do we have?

What do we want to use?

We want to use our inductive hypothesis. Thus, which form of area should we use?

We already know, by the inductive hypothesis, that the area of $AEF$ is $I_{AEF}+\frac{B_{AEF}}{2}-1$ and that the area of $ABCDE$ is $I_{ABCDE}+\frac{B_{ABCDE}}{2}-1$.

What do we want to show?

We want to show that $I_{AEF}+\frac{B_{AEF}}{2}-1+I_{ABCDE}+\frac{B_{ABCDE}}{2}-1=I_{ABCDEF}+\frac{B_{ABCDEF}}{2}-1$.

How can we simplify $I_{AEF}+\frac{B_{AEF}}{2}-1+I_{ABCDE}+\frac{B_{ABCDE}}{2}-1$?

We combine like terms, like earlier.

What do we have now?

We have $(I_{AEF}+I_{ABCDE})+\frac{B_{AEF}}{2}-1+\frac{B_{ABCDE}}{2}-1$.

What do we have now?

We have $(I_{AEF}+I_{ABCDE})+(\frac{B_{AEF}}{2}+\frac{B_{ABCDE}}{2})-1-1$.

We're forgetting...

We have $(I_{AEF}+I_{ABCDE})+(\frac{B_{AEF}+B_{ABCDE}}{2})-2$.

What is $I_{AEF}+I_{ABCDE}$?

What do we want to relate it to?

We want to relate it to $ABCDEF$.

$I_{AEF}+I_{ABCDE}$ is $I_{ABCDEF}$ except for...

The points on $AE$ except $A$ and $E$ are not counted.

What is $B_{AEF}+B_{ABCDE}$?

$B_{AEF}+B_{ABCDE}$ is $B_{ABCDEF}$ in addition to...

The points on $AE$ are counted twice, except $A$ and $E$ are already counted once each in $B_{ABCDEF}$.

Let's put this together!

The area of $ABCDEF$ is $I_{ABCDEF}$ minus the number of points on $AE$ plus two plus half of the following - $B_{ABCDEF}$ plus twice the number of points on $AE$ minus two - minus two.

Let's simplify this!

The area of $ABCDEF$ is $I_{ABCDEF}$ minus the number of points on $AE$ plus two plus $\frac{B_{ABCDEF}}{2}$ plus the number of points on $AE$ minus one minus two.

The area of $ABCDEF$ is $I_{ABCDEF}+\frac{B_{ABCDEF}}{2}-1$.

Wait what?

That's right, celebration time! We proved Pick's theorem! Now continue exploring expii!

If a polygon is constructed on an equally-distanced point grid, this is when Pick's theorem comes in handy! Pick's theorem provides a formula for evaluating the area of a polygon using two terms:

• i = lattice points located in the INTERIOR

• b = lattice points located on the BOUNDARY

Here is the formula: $$A=i+\frac b2-1$$ Simple, isn't it?

Pick's Theorem

Pick's theorem talks about the area of polygons on square grids like the one below.

A lattice polygon is a polygon whose vertices are on lattice points. For example:

Pick's Theorem says that the area of a lattice polygon is $A=i+\frac{b}{2}-1$ where $i$ is the number of interior points, or points strictly inside the polygon, and $b$ is the number of boundary points, or points on a side of the polygon.

Let's do an example.

Great job! Let's try another one. This time, no colors to help you.

Well done!