dividing squares

[lionelhill]

Here's another one:

Every square number is a sum of odd numbers:
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
etc. etc.

Given a square of tiles, say 4 by 4, how many ways can you divide it into areas of 1 + 3 + 5 + 7 tiles?

(obviously an area of 7 tiles can be 7 tiles joined however you want, but it has to be one continuous shape that you could cut out of cardboard and it would be just one piece).

I think this is a nice little thing for finding the answer programatically, by trying alternatives, but I'm wondering if there is a more elegant way to do it. Before anyone feel cheated, I don't have an answer (yet).

 

[brigmar]

Not looked into this one, but a question that is bound to come up is based around your definition of 'continuous shape'.
Would that include corner connections?
eg, could the three piece be variations of:
[tt]X X
XX or X X[/tt] ?

I would assume not.

 

[kwbMitel]

Brigmar makes a good point.

Additionally, Are the individual 1 Sq unit pieces limited in shape? Are triangles, Circles, Irregular Polygons, etc permitted.

Your question seems to suggest that the 1 sq unit pieces are themselves square and must be placed side by side with at least 1 edge touching another square and corners always matching. It does not say that though.

Further, would you include mirror images as unique?
X X X X
X And X = 2 solutions or 1 for 5 SQ units
X X
X X

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[CajunCenturion]

Anyone wonder why attorneys are so popular?



--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

Too bad we can't communicate by a more efficient means.

I've always been cursed with being able to see alternative interpretations. Some meaningful, some not. I try to self analyse as much as I can.

Oh, and my Ascii Representation sucks.
This it what it should have looked like:[tt]
X X X X
X And X = 2 solutions or 1 for 5 SQ units
X X
X X[/tt]

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[CajunCenturion]

==> Too bad we can't communicate by a more efficient means.
I think the problem is well stated.

==> it has to be one continuous shape that you could cut out of cardboard and it would be just one piece
I think that makes it pretty obvious that corners are excluded.

==> Given a square of tiles, say 4 by 4
I think that's pretty clear what shape we're working with.

==> I've always been cursed with being able to see alternative interpretations. Some meaningful, some not. I try to self analyse as much as I can.
Might I suggest that you follow the advice of your signature. Go with the interpretation that requires the fewest number of assumptions.



--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[brigmar]

... if you're not limited to shape to the tile squares, your answer will be infinity (so I'm guessing squares it is).

... as for mirrors, those are different shapes. Ask anybody who's played Tetris!

 

[kwbMitel]

CajunCenturion:

Given a square of tiles, say 4 by 4, how many ways can you divide it into areas of 1 + 3 + 5 + 7 tiles?

Do the resulting shapes need to be able to reform a 4 X 4 Square? If not, then you must define how they can or cannot be combined.

Suggestion: All Squares must connect to any other square by touching at 2 corners.

(obviously an area of 7 tiles can be 7 tiles joined however you want, but it has to be one continuous shape that you could cut out of cardboard and it would be just one piece).

Does this include the following?[tt]

----
---- | | ----
| |--------| |
----| || |----
----------
| | | |
---- ----[/tt]

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[CajunCenturion]

Why are you making this so difficult?
==> Given a square of tiles, say 4 by 4,
[tt]
+-----+-----+-----+-----+
| | | | |
+-----+-----+-----+-----+
| | | | |
+-----+-----+-----+-----+
| | | | |
+-----+-----+-----+-----+
| | | | |
+-----+-----+-----+-----+
[/tt]
==> how many ways can you divide it into areas of 1 + 3 + 5 + 7 tiles?
[tt]
+-----+-----+-----+-----+
| 7 | 7 | 7 | 7 |
+-----+-----+-----+-----+
| 5 | 5 | 5 | 7 |
+-----+-----+-----+-----+
| 3 | 3 | 5 | 7 |
+-----+-----+-----+-----+
| 1 | 3 | 5 | 7 |
+-----+-----+-----+-----+
[/tt]
That's one.
[tt]
+-----+-----+-----+-----+
| 7 | 7 | 1 | 3 |
+-----+-----+-----+-----+
| 5 | 7 | 7 | 3 |
+-----+-----+-----+-----+
| 5 | 5 | 7 | 3 |
+-----+-----+-----+-----+
| 5 | 5 | 7 | 7 |
+-----+-----+-----+-----+
[/tt]
That's two.
How many ways can you divide it into areas of 1 + 3 + 5 + 7 tiles?

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

CajunCenturion - I'm not trying to be difficult. I'm trying to understand. Maybe there is some club where all these rules are just understood but I don't seem to be a member.

TTFN

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[lionelhill]

Cajun is interpreting correctly. Tiles implies the thing is divided into squares and no funny triangles etc.; the cardboard cutout defines what constitues a single lump of something; the shapes must be able to make the original square because my request was how to divide up the original square.

 

[kwbMitel]

Thanks lionhill - I'm not trying to be a pain and that interpretation seemed the most obvious but I need to be sure before I invested time.

Thanks again.

*******************************************************
Occam's Razor - All things being equal, the simplest solution is the right one.

 

[kjv1611]

I think the wording of this statement made it difficult to grasp the first time around:

Given a square of tiles, say 4 by 4, how many ways can you divide it into areas of 1 + 3 + 5 + 7 tiles?

So, instead of that, maybe if it were stated:
Given a square of tiles, 4 by 4, how many ways can you divide it into areas of 1 + 3 + 5 + 7 tiles?

At least to me, the original wording made it sound like you could also go to a higher square number to begin with, that the 4x4 example was just that - an example.

Of course, that's me, sleepy, and far from a linguistics expert by any stretch.

 

[Thadeus]

Does the '1' tile need to be continuous with other tiles? It doesn't state just what to do with the '1' tile as it cannot touch any other corners with itself unless I fold it.... Can I fold it? it doesn't say I can't... hmmmm you know what would be an interesting puzzle? if we could stack our tiles like the game Upwords... the corners would still be touching, and I could cut that out of paper. Is that OK if I solve it by stacking folded tiles? AND..... done!

~thadeus

 

[kjv1611]

Wow! That's some purty interesting squares for sure! [ROFL2]

 

[lionelhill]

Strewth, you lot have a complicated way of looking at questions!

kjv1611, you interpret my wording correctly. If anyone wishes to give a definite solution to 4*4 I am happy, but obviously I would be interested in approaches that can be extended to other squares. The method is more interesting than the answer for one particular square.

 

[Skie]

Well, 2 x 2 is easy. You either have 1 or 4 depending on whether rotating the solution counts.

I started working on 3 x 3 and the number of solutions increases dramatically. It looks like you have about 7 solutions when the 1 tile starts in a corner. 3 solutions when the 1 tile starts middle-edge. And, 8 solutions when it's in the middle. So 7x4 + 3x4 + 1x8 = 48.

4 x 4 is more than I want to work with.

 

[lionelhill]

Yes, it's obvious that all the solutions of one square are a subset of the solutions of the next square up (by adding one big L-shape round the edge of the smaller square), but it's far from obvious how you deal with all the solutions that are not a subset.

I am still puzzling over how to do this computationally without counting mirror images and rotations several times.