Lattice Polgyons Part 2

In the previous post, I introduced the idea of a lattice polygon and a method for calculating the area. I want to discuss a very powerful theorem.

Before we can state the theorem, we need to identify two types of points.

  • A boundary point (B) is a point that lies on one of the lines of the lattice polygon
  • An interior point (I) is a point that is contained inside the lattice polygon

In the lattice polygon below the boundary points are in blue and the interior points are in red.

polygon 1

This lattice polygon has B = 11 (blue points) and I = 6 (red points)

The theorem, formulated in 1899 by Georg Pick, states the following:

Area = \frac{1}{2}*B+I-1

Therefore, the theorem states that our previous lattice polygon has an area of:

Area = \frac{1}{2}*11+6-1 = 10.5

You can use the method from the previous post and verify that the area is indeed 10.5. This theorem is cool because you can take any huge and complicated lattice polygon and find the area with a super simple formula. We have no need to resort to cutting up the shape into smaller triangles and rectangles. For example, find the area of the following lattice polygon:

polygon 2

You should find B = 25, I = 10, and area = 21.5. Pretty cool.

Leave a comment

Filed under Uncategorized

Lattice Polygons Part 1

A lattice polygon:

polygon 1

It has straight sides, and each point lies on a lattice (grid). Lattice polygons are really fun because we can practice area calculations without getting messy numbers. For example: consider the following lattice polygon:

polygon 2

Since it is a rectangle, we can use the formula arearectangle = base * height which in this case is 2*3 = 6. We could also have counted the 6 squares inside the shape. Ok, that was too easy; we need to move on to a more complicated shape. How about the following lattice polygon:

polygon 3

If you use the square counting method, then the area is clearly 8. How could we apply our formula to get the same result? The shape is not a rectangle.

If you take a shape and cut it into pieces, those pieces will have the same area as the original shape. Therefore, if we are clever enough with our cuts, we can turn the shape into a bunch of smaller rectangles.

polygon 4

Now we have:

  • a rectangle with base 1 and height 1 (area 1)
  • a rectangle with a base of 3 and a height of 1 (area 3)
  • a rectangle with a base of 2 and a height of 2 (area 4)

Putting that all together, we have the following area: 1 + 3 + 4 = 8

Time to ramp it up a notch. We need one more formula and things will get crazy. The area of a triangle is areatriangle = 1/2 * base * height

Consider the original lattice polygon. Here is how we could split it up:

Polygon 5

We have the following:

  • a triangle of base 3 and height 1 (area 1.5)
  • a triangle of base 1 and height 1 (area 0.5)
  • a triangle of base 2 and height 2 (area 2)

Putting that all together, we have the following area: 1.5 + 0.5 + 2 = 4

One last, massive, lattice polygon:

Polygon 6

Here is one way to split up the giant shape:

Polygon 7

If you do all of the relevant calculations, you will find that the area is 18. Stay tuned for the next post.

Leave a comment

Filed under Uncategorized

M&Ms

I remember a time long ago, elementary school, when the school would hold a contest. There were different varieties of this contest but the basic version went as follows.

Guess the number of M&Ms contained in the jar. The person closest wins the jar!

MMdispenser

The question is simple but to get anything better than a random guess, it’s best if we apply some mathematics.

First, we need to find the volume of container. We will assume that the jar is cylinder. Maybe it is 20 cm tall and 10 cm in radius. Therefore, the volume is calculated using the formula:

V = \pi * r^2 * h = 3.14 * 10^2 * 20 = 6280 cm^3

Now we need to find the volume of each M&M. A quick Google search gives us a volume of 0.636 cm3 for each M&M. Now we divide these two quantities to determine how many M&Ms fit in the container, 6280 / 0.636 = 9874.

However, this answer is too large. The above equation is assuming that the container is completely filled with M&Ms. If you look closely, you will see that there are little gaps between the pieces that are filled with air and not candy. To account for this, we need to take a quick detour.

Consider the following problem, how many of these circles can you fit into this square without overlapping?

 

picture 1

Here is one attempt where I get 6 circles:

picture 2

Here is one where I can get 7 circles:

picture 3

The best packing I can get is 8 circles:

picture 4

In this configuration, the circles take up 73% of the total area. We can use the same concept with the M&Ms. For packing circular objects into a container, the percentage is 64%. This means that we have a total of:

9874 * 64% = 9874 * 0.64 = 6319

There you have it, there should be 6319 M&Ms. Next time you are guessing at the jar, use a little math.

 

1 Comment

Filed under Uncategorized

Handshakes

10 handshakes were exchanged at the end of a party. Assuming that everyone shook hands with everyone else at the party, how many people were at the party?

I saw the above problem posted in set of problems and it caught my interest. My approach was guess and check. I used pictures to help organize my thoughts.

What if there were only 2 people at the party? Naturally, they would only shake hands with each other and only 1 handshake would occur. We can represent this with a picture:

picture 1

For those of you who remember my brainteaser post, this is a graph! The dots represent the people at the party and the line between them represents a handshake.

Ok, let’s try a more interesting party, 3 people. Person 1 and 2 will shake hands, person 1 and 3 will shake hands, and person 2 and 3 will shake hands. Here is a picture:

