9
$\begingroup$

There is a $3\times3$ dot grid. How many different non-congruent polygons can you make on the grid?

Rules:

  1. All vertices of the polygon must be on the grid
  2. Only non self intersecting polygons
  3. Only polygons with non-empty interior (<=> positive area)
|improve this question
$\endgroup$
  • $\begingroup$ "Non-congruent" means they can't overlap? $\endgroup$ – A E Mar 19 '15 at 15:15
  • $\begingroup$ Clarification request: If I understand congruency correctly, that means you can only count the 1x1 square once. If a shape can be rotated or reflected to match another shape you've already made regardless of any translation required, then it's not allowed. Is that correct? $\endgroup$ – Engineer Toast May 7 '15 at 12:42
  • $\begingroup$ @EngineerToast It is correct. $\endgroup$ – moti May 10 '15 at 11:18
6
$\begingroup$

Working up from a 2x2 grid.

2x2

We can make a square and a triangle. All triangles at this scale are congruent.

14  1-
23  23

Answer: 2

2x3

We can make everything we had before, plus we can make a few new triangles. And a large rectangle. And a quadrilateral, and a parallelogram.

13-  1-3  1-3
--2  2--  -2-

14-  14-  (1-4 flip of 1st)  1-4  (1-4 flip of 1st)
2-3  -23  (23-            )  2-3  (-23            )

Answer: 6

3x3

Here is where it gets crazy.

For triangles, you can make a few more. But some are congruent to the small version. Since we've already accounted for all the 2x3 triangles, we only need to consider points on the edges that necessitate all three rows/columns.

13-  (1-3                   )  1-3  1--
---  (--- congruent to small)  ---  --3
--2  (2--                   )  -2-  -2-

Triangles: 3

Squares and rectangles have nothing new that isn't the same as or congruent to what we had before. Generic quadrilateral, however, is a different matter.

   xx-     14-
1  x-- --> 2--
   --x     --3

   xx-
2  -x- --> none
   --x

   xx-     14-
3  --x --> --3
   x--     2--

   xx-     14-
4  --x --> --3
   -x-     -2-

   xx-     14-
5  --x --> --3
   --x     --2

   xx-     14-
6  --- --> ---
   x-x     2-3

   xx-     14-
7  --- --> ---
   -xx     -23

   x-x
8  x-- --> same as 3rd row
   -x-

   x-x
9  x-- --> same as 6th row
   --x

   x-x
10 -x- --> none
   x--

   x-x     1-3  1-4  (1-4              )  
11 -x- --> -4-  -3-  (-2- mirror of 2nd)  
   -x-     -2-  -2-  (-3-              )  

   x-x
12 -x- -> none
   --x

   x-x
13 --x --> mirror of rows 8 and 9
   ??? 

   x-x
14 --- --> flip of 6th row
   xx- 

   x-x
15 --- --> congruent to single square
   x-x 

   x-x
16 --- --> mirror of 14th row
   -xx 

   -xx
17 ??? --> flip of 1st - 7th row
   ???

   x--
18 x?? --> rotation of 17th row
   ???

   x--
19 -xx --> rotation of 11th row
   x--

   x--     1--  1--  (1--            )
20 -xx --> -34  -43  (-24 same as 2nd)
   -x-     -2-  -2-  (-3-            )

   x--  x--     rotate 180 degrees and there will be 2 
21 -x-  --x --> in the top row, which is covered by
   ???  ???     rows 1-17

   -x-
22 xx- --> rotation of 20th row
   --x

   -x-
23 x-x --> adjacent to corner already covered by rows 1-7
   ?-?

   -x-
24 x-x --> congruent to single square
   -x- 

   -x-
25 -xx --> rotation of 22nd row
   x--

   -x-  -x-     rotate 180 degrees and there will be 2 
26 -x-  --x --> in the top row, which is covered by
   ???  ???     rows 1-17

   --x
27 ??? --> flip of rows 18-21
   ???

Quadrilaterals: 10

Pentagons now exist. We need to start numbering the points, keeping in mind we must always use the first and last rows and columns.

   xxx  xxx  xxx  xxx      
1  x--  x--  x--  -x-  --> none 
   x--  -x-  --x  x--     

   xxx     153  143
2  -x- --> -4-  -5
   -x-     -2-  -2-

   xxx
3  -x- --> none (same as 4th in top row)
   --x

   xxx  
4  --x --> none (same as first 3 in first row)
   ???

   xxx  xxx  xxx
