3
$\begingroup$

Following on from:

How many different non congruent polygons can you make on a 3x3 dot grid?

How many combinations of pentagons can you make on a 4 by 4 dot grid?

Since this is an even $n$ square grid, it is difficult to me to just draw it one by one.

How can I solve this problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$
    – Rubio ♦
    Sep 5, 2017 at 5:03

1 Answer 1

Reset to default
3
$\begingroup$

Partial answer:

We have a 4x4 grid, so we first want to find all possible ways to place 5 vertices in 16 slots, while skipping rotations and reflections. Then for every unique vertex configuration, count the number of pentagons that can be formed.

Finding the non-congruent configurations by hand would be very tedious. We're looking at $C(16,5)$ ways to arrange the vertices, then eliminating all reflections or rotations that have already been counted. Most configurations have 8 rotations and reflections, so expect somewhere around $C(16,5)/8=571$ total. Also, we can skip any configuration with 4 collinear vertices, which cannot form a pentagon.

Iterating by hand would be extremely tedious, so instead I wrote a program to do the work for me. It calculated 549 valid non-congruent configurations.

(For the curious: The program is a brute-force approach in Python. Keep a list to track various 4x4 grids. Iterate through all possible grids with 5 spaces filled in. For each grid, if it has 4 collinear filled spaces, or if any reflections and rotations have already been included in the tracker list, then continue to the next iteration; otherwise add it to the list. Then print and number the grids in the tracker list. It's not elegant but it only takes a few seconds to complete.)

Next, we would check each configuration and count the pentagons that can be formed. There are 12 different ways to connect any 5 vertices (thanks JaapScherpius for the correction), many of which won't result in valid pentagons. So our workload looks like 6588 different arrangements to check!

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ There are 10 pairs of vertices, so 10 possible edges for the pentagon, but that doesn't mean there are 10 arrangements to check as you are not checking each edge individually but checking which selection of 5 edges forms a pentagon. Really there are $5!$ ways to order the 5 vertices, and if cyclic shifts and reversing the order are considered the same we are left with $5!/5/2=12$ distinct orders. So there $12$ possible pentagon shapes to be checked for each set of 5 points. $\endgroup$
    – Jaap Scherphuis
    Aug 26, 2017 at 6:01
  • $\begingroup$ @Mike Q how is it that there's only 10 different ways to connect any 5 vertices? $\endgroup$
    – Sierra Sorongon
    Aug 26, 2017 at 15:49
  • $\begingroup$ @Mike Q can you paste the program you wrote??? If ever😂😂😂 $\endgroup$
    – Sierra Sorongon
    Aug 26, 2017 at 16:03
  • $\begingroup$ @JaapScherphuis Whoops, you're right. I updated my answer with the correction. $\endgroup$
    – MikeQ
    Aug 26, 2017 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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