Tiling a rectangle: Another surprisingly tricky problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Thu Aug 05, 2010 5:47 pm UTC

Problem wrote:Call an m*n rectangle proper if either m or n (or both) is a whole number. Show no improper rectangle can be tiled by proper rectangles.

The second sentence means that there's no collection of proper rectangles that don't overlap except on their boundaries and whose union is an improper rectangle.

(I have a soft spot for "cute" problems that can be solved using seemingly unrelated ideas or techniques. What charms me about this problem is that I've seen two such solutions for it, and they are completely different! I'm sure you guys will find a bunch more...)

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby z4lis » Fri Aug 06, 2010 2:07 am UTC

Spoiler:
Let's call one direction for the rectangles edges "vertical" and the other "horizontal". Consider the vertical edge of the large rectangle. This edge is composed of several smaller edges of the tiling rectangles. Since this large edge is not a whole number, at least one of the vertical edges of the tiling rectangles must also be a non-whole number. Call this rectangle R. Since that rectangle's vertical edge is not a whole number, the other edge must be a whole number. That is, the horizontal edge. We may then draw a vertical line through the vertical edge of R that is not on the vertical edge of the large square to divide the large rectangle into two pieces, one of which does not contain R. Now, if the subrectangle that does not contain R is "trivial", in that the other edge of R lies on the other edge of the large rectangle, then the horizontal length of the large rectangle must be a whole number, which is a contradiction.

We now consider this smaller rectangle. The edges must not be whole numbers, so it is improper. The tiling on it inherited from the original rectangle must also be proper, since the changes in either of the edge lengths is by whole numbers. Finally, note that every rectangle in this tiling was present in the old tilling, and so the size of our tiling has decreased. Continuing this inductively, we must eventually arrive at an improper rectangle tiled by a single proper rectangle, which cannot happen.

An amazing illustration:

tiling.jpg
tiling.jpg (8.19 KiB) Viewed 5904 times
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Mike_Bson » Fri Aug 06, 2010 6:01 am UTC

Spoiler:
The only one I can think of is this: let's say that our two rectangles are AB and CD. CD is the proper rectangle that you want to tile AB with. The dimensions of AB are a*b, and CD is c*d, respectively. Let's say, for example, when we are tiling, sides of the length c will be parallel with the sides of a, and d with b. Now that we have that out of the way: if we are attempting to tile so that a certain amount of CDs that go perfectly into AB, then since a is parallel to c and b to d, c must go into a (via division of the lengths) and d into b, or else you'd have to cut off part of the rectangle. Since either a or b are not whole numbers, and c and d are both whole numbers, this means that either c cannot go into a OR d cannot go into b, the rectangles would not be able to tile perfectly.


I came up with this is a fraction of a second, I wonder why it took so much to type it out.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby gmalivuk » Fri Aug 06, 2010 6:15 am UTC

Mike_Bson: the tiling is not meant to be done with a collection of *identical* rectangles, just ones that are all proper.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Mike_Bson » Fri Aug 06, 2010 6:18 am UTC

gmalivuk wrote:Mike_Bson: the tiling is not meant to be done with a collection of *identical* rectangles, just ones that are all proper.

Oh, dang. I guess this is a really tough one, then.

EDIT-
Spoiler:
I guess I really could say that c and d would be variable, but always natural, and any natural numbers cannot be added to make a non-natural number.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby jaap » Fri Aug 06, 2010 6:38 am UTC

z4lis, there is a gap in your proof.
Spoiler:
z4lis wrote:We now consider this smaller rectangle. The edges must not be whole numbers, so it is improper. The tiling on it inherited from the original rectangle must also be proper, since the changes in either of the edge lengths is by whole numbers.

This is not necessarily the case. It is as if you are assuming that all the rectangles your cut goes through touch the left boundary, or at the least have an integer x coordinate. If a rectangle dissected by your cut has an x coordinate (of the left hand side) that is not an integer, then the part left over need not be a proper rectangle any more.

I don't have my own proof. I have read two entirely different proofs of it, but I don't remember enough detail to reproduce either.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby WarDaft » Fri Aug 06, 2010 7:46 am UTC

Spoiler:
It seems fairly obvious that a "proper" rectangle or rectangular tiling thereof can be tiled by other proper rectangles, and greedily at that. So, all we should need to do is make a series of the largest proper rectangles we can (there will actually only be two) and show that there is some bit that is necessarily smaller than any proper rectangle left over.

Is it more difficult than I suspect to prove there are no proper rectangles or rectangular tilings thereof that cannot be tiled in any other way?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
MartianInvader
Posts: 808
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby MartianInvader » Fri Aug 06, 2010 9:28 am UTC

