# Little math problem

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.

Tags

1. JD says:

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 wx 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 wx 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. π

2. timts says:

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.

4. timts says:

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

5. JD says:

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 guess it’s a good thing I didn’t go into math; I’m getting brain strain on this "little" problem. π

I had this brain strain too π

Disclaimer: The problem is not quite easy when you want to demonstrate that a rectangle convered with squares is always rational.

Probably there is a five-line proof somewhere but I couldn’t find it.

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

9. Dehn’s theorem

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

10. sreedhar says:

11. sreedhar says:

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 = n1b+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 = n2r1+r2

n1+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: