Count count count! if you can

Question

How many pentagons are there in the shape below by filling the triangles as shows on the second graph?

For example if this question was asked for the shape below on the left side, the result would be 9!

Answer 1

there are

138 pentagons.

Before putting the code, I will explain the methodology that I have used to solve this. First of all, I have given all triangles the numbers to show you this solution is correct:

As the methodology I have used some steps:

1- I have found all possible polygons by defining neighbour matrices for each triangles as below:

and put this matrices into the code and find all possible polygons which consist of at least 5 triangles since you cannot create a pentagon with less then 5 triangles. (To be honest it does not matter if you consider the polygons with less than 5 triangles anyway.)

To do this, I have checked all possible combination starting with C(19;5) to C(19,19) and check whether if it is polygon or not by using matrices that I have mentioned above.

2- I have put a coordination system to the triangles to define their position and find the number of sides of the polygon. Since they have three directions, 3D coordination system fits very well to find # of sides:

Here is the coordination system, which consists of x,y,z coordinates and every single triangles has coordinates such as, $T_1={1,5,4}$. The rest is as below:

3- So we have unique coordinates for each triangles and and we have all possible polygons. The only part is to find the # of sides of each polygons:

In order to find the sides, I check every single direction for all x,y,z possibilities and see whether if there is a side.

I will give an example how I have done it:

Here is an example where there are 5 triangles. If you check the coordinates, $T_1={1,5,4}$ and $T_4={2,4,4}$ has the same dimension as on $z=4$ direction and there is no other triangle between them even they are not counted as neighbours. so only one side over there and will be counted as one side. Similarly, $T_1$ and $T_2$.

While counting the sides, if there is neighbouring and they are the only common triangles on that direction, I do not count them as sides, such as $z=3$; On that direction, there is only $T_2$ and $T_3$ exist and since there are neighbours, I do not count them.

Lastly, sometimes there are neighbours and non-neighbour triangles on some directions, such as $x=2$; for that kind of situations, I neglected the neighbours and count all non-neighbours as one side.

As a result, all possible polygons which could be counted as pentagon becomes:

138, you may find the results with numbers in the code below to check.

You may check and run the code as you wish: (dont bother with Turkish comments, they are for my own purposes.)

You may also play with number of side check in the code and see how many quadrilateral, octagon etc.

Answer 2

There are exactly:

111 pentagons

in the figure.

How do I know that? Simple, I created a computer program in Java to find out that:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * @author Victor Stafusa
 */
public class Penta {

    private static class Point {
        private final int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        /*public Point add(Point p2) {
            return new Point(x + p2.x, y + p2.y);
        }*/

        public Point sub(Point p2) {
            return new Point(x - p2.x, y - p2.y);
        }

        /*public int dot(Point p2) {
            return x * p2.x + y * p2.y;
        }*/

        /*public double len() {
            return Math.sqrt(x * x + y * y);
        }*/

        public static boolean line(Point p1, Point p2, Point p3) {
            Point pa = p3.sub(p1);
            Point pb = p2.sub(p1);
            int determinant = pa.x * pb.y - pa.y * pb.x;
            return determinant == 0;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object other) {
            if (!(other instanceof Point)) return false;
            Point u = (Point) other;
            return u.x == x && u.y == y;
        }

        @Override
        public String toString() {
            return "[" + x + "," + y + "]";
        }
    }

    private static class Poly {
        private final List<Point> points;

        private Poly(List<Point> points) {
            List<Point> copy = new ArrayList<>(points);
            out: while (true) {
                int s = copy.size();
                for (int i = 0; i < s; i++) {
                    if (Point.line(copy.get(i), copy.get((i + 1) % s), copy.get((i + 2) % s))) {
                        copy.remove((i + 1) % s);
                        continue out;
                    }
                }
                break;
            }
            this.points = copy;
        }

        public static Poly tri1(int x, int y) {
            return create(new Point(x, y), new Point(x + 1, y + 1), new Point(x - 1, y + 1));
        }

        public static Poly tri2(int x, int y) {
            return create(new Point(x, y), new Point(x + 1, y - 1), new Point(x - 1, y - 1));
        }

        public static Poly create(Point... p) {
            return create(Arrays.asList(p));
        }

        public static Poly create(List<Point> p) {
            Poly pp = new Poly(p);
            if (pp.points.size() < 3) return null;
            return pp;
        }

        public static Poly join(Poly a, Poly b) {
            List<Point> d = new ArrayList<>(a.points);
            d.retainAll(b.points);
            if (d.size() < 2) return null;
            Point pa = d.get(0);
            Point pb = d.get(d.size() - 1);
            int c1 = a.points.indexOf(pa);
            int c2 = a.points.indexOf(pb);
            int c3 = b.points.indexOf(pa);
            int c4 = b.points.indexOf(pb);
            List<Point> border1 = new ArrayList<>(10);
            List<Point> border2 = new ArrayList<>(10);
            List<Point> border3 = new ArrayList<>(10);
            List<Point> border4 = new ArrayList<>(10);
            for (int i = c1; i != c2; i = (i + 1) % a.points.size()) {
                border1.add(a.points.get(i));
            }
            border1.add(pb);
            for (int i = c1; i != c2; i = (i + a.points.size() - 1) % a.points.size()) {
                border2.add(a.points.get(i));
            }
            border2.add(pb);
            for (int i = c3; i != c4; i = (i + 1) % b.points.size()) {
                border3.add(b.points.get(i));
            }
            border3.add(pb);
            for (int i = c3; i != c4; i = (i + b.points.size() - 1) % b.points.size()) {
                border4.add(b.points.get(i));
            }
            border4.add(pb);
            List<Point> result = new ArrayList<>(10);
            List<Point> aa, bb;
            if (border1.equals(border3)) {
                aa = border2;
                bb = border4;
            } else if (border2.equals(border3)) {
                aa = border1;
                bb = border4;
            } else if (border1.equals(border4)) {
                aa = border2;
                bb = border3;
            } else if (border2.equals(border4)) {
                aa = border1;
                bb = border3;
            } else {
                return null;
            }
            result.addAll(aa);
            bb.remove(bb.size() - 1);
            bb.remove(0);
            Collections.reverse(bb);
            result.addAll(bb);
            return new Poly(result);
        }

        @Override
        public String toString() {
            return points.toString();
        }
    }

    public static void main(String[] args) {
        Poly[] tris = new Poly[] {
            Poly.tri1(0, 0),
            Poly.tri2(0, 2),
            Poly.tri1(-1, 1),
            Poly.tri2(-1, 3),
            Poly.tri1(1, 1),
            Poly.tri2(1, 3),
            Poly.tri1(-2, 2),
            Poly.tri2(-2, 4),
            Poly.tri1(0, 2),
            Poly.tri2(0, 4),
            Poly.tri1(2, 2),
            Poly.tri2(2, 4),
            Poly.tri1(-1, 3),
            Poly.tri2(-1, 5),
            Poly.tri1(1, 3),
            Poly.tri2(1, 5),
            Poly.tri1(-2, 4),
            Poly.tri1(0, 4),
            Poly.tri1(2, 4)
        };
        int found = 0;
        for (int i = 0; i < (1 << tris.length); i++) {
            List<Poly> polys = new ArrayList<>();
            for (int j = 0; j < tris.length; j++) {
                if (((1 << j) & i) != 0) polys.add(tris[j]);
            }
            back: while (true) {
                for (int d = 0; d < polys.size() - 1; d++) {
                    Poly p1 = polys.get(d);
                    for (int e = d + 1; e < polys.size(); e++) {
                        Poly p2 = polys.get(e);
                        Poly r = Poly.join(p1, p2);
                        if (r != null) {
                            polys.remove(p1);
                            polys.remove(p2);
                            polys.add(r);
                            continue back;
                        }
                    }
                }
                break;
            }
            if (polys.size() != 1) continue;
            Poly single = polys.get(0);
            if (single.points.size() == 5) {
                System.out.println(single);
                found++;
            }
        }
        System.out.println(found);
    }
}

I will describe the program avoiding most of its gory details:

• The class Point declares a point as a pair of coordinates x and y. They are also used to represent 2D vectors. There are a method (a.k.a operation) to do vectorial subtraction and decide if three points are collinear (the line method).

• An older version of this program also featured vectorial addition, the dot product, and the length of the vector for determining collinearity in the Point class, but I removed those because I am not using them anymore. I left them commented-out in the code though. Collinearity is now determined by using vector subtraction and a 2x2 matrix determinant, which is far easier and faster to calculate.

• The class Poly represents a polygon. It features a list of points, in the order that they are defined, either clockwise or counter-clockwise, as long as they are properly ordered.

• In Poly's constructor (the private Poly(List<Point> points) thing), I used a while loop to look at each point triplet to see if they are collinear. If a collinear triplet is found, the middle point is deleted from the vertexes list. When no more collinear triplets are found, the polygon is done. This procedure ensures that larger sides are properly built from smaller ones and that I wouldn't overcount vertexes and consider a quadrilateral or a triangle as if it were a pentagon.

• Poly also features the tri1 and tri2 methods. They produces small triangles pointing upwards (for tri1) or pointing downwards (for tri2). They receive the vertex coordinate of the uppermost (for tri1) or lowermost (for tri2) vertexes and calculate the position of the other two vertexes, producing the triangle.

• Poly also features two versions of the create method, which produces a polygon from a list of vertexes. If the resulting polygon would end having less than 3 vertexes, it is discarded. This ensures that degenerate polygons are not generated.

• The join method is the hardest one in Poly. It produces a new polygon from the union of two smaller polygons:

  • To work with that, first I get the set of shared vertexes.

  • If there are less than two shared vertexes, then there is no result polygon (either they don't touch with zero shared vertexes or they touch only in a single point with one shared vertex). So, I discard those (if (d.size() < 2) return null;).

  • Knowing that the obtained set of vertexes is properly ordered from the sides of one of the polygons, lets call its endpoints as pa and pb. Then, walking from vertex to vertex on both of the polygons and on both directions (clockwise and counter-clockwise) should produce 4 vertex paths. If the polygons are touching in more than a vertex (but not overlapping), then there should be a vertex path from one of the polygons that is the same as a vertex path from another polygon. If there aren't then they are either overlapping or featuring a hole when joined.

  • After knowing what are the two paths that touch, I produce a vertex cycle from the other two paths. I just need to remove the end points of the second path (to avoid repeating vertexes) and reverse its order.

• In the main method, I produce an array (tris) of the 19 small triangles by using the tri1 and tri2 methods.

• Having the 19 triangles, there are $2^{19}$ ways of selecting them, which I brute-force:

  • For every iteration, I create a list of polygons containing those triangles and try to join two of them by brute-forcing each possible pair. When a pair is found, I remove them from the list and add the joined polygon there. The pair brute-force is then started over again until no more polygons could be joined.

  • After no more joinable pairs are found if there is only a single polygon left on the list and it is a pentagon, then the selected set of triangles forms one of our pentagons.

  • For each pentagon found, I print the five vertexes coordinates and increment a counter, showing the counter final value in the very end of the program.

The full output is in the block below.

I couldn't find a way for convincing SE's markdown to spoiler-protect the output
without also destroying the formatting, so I added a bunch of blank lines
and this note before the actual output.

Scroll down to see the actual output.

































[[0,2], [-1,3], [-2,2], [0,0], [2,2]]
[[0,2], [-2,2], [0,0], [2,2], [1,3]]
[[0,2], [2,2], [0,0], [-3,3], [-1,3]]
[[-2,4], [-3,3], [0,0], [2,2], [0,2]]
[[1,3], [-1,3], [-2,2], [0,0], [2,2]]
[[0,2], [1,1], [-1,1], [-3,3], [1,3]]
[[0,2], [2,2], [1,3], [-3,3], [-1,1]]
[[1,3], [-3,3], [-1,1], [1,1], [2,2]]
[[-1,3], [-2,4], [-3,3], [-1,1], [1,3]]
[[0,2], [-1,1], [-2,2], [0,4], [2,2]]
[[0,2], [1,1], [2,2], [0,4], [-2,2]]
[[0,4], [-2,2], [-1,1], [1,1], [2,2]]
[[-1,3], [-3,3], [-1,1], [1,3], [0,4]]
[[-1,3], [-3,3], [-2,2], [2,2], [0,4]]
[[0,0], [2,2], [0,4], [-1,3], [-3,3]]
[[0,2], [-2,2], [0,0], [3,3], [1,3]]
[[0,2], [-1,1], [1,1], [3,3], [-1,3]]
[[0,2], [-2,2], [-1,3], [3,3], [1,1]]
[[3,3], [1,1], [-1,1], [-2,2], [-1,3]]
[[-3,3], [-1,1], [0,2], [2,2], [3,3]]
[[0,2], [-2,2], [-3,3], [3,3], [1,1]]
[[0,0], [3,3], [-1,3], [-2,4], [-3,3]]
[[1,3], [3,3], [2,2], [-2,2], [0,4]]
[[1,3], [0,4], [-1,3], [1,1], [3,3]]
[[0,0], [-2,2], [0,4], [1,3], [3,3]]
[[3,3], [2,4], [0,2], [-2,2], [0,0]]
[[1,3], [-1,3], [1,1], [3,3], [2,4]]
[[0,0], [-3,3], [1,3], [2,4], [3,3]]
[[2,2], [-2,2], [-1,3], [-2,4], [0,4]]
[[0,4], [-2,4], [-3,3], [-1,1], [1,3]]
[[0,4], [2,2], [-2,2], [-3,3], [-2,4]]
[[0,4], [-2,4], [-3,3], [0,0], [2,2]]
[[1,3], [3,3], [1,1], [-2,4], [0,4]]
[[-1,3], [-2,2], [-3,3], [-1,5], [1,3]]
[[2,2], [-2,2], [-1,3], [-2,4], [-1,5]]
[[-1,3], [0,2], [1,3], [-1,5], [-3,3]]
[[2,2], [0,2], [-1,3], [-3,3], [-1,5]]
[[-1,5], [-3,3], [-1,3], [1,1], [2,2]]
[[-1,5], [-3,3], [-2,2], [0,2], [1,3]]
[[-1,1], [0,2], [2,2], [-1,5], [-3,3]]
[[1,1], [2,2], [-1,5], [-3,3], [-1,1]]
[[-1,5], [-2,4], [1,1], [3,3], [1,3]]
[[-3,3], [-1,5], [1,3], [3,3], [0,0]]
[[1,3], [2,2], [-2,2], [0,4], [2,4]]
[[-1,3], [-3,3], [-1,1], [2,4], [0,4]]
[[2,4], [3,3], [2,2], [-2,2], [0,4]]
[[2,4], [0,4], [-1,3], [1,1], [3,3]]
[[0,0], [-2,2], [0,4], [2,4], [3,3]]
[[-1,3], [-2,2], [0,2], [2,4], [-2,4]]
[[1,3], [2,2], [0,2], [-2,4], [2,4]]
[[-1,3], [-3,3], [-2,4], [2,4], [0,2]]
[[2,4], [0,2], [-2,2], [-3,3], [-2,4]]
[[1,3], [3,3], [2,4], [-2,4], [0,2]]
[[2,4], [-2,4], [0,2], [2,2], [3,3]]
[[-2,4], [-3,3], [0,0], [3,3], [2,4]]
[[0,4], [2,4], [1,3], [-3,3], [-1,5]]
[[0,4], [-1,5], [-2,4], [0,2], [2,4]]
[[-1,1], [-3,3], [-1,5], [0,4], [2,4]]
[[3,3], [2,4], [0,4], [-1,5], [-3,3]]
[[1,3], [2,2], [-2,2], [1,5], [2,4]]
[[2,4], [1,5], [-1,3], [-3,3], [-1,1]]
[[1,3], [0,2], [-1,3], [1,5], [3,3]]
[[1,5], [3,3], [1,3], [-1,1], [-2,2]]
[[1,3], [2,2], [3,3], [1,5], [-1,3]]
[[1,5], [-1,3], [0,2], [2,2], [3,3]]
[[-2,2], [0,2], [1,1], [3,3], [1,5]]
[[1,1], [3,3], [1,5], [-2,2], [-1,1]]
[[3,3], [1,5], [-1,3], [-3,3], [0,0]]
[[0,4], [-2,4], [0,2], [2,4], [1,5]]
[[0,4], [-2,4], [-1,3], [3,3], [1,5]]
[[1,1], [3,3], [1,5], [0,4], [-2,4]]
[[1,3], [-3,3], [-2,4], [-3,5], [-1,5]]
[[-1,5], [-3,5], [-1,3], [-2,2], [2,2]]
[[-1,5], [-3,5], [1,1], [3,3], [1,3]]
[[0,4], [2,4], [0,2], [-3,5], [-1,5]]
[[0,4], [1,3], [-3,3], [-1,5], [1,5]]
[[3,3], [-1,3], [0,4], [-1,5], [1,5]]
[[1,5], [2,4], [1,3], [-3,3], [-1,5]]
[[1,5], [-1,5], [-2,4], [0,2], [2,4]]
[[-1,1], [-3,3], [-1,5], [1,5], [2,4]]
[[1,5], [3,3], [-1,3], [-2,4], [-1,5]]
[[1,5], [-1,5], [-2,4], [1,1], [3,3]]
[[-3,3], [-1,5], [1,5], [3,3], [0,0]]
[[-2,4], [-3,3], [-1,3], [1,5], [-3,5]]
[[0,4], [1,3], [-1,3], [-3,5], [1,5]]
[[0,4], [1,5], [-3,5], [0,2], [2,2]]
[[0,4], [2,4], [1,5], [-3,5], [-1,3]]
[[1,5], [-3,5], [-1,3], [1,3], [2,4]]
[[-2,4], [-3,3], [3,3], [1,5], [-3,5]]
[[0,2], [1,3], [3,3], [1,5], [-3,5]]
[[2,2], [3,3], [1,5], [-3,5], [0,2]]
[[1,5], [3,5], [1,3], [2,2], [-2,2]]
[[1,5], [3,5], [-1,1], [-3,3], [-1,3]]
[[2,4], [3,3], [-1,3], [1,5], [3,5]]
[[0,4], [-2,4], [0,2], [3,5], [1,5]]
[[0,4], [-1,3], [1,3], [3,5], [-1,5]]
[[3,5], [-1,5], [0,4], [-2,2], [0,2]]
[[2,4], [3,3], [1,3], [-1,5], [3,5]]
[[0,4], [-2,4], [-1,5], [3,5], [1,3]]
[[3,5], [1,3], [-1,3], [-2,4], [-1,5]]
[[-3,3], [-1,3], [0,2], [3,5], [-1,5]]
[[0,2], [3,5], [-1,5], [-3,3], [-2,2]]
[[-3,3], [3,3], [2,4], [3,5], [-1,5]]
[[-3,5], [-1,3], [0,4], [2,4], [3,5]]
[[0,4], [-2,4], [-3,5], [3,5], [1,3]]
[[-2,4], [-3,3], [1,3], [3,5], [-3,5]]
[[0,2], [-2,2], [-1,3], [-3,5], [3,5]]
[[0,2], [2,2], [1,3], [3,5], [-3,5]]
[[3,5], [-1,1], [-3,3], [-1,3], [-3,5]]
[[3,5], [1,3], [3,3], [1,1], [-3,5]]
[[-1,3], [3,3], [2,4], [3,5], [-3,5]]
111

Note: It is easy to modify this program to count pentagons in different given figures by poking with the tris array (don't need to all be triangles, any non-overlapping non-self-intersecting polygons would do). Also, to count something other than pentagons, it should suffice to poke around the if (single.points.size() == 5). However, this thing grows exponentially in execution time as more polygons are added to the given figure, so it would become intractable quickly.