There is a 3×3 dot grid. How many different non-congruent polygons can you make on the grid?
Rules:
- All vertices of the polygon must be on the grid
- Only non self intersecting polygons
- Only polygons with non-empty interior (<=> positive area)
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this communityThere is a 3×3 dot grid. How many different non-congruent polygons can you make on the grid?
Rules:
Working up from a 2x2 grid.
We can make a square and a triangle. All triangles at this scale are congruent.
14 1-
23 23
Answer: 2
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
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
The total is the sum of the previous.
Total: 66+6+2=74
First I counted polygons, then I counted congruence classes of polygons. First, counting polygons, I found 76 triangles, 94 quadrilaterals, 164 pentagons, 158 hexagons, 36 heptagons, 0 octagons, and 0 nonagons, for a total of 528 distinct polygons. Next, counting congruence classes, I found 8 triangles up to congruence, 16 quadrilaterals up to congruence, 23 pentagons up to congruence, 22 hexagons up to congruence, and 5 heptagons up to congruence, for a total of 74 congruence classes of polygons.
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
2x2 - 35
Total so far: 73
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.
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
Heavily based on Trenin's answer (in hexagons and heptagons). I got the final number to be 73. Trenin used one mirrored hexagon twice (the crossed on my image). Then there is: Triangles: 8 Quadrilaterals: 16 Pentagons: 23 Hexagons: 21 Septagons: 5 Octagons: 0 Sum = 73