Line segments and the conservation of space

[BMAD]

Let us define a line segment as a segment that joins two vertices either vertically or horizontally.  So in the image below, drawing a line from top to bottom vertically can have a maximum of 5 line segments.

 

 

The tasks:

 

Divide the shape into two figures with identical areas using....

• the least amount of line segments
• the most amount of line segments

 

**It should be noted that the shape is "missing" one square in the upper left and two in the lower right intentionally.  I realize that the image may make the missing square(s) appear present.**

Edited February 12, 2015 by rookie1ja

[gavinksong]

 AAABBB

AAAABBB

AAABBBB

AAABBBB

AAABB

 

 AAAAAA

AABBBBB

ABBAAAB

AAAABBB

BBBBB

[gavinksong]

It takes 6 and 22 line segments for each respective task.

[BMAD]

It takes 6 and 22 line segments for each respective task.

elaborate please

[bonanova]

@BMAD by figures with "identical areas" do you mean figures having "equal areas" or figures having "congruent shapes"?

[BMAD]

@BMAD by figures with "identical areas" do you mean figures having "equal areas" or figures having "congruent shapes"?

just equal areas

[BMAD]

 AAABBB

AAAABBB

AAABBBB

AAABBBB

AAABB

 

 AAAAAA

AABBBBB

ABBAAAB

AAAABBB

BBBBB

but how do you 'know' these can't be further optimized?

[gavinksong]

 

 AAABBB

AAAABBB

AAABBBB

AAABBBB

AAABB

 

 AAAAAA

AABBBBB

ABBAAAB

AAAABBB

BBBBB

but how do you 'know' these can't be further optimized?

 

 

Well.... I guess I don't.

 

1)There's no straight vertical line that can split the figure equally in half, which is really the only thing that might take fewer lines. So I must be right.

 

2) The maximum number of boundary segments that a figure composed of N unit squares can have is 2N + 2. Granted, I don't know how to prove this rigorously - but if I accept this, then I can actually calculate the number of line segments I need to create these shapes: (2 * (2 * 16 + 2) - 24) / 2 = 22. That's exactly how many I used.

[k-man]

 

 

 AAABBB

AAAABBB

AAABBBB

AAABBBB

AAABB

 

 AAAAAA

AABBBBB

ABBAAAB

AAAABBB

BBBBB

but how do you 'know' these can't be further optimized?

 

 

Well.... I guess I don't.

 

1)There's no straight vertical line that can split the figure equally in half, which is really the only thing that might take fewer lines. So I must be right.

 

2) The maximum number of boundary segments that a figure composed of N unit squares can have is 2N + 2. Granted, I don't know how to prove this rigorously - but if I accept this, then I can actually calculate the number of line segments I need to create these shapes: (2 * (2 * 16 + 2) - 24) / 2 = 22. That's exactly how many I used.

 

 

Your assumption (highlighted in the quote) is not that difficult to prove.

Each square has 4 sides, so you start with 4N maximum sides, but every time you attach 2 squares to each other you lose 2 sides. So, you need to subtract double the number of connections (or common sides), which must be at least N-1, so the formula for the maximum perimeter of a figure made up of identical squares could be written as 4N - 2(N-1), which is the same thing as 2N+2.