r/askmath • u/Blah_Blah9is9blah • Jul 16 '26
Discrete Math Is there a "good" way to solve this question I thought of?
Recently I have thought of this question, and I have not seemed to find anything similar (it's not really a "proper" or "useful" question, I think):
I am making patterns on a 4 by 4 grid of unit squares. I shade at least one and at most all of the unit squares black such that the resulting shape has at least one line of symmetry. In how many different ways can I do this? Note that two shapes that are rotations and/or reflections of each other are still treated as different.
I've tried to count by how many squares are shaded one at a time, but is there a way to more systematically solve it? Additionally, I haven't come to an actual answer yet. This question does seem easier (or at least less time-consuming) with a 3 by 3 grid so I'm wondering if there's an actual systematic way to approach it with that I'm just not seeing or if it just gets harder with larger grids.
•
u/CrookedBanister Jul 16 '26
Seems like recursion should help, try looking at small examples and see if there's anything systematic you can do to build the n×n case up from the (n-1)×(n-1) or (n-2)×(n-2) ones.
So like in a 4x4 grid anything that would work in a 2×2 would work, plus whatever could be added to the new 1-unit border that preserves symmetry.
•
u/Desperate_Penalty690 Jul 16 '26 edited Jul 16 '26
If you look at it by line of symmetry:
Horizontal or vertical line down the middle: each has 2^8 possible shapes.
Then there are the two diagonal lines with 2^10 possible shapes each.
The double counts are, I think, only the empty shape. This is counted 4 times and might not be valid at all.
With 3 by 3 grid, you get 2^6 for each of the 4 symmetry lines. But now there is more double counting. For example, marking only the middle, is symmetrical in all 4 lines. Is that the only one though?
•
u/bluesam3 Jul 16 '26
You've double counted loads of others on the 4x4 grid: you've double counted shading all four corners, for example. In fact, if you look at just the top-left 2x2, you can fill it in any way you like and copy it into the other four corners with the necessary flips to get another pattern that you've double counted. You've also double counted within each category: all of my examples above are counted four times, for example.
•
u/Desperate_Penalty690 Jul 16 '26 edited Jul 16 '26
Ah right, I had a feeling I was missing some doubles.
How about for the 4x4:
2^8 - 2^4 + 2^10 - 2^62^4 being the number of double counts between horizontal and vertical symmetry, and 2^6 the double counts between the two diagonals.
How is shading the 4 corners counted 4 times? Should only be counted twice in the 2^8.
•
•
u/Creative-Feature-264 Jul 17 '26
Per risolvere le domanda che hai in mente devi svelare i principi primi delle cause che la hanno scatenata. Questo è un metodo "buono".
•
u/bildramer Jul 17 '26
The Pólya enumeration theorem is a way to calculate numbers of configurations under symmetry, so for problems exactly like yours. It's very convenient, but a bit complicated. It goes like this:
List all group elements of your symmetry group. That is, e.g. if you only count rotations, you have 0, 90deg, 180deg, 270deg. If you have rotation and mirroring, you have 8 elements.
For each element, count how many configurations are unaffected by it. All 65536 colorings are unaffected by not doing anything; if you rotate the square 90 or 270 degrees, all 2x2 corners have to match, which means 16 colorings; if you rotate it 180 degrees, it's a 2x4 instead, which has 256 colorings.
Simply average these numbers. You have (65536 + 16 + 256 + 16)/4 = 16456 patterns up to rotation.
Adding reflections, it's a bit more complicated, you get 8548. Adding color flips, figuring out what's "unaffected" becomes a mess, but pretty sure you get 4324.
•
u/Bounded_sequencE Jul 16 '26 edited Jul 16 '26
Needs more clarification:
That said, there are "only" 216 - 1 = 65535 shapes to consider, so brute-forcing with a short program is a good way to verify your result.