There is a $3\times3$ 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)
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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
-
$\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
$\begingroup$
$\endgroup$
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
-
$\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
$\begingroup$
$\endgroup$
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.
-
$\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
$\begingroup$
$\endgroup$
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
-
$\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
