## A recipe for finding pentagons

There's the old formula for planar graphs, regions+points = edges+2. That is,

```  r+p = l+2
```

Let s be the average number of sides per region, then

```  r+p = (rs/2)   + 2
p = (rs/2)-r + 2
p/r = (s-2)/2  + 2/r  (2/r goes to zero as r goes to infinity)
```
which tells you how many angles are filled in by the average tile. If a corner has n tiles touching it, each touching tile is credited 1/n of a corner. The total credits for a tile is the sum of the reciprocals of the number of tiles meeting at each of its corners.

Planar pentagons have p/r of 1.5. Four tiles per corner would yield 5/4, that's hyperbolic. Three yields 5/3, that's elliptical.

Suppose a single pentagon tiles the plane. p/r must be 1.5 over the whole plane, although individual uses of the pentagon may appear hyperbolic or elliptical. Since the hyperbolics must be cancelled out by ellipticals, any single pentagon that tiles the plane has planar or elliptical uses, that is, p/r >= 1.5. And the arrangement of corners for planar or elliptical uses of pentagons can be enumerated, namely:

```  1/2 + 1/2 + 1/2 + 1/n  + 1/n
1/2 + 1/2 + 1/3 + 1/3..6 + 1/n
1/2 + 1/2 + 1/3 + 1/7  + 1/7..42
1/2 + 1/2 + 1/3 + 1/8  + 1/8..24
1/2 + 1/2 + 1/3 + 1/9  + 1/9..18
1/2 + 1/2 + 1/3 + 1/10 + 1/10..15
1/2 + 1/2 + 1/3 + 1/11 + 1/10..13
1/2 + 1/2 + 1/3 + 1/12 + 1/12
1/2 + 1/2 + 1/4 + 1/4  + 1/n
1/2 + 1/2 + 1/4 + 1/5  + 1/5..20
1/2 + 1/2 + 1/4 + 1/6  + 1/6..12
1/2 + 1/2 + 1/4 + 1/7  + 1/7..9
1/2 + 1/2 + 1/4 + 1/8  + 1/8
1/2 + 1/2 + 1/5 + 1/5  + 1/5..10
1/2 + 1/2 + 1/5 + 1/6  + 1/6..7
1/2 + 1/2 + 1/6 + 1/6  + 1/6
1/2 + 1/3 + 1/3 + 1/3  + 1/n
1/2 + 1/3 + 1/3 + 1/4  + 1/4..12
1/2 + 1/3 + 1/3 + 1/5  + 1/5..7
1/2 + 1/3 + 1/3 + 1/6  + 1/6
1/2 + 1/3 + 1/4 + 1/4  + 1/4..6
1/2 + 1/4 + 1/4 + 1/4  + 1/4
1/3 + 1/3 + 1/3 + 1/3  + 1/3..6
1/3 + 1/3 + 1/3 + 1/4  + 1/4
```
The last set of numbers means 3 corners with 3 tiles per corner, 2 corners with 4 tiles per corner.

I have a handwaving proof that there always exists a tile with no more than 15 tiles meeting at any corner. It runs like this: Assume every tile has a corner with at least n tiles meeting at it. The case with 2 corners per tile having more than 12 tiles apiece is easy to rule out. The remaining case has 1 corner per tile with more than n tiles apiece. Group tiles into pinwheels around those corners. These pinwheels must tile the plane, so they must have at most 6 (ragged) edges. If there is only 1 edge per tile on the outside of the pinwheel, each ragged edge has only 1 real edge, so n <= 6. There are at least 2 edges per tile on the interior of the pinwheel, leaving at most 3 edges on the border per tile. Pinwheel ragged edges have to fit together: if one ragged edge is convex, the other must be concave. If tiles are placed symmetrically around the pinwheel, all pinwheel corners will be convex, so n <= 6. If every other tile has a different corner in the interior of the pinwheel, the exterior could alternate (convex, concave, convex), allowing n <= 12. There are examples of this. If there are three or more different corners which are used in the interior of the pinwheel, well, the convex hull of the tile has at most 2 corners of less than 60 degrees. So corners other than those first 2 can be used at most 5 times. A tile using such a corner, along with tiles using the other two corners on either side, can form a flat or concave pinwheel edge, allowing n <= 15.

Next, label each corner, and place one pentagon on the plane. Choose a formula above, that tells you how many tiles meet at each corner. Each of those tiles is just like this one, so any of its 5 corners could meet the central pentagon's corner. Now you've got one pentagon surrounded by other pentagons, with all the corners of all the pentagons labelled.

You know each corner sums to 360 degrees. You've got 5 corners. You also know that all the corners together sum to 540 degrees. That means you have 5 unknowns (the angles) and 6 equations. For every possible combination, solve. Discard contradictory solutions, or solutions with angles >360 or <0.

The solutions I have found so far were found by doing exactly that, assuming that all sides were equal length. I've found all such solutions. You can't have more than 12 tiles meeting in a corner if all sides are equal (because (2*asin(1/4))*13 > 360).

There are two cases I haven't handled yet:

1. Not all sides are the same length.
2. The system of equations is linearly dependent, that is, there are four or fewer independent equations.

Case (1) is a solvable set of equations if the angles are fixed. It helps that at least two sides are always equal. Case (2) is a problem for linear programming. When I get the motivation, or the inspiration for a simpler solution, I'll find all the remaining pentagons. Chances are the remaining solutions aren't as interesting -- the increased internal flexibility comes from a reduced flexibility in tilings.

There's the issue of using a single tile, or using a single tile and its mirror image. Although I've only been looking for single tiles, the ideas above can let you exhaustively enumerate either. There's also the question of allowing corners to meet along the edge of some other tile. I was assuming all tiles have corners wherever any tile has corners; I allow corners with angles of 180 degrees.

The files sort.c and distinct.c also help a lot.