Little math problem


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.

Comments (14)

  1. Anonymous 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. Anonymous says:

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

  3. Anonymous says:

    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. Anonymous says:

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

  5. Anonymous says:

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

  6. Anonymous says:

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

  7. Anonymous says:

    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.

  8. Anonymous says:

    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. Anonymous says:

    Dehn’s theorem

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

  10. Anonymous says:

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

  11. Anonymous 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

  12. Anonymous says:

    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.

  13. Anonymous says:

    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

  14. Anonymous says:

    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)