[Guest]

How many different patterns can be formed by blackening 3 squares of a grid consisting of 5x5 squares?

Note : If a pattern can be produced by rotating another pattern (90, 180 or 270 degrees) then these two patterns are not considered as different.

[superprismatic]

578

[Guest]

25C3/4=575

[Guest]

Both superprismatic and deepan c have nearly got it right. Here is why I think the answer is 611. As deepan observed there are 25 choose 3 patterns, or 2300, if one ignores symmetry; 2300/4 or 575 if it is assumed any rotation by 90, 180 & 270 degrees produces a distinct one. However, a few patterns already have a built-in symmetry, so we have taken away too much by that division.

So what are the few patterns with some symmetry? First, there is no 90 deg symmetry, but there is 180 deg sym for certain patterns: the square in the center must be black, then a second one from the top two rows or from the two squares to the left of the center. The third square must be taken to be the one on the opposite side of the center from the second, and equidistant, so that that pattern has 180 degree symmetry. Each of these 12 patterns, when rotated 90 degs, gives us another of this type of pattern, so we only get 12 distinct patterns out of these, not 48, hence we decreased the total too much when we did the division by 4. We should now add back in 3x12 or 36, giving 611 total.

[superprismatic]

Both superprismatic and deepan c have nearly got it right. Here is why I think the answer is 611. As deepan observed there are 25 choose 3 patterns, or 2300, if one ignores symmetry; 2300/4 or 575 if it is assumed any rotation by 90, 180 & 270 degrees produces a distinct one. However, a few patterns already have a built-in symmetry, so we have taken away too much by that division.

So what are the few patterns with some symmetry? First, there is no 90 deg symmetry, but there is 180 deg sym for certain patterns: the square in the center must be black, then a second one from the top two rows or from the two squares to the left of the center. The third square must be taken to be the one on the opposite side of the center from the second, and equidistant, so that that pattern has 180 degree symmetry. Each of these 12 patterns, when rotated 90 degs, gives us another of this type of pattern, so we only get 12 distinct patterns out of these, not 48, hence we decreased the total too much when we did the division by 4. We should now add back in 3x12 or 36, giving 611 total.

As matho states, there are 12 patterns

which have 180 degree symmetry without

90 degree symmetry. 6 of these are

90 degree rotations of the other 6.

So, we have 6 patterns counted twice

each in the 2300 total. The rest are

counted 4 times each. So, there are

(2300-12)/4 = 572 representatives of

the patterns counted 4 times. When we

add back in the 6 representatives of

the 12 which were counted twice, we

get 578.

[Guest]

How many different patterns can be formed by blackening 3 squares of a grid consisting of 5x5 squares?

Note : If a pattern can be produced by rotating another pattern (90, 180 or 270 degrees) then these two patterns are not considered as different.

322 unique layouts with mirrored symmetry allowed.

The number of combinations formed by picking X from Y is calculated as (Y!)/((X!)*((Y-X)!)). So 3 from 6 would be (6!)/((3!)*(3!)) = 20.

I numbered the grid starting from the top left as 1 and incremented from left to right, by row, until all grid spaces are numbered (center should be 13):

01.02.03.04.05

06.07.08.09.10

11.12.13.14.15

16.17.18.19.20

21.22.23.24.25

Split the grid into rotational segments:

90 degree rotations: spaces 01-04,07-08,13

180 degree rotations: spaces 01-05,07-10,13-15,20

full-board rotations: one from spaces 01-05,07-08; one from spaces 18-19,22-25; and center space 13

Calculate the combinations for each set of rotations:

90 degrees: 7 spaces -- (7!)/((3!)*(5!)) = 35

180 degrees: 13 spaces -- (13!)/((3!)*(10!)) = 286

For the full-board rotations, first number both sections 1-6 on both sides of the board, mirroring across the diagonal:

1.2.3.4._

_.5.6._._

_._.X._._

_._.6.5._

_.4.3.2.1

Since any combination involving 1,1 - 6,6 will be ignored in the combination calculation, we will need to add these 6 back in.

(6!)/((2!)*(4!)) = 15

15 + 6 = 21