picture 2

Clearly 3 handshakes take place at this party. The 3 lines represent this fact.

For a party of 4 people the verbiage is going to get complicated. I am going to let the picture do the talking:

picture 3

And 5:

picture 4

Sweet! We found our answer. We need 5 dots to get a total of 10 lines. Or in the language of the problem, we need a party of 5 people to get 10 handshakes. It is amazing to me that the framework of graph theory can have so many applications. This one of the strengths of mathematics; abstract structures can have a multitude of useful applications.

Leave a comment

Filed under Uncategorized

Probability Sums

The other day as I was perusing the MTBoS, I found an interesting problem.

“5 distinct numbers are chosen at random from {1,2,3,4,5,6,7,8,9}.

P(k) = probability their sum = k.

What are some of the ways you can find this in general?

What sum is/are the least likely?

Which sum is/are most likely?”

http://matharguments180.blogspot.ca/2014/10/269-probability-sums.html

At first, I started trying to make different numbers with different sums. For example: choose 2,3,5,6,7 and you get 2+3+5+6+7 = 23.

Then I realized there would be many possible sums. 126 in fact.1

I didn’t really feel like working with all 126 of those different sums so I wrote a quick script in Python to do it for me. Here are the results:

sums table

You can clearly see that 25 is the most likely sum with 12 ways of making 25. For fun, here are all 12 ways of making 25:

[1, 2, 5, 8, 9]
[1, 2, 6, 7, 9]
[1, 3, 4, 8, 9]
[1, 3, 5, 7, 9]
[1, 3, 6, 7, 8]
[1, 4, 5, 6, 9]
[1, 4, 5, 7, 8]
[2, 3, 4, 7, 9]
[2, 3, 5, 6, 9]
[2, 3, 5, 7, 8]
[2, 4, 5, 6, 8]
[3, 4, 5, 6, 7]

 

Also, 15, 16, 34, and 35 are the least likely sums. Since the table is symmetric about 25, this also means that, on average, your sum will be 25. Problem solved.

 

1You have to select 5 numbers from the set of 9 total. This corresponds to the mathematical idea of “choose.” We have 9 choose 5 = 126 possible options

Leave a comment

Filed under Uncategorized

Seats and Grades

I often have ideas for research questions that would be interesting but very impractical. My most recent question was how do seating arrangements affect student grades?

I would allow my students to pick their seat but they would have to stay in the same seat throughout the year. At the end of the year, I would record each student’s final grade in a spreadsheet along with his or her seat choice. After years of data, I could analyze how grades are correlated with seat choice!

Sadly, this idea is at least a few years away. Therefore, in the meantime, I created some fake data to display how this concept could, in theory, play out. Below is a heat map of the grades of a fictitious class. The cells are greener if the mark is higher and redder if the mark is lower:

rand1

My hope would be that out of the randomness, some type of pattern would emerge. Maybe the stereotype is true and the strong students sit at the front while the weak students sit at the back. If I condensed the years of data into a graphic, it might look something like this:

heat map gif

At first, the data seems random, but as the years progress you can clearly see that the higher grades are clustered near the front and the lower grades at the back. Maybe this is true, maybe it’s not, maybe one day I’ll know for sure. Until then.

2 Comments

Filed under Uncategorized

Odd Sums Re-Revisited

In my previous post you may have noticed that I neglected to prove one of the important results. One of my readers requested I post a formal proof. So here it is. Be warned, this is some serious stuff.

Consider the sequence of odd numbers:

1, 3, 5, 7, …

We want to prove:

\displaystyle\sum_{i=1}^{k} a_i \div \displaystyle\sum_{i=k+1}^{2k} a_i = \dfrac{1}{3}

Let’s start with something easier. For any arithmetic sequence:

a1, a2, a3, …, an

The sum of the first n terms is:

S_n = \dfrac{n(a_1+a_n)}{2}

Instead of giving a proof for this lemma, I will elect to show a conceiving example.

How would we add up the numbers 1 to 100?

Write the sum:

S = 1 + 2 + 3 + … + 98 + 99 + 100

Write the sum in reverse:

S = 100 + 99 + 98 + … + 3 + 2 + 1

Add these two sums together:

2S = 101 + 101 + 101 + … + 101 + 101 + 101

Simplify:

2S = 100 * 101

Solve for S:

S = 100 * 101 ÷ 2

So in general:

S_n = \dfrac{n(a_1+a_n)}{2}

Now using this formula we can prove the general result.

\displaystyle\sum_{i=1}^{k} a_i = \dfrac{k(1+(2k-1))}{2} = \dfrac{k(2k)}{2} = k^2

\displaystyle\sum_{i=k+1}^{2k} a_i = \dfrac{k((2k+1) +(4k-1))}{2} = \dfrac{k(6k)}{2} = 3k^2

Hence:

\displaystyle\sum_{i=1}^{k} a_i \div \displaystyle\sum_{i=k+1}^{2k} a_i = \dfrac{k^2}{3k^2} = \dfrac{1}{3}

Leave a comment

Filed under Uncategorized