Darn centigons

Let P P be a regular centigon (100 sided shape) of side length 1. We draw lines in P P and dissect it completely into a number of rhombuses such that all have side length 1, and any pair of the rhombuses are either disjoint, or share only a vertex, or share a whole side.

How many points are the vertices of all the rhombuses in the resulting diagram?

Bonus: Generalize this for a polygon with 2 n 2n sides.


The answer is 1276.

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

Julian Poon
Dec 12, 2016

Disclaimer: Solution not completed. Claimer (?): Sharky's solution is at the bottom. His solution is completed and very short.


We start by finding a way to dissect a 2n-gon in hope of inspiration.

Here's a way (Note: this is not the only way. There are at least 2 ways of arranging the rhombi such that it forms the 2n-gon, if n>3)

This is obtained by taking a 2n-gon, duplicating it and rotating it about a vertex at angle 2 π n \frac{2\pi}{n} , repeating until you come back to the original 2n-gon:

It is easy to prove that all the shapes are rhombi by noticing that the opposite edges of each shape is parallel.


Now we need to prove that in every possible dissection of a 2n-gon, the number of rhombi in the dissection remains the same. This is needed since the number of points that are vertices of at least one of the rhombuses can be expressed as:

P = N ( 360 ) 180 ( 2 n 2 ) 360 + 2 n P=\frac{N\left(360\right)-180\left(2n-2\right)}{360}+2n

Where N N is the number of rhombi. Hence, for the solution to be unique, there has to be a unique number of rhombi.

To do so, we use this approach: The area sum of all the rhombi is equal to the area of the 2n-gon.


Lemma 1: All rhombi in the dissection have sides that are parallel to 2 sides of the 2n-gon.

Proof: (idk how to improve on phrasing here) Consider a rhombus which shares a side with the 2n-gon. This rhombus would have 2 sides parallel to the side of the 2n-gon. Another rhombus which shares the parallel side with the first rhombus would also have 2 sides that are parallel. A third rhombus that shares the parallel side with the second rhombus would also have 2 sides that are parallel. Using this logic, we can start from any rhombus inside the 2n-gon and go outwards until we reach a side.


Using lemma 1, we can see that there exists a maximum of n 2 \left\lfloor \frac { n }{ 2 } \right\rfloor types of rhombi in a dissection of a 2n-gon. For instance, a 6-gon dissection would have 3 congruent rhombi (1 type). A 8-gon dissection would have 2 squares and 4 rhombus (2 types). Let the types of rhombi for a 2n-gon dissection be T 2 n , 1 , T 2 n , 2 . . . T 2 n , n 2 T_{2n,1}, T_{2n,2}...T_{2n,\left\lfloor \frac { n }{ 2 } \right\rfloor} , where the area of T 2 n , j T_{2n,j} is more than T 2 n , j 1 T_{2n,j-1} . It can be found through some trigonometry that:

A ( T 2 n , j ) = sin ( π n j ) A(T_{2n,j}) = \sin \left(\frac{\pi }{n}\cdot j\right)

Where A ( T ) A(T) denotes the area of T T .

Now, suppose a dissection of a 2n-gon would consist of a j a_j number of T 2 n , j T_{2n,j} , where a j a_j is a non-negative integer, then since the area of the 2n-gon is 1 2 n cot ( π 2 n ) \displaystyle \frac{1}{2}n\cot \left(\frac{\pi }{2n}\right)

1 2 n cot ( π 2 n ) = j = 1 n 2 a j sin ( π n j ) \frac{1}{2}n\cot \left(\frac{\pi }{2n}\right)=\sum _{j=1}^{\lfloor\frac{n}{2}\rfloor}a_j\sin \left(\frac{\pi }{n}\cdot j\right)

According to the solution that is found above,

