Archive for July, 2008

Rectangle Tiling Problem

July 31, 2008

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.

Advertisements

Limitation of a data structure

July 5, 2008

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

July 2, 2008

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 \sum_{i=1} ^{n} i = n(n+1)/2. 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