Hulver's site || The Home of Lonely White K5ian Geeks Who Browse Teh Intarweb A Lot

Diaries
Everything
Who's Online?
FAQ / Help

Quick question for everyone:

By ambrosen (Tue Apr 12, 2011 at 01:57:00 PM EST) puzzles, teh riddlar, old school stuff, centipede full of blackboard chalk, slide rule loving cowqqas (all tags)

It's been a while since we've had any puzzles here, and a tiny little maths problem struck me while reading the description for a laptop bag.

It may be trivial to some of you, it may be a tricky one to work out in the mind, or it may even need a minute or two with a pen and paper, but it's got me wondering.

So, what's the smallest rectangle by area in which you can fit any rectangle having a diagonal of length n.

Obviously the upper bound is an n×n square, and the lower bound a √2n×√2n square, but I'm having to use my brain in ways it's not used to in order to find the the answer. I refuse to break out the pen and paper.

Post any answers in comments, but please put them in spoilers. Quick reminder on how to write spoilers: type "((spoiler your text))". Sorry, I don't know if they work in the fancy editor.

< PC Upgrade: Trials and Tribulations | Puttin' on the Ritz >

Login

Poll

Votes: 2
Results	\|	Other Polls

Related Links

- ambrosen's Diary

Hit Counter

84 Husi users have viewed this.

Comment Controls

Quick question for everyone: | 35 comments (35 topical, 0 hidden)

On the back of a envelope, by ni (4.00 / 2) #1 Tue Apr 12, 2011 at 03:43:23 PM EST

I suggest:
(n^2)/2

This envelope is too small to contain the proof.

"These days it seems like sometimes dreams of Italian hyper-gonadism are all a man's got to keep him going." -- CRwM

Handwaving proof by ni (2.00 / 0) #3 Tue Apr 12, 2011 at 04:33:55 PM EST

contained here, since multiline spoilers don't seem to be an option. Help with the derivative thanks to one Isambard Kingdom Brunel, as after having written 15 pages of molecular genetics papers today basic calculus seemed beyond me.

"These days it seems like sometimes dreams of Italian hyper-gonadism are all a man's got to keep him going." -- CRwM

[ Parent ]

That's what I got also. by ana

(2.00 / 0) #4 Tue Apr 12, 2011 at 04:52:47 PM EST

And then I started worrying about whether there's an angled way of putting the long skinny rectangles in, so that the long side of the briefcase doesn't have to be as big as n. But I don't think that helps.

"And this ... is a piece of Synergy." --Kellnerin

[ Parent ]

We don't have to worry about that by ni (2.00 / 0) #5 Tue Apr 12, 2011 at 05:04:19 PM EST