We also need to eliminate the use of the center space and pick two spaces from the top and one space from the bottom. This will ignore any combinations such as 1,2 & 1 or 1,2, and 2. There are 15*2 of these (15 combinations of 2 from 6, and two positions each that can match) so we will need to add 30. Note that by rotation, we are doing the same as picking one from the top and two from the bottom.

(6!)/((3!)*(3!)) = 20

20 + 30 = 50

Total full-board rotations = 21+50 = 71

Now, one might note that all 90 degree rotations are included within the 180 degree rotations. Infact the set of 90 degree rotations occur twice within the 180 degree rotations. Also, it is important to note that none of the full-board rotations are included in either the 90 or 180 degree set. This leads us to conclude that the number of unique layouts (mirrored allowed) is:

#90deg + (#180deg - 2(#90deg)) + #full-board

35 + (286 - 2(35)) + 71 = 322

[superprismatic]

319 unique layouts with mirrored symmetry allowed (although the original post did not allow for this type of symmetry).

[Guest]

319 unique layouts with mirrored symmetry allowed (although the original post did not allow for this type of symmetry).

Mirrored symmetry is not always equivalent to rotational symmetry. Rotate the number 2 as many times as you want and you will never achieve the number 5, however it is possible by mirroring and rotating.

The original post only mentions rotational symmetry; I wouldn't mind seeing how you arrived at your answer, or point out where I made an error. (I've been known to make mistakes in the simplest math)

Edited December 21, 2009 by Egghead

[superprismatic]

Mirrored symmetry is not always equivalent to rotational symmetry. Rotate the number 2 as many times as you want and you will never achieve the number 5, however it is possible by mirroring and rotating.

The original post only mentions rotational symmetry; I wouldn't mind seeing how you arrived at your answer, or point out where I made an error. (I've been known to make mistakes in the simplest math)

By 'mirrored symmetry' I mean a flip is required, e.g.,

a flip is required to transform this

ABCDE

FGHIJ

KLMNO

PQRST

UVWXY

[/code]


into this

[code]

EDCBA

JIHGF

ONMLK

TSRQP

YXWVU

as it can't be done using rotations alone.

I don't understand your terminology. So,

I can't really follow your argument. What

are 'rotational segments' and 'full-board

rotations'? And I can't see where the

'mirrored' part comes in.

[Guest]

I don't understand your terminology. So,

I can't really follow your argument. What

are 'rotational segments' and 'full-board

rotations'? And I can't see where the

'mirrored' part comes in.

By rotational segments, I was referring to a grouping of grid spaces that, when rotated 90, 180, or 270 degrees around the center grid space, will completely cover the grid with the center being the only overlap. Like using quarters and halves of a circle to define a full circle.

The 90 degree rotational segment needs four total rotations to cover the grid and only the center space is included in all four rotations. This is simply used to identify a set of spaces from which all three blackened squares can be selected. Any orientation within a rotational segment is unique and can be found 2 or 4 times (by rotation) within the full 2300 possible grid layouts.

The full-board rotations are orientations that have at least one blackened square that cannot be confined in the same half of the grid as the other two and therefore cannot be defined by the 90 and 180 degree rotational segments, however, these all have rotational counterparts, some appear twice in the 2300 and some appear 4 times. Think of it like we are rotating the entire grid around one of its corners.

If we were to consider mirroring, we would need to define the position of the mirror or fold. If the fold is on one (or all) side(s) of the grid, then just divide by two. If the fold is within the grid, then more complex equations might be needed.

Mirroring is allowed in my answer since 01,13,19 and 05,13,17 are both considered unique.

Edited December 21, 2009 by Egghead

[superprismatic]

By rotational segments, I was referring to a grouping of grid spaces that, when rotated 90, 180, or 270 degrees around the center grid space, will completely cover the grid with the center being the only overlap. Like using quarters and halves of a circle to define a full circle.

The 90 degree rotational segment needs four total rotations to cover the grid and only the center space is included in all four rotations. This is simply used to identify a set of spaces from which all three blackened squares can be selected. Any orientation within a rotational segment is unique and can be found 2 or 4 times (by rotation) within the full 2300 possible grid layouts.

