What! Triangles made that Rectangle?

Probability Level 5

A rectangle has corners at the points (0,0), (5,0), (5,1), and (0,1). How many ways can it be tiled with triangles of area 1/2 and with vertices on lattice points?

This problem was adapted from one from the 2014 ARML competition.


The answer is 252.

Anonymous Anonymous by Anonymous Anonymous , 25, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Notice that any triangle that is part of the tiling of the rectangle has one line segment on either the top or bottom side of the rectangle, and a vertex on the opposite side as the line segment. Thus we can express any tiling of the rectangle as a string of bottom-top line segments, as look at the rectangle from left to right. Since there are exactly 10 triangles that must be used to tile the rectangle, and 5 of which must be on each of the bottom and top of the rectangle, there are exactly 10 choose 5 ways of ordering the top and bottom triangles, and thus exactly 10 choose 5 ways to tile the rectangle.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Robert, aren't some of your orderings forbidden? For example, how can you draw the tiling bbbbbttttt?

I think I agree with Evan. Each unit square has two possible ways in which it can be tiled, and the tiling configuration of each unit square is independent from all other unit squares. There are 5 unit squares, so there are 2^5 = 32 possible tilings.

Edmund Berry - 6 years, 3 months ago

Can someone tell me why it's not something like 2 5 = 32 2^5=32 ? Since for each unit square, there are only two ways to arrange the pair of triangle.

Evan Lee - 6 years, 3 months ago

Log in to reply

I was confused by this, too. Consider the triangle with vertices at (0,1), (1,0), and (2,0). This triangle has an area of 1/2, and its vertices are lattice points. If you consider triangles like this one, then it becomes clear that there are many more possibilities than 32.

Andy Hayes - 6 years, 3 months ago

Explaining the second part a bit more: if we select 5 vertices (with repetiton) from the top line, then there is exactly 1 way to construct the bottom triangles so that they have those 5 vertices as apexes; and this leaves exactly 1 way to complete the construction of the top triangles. So there is a bijection between the number of tilings and the number of ways of selecting the 5 vertices. The latter can be viewed as stars-and-bars, where the 5 stars are the apex of a bottom triangle, and the 5 bars are the base of a top triangle.

Matt McNabb - 6 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...