## Rectangle Tiling Problem

Well,

It has been a long break on this blog, but I am back now and I hope to be regular posting here now on. Anyways, this problem has a long history but recently it was brought to me by sagarmoy .

Problem : Let there be a rectangle of type-A and type-B. type-A rectangle have at least one integral side ( that is length of the side is integer ) and type-B rectangle have no side of integral length.

1) Prove that from a given instance of a type-A rectangle, it is impossible to tile up these rectangle and make a big type-B rectangle

2) Prove that there is no way of tiling up (any) type-A rectangles to make a big type-B rectangle.

Solution :

It is easy to see tha version 1 of the question is a special case of version 2.

1) we have a specific type-A rectangle. so let it have two sides i ( integral ) and r (rational )

Suppose we have made a type-B rectangle using this type-A rectangle. Then the sides of type-B rectangle is

m1i + n1r, m2i + n2r , where m1,m2,n1 and n2 are positive integers. Area of the big rectangle should be equal to the area of the sum of the smaller rectangles.

$m1m2i^2 + m1n2ir + n1m2ir + n1n2r^2 = kir$ where, $k$ is the total number of tiles used to form bigger rectangle.

r being a rational can be written in a form p/q where p and q are integers which are relatively prime. So

$m1m2i^2 + (m1n2 + n1m2)i(p/q) + n1n2(p/q)^2 = ki(p/q)$

Multiplying by q

$m1m2i^2q + (m1n2 + n1m2)ip + n1n2p^2 / q = kip$

Right hand side of the equation is an integer. Also, first and second term of the left hand side is also clearly an integer.  To make the equation correct q has to divide n1 or n2 because it can not divide p ( remember that p and q are  relatively prime ). Without loss of generality, let us say q divides n1 then the side with length

m1i + n1(p/q ) becomes an integer ( as q divides n1 ).

2) Frankly speaking, none of us ( me, deepanjan and sagarmoy ) could come up with a proof for this second case. However, an interesting compilation of 14 different proof of this version is available at :

http://www.jstor.org/stable/2322213?seq=1

Those of you who are not subscribed to this journal, I am writing down one proof mentioned in that link which I found as most elegant.

Let our big rectangle R be aligned in a way such that bottom-left corner co-incide with (0,0), and the sides are aligned with x and y axis. Let T be the set of constituent tiles ( of type A ).

Let S = { (x,y) | x and y are integers, (x,y) is a corner of some tile in T }

We can draw a bipartite graph now with S and T forming two partitions of this graph. There is an edge from $s \in S$ to $t \in T$ if and only if tile t is having s as one of its corner. As all tiles in T are of type-A ( one integer side ), all tiles should have either 0,2 or 4 neighbours in S. Total number of edges between S and T has to be even. Each point in S which is not a corner of R will have 2 or 4 neighbours in T.

Note that (0,0) has only one neighbour in T, to make total number of edges even, there has to yet another point in s which lies on odd number of tiles.  Clearly, this point s has to be another corner of R ( so as to have only one neighbour in T ). If R has any other corner apart from (0,0) in S then R must have width or height of integer size.

There is one proof mentioned in the linked article which works like a magic, comes out of thin air. I won’t call that proof very elegant, but it really requires imagination to come up with such a proof. But I guess, I will mentioned that proof in some alter post.