OK, probably you already had your latte this morning but here is nice puzzle:

Let's say that a rectangle is "rational" if the ratio between the width and height is a rational number. Now, proof that a rectangle is rational if and only if the rectangle can be completely covered with a finite number of squares. Obviously, the squares must not overlap and must be contained in the rectangle.

A rectangle can be completely covered by squares of size n iff the width w and height h are both multiples of n. (It would take h/n rows of w/n squares to do so.)

Therefore, the rectangle can be covered iff we can find a common divisor n of h and w.

If the rectangle is rational (w/h is rational), there exists some x such that w

x and hx are both integers. (x itself need not be rational.)This is arithmetically equivalent to saying that w/(1/x) and h/(1/x) are integral.

Thus we have shown that for some x, 1/x is a divisor of both w and h.

If we then take a square of length 1/x we will be able to cover the rectangle.

Assume now that the rectangle is not rational. Then there exists no x such that w

x and hx are both integers. Therefore, there is no common divisor of both w and h and there can be no square that will cover the rectangle.It’s not the most rigorous proof, but it’s been a few years since my last math class. π

I rememeber this was one of my elementary school home work.. several decades ago…

Nice, JD. I was getting caught up in the mental image of a rectangle divided up into DIFFERENT size squares.

Your proof assumes a rectangle divided into a whole bunch of same-sized squares.

So can we say for sure that a rectangle that can be divided into a bunch of DIFFERENT sized squares can also be divided into SAME sized squares?

You’d have to prove that all the squares that make up the rectangle themselves have a common divisor.

I rememeber this was one of my elementary school home work.. several decades ago…

BradC: I hadn’t even thought about different sized squares. π

Although from a very cursory thought about it, I’d say that if you could use different sized squares to fill a rectangle, then those squares could themselves be filled with squares with side lengths of some (2,1,1/2,1/3,etc.) multiple of "1/x".

I guess it’s a good thing I didn’t go into math; I’m getting brain strain on this "little" problem. π

I agree that rational –> coverable is relatively easy, as JD showed.

Coverable by same-sized squares –> rational, also.

Let’s explore a rectangle covered by a finite number of different-sized squares.

Case 1) If all the different sizes have a common real divisor, then we can subdivide each big square and we have reduced it to JD’s case above.

(note I am using "common real divisor" in a slightly nonstandard manner. x and y have a common real divisor if we can find a real number z where Az=x and Bz=y where A and B are integers. Note that this divisor could be irrational– 2pi and 3pi have a common divisor of pi. But pi and 2 have no common real divisor, because if we could find a number z where 2/z is an integer A, then z would be 2/A, which is rational. And since pi is irrational, there is no integer B where Bz=pi.)

Case 2) If any two squares don’t have a common real divisor, then we can’t subdivide them.

So in that second case, we still have two possibilities: either EVERY covering of a rational rectangle consists of squares that have a common real divisor. (my feeling is that this is the case)

Or there is a way to cover a rational rectangle by using squares with no common real divisor.

Well, don’t know if I really got anywhere here, but maybe this helps someone else.

Actually this puzzle is equivalent of statement

that every rational bnumber can be represented as a finit chain fraction:

if a belongs Z and b belongs N

then exists sequence <n1, n2, n3, nK> that

a/b = (n1+(1/(n2+(1/(n3+…..))))

see

http://64.233.167.104/search?q=cache:9BJlhgqHsUEJ:planetmath.org/encyclopedia/ChainFraction.html+canonical+chain+fraction&hl=en

Dehn’s theorem

But it is not so simple to solve at having latte in the morning… π

Nice! this is the first time for about this problem. thank you

it is the good idea of putting these types of puzzles on the net, let the peaple come to know about these and they improve thier programming skills

There is simple reasoning:

Let a > b then exists n1 (that belongs to Z ) and r1 (that belongs to N) (to be noted that b > r1)

such as a = n1

b+r1.a/b = (n1b+r1)/b = n1 + r1/b = n1 + 1/(b/r1)Exists n2 (that belongs to Z ) and r2 (that belongs to N) (to be noted that r1 > r2)

such as b = n2

r1+r2n1+1((n2r1+r2)/r1) = n1+1/(n2+r2/r1)continuing this pattern we will get sequence

b > r1 > r2 > r3 > … >1

where ri belongs to N

It is obvious that there is a finite count of natural numbers that are less then b so this algorithm will finish when ri become 1 as a result of this algorithm we will get finite sequence of

<n1, n2, …,ni>

which are coefficients of a finite chain fraction.

This is correct but note that the original problem stated "if and only if". This means that you have to proof it both ways:

1) if the rectangle has edges a and b, and a/b is rational then you can cover it with squares.

2) If the a/b is irrational then you cannot cover it with a finite number of squares.

The part (2) is a difficult one… π especially when you have a rectangle covered with squares which looks like this:

http://adi_oltean.members.winisp.net/temp/rectangle.png

I thought I had too an reasonable simple proof for the opposite implication but this was not the case.

Anyway, Adrian is right – Max Dehn published the proof about 100 years ago. I looked for the original article on the internet and I found it. Here is the text http://adi_oltean.members.winisp.net/temp/article.pdf

(unfortunately in German)