The full-board rotations are orientations that have at least one blackened square that cannot be confined in the same half of the grid as the other two and therefore cannot be defined by the 90 and 180 degree rotational segments, however, these all have rotational counterparts, some appear twice in the 2300 and some appear 4 times. Think of it like we are rotating the entire grid around one of its corners.

If we were to consider mirroring, we would need to define the position of the mirror or fold. If the fold is on one (or all) side(s) of the grid, then just divide by two. If the fold is within the grid, then more complex equations might be needed.

Mirroring is allowed in my answer since 01,13,19 and 05,13,17 are both considered unique.

I wrote a program to take all 2300, look at all pairs to see if I could flip and/or rotate one to make it like the other, throwing one out if it did. It did this over and over until it couldn't find such a pair. 319 were left. I'll go back and try to understand your process.

[Guest]

322 unique layouts with mirrored symmetry allowed.

The number of combinations formed by picking X from Y is calculated as (Y!)/((X!)*((Y-X)!)). So 3 from 6 would be (6!)/((3!)*(3!)) = 20.

I numbered the grid starting from the top left as 1 and incremented from left to right, by row, until all grid spaces are numbered (center should be 13):

01.02.03.04.05

06.07.08.09.10

11.12.13.14.15

16.17.18.19.20

21.22.23.24.25

Split the grid into rotational segments:

90 degree rotations: spaces 01-04,07-08,13

180 degree rotations: spaces 01-05,07-10,13-15,20

full-board rotations: one from spaces 01-05,07-08; one from spaces 18-19,22-25; and center space 13

Calculate the combinations for each set of rotations:

90 degrees: 7 spaces -- (7!)/((3!)*(5!)) = 35

180 degrees: 13 spaces -- (13!)/((3!)*(10!)) = 286

For the full-board rotations, first number both sections 1-6 on both sides of the board, mirroring across the diagonal:

1.2.3.4._

_.5.6._._

_._.X._._

_._.6.5._

_.4.3.2.1

Since any combination involving 1,1 - 6,6 will be ignored in the combination calculation, we will need to add these 6 back in.

(6!)/((2!)*(4!)) = 15

15 + 6 = 21

We also need to eliminate the use of the center space and pick two spaces from the top and one space from the bottom. This will ignore any combinations such as 1,2 & 1 or 1,2, and 2. There are 15*2 of these (15 combinations of 2 from 6, and two positions each that can match) so we will need to add 30. Note that by rotation, we are doing the same as picking one from the top and two from the bottom.

(6!)/((3!)*(3!)) = 20

20 + 30 = 50

Total full-board rotations = 21+50 = 71

Now, one might note that all 90 degree rotations are included within the 180 degree rotations. Infact the set of 90 degree rotations occur twice within the 180 degree rotations. Also, it is important to note that none of the full-board rotations are included in either the 90 or 180 degree set. This leads us to conclude that the number of unique layouts (mirrored allowed) is:

#90deg + (#180deg - 2(#90deg)) + #full-board

35 + (286 - 2(35)) + 71 = 322

I wrote a program to take all 2300, look at all pairs to see if I could flip and/or rotate one to make it like the other, throwing one out if it did. It did this over and over until it couldn't find such a pair. 319 were left. I'll go back and try to understand your process.

I just noticed that in my full-board rotations (with center), 2,2 and 4,4 are rotations of one another. So this brings my total to 321. I am still looking for the other two instances that would bring it down to 319.

[Guest]

...superprismatic, actually. I got 578. Here's how:

So without any rotation, there are clearly 25C3 = 2300 different configurations. I think everyone agrees on this part.

Most people also caught onto the fact that there are 12 configurations that have 180-degree symmetry (i.e. are symmetric about the center square), which leaves 2288 configurations that do not have such symmetry.

So we have 2288 configurations, each of which have 4 different rotations, and 12 configurations that have 2 rotations. Final answer: 2288/4 + 12/2 = 572 + 6 = 578. No program needed.

I find that writing programs for these problems can present more problems than the problem itself...for example, common sense would tell you here that (25C3)/4 would be the minimum possible answer (if each configuration had 4 rotations), so the answer should be at least 575, which would immediately raise a red flag for the answers in the 300's. Programming is a great way to solve by brute force, or when you have a long, drawn out process (believe me, I do it for a living), but I still think pen, paper, and a bit of thought is the way to go.