I must be missing something in this problem. Why don't we just say
Spoiler:
If we have a big m-by-n rectangle tiled by proper rectangles, the sidelength of the big rectangle is a sum of certain sidelengths of the proper rectangles. A sum of whole numbers is a whole number, thus m and n are whole numbers, QED
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby t1mm01994 » Fri Aug 06, 2010 9:58 am UTC

the part your missing is "either" in the original statement. Not both sides have to be integers, just m OR n, with OR the inclusive or.
My vote is for
Spoiler:
infinite descent, or something of that kind. If we place a rectangle anywhere, we can divide the remaining figure in 2 rectangles, always with at least 1 improper one [/HUGE HANDWAVE]. So, the dimensions keep on getting smaller, and smaller, and smaller. Thereby we can conclude that there is a point where a dimension is lower than 1, and thereafter, the other side will get smaller than 1 too. That can't be tiled with integer sides.


Sorry for handwavyness, but this was the first I thought of.. There's probably some big mistake in it.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Fri Aug 06, 2010 11:44 am UTC

Do we need to worry about infinite tilings and/or rotated rectangles?

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Tirian » Fri Aug 06, 2010 11:59 am UTC

There isn't necessarily a line cleanly fracturing the larger rectangle. It could look something like this:

Code: Select all

*********
*    *  *
******  *
* *  *  *
* *******
* *     *
*********


Spoiler:
I'm tempted to think of the problem as related to finding perfect rectangles that can be decomposed into squares of different non-integral sizes, particularly the formation of the Smith diagram which is a digraph where the vertices represent the horizontal line segments in the decomposition and arcs are the vertical lines with labels representing their "potential drop". One might imagine forming such a diagram for our problems and then coloring the vertices and arcs if their corresponding lengths were integral, and then somehow showing that either the source and sink vertices were colored or that there was a path connecting them made up only of colored arcs. There is a subrectangle corresponding to every arc of the digraph and obviously if its height were integral then it would be colored, but I can't see without my morning caffeine how it would impact the digraph knowing that its width were the integral component.

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Syrin » Fri Aug 06, 2010 12:35 pm UTC

Torn Apart By Dingos wrote:Do we need to worry about infinite tilings and/or rotated rectangles?

No, because an infinite case is identical to a finite case (as it must be tiled by proper rectangles, and at least one side of a proper rectangle is at least 1) - and as such, a tiling by rotated rectangles wouldn't be possible (because that would have to be exclusively infinite).

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Fri Aug 06, 2010 1:00 pm UTC

Syrin wrote:No, because an infinite case is identical to a finite case (as it must be tiled by proper rectangles, and at least one side of a proper rectangle is at least 1)
I don't understand your reasoning.

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Syrin » Fri Aug 06, 2010 1:11 pm UTC

Torn Apart By Dingos wrote:
Syrin wrote:No, because an infinite case is identical to a finite case (as it must be tiled by proper rectangles, and at least one side of a proper rectangle is at least 1)
I don't understand your reasoning.

Well, think about it - is there any infinite tiling that could not be done the same way by finite tiling of proper rectangles?

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Fri Aug 06, 2010 1:22 pm UTC

What do you mean by "done the same way"? Yes, a hypothetical tiling using rotated rectangles.

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby greengiant » Fri Aug 06, 2010 6:37 pm UTC

I've got a neat proof of this, but to be fair I've seen something a bit similar before.
Spoiler:
It's easiest to see with pictures, but this should give you the general idea.

Take the improper rectangle you wish to tile and put a checkerboard pattern on it using squares of size 0.5 units, starting with a white square at the top left. Since the sides of the rectangle are not whole numbers, more of the rectangle is now coloured white than black.

Consider any proper rectangle. Since one side has integer length, no matter how you offset it on the checkerboard, there will always be equal amounts of each colour within the rectangle.

Therefore you cannot tile the improper rectangle with proper rectangles since there's no way to introduce the colour disparity.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Talith » Fri Aug 06, 2010 6:43 pm UTC

Is it possible to prove that there always exists at least one path from one corner of a tiled rectangle to another taking only paths along the integral edges of the proper sub rectangles. If you can, then it would imply that both of the corners are on grid points on an integer grid and so are integer distance apart.

I've tried to create counter examples but can't seem to make a tiling starting in one corner of a rectangle which can't be traversed on the integer lengths. I'll keep working on it though :D. If someone sees a counter-example or an insight into a proof please share.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Fri Aug 06, 2010 6:47 pm UTC

