3
$\begingroup$

Yesterday I watched "The man who knew infinity" about the amazing Ramanujan. Inspired by the partitions problem from the movie I came up with a puzzle: In how many ways can you partition a 3x3 grid into rectangles? Can you find an efficient way to count them? Note: rotations and reflections of the grid are counted as the same partition.

Good luck!

$\endgroup$
  • $\begingroup$ Are rotations and reflections considered different partitions? Also, minor nitpick, but squares are also rectangles, so it’s a bit redundant to list both $\endgroup$ – HTM Oct 12 '19 at 22:36
  • $\begingroup$ Thanks for that. Rotations and reflections are the same partition. Removed squares and updated the problem statement. $\endgroup$ – Dmitry Kamenetsky Oct 12 '19 at 23:00
  • 3
    $\begingroup$ This seems more like a math problem than a puzzle - I don't think there's any particularly clever method to solve it other than enumerating all the options. $\endgroup$ – Deusovi Oct 12 '19 at 23:37
  • $\begingroup$ sorry, but this seems not on-topic, according to the scope defined in the help center. such off-topic posts may get deleted or closed. please check the help center or faqs on the meta site to see what questions you should/ can ask here on P.SE. happy puzzling! ;) $\endgroup$ – Omega Krypton Oct 14 '19 at 3:28
  • $\begingroup$ Yes fair enough. I admit it is not much of a puzzle, simply a problem in counting. $\endgroup$ – Dmitry Kamenetsky Oct 14 '19 at 3:32
5
$\begingroup$

If I counted correctly and didn't miss any, there are

54

arrangements. There is no particular method to this - just going through all possible combinations of rectangles, and then trying all arrangements.

enter image description here

EDIT:

An alternative method which does not rely on going through quite so many cases is as follows:

There are 12 internal edge segments, and we can remove some to form the rectangle partition. Not every combination of removed segments produces a valid partition however. It is invalid when at one or more of the four internal intersect points there are three removed segments, or if there are two removed segments at right angles. All other cases will result in a valid partition.

As far as I can see, enumerating just the valid combinations of those intersection points still involves a bit of case work. You could split it into cases depending on which sides of the central square are removed:

1. No sides removed. There are 3 possibilities for each intersection point, so $3^4=81$ valid rectangular partitions with a central 1x1 square. After applying Burnside's lemma to reduce by symmetry, there are $15$ left.

2. One side removed. There are 2 possibilities at the points on either side of the removed segment, and 3 at the other points, for $2^2 3^2=36$ possibilities. Reducing this due to the mirror symmetry there are $21$ unique ones.

3. Two opposite sides removed. There are 2 possibilities at each point, so $2^4=16$ arrangements but after symmetry reduction only $7$ unique ones remain.

4. Two adjacent sides removed. There are $3*2^2*1 = 12$ possibilities, which reduces to 7 after symmetry reduction.

5. Three sides removed. There are $2^2*1^2 = 4$ possibilities, which reduces to 3 after symmetry reduction.

6. Four sides removed. There is only $1^4 = 1$ possibility.

Adding these together, we get $15+21+7+7+3+1 = 54$ rectangular partitions.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Beautiful answer! I love the diagrams. $\endgroup$ – Dmitry Kamenetsky Oct 13 '19 at 0:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.