Skip to content

Lát sàn (Tiling)

Tháng Mười Một 4, 2010

A favorite topic of mine is linear algebra. It keeps surprising me with wonderful and useful facts. Among others, I found this gem recently:

Theorem. Let R be a rectangular in the place with edge lengths a and b. It is clear that if a/b is rational, then R can be partitioned into edge parallel squares. Prove that the inverse also holds, namely that if R can be partitioned into edge parallel (not necessarily equal)
squares, then a/b is rational.

Sketch of proof. Assume that R is partitioned into squares with sides x_1, \dots, x_n in a particular way. Looking at the sides and the positions of
the squares, we can write up a system of linear equations, each of which has the form either c_1x_1+ \dots+c_n x_n =a, or c_1x_1+\dots + c_n x_n =b
or x_i=x_j. Collecting all these equations, we end up with Ax= h, where x=(x_1, \dots, x_n), A has integer entries, and the coordinates of h are a,b or 0.

Assume that there is a unique solution. Then each x_i can be written as \alpha_i a +\beta _i b, for some rational \alpha_i, \beta_i (since A has integer coefficients). Plugging these back to the original equations and subtracting a or b from the right hand side if necessary, we obtain equations of the form p_j a + q_j b=0, where p_j, q_j are linear combinations (with integer coefficients) of some \alpha_i, \beta_i. If there is some j such that p_j, q_j \neq 0, then a/b= -q_j/p_j is rational and we are done.

If p_j=q_j=0 for all j, then this means that the given partition works for all R, regardless the values of a and b. On the
other hand, by considering the areas, we have \sum_{i=1}^n x_i^2 =ab. The right hand side can be rewritten as a quadratic form in
a and b as (\sum_{i=1}^n \alpha_i^2)a^2 + (\sum_{i=1}^n \beta_i^2)b^2 + 2 \sum_{i=1}^n \alpha_i \beta_i ab. But it is
impossible that such a form equals ab for all a,b >0. A contradiction.

To conclude the proof, it suffices to show that there is a unique solution. We leave it as an exercise. For more about this theorem and other interesting results, I highly recommend
PROBLEMS AND THEOREMS IN LINEAR ALGEBRA by V. Prasolov.

From → Khác

4 phản hồi
  1. Nkd permalink

    Hai thằng cu nhà anh có được gen giỏi toán của bố không???

  2. chung no choi may tinh rat tai !!!

  3. Space permalink

    em đọc quyển Prasolov thấy khó quá chẳng hiểu gì , các nhà toán học tư duy trừu tượng quá

  4. thilan permalink

    Hehe, hồi xưa em có đọc blog của anh Văn rồi, nhào vô rồi lại nhào ra ! Bây giờ em thấy anh viết dễ hiểu hơn, thử đọc lại xem sao nhưng mà em lại sắp nhào ra😀😀 Ủa nhưng mà con nhỏ Nkd nó đâu mất rồi? Em cũng thích đọc các comments mà sao không thấy ai comment nữa?

    Nói chung là các ông thày dạy toán đều có vẻ rất hiền🙂 trừ ông NTZ hơi hung một tí nhưng mà rất cưng con gái🙂

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: