Official

A - Dodecagon Editorial by rng58_admin


Suppose that we have a dodecagon-shaped box (with side lengths \(d\)), and let’s count the number of ways to fill it with tiles.

Consider a vertex of the polygon (the box). Since the angle is \(150\) degrees, we must use a triangle and a square to cover the vertex. There are two ways to do that, and once we decide which way to go, we can determine the positions of some more tiles uniquely. After that, the shape of the remaining region will be as follows: again a dodecagon, all inner angles are \(150\) degrees too, but the side lengths are \(d, d-1, d, d-1, d, d-1, d, d-1, d, d-1, d, d-1\).

Let \(f(a, b)\) be the number of ways to fill a dodecagon-shaped box with side lengths \(a, b, a, b, \ldots\). By a similar observation, we get \(f(a, b) = f(a-1, b) + f(a, b-1)\). Therefore, \(f(a, b) = \binom{a+b}{a}\).

Don’t forget to divide the answer by two because of rotations. The answer is \(\frac{1}{2} \binom{2d}{d}\).

posted:
last update: