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.

where, 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

Multiplying by q

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 to 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.

Limitation of a data structure

Well,

I must give credit to my favourite professor sundar for this problem.

Problem : Let there be an abstract data structure D. D is a k-Max data structure, in a sense that on performing delete() on this data structure, it returns the k-th largest(Maximum ) element of the elements stored in it. Only two operations are allowed on D, insert(number) and delete(). Obviously, insert(n) will insert the given number n to the data structure.

Prove that, it is impossible to implement D in a way such that both insert(n) and delete() takes O(1) time. Or in other words, any implementation of D will have at most one operation that can perform in O(1). The other operation can not be implemented in O(1).

On sujith‘s request, I am giving a bit more space between the problem definition and solution so that one can avoid accidental peeking :-).

Solution : If someone want a bit of a hint, I would say, the proof goes by contradiction. If ,indeed, we have one such data structure we will defy rules of computational complexity.

Let us assume that we have such a data structure D. and let k=1, that is D is a 1-max data structure, which returns the largest element in D. Also, assume that insert(n) and delete() are both O(1) operations. Now, if I am given n integers. I would insert them one by one. After all insertions I will perform deletions. It is easy to see that this way, I can sort n integers in time O(n)!!!!

It should be fairly easy to see why this is true for any value of k>0. In linear time we can find the largest, say Max, of n integers. I can insert (k-1) dummy integers which are greater than Max in D. And again, I have a linear time sorting algorithm in the worst case!!!

It is a clear contrast to logarithmic lower bound for sorting.

Now we know why we don’t have any such data structure 🙂

— Saurabh Joshi

The ring of numbers

Well,

I am back from my short break, however, will go for another short break in a week’s time. But meanwhile lets get back to business.

Title of this post may be a bit misleading as I am not referring to ring as they appear in number theory. Deepanjan gave me this puzzle yesterday and I could come up with a very simple solution where as his solution was a bit involved.

Problem : Integers from 1 to n are arranged in a circle in some random permutation. Prove that there exist a set of k consecutive  integers on the circle sum of which would be at least k(n+1)/2.

Solution : Set of k consecutive integers can be uniquely specified by the start position and the direction ( clockwise, or counter clockwise ). We will call it a k-box. Because they are arranged in a circular fashion there are n positions. We will assume clockwise direction. For each of these n position compute sum of its corresponding k-boxes. Sum of all these k-boxes would be kn(n+1)/2. The reason is that . and each number will appear in k different k-boxes.

So on average, each k-box makes a contribution of k(n+1)/2. So there exist at least one k-box which makes contribution of at least k(n+1)/2.

Or, in other words. If none of the k-box can make contribution of at least k(n+1)/2 then the total of all k-boxes would be strictly less than kn(n+1)/2 which is a contradiction.

— Saurabh Joshi