{"id":148,"date":"2016-05-09T01:29:39","date_gmt":"2016-05-09T01:29:39","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=148"},"modified":"2016-05-30T08:57:34","modified_gmt":"2016-05-30T08:57:34","slug":"counting-parallelograms","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/counting-parallelograms\/","title":{"rendered":"Counting parallelograms"},"content":{"rendered":"

The following problem appeared in the 1991 CMO<\/a>, and it has a particularly clever solution.<\/p>\n

In the figure, the side length of the large equilateral triangle is $3$ and $f(3)$, the number of parallelograms bounded by sides in the grid, is $15$. For the general analogous situation, find a formula for $f(n)$, the number of parallelograms, for a triangle of side length $n$.<\/p>\n

\"triangle_lattice\"<\/p>\n

[Show Solution]<\/a><\/p>\n

\n

The edges of any parallelogram will be parallel to two of the three sides of the big equilateral triangle. Let’s start by counting the parallelograms whose edges are not<\/em> parallel to the horizontal (bottom) edge. Extend the bottom edge of the big triangle by $1$ (see figure below), and also extend the parallel edges of the parallelogram down until they intersect the new edge. This will create four points (indicated in red on the figure).<\/p>\n

\"triangle<\/p>\n

The key observation is that each different parallelogram maps to four distinct vertices on the bottom edge and conversely, any set of four distinct vertices along the bottom edge maps to a single parallelogram of interest. It’s a one-to-one mapping! So the number of different parallelograms is precisely the number of different ways of choosing four points on the bottom edge.<\/p>\n

If the original triangle has side-length $n$, the extended bottom edge has $n+2$ vertices. So there are ${n+2}\\choose{4}$ ways of choosing the four points. We must multiply our final answer by $3$ to account for the three different possible parallelogram orientations. The final result is that:<\/p>\n

$\\displaystyle f(n) = 3{{n+2}\\choose{4}}$<\/span><\/p>\n

We can check that $f(3) = 15$ as expected.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

The following problem appeared in the 1991 CMO, and it has a particularly clever solution. In the figure, the side length of the large equilateral triangle is $3$ and $f(3)$, the number of parallelograms bounded by sides in the grid, is $15$. For the general analogous situation, find a formula for $f(n)$, the number of … Continue reading “Counting parallelograms”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[13],"tags":[6],"class_list":["post-148","post","type-post","status-publish","format-standard","hentry","category-competition","tag-counting"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/148","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=148"}],"version-history":[{"count":14,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/148\/revisions"}],"predecessor-version":[{"id":261,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/148\/revisions\/261"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=148"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=148"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=148"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}