Talith: I had that idea too, but it doesn't seem to be true.

NEW EDIT: That approach seems to work! Proof:
Spoiler:
Assume that a big rectangle is tiled by finitely many proper rectangles. I'll prove that we can move along a path from one corner to another along full integer sides of proper rectangles only, proving that one side of the big rectangle must have integer length. All proper rectangles have two opposite integer-length sides, color these red (in case a rectangle has four integer sides, chose any two opposite sides). Each corner of a rectangle coincides with exactly one or three other corners of other rectangles, except in the case when the corner is a corner of the big rectangle. So if we enter an "inner" corner along a red line, we can exit it along another red line. If we start from one corner of the big rectangle (which we can never return to) and walk along red sides of rectangles, using no side twice, we will leave each "inner" corner equally many times that we reach it, and the path must end at another corner of the big rectangle.


(I'm still not sure that an infinite tiling would not work, though.)

Newer edit: This proof is exactly the same as greengiant's below. :)
Last edited by Torn Apart By Dingos on Sat Aug 07, 2010 10:51 am UTC, edited 8 times in total.

greengiant
Posts: 272
Joined: Thu Jul 09, 2009 9:26 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby greengiant » Fri Aug 06, 2010 8:30 pm UTC

Nice idea, think it's doable too.

Spoiler:
Sorry for the rough and ready nature of the proof again.

Code: Select all

So, you've got some rectangular tiling of proper rectangles. Create a multigraph whose vertices are the corners of the tile rectangles. For each of the tile rectangles, add two edges to the graph. The edges should correspond to the two parallel integer sides of the tile (if both dimensions of the tile are integers, simply pick one dimension and use the two sides of that length). So, for each tile
 ____________
|           |
|           |
|___________|

you either end up taking

___________
                   
                   
___________

or

|           |
|           |
|           |

and whichever two you take definitely correspond to integer sides of the tile.

Claim:Each of the four corners of the tiling becomes a vertex of degree 1 and ever other vertex has even degree greater than or equal to 2

Proof: The corners are trivial since each of them is on one tile and hence has one edge going from it.

Any other vertex is the meeting of either two three or four tiles.

Two tiles:

         |
         |  Tile A
Outside  |____________
         |
         |  Tile B

Then obviously the vertex is of degree 2 since it gets an edge from each of the tiles. (Note: in this picture, it might use the horizontal side of both tiles, but this would make two separate edges on the multigraph)

Three tiles:

         |
         |  Tile A
Tile C   |____________
         |
         |  Tile B


Vertex is still of degree 2. Since it's not a corner of Tile C, it doesn't get any edges from tile C, so same as case above

Four tiles

        |
Tile A  | Tile B
________|_________
        |
Tile C  |  Tile D

Then in this case the vertex will have an edge from each of the four tiles and will have degree 4.

End of Proof

Now simply start a walk from one of the corners on this graph. As long as you never repeat an edge, you'll have to end up at one of the other corners. Since the edges correspond to integer sides of tiles, that means you can get from corner to another corner just using integer sides.


Edited to fix formatting of 'diagrams'

User avatar
OverBored
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby OverBored » Sat Aug 07, 2010 10:41 am UTC

greengiant wrote:Consider any proper rectangle. Since one side has integer length, no matter how you offset it on the checkerboard, there will always be equal amounts of each colour within the rectangle.



I thought this was the case for a while, but it does depend where you put it. For example, the 3x3 rectangle can have more white, more black, or equal amounts by offsetting it by 0, 1 and 0.5 respectively.
Apparently 0.5 =/= 1.
Who knew?!


The other proof is fine, I think, and quite clever. I would quite like to see the OP's proofs though.
Last edited by OverBored on Sat Aug 07, 2010 11:17 am UTC, edited 1 time in total.
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Sat Aug 07, 2010 10:56 am UTC

OverBored: A 3x3 rectangle can be decomposed to nine 1x1 rectangles, and each of these have equal amounts of white and black no matter how we offset them. I think that proof is fine, and the upside of that one is that it doesn't need to assume a finite tiling (it assumes there are no rotated rectangles though, but depending on how you interpret the problem, this might not be allowed anyway).

User avatar
OverBored
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby OverBored » Sat Aug 07, 2010 11:16 am UTC

Sorry, being a moron. the rectangles are 0.5 by 0.5. Will edit to reflect this...
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.

User avatar
[Kreativername]
Posts: 18
Joined: Fri Mar 20, 2009 1:57 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby [Kreativername] » Sat Aug 07, 2010 12:57 pm UTC

EDIT: I misread the problem because I somehow thought "whole number"="even number" so I solved an entirely different (and apparently much easier) problem.

Spoiler:
Call any 1*1 rectangle a unit square. Then any improper rectangle will cover an uneven number of unit squares whereas any proper rectangle will cover an even number of unit squares.
Any combination of proper rectangles will cover an area that is the sum of the areas covered by the individual rectangles and this combined area will therefor also cover an even number of unit squares. It follows that no combination of proper rectangles can tile any shape that covers an uneven number of unit squares. And this includes improper rectangles
Last edited by [Kreativername] on Sat Aug 07, 2010 2:51 pm UTC, edited 1 time in total.
@agitpopblog wrote:I'm a cat in a steel chamber with a Geiger counter, a bit of radioactive substance and hydrocyanic acid. I am the 50 percent!

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Syrin » Sat Aug 07, 2010 1:33 pm UTC

[Kreativername] wrote:Call any 1*1 rectangle a unit square. Then any improper rectangle will cover an uneven number of unit squares whereas any proper rectangle will cover an even number of unit squares.

What about the proper 1x1 rectangle? Or 1x3?

georgehorse
Posts: 12
Joined: Sat Dec 08, 2007 5:11 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby georgehorse » Sat Aug 07, 2010 2:16 pm UTC

Syrin wrote:
[Kreativername] wrote:Call any 1*1 rectangle a unit square. Then any improper rectangle will cover an uneven number of unit squares whereas any proper rectangle will cover an even number of unit squares.

What about the proper 1x1 rectangle? Or 1x3?

I think 'even' is meant to be read as 'a whole number', not 'divisible by two'. Though the statement would still be false.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Sat Aug 07, 2010 5:27 pm UTC

OverBored wrote: I would quite like to see the OP's proofs though.

Mine were exactly the checkerboard proof given by greengiant, and the graph proof given by Torn Apart by Dingos and greengiant. :D

I've also seen another version of greengiant's checkerboard proof.
Spoiler:
Instead of the checkerboard coloring, which we can think of as a function that assigns 1 to white checkboard regions and -1 to black ones, use the function f(x,y) = cos(x/pi) cos(y/pi). This function also has the property that its integral is zero over any axis-aligned proper rectangle, and is not zero on some shift of any improper rectangle. Many proofs that a region cannot be tiled can be stated in this form: create a function that have total value 0 over any tile but is not zero over the full region.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Talith » Sat Aug 07, 2010 5:48 pm UTC

I managed to prove it using the path method eventually last night too, so I'm happy I didn't see any hints on here before I finished it. Thanks for these fun problems aleph_one, keep them coming please.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Sun Aug 08, 2010 12:12 am UTC

aleph_one: Nice trick!

Talith: Thank you for making to reexamine my counterexample, I had given up on that approach. :) (Though I thought that you could do it by only going right and up from the bottom left corner, which I had a counterexample to - but when I examined it, I realized that it might work if we lose that restriction.)

