4

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.

Jesse
  • 235
  • 1
  • 10
Alex
  • 8,566
  • 20
  • 61
  • 2
    Are we restricted to regular polygons? – A. P. Jan 11 '18 at 18:01
  • @A.P. Yes thanks I will add it to the question – Alex Jan 11 '18 at 18:09
  • 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)? – DqwertyC Jan 11 '18 at 18:17
  • @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. – Alex Jan 11 '18 at 18:31
  • This seems like a good one potentially for math.stackexchange as well given the nature of the puzzle. – Sean Henderson Jan 11 '18 at 18:38
  • Must all polygon sides be touching either completely or not at all? If not, and we have part (but not all) of a polygon's side touching another polygon, does that count the same as if the entirety of its side is touching? Does it count fractionally? Does it not count at all? – Michael Seifert Jan 11 '18 at 19:12
  • @SeanHenderson I'm totally fine to move this if it fits math.SE – Alex Jan 11 '18 at 20:08
  • @MichaelSeifert for simplicity let's assume it has to be completely touched. I will add it to the question. – Alex Jan 11 '18 at 20:09
  • What do you mean by "one of each kind"? That would already be an unlimited number (triangle to 10000000-gon) and never fit the board. – Thomas Weller Jan 11 '18 at 21:46
  • @ThomasWeller Yes that's the intention, but you'll never able to fit all of them into the board - so it's the max number that you can fit following the rules – Alex Jan 11 '18 at 23:30
  • 1
    Ok, I got it. You don't want to fill the whole area. – Thomas Weller Jan 11 '18 at 23:36
  • The constraint that you limit the number of edges touching is not too good. In a mathematical sense, you can place it arbitrary close, but still not touching. I think leaving out this constraint wouldn't make the puzzle much easier. – Simon Marynissen Jan 17 '18 at 14:56
  • @SimonMarynissen thanks! I'm not sure how to improve in terms of 'arbitrary close but not touching'. Like we can argue that nothing in this world touches other things in the atom level. But i'm not going against your ideas thou - while leaving it out will make it less interesting (i.e. biggest polygon that can fit placed in middle, and filling holes), I'm thinking of another ways – Alex Jan 17 '18 at 16:02

1 Answers1

8

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.

hexomino
  • 135,910
  • 10
  • 384
  • 563
  • 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 %$. – Carl Löndahl Mar 05 '18 at 20:14
  • 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! – Alex Mar 06 '18 at 15:14