zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

I'll try to tackle this by the following:

Since we're given a rectangle divided into smaller rectangles, we know that each side of the given rectangle is composed of some finite number of the sides of smaller rectangles. Since every smaller rectangle has integral sidelengths, the sum of integers is also an integer, and thus the sidelength of the large rectangle is an integer.

____________________________

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

You got the puzzle wrong... each small rectangle must have at least one side that's an integer, but that doesn't mean that both height and width are integers. One could be a non-integer.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

Whoops...I saw sides, not a side. Back to the thinkingboard.

____________________________

Drgamer
Level: Master Delver
Rank Points: 113
Registered: 09-09-2006
IP: Logged

UrAvgAzn wrote:

Schik wrote:
I'll guess the gardener. If we assume the garden is outside, then why is she watering the plants if it's "dark and stormy"?

Good job Schik! Your turn. So I'll just +1 that post since it's already +1ed. Okay, so did I do it right?

Keep posting,

Not to be rude or anything, but there are such a thing as INDOOR plants...

However, the dog's excuse has one flaw: No cat was ever mentioned...

Was the cat in the pound at the time or something?

MartianInvader
Level: Master Delver
Rank Points: 126
Registered: 01-30-2004
IP: Logged

michthro wrote:
Ok, here's one of my all-time favourites:

Given a rectangle R divided into smaller rectangles, prove that if every smaller rectangle has a side of integral length, then R has a side of integral length.

Wow! This is a tough one! I'm guessing there's some trick to this that I'm just not seeing... I'll keep thinking about it...

Anyone interested in a partner deal on this one? You prove the big rectangle has at least one integral side, and I'll then prove it has at least TWO integral sides!

____________________________
Yes, I very rarely post. But I DO keep coming back to check the forum.

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

Oh, that is awesome. I haven't quite proven it fully to myself yet, but I'm pretty sure I know what to do. Hopefully I'll be able to post my proof soon.

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

Alright. Secreted because its so awesome, and I don't want to ruin it for anybody that still wants to think about it.

Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged

TripleM wrote:

Click here to view the secret text

×Start at the very top left of the big rectangle. There will be some integer side that starts at this point, so move along that side until we reach the end of that side. Then choose another side of integer length starting at that point, etc.

Its not too hard to see that every point we come across have an even number of options for the next side to choose, apart from the 4 corners of the large rectangle. So after doing the above as many times as possible and making sure we never choose the same side twice, we will be at one of the other 3 corners. Our total x-distance and y-distance are both integers (since we only moved in integer steps). So if we are at one of the right two corners, the x-length is an integer; if at one of the bottom two, the y-length is an integer.

---

[Last edited by Niccus at 11-20-2006 02:05 AM]

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

File: rect2.JPG (3.5 KB)
Downloaded 88 times.
License: Public Domain

edit: I've added a picture demonstrating the idea.

---

[Last edited by TripleM at 11-20-2006 02:16 AM]

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

That's a great idea, TripleM, but sorry, I'm not convinced yet. I'm sure you can make it work, but you'll have to prove:

Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged

I have some idea of how to prove the puzzle by means of its contrapositive (heck, I have sheet of paper filled out with a sort of outline), but I'll have to ask:
What would be a valid contrapositive of the question so that, when proven, proves the that little conjecture?
Would "Given that rectangle R is dissected into smaller rectangles, if all of R's sides are of nonintegral length, then at least one of the smaller rectangles is of all nonintegral lengths / then it is impossible to divide R into smaller rectangles, all of at least one integral length" work?