a j = { n { mod ( 2 n , 4 ) = 2 } { n 2 j = n 2 n o . w { mod ( 2 n , 4 ) = 0 } a_{ j }=\begin{cases} { n }\quad \left\{ \operatorname{mod}\left( 2n,4 \right) =2 \right\} \\ \begin{cases} \frac { n }{ 2 } \quad j=\frac { n }{ 2 } \\ n\quad o.w \end{cases}\left\{ \operatorname{mod}\left( 2n,4 \right) =0 \right\} \end{cases}

Now we need to prove that this is the only possible sequence of a j a_j

Assume that there is another possible sequence, then there exists a sequence of integers b j b_j such that

j = 1 n 2 b j sin ( π n j ) = 0 \sum _{j=1}^{\lfloor\frac{n}{2}\rfloor}b_j\sin \left(\frac{\pi }{n}\cdot j\right)=0

Now this is where the proof is incomplete. I am unable to prove that b j b_j doesn't exist. But after fiddling around a little, I'm confident that such a sequence is impossible.


Side note: I had a lot of difficulty phrasing this solution, so the solution might seen unclear. Feel free to ask questions


Now that you have read (or haven't) my humongous (and uncompleted) solution, graze thy eyes on the superior

Sharky’s Solution \LARGE\textbf{Sharky's Solution}

Following from Lemma 1 from my solution (yay part of my solution is usable), in a dissection, there exists a path from one edge of the 2n-gon to its opposite edge composed of rhombi with 2 of their sides parallel to the side of the 2n-gon:

Consider 2 paths coming from 2 non-parallel sides of the 2n-gon. Via Intermediate Value Theorem, these 2 paths would intersect at at least 1 rhombus.

Now we proof via contradiction that 2 paths would not intersect at more than 1 rhombi.

Assume that 2 paths intersect at more than 1 rhombi. Then there will be more than 1 congruent rhombi with the same orientation. Now, consider 1 of the path that would contain these rhombi:

Now we try to fit in the second path that would contain these rhombi. Since the second path would have to thread through the middle curvy bit, we can conclude, that all these rhombi the 2 paths contain would be together.

Now, consider the rhombi in the middle of the red bit (the "..." region). These rhombi must have a path leading to an edge as well right? (via lemma 1). Since there is only 2 edges of a regular 2n-gon that is parallel, that means that several paths must converge into a single path. This is impossible (since a rhombus only has 2 sets of parallel edges). Hence we conclude that 2 paths must intersect at exactly 1 rhombus.

This makes counting the rhombus much easier! Since every rhombus must have 2 paths that leads it to an edge (lemma 1), that means that if we consider the intersection of every 2 possible paths, their intersections would make up all the rhombi in the dissection. Every 2 paths intersect at 1 rhombus, and there are n n different paths. Hence, the number of rhombi equates to n ( n 1 ) 2 \frac{n(n-1)}{2} . Plugging that into the equation given in my solution, and having n=50:

P = n ( n 1 ) 2 ( 360 ) 180 ( 2 n 2 ) 360 + 2 n P=\frac{\frac{n(n-1)}{2}\left(360\right)-180\left(2n-2\right)}{360}+2n

We get the answer


Additional: Sharky's solution also proves that there exists a unique sequence a j a_j , and consequently, no such sequence b j b_j . So my solution wasn't a complete waste. Maybe I'll post a problem on it.

Nice problem! I'd suggest clarifying how you arrived at the formula for P P as a function of N N and n n , unless it's a well-known geometric formula of which I'm unaware (which wouldn't surprise me!). I've been studying it for a while and I believe I understand the derivation: Let I I be the number of points inside the 2 n 2n -gon. The interior angle sum of the 2 n 2n -gon ( 180 ( 2 n 2 ) 180(2n - 2) ) plus one revolution per interior point ( 360 I 360I ) equals the total interior angle sum of all the rhombuses ( 360 N 360N ). Solving for I I gives the first term in the formula, and the number of exterior points is clearly the number of vertices of the polygon, or 2 n 2n , so P = interior + exterior = I + 2 n P = \text{interior + exterior} = I + 2n . An explanation along these lines would clarify things a lot, especially why proving uniqueness of N N is sufficient to make P P unique. By the way, since N = n ( n 1 ) / 2 N = n(n - 1)/2 , P P simplifies to n ( n + 1 ) / 2 + 1 n(n + 1)/2 + 1 , which makes it much easier to answer the question for a particular n n .

William Allbritain - 4 years, 6 months ago

My solution involves trying to prove the number of rhombuses is ( n 2 ) \dbinom{n}{2} and the number of edges is n 2 n^2 . From here, we can apply Euler's formula to get the number of vertices. Have you tried looking at the problem from this aspect?

Sharky Kesa - 4 years, 6 months ago

Log in to reply

This problem is mainly trying to find the number of rhombi, what is your approach in doing so?

Julian Poon - 4 years, 6 months ago

Log in to reply

I proved that if you consider path passing through the sides parallel to each other, these paths intersect with each other exactly once (proof using Intermediate Value Theorem). From here, it's just counting.

Sharky Kesa - 4 years, 6 months ago

Log in to reply

@Sharky Kesa That's genius! Why didn't I think of that?

Julian Poon - 4 years, 6 months ago

Log in to reply

@Julian Poon You can update your solution to include this if you want. Also, instead of writing floor ( x ) \text{floor}(x) , write \lfloor x \rfloor (using latex brackets of course).

Sharky Kesa - 4 years, 6 months ago

Log in to reply

@Sharky Kesa Oh, I was already at it :P

Julian Poon - 4 years, 6 months ago

@Sharky Kesa By the way, how did you get the inspiration for this problem?

Julian Poon - 4 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...