BrainDen.com - Brain Teasers
• 0

# Line segments and the conservation of space

## Question

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. 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 by rookie1ja

## Recommended Posts

• 0

AAABBB

AAAABBB

AAABBBB

AAABBBB

AAABB

AAAAAA

AABBBBB

ABBAAAB

AAAABBB

BBBBB

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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

just equal areas

##### Share on other sites

• 0

AAABBB

AAAABBB

AAABBBB

AAABBBB

AAABB

AAAAAA

AABBBBB

ABBAAAB

AAAABBB

BBBBB

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

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

• 1

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.