4
$\begingroup$

Comes up with this puzzle idea while watching the little kids play. Warning first of all - I don't have an answer for it so it might be a joint effort to find out the best answer. Here we go:

Materials:

1) a 50 cm x 50 cm board
2) Regular Polygons starting from triangle with only 1 of each kind (1 square, 1 pentagon, etc) and no circle. All sides of each polygon are 1 cm long.

You're to fit the max number of polygons onto this board. Here are the rules:

1) You cannot place any polygon outside the edge of the board.
2) All polygons are placed flat (i.e. you cannot 'standing up a triangle to save spaces) and cannot overlaps.
3) Each polygon can only have number_of_side - 2 side(s) touching other polygon. I.e. a triangle can only have 1 side touching other polygon while a octagon can have 6.
4) For simplicity purpose, we can ignore spaces between 2 edges (If we put two '1cm x 1cm square' side by side for an example, it results in 2 cm long rectangle)
5) Again for simplicity purpose (which is a good candidate for next level), any touches between 2 sides will be counted as one touch:

enter image description here

Corners touching corners / side won't be counted.

Suggestions to refine the question are welcome.

$\endgroup$
  • 2
    $\begingroup$ Are we restricted to regular polygons? $\endgroup$ – A. P. Jan 11 '18 at 18:01
  • $\begingroup$ @A.P. Yes thanks I will add it to the question $\endgroup$ – Alex Jan 11 '18 at 18:09
  • $\begingroup$ Are we required to use each shape in order, or could we skip one and come back to it later? (i.e. does the square have to touch the triangle, or could we put the pentagon down first and connect the square to that)? $\endgroup$ – DqwertyC Jan 11 '18 at 18:17
  • $\begingroup$ @DqwertyC I had that in my mind before but decided not to make it a rule - so it does not have to be in order. A triangle can be attached to say a octagon. $\endgroup$ – Alex Jan 11 '18 at 18:31
  • 1
    $\begingroup$ Ok, I got it. You don't want to fill the whole area. $\endgroup$ – Thomas Weller Jan 11 '18 at 23:36
8
$\begingroup$

Let $N$ be the maximum number of polygons that can be so placed.
It can be proven that

$39 \le N \le 43$

Proof of upper bound

The area of the regular $n$-sided polygon of side length 1cm is given by $$A = \frac{n}{4} \cot \left( \frac{\pi}{n} \right) \,\text{cm}^2.$$
Hence, the combined area of the smallest $44$ distinct regular polygons, each of side 1cm, is $$ \sum_{n=3}^{46} \frac{n}{4} \cot \left( \frac{\pi}{n} \right) \approx 2654.736 \,\text{cm}^2. $$ This is larger than the size of the board ($2500 \,\text{cm}^2$) so we will never be able to fit $44$ regular polygons. On the other hand, $$ \sum_{n=3}^{45} \frac{n}{4} \cot \left( \frac{\pi}{n} \right) \approx 2486.612 \,\text{cm}^2. $$ so it is, in theory at least, still possible to fit $43$ regular polygons and this is our upper bound.

Proof of lower bound

The lower bound is a bit trickier but we can simplify the problem a bit by realising that the larger a regular polygon becomes, the more circular it appears. Also, the larger polygons will have more of an influence on the overall packing than the smaller ones.

With that in mind, we can instead consider a different and more well-known problem - that of packing circles in a square. In this case, we aim to pack the circumcircles of the polygons. Each polygon has circumradius $\frac{1}{2 \sin \left( \frac{\pi}{n}\right)}$ cm. Any solution of this new problem automatically gives a solution to the original.

The nice thing is that such problems are well-researched and there is software available to try and determine an optimal packing. In particular, we can feed in a set of circles and ask for the smallest square in which such circles can be packed.

The smallest $39$ regular polygon circumcircles fit into a square of side $49.23$ cm in the following way:
enter image description here
The program used does not always find the best global solution so I do not yet know if this can be bettered (I have run it several times with $40$ polygons but not yet managed a fit).

Further notes

I strongly suspect that the answer is $39$ as this yields a packing ratio of around $0.754$ which is in the vicinity of what one would expect for the corresponding problem with circles. The case of $40$ polygons yields a packing ratio of $0.81$ which seems too high. I'll keep trying to get this for a while and, if achieved, I'll update the answer.

$\endgroup$
  • $\begingroup$ Great answer! Given that the smallest polygons are farthest away from the circle approximation (i.e., triangle, square...), the error you are introducing becomes really small, about $0.93 \%$. $\endgroup$ – Carl Löndahl Mar 5 '18 at 20:14
  • $\begingroup$ The answer turns out is a little different than what I would imagine - more sophisticated but at the same time easy to understand. Great answer! $\endgroup$ – Alex Mar 6 '18 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.