5  ---  ---  --- --> none
   xx-  x-x  -xx

   xx-     15-  14-  (15-                 15-              )
6  xx- --> 24-  25-  (23-  mirror of 1st  32- mirror of 2nd)
   --x     --3  --3  (--4                 --4              )

   xx-
7  x-x --> none (same as 2nd in top row)
   x--

   xx-     15-
8  x-x --> 2-4
   -x-     -3-

   xx-     15-
9  x-x --> 2-4
   --x     --3

   xx-     15-  15-  14-  15-
10 -xx --> -34  -43  -53  -24
   x--     2--  2--  2--  3--

   xx-     15-  15-  14-  15-
11 -xx --> -34  -43  -53  -24
   -x-     -2-  -2-  -2-  -3-

   xx-
12 -xx --> none
   --x

   xx-
13 x-- --> none (same as 3rd in top row)
   x-x

   xx-     15-
14 x-- --> 2--
   -xx     -34

   xx-     15-  15-  14-  15-
15 -x- --> -3-  -4-  -5-  -2-
   x-x     2-4  2-3  2-3  3-4

   xx-     15-  15-  (14-                   15-                 )
16 -x- --> -4-  -3-  (-5- congruent to 2nd  -2- congruent to 1st)
   -xx     -23  -24  (-23                   -34                 )

   xx-     15-
17 --x --> --4
   xx-     23-

   xx-     15-  
18 --x --> --4  
   x-x     2-3  

   xx-
19 --x --> same as 9th row
   -xx

   xx-
20 --- --> none (same as last in 5th row)
   xxx

   x-x  x-x  x-x      Two adjacent 'x's in
21 x??  -xx  -x-  --> a corner is the same
   ???  ???  xx-      as something above

   x-x     1-4
22 -x- --> -5-
   x-x     2-3

   x-x  -xx  x--  x--  x--      Two adjacent 'x's in
23 -x-  ???  x??  -xx  -??  --> a corner is the same
   -xx  ???  ???  ???  xxx      as something above

   -x-     -1-  -1-  (-1-                -1-              )
24 xxx --> 254  245  (235 mirror of 2nd  325 mirror of 1st)
   -x-     -3-  -3-  (-4-                -4-              )

   --x
25 ??? --> already covered by the 23rd row
   ???

Pentagons: 26

Hexagons are also in play

   xxx
1  xx- --> none
   x--

   xxx     164  154  
2  xx- --> 25-  26-  
   -x-     -3-  -3-  

   xxx     164  154
3  xx- --> 25-  26-
   --x     --3  --3

   xxx  xxx  xxx
4  x-x  x-x  x-x --> none
   x--  -x-  --x

   xxx
5  -xx --> mirrors of first three rows 
   ???

   xxx
6  x-- --> Same as 4th row
   xx-

   xxx
7  x-- --> none
   x-x

   xxx
8  x-- --> none
   -xx

   xxx     164  154  
9  -x- --> -5-  -6-  
   xx-     23-  23-  

   xxx     164  154
10 -x- --> -5-  -6-
   x-x     2-3  2-3

   xxx
11 -x- --> same as 9th row above
   -xx

   xxx
12 --x --> mirror of rows 6-8
   ???

   xxx
13 --- --> none
   xxx

   xx-     
14 xxx --> same as 2nd row
   x--     

   xx-     16-  15-  16-  (16-                  16-              )
15 xxx --> 254  264  245  (235 mirror of first  325 mirror of 2nd)
   -x-     -3-  -3-  -3-  (-4-                  -4-              )

   xx-     16-  16-  15-  16-
16 xxx --> 245  254  264  325
   --x     --3  --3  --3  --4

   xx-     
17 xx- --> mirror of 3rd row
   x-x     

   xx-
18 xx- --> mirror of 16th row
   -xx

   xx-
19 x-x --> rotate 90 degrees so 3 'x' are on top;
   x??     already covered

   xx-     16-
20 x-x --> 2-5
   -xx     -34

   xx-     16-  (16-            )  15-  (16-            )  16-
21 -xx --> -45  (-54 flip of 1st)  -64  (-35 flip of 3rd)  -25
   xx-     23-  (23-            )  23-  (24-            )  34-

   xx-     16-  16-  (15-              )  16-  (16-              )
22 -xx --> -45  -54  (-64 mirror of 1st)  -35  (-25 mirror of 4th)
   x-x     2-3  2-3  (2-3              )  2-4  (3-4              )

   xx-
23 -xx --> flip of 18th row
   -xx

   xx-