because for any n, the rectangle that occupies the greatest area is a square (shown on line 26 of the previous post). Long skinny rectangles are not our limiting case, so we don't have to be concerned about what angle they're on: they will always occupy less area than a square of equal n. (Obviously altering the angle of the square doesn't get you anywhere.)

"These days it seems like sometimes dreams of Italian hyper-gonadism are all a man's got to keep him going." -- CRwM

[ Parent ]

this is wrong by gzt (2.00 / 0) #13 Wed Apr 13, 2011 at 10:49:16 AM EST

has biggest area, but not everything will fit in it.

[ Parent ]

in fact... by gzt (2.00 / 0) #14 Wed Apr 13, 2011 at 10:50:33 AM EST

...none of the others will.

[ Parent ]

You're misunderstanding. by ni (2.00 / 0) #19 Wed Apr 13, 2011 at 11:00:32 AM EST

They will not fit in that specific square, no. But they will fit in some rectangle with equal n -- themselves, if nothing else -- and it provably has an area less than the square (since the square has the greatest area for a given n).

"These days it seems like sometimes dreams of Italian hyper-gonadism are all a man's got to keep him going." -- CRwM

[ Parent ]

this post is even more mysterious. by gzt (2.00 / 0) #21 Wed Apr 13, 2011 at 11:56:25 AM EST

I'm not disputing that. I suspect we're answering different questions, given how wrong I think your answer is.

[ Parent ]

I believe so. by ni (2.00 / 0) #24 Wed Apr 13, 2011 at 12:16:51 PM EST

Yes, actually, I think we might be. I suspect you are looking for the smallest single rectangle in which all others of equal n fit, while I am finding the smallest area sufficient to contain all rectangles of equal n. The question is ambiguous about which is asked for, I suppose. If one is to take the inspiration of laptop cases (which are not moldable) into consideration, yours may be the more accurate, although asking for area (instead of fixed dimensions) specifically makes it unclear.

"These days it seems like sometimes dreams of Italian hyper-gonadism are all a man's got to keep him going." -- CRwM

[ Parent ]

Or to rephrase, by ni (2.00 / 0) #25 Wed Apr 13, 2011 at 12:23:11 PM EST

I am giving the area of an unknown rectangle which I can be certain will contain the rectangle. You are aiming for the area of a known rectangle which you can be certain will contain all possible rectangles.

"These days it seems like sometimes dreams of Italian hyper-gonadism are all a man's got to keep him going." -- CRwM

[ Parent ]

: Good old quantifier scope ambiguity, eh? by ambrosen (2.00 / 0) #27 Wed Apr 13, 2011 at 12:27:47 PM EST

Yeah, known rectangle and all possible rectangles is a much clearer way to put it.

[ Parent ]

gzt's is the question I was asking, I'm afraid. by ambrosen (2.00 / 0) #26 Wed Apr 13, 2011 at 12:25:27 PM EST

But I understand where I was unclear. I asked for area because that's the only scalar value I could think of to compare rectangles by. I guess minimising the perimeter would be a goal, too.

[ Parent ]

well, the 0×n rectangle does. by ambrosen (2.00 / 0) #28 Wed Apr 13, 2011 at 12:29:53 PM EST

If you choose to call that a rectangle.

[ Parent ]

: i was halfway through a comment noting that by gzt (2.00 / 0) #30 Wed Apr 13, 2011 at 12:40:38 PM EST

but n - ε x ε doesn't.

[ Parent ]

There is. by gzt (2.00 / 0) #16 Wed Apr 13, 2011 at 10:53:58 AM EST

Draw a circle.

[ Parent ]

Trying to get spoilers to work... by gzt (2.00 / 0) #17 Wed Apr 13, 2011 at 10:56:05 AM EST

... is this how spoilers work?

[ Parent ]

: Awesome. by gzt (2.00 / 0) #18 Wed Apr 13, 2011 at 11:00:26 AM EST

the proof doesn't work - draw a circle and draw a diameter. make the square from that diameter. then pick another point on the circle and, using it, make the rectangle. that rectangle cannot fit inside the square because both have a diagonal of n. so you need something bigger than will fit inside the circle. no rectangle inscribed in the circle will fit into any other.

[ Parent ]

Well, the longest, skinniest rectangle by ambrosen (2.00 / 0) #23 Wed Apr 13, 2011 at 12:13:06 PM EST

fits in an n/√2 by n/√2 square at an angle of π/4, so I think it's fair to assume that you can get a height of less than n.

[ Parent ]

Right. by ana

(2.00 / 0) #29 Wed Apr 13, 2011 at 12:34:01 PM EST

One answer that may not be the absolute smallest is a rectangle with a base of length n and a height of length n/sqrt(2), as other people have proposed. That makes it high enough to accommodate the square, and any non-square rectangle will fit because the 45-degree sector of radius n is inscribed within my brief-case rectangle. It would take some playing around with angle parameters to see if there's a tighter-packing solution.

"And this ... is a piece of Synergy." --Kellnerin

[ Parent ]

: yeah, I think the length... by gzt (2.00 / 0) #31 Wed Apr 13, 2011 at 12:56:08 PM EST

...can be smaller, but I can't get a rigorous answer at the moment. so we have an upper bound.

[ Parent ]

(Comment Deleted) by gzt (2.00 / 0) #12 Wed Apr 13, 2011 at 10:48:07 AM EST

This comment has been deleted by gzt

[ Parent ]

I'm missing info by garlic (2.00 / 0) #2 Tue Apr 12, 2011 at 03:50:15 PM EST

Are you assuming that the internal rectangle will only be at right angle orientation to the external rectangle, or that it fits at any orientation?

a rectangle's diagnal is the sqrt of the sum of the squares of it's sides. a rectangle of diagnal n can have either alpha height and beta width, or beta width and alpha height. If you're assuming the orientation of the external and internal rectangles cannot be changed, then the internal rectangle will fit in an n diameter circle, and thus an nxn square. Otherwise it'll fit in it's width by height sized rectangle, i.e. itself. Also, FUCK.

(Comment Deleted) by gpig (2.00 / 0) #6 Tue Apr 12, 2011 at 05:42:50 PM EST

This comment has been deleted by gpig

Never mind by gpig (2.00 / 0) #7 Tue Apr 12, 2011 at 05:45:32 PM EST

Thought I'd cracked it but my solution was actually bollocks. As you were.
---
(, ,') -- eep

[ Parent ]

Actually by gpig (2.00 / 0) #8 Tue Apr 12, 2011 at 05:51:50 PM EST

No it wasn't .... here we go again.

This will be easier to get if you draw it.

Fitting a rectangle in another is equivalent to fitting the cross describing the diagonals inside the outer rectangle, since rectangles are convex. Superimpose all such possible crosses, with the centres aligned, and we get a circle of diameter n.

Now take one of the radii of the circle which touches the square. All diagonals with an angle of more than π/4 from this radius can be discarded, since they have an equivalent with an angle of less than π/4. Using this to truncate the enclosing square, we get a rectangle with sides n and √2n.

Not a rigorous proof that this is minimal, but it feels right.
---
(, ,') -- eep

[ Parent ]

Duh by gpig (2.00 / 0) #9 Tue Apr 12, 2011 at 05:53:25 PM EST

Obviously in that last paragraph I meant √2n/2.
---
(, ,') -- eep

[ Parent ]

Duh again by gpig (2.00 / 0) #10 Tue Apr 12, 2011 at 05:56:50 PM EST

Missed the 'by area' bit, my solution gives √2n²/2, somewhat unsurprisingly.
---
(, ,') -- eep

[ Parent ]

I agree with you. by gzt (2.00 / 0) #20 Wed Apr 13, 2011 at 11:19:05 AM EST

though I'm just doublechecking that the worst-case rectangle doesn't fit in a smaller one.

[ Parent ]

I didn't have the time I thought to look at this by ambrosen (2.00 / 0) #22 Wed Apr 13, 2011 at 12:08:05 PM EST

when I posted it, but I've got Excel to give me n/√2 by 0.884618n by simulating for a range of numbers, but I can't find any reason for that. I was assuming that something related to √3/2 would jump out at me when I did that, but it didn't, so that's a pretty unsatisfying answer, and I'll have to go back to the drawing board on this.

I'm not sure why I thought it would be so easy.

[ Parent ]

: well... by gzt (2.00 / 0) #32 Wed Apr 13, 2011 at 01:06:40 PM EST

...I think you can get less than cos(π/8).

[ Parent ]

Furthermore by gpig (2.00 / 0) #11 Tue Apr 12, 2011 at 06:05:59 PM EST

ni's proof looks reasonable, so I guess my intuition was wrong ....
---
(, ,') -- eep

[ Parent ]

: his proof is wrong by gzt (2.00 / 0) #15 Wed Apr 13, 2011 at 10:52:09 AM EST

draw a circle to see why.

[ Parent ]

Intuitive Guess by anonimouse (2.00 / 0) #33 Thu Apr 14, 2011 at 05:27:35 AM EST

A rectangle with a diagonal of length n can be:

n x 0
to
√2n x √2n

The nx0 line object can be fitted diagonally into the √2n square, so I suspect that all rectangles with diagonal n can be fitted in at some angle into the √2n square.

Girls come and go but a mortgage is for 25 years -- JtL

: Afraid not by ambrosen (4.00 / 1) #34 Thu Apr 14, 2011 at 06:22:15 AM EST

Only the n/√2 square and the n×0 rectangle fit in. For any others, the diagonal n can't line up with the diagonal of the n/√2 square.

[ Parent ]

Dunno by nebbish (4.00 / 1) #35 Fri Apr 15, 2011 at 08:30:22 AM EST

--------
It's political correctness gone mad!

Quick question for everyone: | 35 comments (35 topical, 0 hidden)