(or something like that, I don't word well)

On TripleM's proof:

---

[Last edited by Niccus at 11-20-2006 08:07 AM]

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

michthro wrote:
That's a great idea, TripleM, but sorry, I'm not convinced yet. I'm sure you can make it work, but you'll have to prove:

Click here to view the secret text

×That you can avoid going in circles. Or more to the point, there *is* a path between some pair of corners. Having an even number of potential options doesn't imply anything. If you had an odd number of *valid* options everywhere except at the corners, you'd be getting somewhere, but you don't have that. Graph-theoretic connectedness will do. I'm sure disconnectedness implies some invalid rectangle, but prove it. (Well, just an idea - connectedness is more than you need.)

edit -
Double edit - Actually, I'm not sure what you mean at all. I'm 100% convinced of its correctness, though, so I guess I just didn't explain it that well.

---

[Last edited by TripleM at 11-20-2006 08:20 AM]

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Are you not assuming that exactly one side has integral length?

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

Well, OK then.

---

[Last edited by TripleM at 11-20-2006 09:03 AM]

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

EDIT:

EDIT2:

---

[Last edited by michthro at 11-20-2006 09:15 AM]

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

Let me restate exactly the process you go through very precisely:

edit responding to your edit:

---

[Last edited by TripleM at 11-20-2006 09:19 AM]

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

And just to make you slightly more convinced, I've just done some googling and found this, of which the third proof is identical to mine.

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Ok, now that you've explained about choosing sides, but that needed to be done. There's a big difference between the arm-waving in your first post, and the graph you construct in your last post. Well done!

Anyway, if you think that's awesome, how do you like the complex integration proof? That's the reason I like this problem so much.

---

[Last edited by michthro at 11-20-2006 09:37 AM]

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

Why do I get the feeling (after the Grey Labyrinth puzzle hunt thing we worked on, and now this) that we think so much alike

99.9% of puzzles I hear nowadays I have heard of before, and I can't believe I haven't seen that one, with it being so incredibly beautiful.

Anyway, to continue the trend of geometry-style things, how about this:
You have a container of size 2 by n containing 2n tennis balls of diameter 1 packed nicely and rectangularly. (OK, tennis balls are really 3d, but I'm just talking about 2d circles here).

Assuming n is big enough, describe how you could rearrange the balls so that you can fit one more tennis ball in the container. Yes, it is possible (for a big enough n that is)! (For those mathematically inclined, try to work out how big n actually has to be.)

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

hmmm.. I think I know what to do.

A note on the rectangles: I never said *finitely many* smaller rectangles.. Muhahahahaha

Ok, that is what I meant, but for those interested: How about proving it for infinitely many? (It would have to be countable. Proof? Proof without Axiom of Choice?) Going further, the finite version implies the same for "integral" replaced by "rational". How about the infinite rational version? (Probably doesn't make a difference to the proof.)

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

I always get slightly confused when dealing with infinity, but for the integer case I think we can handle it in precisely the same way. The only reachable vertices will be those at lattice points, of which there are finitely many. Each lattice point has at most 4 rectangles with it as a corner, so we also have finitely many edges, and exactly the same proof applies. I think.
That wouldn't work for rationals, of course.

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

Rearrange the balls? Why not just squeeze them to make them more cubical? Say a 0.01 (1%) gain off each side means that with 100 balls in, you can squeeze in 2 more balls without a problem. With bowling balls it wouldn't work, but tennis balls are definitely squeezable...

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

TripleM wrote:
I always get slightly confused when dealing with infinity, but for the integer case I think we can handle it in precisely the same way. The only reachable vertices will be those at lattice points, of which there are finitely many. Each lattice point has at most 4 rectangles with it as a corner, so we also have finitely many edges, and exactly the same proof applies. I think.

Yes, it works. Very elegant.
It seems integral versus rational does make a big difference after all.

Oh, I was wrong about knowing what to do with the balls. With the idea I had I'm only losing ground as n increases.

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

Same here, the only arrangement I can think of gives me sqrt(3) balls per 1 diameter unit of box, but the original arrangement gives you 2 balls per diameter unit.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

MartianInvader
Level: Master Delver
Rank Points: 126
Registered: 01-30-2004
IP: Logged

File: tennisballs.JPG (20.3 KB)
Downloaded 292 times.
License: Public Domain

Okay, I think I've got it. Start by putting four balls together in a hexagonal pattern (which I think is what Maurog was talking about). Then rotate the four-ball group so that the upper-right ball is touching the top of the box, like so (picture not even close to scale, use your imagination):



Do this again on the right with another 4 balls and push it against these 4 until they touch, continue, for the length of the box. I'll get some numbers and post em soon, but I'm pretty sure it works, since the four-formations have parallel "slopes", so when you push them together you'll have both the upper and lower balls touching. Since we're stringing together pairs of balls in a way which always gives us a little better packing than right next to each other (i.e., the balls centers aren't aligned horizontally, so we've got less than two diameters taken up by the pair), this should be more efficient.

EDIT: Okay, after some inane scribblings, I believe I've calculated that the initial four balls take up 1+sqrt(2) diameters, or about 2.414, while each additional block of four adds on another 1.99156 diameters or so. If I got this right, it means that the packing would let you fit in another ball if n were at least 1.99156*(sqrt(2)-1)/(2-1.99156)+2.414, or about 101. How's that sound, TripleM?

____________________________
Yes, I very rarely post. But I DO keep coming back to check the forum.

---

[Last edited by MartianInvader at 11-20-2006 06:54 PM]

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Looks good to me.

Btw, the infinite rational version of the rectangle problem isn't true: Take the square with corners at (0, 0) and (sqrt(2), sqrt(2)), and take an increasing sequence (a_n) of rational numbers that converges to sqrt(2). Divide the square by adding a vertical line through each point (a_n, 0).

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

MartianInvader wrote:
Okay, I think I've got it. Start by putting four balls together in a hexagonal pattern (which I think is what Maurog was talking about). Then rotate the four-ball group so that the upper-right ball is touching the top of the box, like so (picture not even close to scale, use your imagination):

Click here to view the secret text

×

Do this again on the right with another 4 balls and push it against these 4 until they touch, continue, for the length of the box. I'll get some numbers and post em soon, but I'm pretty sure it works, since the four-formations have parallel "slopes", so when you push them together you'll have both the upper and lower balls touching. Since we're stringing together pairs of balls in a way which always gives us a little better packing than right next to each other (i.e., the balls centers aren't aligned horizontally, so we've got less than two diameters taken up by the pair), this should be more efficient.

EDIT: Okay, after some inane scribblings, I believe I've calculated that the initial four balls take up 1+sqrt(2) diameters, or about 2.414, while each additional block of four adds on another 1.99156 diameters or so. If I got this right, it means that the packing would let you fit in another ball if n were at least 1.99156*(sqrt(2)-1)/(2-1.99156)+2.414, or about 101. How's that sound, TripleM?

Very nice.

MartianInvader
Level: Master Delver
Rank Points: 126
Registered: 01-30-2004
IP: Logged

Here's one. Not too tough I think.

This post has a rule. See if you can guess what it is. I think you'll find the rule to be quite a fun one once you get it. As far as I know I made it up, though it could be an old one that I just don't know.
If you think you have it, please make a post of your own that keeps to the rule. I'll let you know which posts get it and which mess it up.


Good luck!

____________________________
Yes, I very rarely post. But I DO keep coming back to check the forum.

---

[Last edited by MartianInvader at 11-21-2006 12:06 AM]

TripleM
Level: Smitemaster
Rank Points: 1377
Registered: 02-05-2003
IP: Logged

Hmm.. I have an idea, but I'm not too sure.. I guess it still works if the key thing is 'six', but other than one word, I would have said 'five'.. if you have any idea what I mean by that.

edit - two words, not one word. Maybe I'm wrong after all.

---

[Last edited by TripleM at 11-21-2006 12:17 AM]

MartianInvader
Level: Master Delver
Rank Points: 126
Registered: 01-30-2004
IP: Logged

TripleM wrote:
Hmm.. I have an idea, but I'm not too sure.. I guess it still works if the key thing is 'six', but other than one word, I would have said 'five'.. if you have any idea what I mean by that.

edit - two words, not one word. Maybe I'm wrong after all.

Hate to say it, but you got it wrong. I know you have great strength of mind, keep at it, and I'm sure you'll get it right! Of course, if I guessed right as to what you thought, then that last bit may have shown you that you're not quite on the right track yet.

By the way, the text that I write in each post will stick to the rule. This does NOT go for things I quote.

____________________________
Yes, I very rarely post. But I DO keep coming back to check the forum.