But still, guys, why can we assume the tiling is finite? Am I missing something obvious here?

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Sun Aug 08, 2010 12:22 am UTC

Torn Apart By Dingos: There checkerboard argument works to rule out an infinite tiling. The path argument carries through as well, with a bit of thought.
Spoiler:
Sure, there are infinite number of vertices, but the ones you can reach can only have whole-number displacements, of which there can be a finite number in the rectangle. Since there are at most two edges between any two vertices, any walk on the reachable component of this graph must be finite and therefore eventually reach a corner.
I don't know of an a priori way to rule out an infinite tiling.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Qaanol » Sun Aug 08, 2010 1:31 am UTC

I found this problem quite interesting, and the solutions clever as well. To me, the checkerboard argument is more intuitive and simpler to understand. However, on further thinking, the edge-length argument is more general.

For example, suppose we define a rectangle to be semi-proper if it has at least one edge with length of the form [imath](a+b\sqrt{2})[/imath] for nonnegative integers [imath]a[/imath] and [imath]b[/imath] not both zero, and want to prove that rectangles which are not semi-proper cannot be tiled by semi-proper rectangles.
wee free kings

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Sun Aug 08, 2010 2:27 am UTC

Indeed, the edge-length argument works for any set of numbers closed under addition and subtraction (additive subgroups of R), such as Z, Q, the terminating decimals (in any base), and algebraic number fields.

Edit: Qaanol, I just noticed that you're restricting to a+b*sqrt(2) where a and b are nonnegative. Does the proof carry through here?
Spoiler:
If the path meander backwards, it can lead to a total displacement that might have a or b negative.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Talith » Sun Aug 08, 2010 2:51 am UTC