24 ??? --> rotate 180 degrees so 3 'x' are on top; 
   xxx     already covered

   x-x  x-x  x-x  -xx     Two adjacent 'x's in
25 x??  -xx  -x-  ??? --> a corner is the same 
   ???  ???  xxx  ???     as something above

   Anything with a single x on top will have at least 2
26 on the bottom, which if rotated, is already covered
   by something above

Hexagons: 22

And Heptagons, but their scope is limited.

   xxx
1  xxx --> none
   x--

   xxx     175  (165                )
2  xxx --> 264  (274 mirror of first)
   -x-     -3-  (-3-                )

   xxx
3  xxx --> flip of first row
   --x 

   xxx
4  xx- --> rotation of 4th row
   xx-

   xxx     
5  xx- --> none
   x-x    

   xxx     175  165
6  xx- --> 26-  27-
   -xx     -34  -34

   xxx
7  x-x --> none
   xx-

   xxx
8  x-x --> none
   x-x

   xxx
9  x-x --> flip of 7th row
   -xx

   xxx
10 -xx --> already covered in 4th-6th row
   ???

   xxx  xxx  xxx
11 x--  -x-  --x --> none
   xxx  xxx  xxx

   xx-
12 xxx --> rotation of 2nd row
   xx-

   xx-
13 xxx --> rotation of 6th row
   x-x

   xx-     17-  16-  (17-  17-    )  (17-    )  (17-    )
14 xxx --> 265  275  (256  246 2nd)  (236 1st)  (326 2nd)
   -xx     -34  -34  (-34  -35    )  (-45    )  (-45    )

   x-x
15 xxx --> rotation of 6th row
   xx-

   x-x
16 xxx --> rotation of 2nd one in 11th row
   x-x 

   x-x
17 xxx --> flip of 15th row
   -xx

   x-x
18 xx- -> rotation of 5th row
   xxx

   x-x
19 x-x --> rotation of 8th row
   xxx

   x-x
20 -xx --> flip of 18th row
   xxx

   -xx
21 ??? --> already covered in 12th-14th rows
   ???

   ???
22 xxx --> already covered in 1st-3rd rows
   xxx

Heptagons: 5

Here are no octagons or nonagons.

Answer: 5+22+26+10+3=66

Total

The total is the sum of the previous.

Total: 66+6+2=74

|improve this answer
$\endgroup$
  • $\begingroup$ "Squares and rectangles have nothing new that isn't the same as or congruent to what we had before" is not true: there's a new large square. I think you're confusing congruence with similarity. $\endgroup$ – Peter Taylor Apr 30 '17 at 6:13
  • $\begingroup$ You are correct - I was assuming similarity. That makes a big difference since I reference that a few times. $\endgroup$ – Trenin May 1 '17 at 12:30
3
$\begingroup$

Well, I don't want to work it all out, but in just a 1x3 grid, I count 18 polygons.

1x1 - 2
1x2 - +6
1x3 - +10

Edit

Decided to try out some more.
L-shape 2x2 - 20 enter image description here
2x2 - 35
Total so far: 73

|improve this answer
$\endgroup$
  • $\begingroup$ I only count 16 2x2 L-shapes. How did you get 17? It's especially strange to have a number that isn't a multiple of four, since each possibility exists in four orientations. $\endgroup$ – JakeRobb Mar 19 '15 at 15:24
  • $\begingroup$ Some of the translations have only 3. Namely, when the top-left and bottom-right pieces are both angled. Also, now that I think about it again, I found 2 more. $\endgroup$ – JonTheMon Mar 19 '15 at 15:27
  • $\begingroup$ Top-left changes - 3 Top-left, middle changes - 2 top-left, bottom-right - 3 + 3 (middle changes) Diagonal across both bottoms - 8 $\endgroup$ – JonTheMon Mar 19 '15 at 15:31
  • $\begingroup$ Yeah, I'm not following. Can you diagram them like I did in my answer? $\endgroup$ – JakeRobb Mar 19 '15 at 15:56
  • $\begingroup$ What are the 6 polygons in a 1x2 area? I can only think of 4 - full square and diagonal half of another, two diagonal halves forming a triangle, two halves forming a parallelogram, and the full 2x1 rectangle. $\endgroup$ – mdc32 Mar 19 '15 at 16:28
2
$\begingroup$

You called it a 3x3 dot grid, and then a 3x3 unit grid. It's unclear if there are four dots marking the points before and after three spaces, or if there are three dots marking the points before and after two spaces. As the former is the more complex possibility, I'm answering based on that assumption.