[superprismatic]

...superprismatic, actually. I got 578. Here's how:

So without any rotation, there are clearly 25C3 = 2300 different configurations. I think everyone agrees on this part.

Most people also caught onto the fact that there are 12 configurations that have 180-degree symmetry (i.e. are symmetric about the center square), which leaves 2288 configurations that do not have such symmetry.

So we have 2288 configurations, each of which have 4 different rotations, and 12 configurations that have 2 rotations. Final answer: 2288/4 + 12/2 = 572 + 6 = 578. No program needed.

I find that writing programs for these problems can present more problems than the problem itself...for example, common sense would tell you here that (25C3)/4 would be the minimum possible answer (if each configuration had 4 rotations), so the answer should be at least 575, which would immediately raise a red flag for the answers in the 300's. Programming is a great way to solve by brute force, or when you have a long, drawn out process (believe me, I do it for a living), but I still think pen, paper, and a bit of thought is the way to go.

all the answers in the 300s were assuming the addition of another symmetry -- a flip, which was not in the original problem but causes an interesting wrinkle. Counting only patterns which are unique up to rotation and flipping, there are 319.

[Guest]

...for example, common sense would tell you here that (25C3)/4 would be the minimum possible answer (if each configuration had 4 rotations), so the answer should be at least 575, which would immediately raise a red flag for the answers in the 300's. Programming is a great way to solve by brute force, or when you have a long, drawn out process (believe me, I do it for a living), but I still think pen, paper, and a bit of thought is the way to go.

If you really think about it, 25C3/4 should be the maximum number of rotationally unique layouts. Each of those 575 layouts can be rotated to form the other 1725 layouts. Also, my solution allows for mirrored patterns as the original post does not mention their exclusion; not to mention the complexity associated with the mathematics when multiple mirrors/folds are defined. Also, looking back at my notes, in my full-board rotations (with center), 2,2 and 4,4 are not 90 degree rotations of one another, so my number is back to 322. I am still looking for the three that reduce my number to 319 that superprismatic came up with.

...there are 12 configurations that have 180-degree symmetry (i.e. are symmetric about the center square), which leaves 2288 configurations that do not have such symmetry

Your 12 would be counted in the 2300 a total of at least two times each with some counted four times. Therefore, less than 2288 configurations remain.

I personally cannot find more than 6 unique configurations that have 180 degree symmetry (folded perpendicular through the center): (1,13,25) (2,13,24) (3,13,23) (4,13,22) (7,13,19) (8,13,18)

Note that any other 180 degree symmetric configuration can be described by rotating one of these 6 by 90, 180 or 270 degrees.

[Guest]

I'm sure that 578 is the answer to the original problem. In fact, here's another way to do it:

We know that if we do not choose the center square, there can be no rotational symmetry. There are (24C3)/4 = 506 ways to choose 3 squares not including the center.

We can also pick the center square, without getting rotational symmetry. For example, picking (1,2,13) would achieve this. So we pick the center (1 way), then another square (24 ways), and then note that there is exactly one square of the remaining 23 that will cause the configuration to be rotationally symmetric, so we pick one of the other 22 (22 ways). Note that the order doesn't matter here (i.e. 1,2,13 = 2,1,13), so we divide by 2. 24*22/2 = 264. These configurations can be rotated in 4 ways, so divide by 4 again. 264/4 = 66.

Finally, we can pick the center square and then two more squares that will cause the final configuration to be symmetric about the center in 6 different ways.

Add them up...506 + 66 + 6 = 578.

Your 12 would be counted in the 2300 a total of at least two times each with some counted four times.

We agree on that...note that I divided my 12 by 2, which leads to the 6 configurations with symmetry.

If you really think about it, 25C3/4 should be the maximum number of rotationally unique layouts. Each of those 575 layouts can be rotated to form the other 1725 layouts.

My mirroring solution is coming soon. It's late and I need sleep.

What a fun problem.

Edited December 23, 2009 by Chuck