共用方式為

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

  • Anonymous
    November 12, 2004
    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. :)
  • Anonymous
    November 12, 2004
    I rememeber this was one of my elementary school home work.. several decades ago...
  • Anonymous
    November 12, 2004
    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.
  • Anonymous
    November 12, 2004
    I rememeber this was one of my elementary school home work.. several decades ago...
  • Anonymous
    November 12, 2004
    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. :)
  • Anonymous
    November 12, 2004
    The comment has been removed
  • Anonymous
    November 12, 2004
    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.
  • Anonymous
    November 12, 2004
    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
  • Anonymous
    November 14, 2004
    Dehn's theorem

    But it is not so simple to solve at having latte in the morning... :-)
  • Anonymous
    November 14, 2004
    Nice! this is the first time for about this problem. thank you
  • Anonymous
    November 14, 2004
    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
  • Anonymous
    November 16, 2004
    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 = (n1    b+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((n2    r1+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.
  • Anonymous
    November 16, 2004
    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
  • Anonymous
    November 19, 2004
    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)