Breaking them down by shape:

Squares and rectangles (height x width):

1x1: 9
1x2: 6
1x3: 3
2x1: 6
2x2: 4
2x3: 2
3x1: 3
3x2: 2
3x3: 1

L's (each leg only 1 square wide, height x width):

2x2: 4 in each orientation = 16 
2x3: 2 in each orientation = 8

For the rest, I'm going to represent them like tic-tac-toe grids, where X means the polygon encompasses that section of the grid, and an O means it does not.

There are four "fat L's", one in each orientation:

XXO OXX XXX XXX
XXX XXX XXX XXX
XXX XXX OXX XXO

Plus eight more "partially fat L's":

XOO OOX XXX XXX
XXX XXX XXX XXX
XXX XXX OOX XOO

XXO OXX XXX XXX
XXO OXX OXX XXO
XXX XXX OXX XXO

One +:

OXO
XXX
OXO

For the rest, I'll omit the four orientations of each possibility, and just multiply what I find by four:

16 C shapes:

XXX XXX XXO OXX
XXO XOO XOO OXO
XXX XXX XXO OXX

12 T shapes

XXX XXX OOO
OXO OXO XXX
OXO OOO OXO

4 right triangles (okay, they're jaggy triangles):

XXX
XXO
XOO

And these 24 oddball shapes:

XXX XXX OXX XXO OXX XXO
OXO OXO OXO OXO XXO OXX
OXX XXO XXO OXX OOO OOO

If I've added up my individual counts correctly, that makes 139 possibilities. I might have missed some, but I don't think so.

|improve this answer
$\endgroup$
  • $\begingroup$ Reflections and rotations still count as congruent... The question asks for non-congruent polygons specifically. $\endgroup$ – mdc32 Mar 19 '15 at 16:37
  • 1
    $\begingroup$ Also, I completely missed that the edges can be diagonal. There are many, many more than the 24 unique patterns I identified above. I'm out. :D $\endgroup$ – JakeRobb Mar 19 '15 at 16:42
1
$\begingroup$

There are 38. Shapes shown by vertices.

--- --- --- --- --- --- --- ---
0-- 0-- -0- 00- 00- 0-0 -00 -00
00- 0-0 0-0 00- 0-0 0-0 00- 0--

0-- -00 0-- 0-0 0-0 -0- -0- 000
--- -0- --0 -0- --- 0-0 --- -0-
0-0 00- 0-0 0-0 0-0 0-0 0-0 0-0

-0- -0- -0- --0 --0 --0 -00 -00
0-0 0-0 0-0 0-- 0-- 0-- --- 0--
-0- 0-- 00- 0-- -0- 00- 00- 00-

-12 -12 1-- 1-- 1-- -12 -12 -12
-5- -3- -23 -42 -52 63- 56- 63-
4-3 5-4 5-4 5-3 4-3 54- 43- -54

-12 -12 -12 -12 -12 -12
63- 56- 65- 64- 74- 75-
5-4 4-3 4-3 5-3 653 643

|improve this answer
$\endgroup$
  • $\begingroup$ Definitely, this list with only points is incomplete without the lines, because : Consider second row, second entry : Does the top point connect with bottom point or with middle left point or with middle right point ? Here itself, we get 6 possibilities for the lines from the top point. Finishing the polygon for this single entry will result in many polygons. Considering all 29 entries, how many polygons will we get ? I guess, too many. (( @Ian MacDonald : Currently, your answer is the best systematic attempt )) $\endgroup$ – Prem May 7 '15 at 9:42
  • 1
    $\begingroup$ @Prem: in the example you have chosen, the top point must be connected to two other points. Because there are three possibilities of which two points are chosen, this one represents three unique polygons. You are correct that the 29 count is incomplete. $\endgroup$ – Ian MacDonald May 7 '15 at 12:15
  • $\begingroup$ thanks for the verification. Unfortunately, your new edit makes my comments out-of-sync, so I will delete it shortly. $\endgroup$ – Prem May 7 '15 at 13:03
  • $\begingroup$ Aren't the first shape in the first and third rows congruent triangles? Also, the 4th shape in the first row and 5th in the second and 1st in the 3rd are also congruent squares. $\endgroup$ – Trenin Apr 27 '17 at 17:33
  • $\begingroup$ I went with congruency only relating to rotations and reflections, not scales. Meh. $\endgroup$ – Ian MacDonald Apr 27 '17 at 17:58

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.