Shouldn't you be careful when generalising the problem? For example, suppose you want to tile a rectangle with irrational side length, using tiles of at least one rational side length. In this case, the question needs to be stated more clearly because the tiles aren't now limited to having it's restricted edge of a minimum size (in the original problem, one unit).

So in the above example, if the rectangles are closed, then we can't cover the irrational rectangle . However, if the rectangles are open, we can tile any irrational rectangle with rational tiles by taking a sequence of rectangles whose sum tends to the irrational rectangle.

I'm guessing that this open and closed case also holds for any metric space and it's completion. Of course, both cases become impossible if we're restricted to finite collections of tiles.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby antonfire » Sun Aug 08, 2010 3:01 am UTC

Here is a variation on the path approach:
Spoiler:
Hilight all the integer length edges in the tiling. If the rectangle is improper, the four corners must not by connected to each other by this set. So we can draw a curve that separates one corner from the rest. This curve must enter the rectangle through a vertical edge and exit through a horizontal one. But when in enters a small rectangle in the tiling, it must exit through the opposite edge, so it can only intersect edges of one orientation!
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Sun Aug 08, 2010 3:10 am UTC

Talith: You're right, I was only considering the finite problem, which is the one I originally intended. (Thankfully, the original problem holds in the infinite case as well.)

antonfire:
Spoiler:
How clever! But it's not clear to me there's a separating curve, since integer-length edges in different graph components can overlap geometrically. Can you account for this?

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby antonfire » Sun Aug 08, 2010 3:30 am UTC

Ah yeah, oops. It's so easy to fall prey to pretty solutions.

No, I don't have a nice salvage right now. Once you start taking into account that structure you can't get much simpler than the original argument.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Torn Apart By Dingos » Sun Aug 08, 2010 10:36 pm UTC

aleph_one wrote:Torn Apart By Dingos: There checkerboard argument works to rule out an infinite tiling. The path argument carries through as well, with a bit of thought.
Spoiler:
Sure, there are infinite number of vertices, but the ones you can reach can only have whole-number displacements, of which there can be a finite number in the rectangle. Since there are at most two edges between any two vertices, any walk on the reachable component of this graph must be finite and therefore eventually reach a corner.
How do you define "reachable" points in an infinite tiling? Suppose you start in the bottom left corner of the big improper rectangle. This point must be part of some proper rectangle in the tiling, and it must be a corner of this rectangle. Then follow along one integer side of this rectangle to get to another corner. There's no guarantee that this point touches the edge of another proper rectangle whose side you can follow along, and you seem to be stuck.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Mon Aug 09, 2010 1:14 am UTC

Torn Apart by Dingos: Hmm, good point. I hadn't really considered the subtleties of a corner not being on a rectangle title in one of the directions from it, but a limit of rectangle tiles. I'll see if I can work something out.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Qaanol » Mon Aug 09, 2010 1:36 am UTC

aleph_one wrote:Indeed, the edge-length argument works for any set of numbers closed under addition and subtraction (additive subgroups of R), such as Z, Q, the terminating decimals (in any base), and algebraic number fields.

Edit: Qaanol, I just noticed that you're restricting to a+b*sqrt(2) where a and b are nonnegative. Does the proof carry through here?
Spoiler:
If the path meander backwards, it can lead to a total displacement that might have a or b negative.

I do not understand what you are saying here. Do you claim there exist rectangles whose sides have negative lengths? I am under the impression that length is by definition a positive quantity.

Spoiler:
I am intentionally ruling out trivial rectangles whose “semi-proper” sides have exactly zero length, because those do not meaningfully contribute to a tiling.
wee free kings

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby aleph_one » Mon Aug 09, 2010 1:42 am UTC

Qaanol:
Spoiler:
I'm imagining that if you start at the bottom left corner, the horizontal displacements along the path are 2 units right, sqrt(2) units left, then 2 units right, reaching the top right corner (with vertical displacements in between). From this, we's like conclude that the main rectangle is proper, but the length of the top side is 4 - sqrt(2), which has a=4, b=-1, is not proper by your definition.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Tiling a rectangle: Another surprisingly tricky problem

Postby Qaanol » Mon Aug 09, 2010 2:59 am UTC

Spoiler:
Actually, that isn’t even enough. Because when negatives are allowed, then rectangles can be made arbitrarily small in both dimensions simultaneously, and can thus tile any arbitrary rectangle. So my example of a generalization is flawed.
wee free kings


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests