ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
PHẠM THÀNH AN
BÀI TOÁN VỀ CHIA HÌNH VUÔNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2015
i
Mục lục
Lời cảm ơn ii
Mở đầu 1
1 Ghép hình chữ nhật từ các hình vuông 3
1.1 Ghép hình chữ nhật từ các hình vuông . . . . . . . . . . . 1.2 Đồ thị và mạch điện . . . . . . . . . . . . . . . . . . . . . 3 6
2 Định lý cơ bản về chia hình chữ nhật thành các hình vuông
không bằng nhau 24
2.1 Định lý cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Bài toán chia hình chữ nhật và dãy Fibonacci 24 41
Kết luận 45
Tài liệu tham khảo 46
ii
Lời cảm ơn
Trước tiên, tác giả xin được gửi lời cảm ơn đến tất cả quý thầy cô đã
giảng dạy trong chương trình Cao học khóa 2013-2015 lớp K7Q, chuyên ngành Phương pháp toán sơ cấp, sự quan tâm chỉ đạo, tạo điều kiện của Ban giám hiệu, các phòng, khoa chuyên môn của trường Đại học Khoa học- Đại học Thái Nguyên, các kiến thức được thầy cô giảng dạy làm cơ
sở cho tác giả thực hiện tốt luận văn này.
Tác giả xin chân thành cảm ơn TS.Nguyễn Văn Minh, đã tận tình
hướng dẫn cho tác giả trong thời gian thực hiện luận văn. Mặc dù, trong quá trình thực hiện luận văn, có giai đoạn không được thuận lợi mang yếu tố chủ quan nhưng thầy đã rất cố gắng hướng dẫn, chỉ bảo, cho tác giả nhiều kiến thức cũng như kinh nghiệm trong thời gian thực hiện đề
tài. Sau cùng, tác giả xin gửi lời biết ơn sâu sắc đến Ban giám hiệu trường THPT Hoàng Hoa Thám- Đông Triều- Quảng Ninh, các anh chị em đồng nghiệp và gia đình, đã luôn tạo điều kiện tốt nhất cho tôi trong suốt quá trình học tập cũng như thực hiện luận văn.
Luận văn này được thực hiện và hoàn thành tại Trường Đại học Khoa
học - Đại học Thái Nguyên.
Thái Nguyên, tháng 4 năm 2015
Phạm Thành An
Học viên Cao học Toán K7Q Trường ĐH Khoa học - ĐH Thái Nguyên
1
Mở đầu
Luận văn trình bày bài toán nổi tiếng: "Chia hình vuông K thành một số hình vuông nhỏ hơn". Vấn đề trở thành dễ dàng nếu không đòi hỏi cách chia các hình vuông con phải khác nhau từng đôi (hình 1).
• Nếu yêu cầu tất cả các hình vuông con phải bằng nhau thì chia được
như hình 1a,b, nghĩa là số hình vuông phải là chính phương.
• Nếu không yêu cầu tất cả các hình vuông bằng nhau, thì số hình
Hình 1:
vuông có thể là 6 (hình 1c) hoặc 7 (hình 1d).
Tuy nhiên nếu yêu cầu “các hình vuông khác nhau từng đôi một” thì vấn đề sẽ không đơn giản. Một điều thú vị, từ bài toán chia hình vuông là biến thành một mạch điện tương đương, bằng cách xem xét các ô vuông
như điện trở nối với các cạnh trên cùng và cạnh dưới cùng của hình vuông lớn, sau đó áp dụng định luật về mạch của định luật Kirchhoff mà sẽ đề cập trong luận văn này để giải quyết bài toán trên.
2
Luận văn đề cập đến hai khái niệm Đồ thị và Mạch điện, dựa vào lý thuyết đồ thị để giải bài toán chia hình chữ nhật thành các hình vuông không bằng nhau, đặc biệt là Định lý Euler "Số đỉnh trừ số cạnh cộng số diện trong mọi đồ thị luôn bằng 1", khi đó ta thấy một song ánh hiếm hoi
giữa Hình học và Điện học. Hơn nữa, việc chứng minh Định lý cơ bản về chia hình chữ nhật thành các hình vuông không bằng nhau thì mọi hình vuông đều chia được thành các hình vuông nhỏ hơn đôi một khác nhau. Bài toán về ghép các hình vuông để được hình chữ nhật cho ta thấy sự
liên hệ của bài toán này với dãy số Fibonacci. Cấu trúc luận văn:
Chương 1: Ghép hình chữ nhật từ các hình vuông: Giải quyết
bài toán về chia hình chữ nhật thành các hình vuông khác nhau từng đôi và ghép hình chữ nhật từ các hình vuông khác nhau từng đôi.
Chương 2: Định lý cơ bản về chia hình chữ nhật thành các hình vuông không bằng nhau: Phát biểu và chứng minh lại Định lý cơ bản về điều kiện cần và đủ của phép chia hình chữ nhật thành các
hình vuông không bằng nhau, tìm được một hệ thức liên hệ giữa bài toán chia một hình chữ nhật thành các hình vuông với dãy Fibonacci đã biết.
Thái Nguyên, tháng 04 năm 2015
Phạm Thành An Học viên Cao học Toán K7Q
Chuyên ngành Phương pháp Toán sơ cấp Trường Đại học Khoa học - Đại học Thái Nguyên Email: Phamthanhan.c3hht@quangninh.edu.vn
3
Chương 1
Ghép hình chữ nhật từ các hình vuông
1.1 Ghép hình chữ nhật từ các hình vuông
Trong mục này ta xét bài toán sau:
Bài toán: Chia một hình chữ nhật thành n hình vuông con khác nhau từng đôi. Liên quan đến bài toán này là bài toán : "Ghép n hình vuông khác nhau từng đôi thành một hình chữ nhật".
Người ta đã chứng minh được rằng, không thể ghép n hình vuông khác nhau từng đôi để được một hình chữ nhật với n ≤ 8 (chi tiết xem [5]).
Hình 1.1:
Với n = 9, có thể ghép 9 hình vuông khác nhau từng đôi thành một hình chữ nhật được minh họa trên hình (1.1, 1.2, 1.3, 1.4).
4
Hình 1.2:
Hình 1.3:
Hình 1.4:
5
Dễ thấy, nếu ta có thể ghép n hình vuông khác nhau từng đôi để được một hình chữ nhật thì cũng có thể ghép n + 1 hình vuông khác nhau từng đôi để được một hình chữ nhật. Thật vậy, nếu hình chữ nhật P được ghép từ n hình vuông khác nhau từng đôi, bằng cách ghép thêm vào P một
hình vuông có cạnh bằng cạnh lớn của P , ta sẽ được một hình chữ nhật P1. Hình vuông thứ n + 1 có cạnh lớn hơn tất cả các cạnh của hình vuông hợp thành P . Như vậy, hình vuông P1 được ghép từ n + 1 hình vuông khác nhau từng đôi.
Một số nhà toán học đã xét bài toán: Tìm số n bé nhất sao cho có thể chia một hình vuông có kích thước cho trước thành n hình vuông con
Hình 1.5:
khác nhau từng đôi. Người đầu tiên xét bài toán này là P Sprag vào năm 1939 [6]. Trên hình 1.5 chỉ ra một cách chia hình vuông cạnh 175 thành 24 hình vuông con khác nhau từng đôi với các cạnh như sau:
1, 2, 3, 4, 5, 8, 9, 14, 16, 18, 20, 29, 30
31, 33, 35, 38, 39, 43, 51, 55, 56, 64, 81
6
Hình 1.6:
Ví dụ này được chỉ ra bởi Willcocks T.H.A.[8]. Cho đến nay, 24 là số ít nhất các hình vuông khác nhau từng đôi mà có thể ghép thành một hình vuông có cạnh 175. Ví dụ cho sự phân hoạch hình chữ nhật có kích thước 422 × 593 thành các hình vuông con khác nhau từng đôi (1.6):
Các kết quả đã kể trên về bài toán chia hình chữ nhật thành các hình vuông con khác nhau từng đôi liên quan đến hai khái niệm quan trọng là
khái niệm đồ thị và khái niệm mạch điện.
1.2 Đồ thị và mạch điện
Các phương pháp đã sử dụng để nhận được đa số các kết quả trong 1.1 liên quan đến cơ sở của lý thuyết đồ thị và phương pháp biểu diễn các
mạng điện phức tạp. Đồ thị trên mặt phẳng là một hệ thống các đường, ví dụ các đoạn thẳng, nối các điểm của một hệ điểm đã cho nào đó. Các điểm này gọi là các đỉnh của đồ thị, còn các đường (các đoạn thẳng) nối các điểm này gọi là các cạnh của đồ thị. Phần mặt phẳng giới hạn bởi
các đường gấp khúc khép kín (nói chung, là các đường cong) lập từ các cạnh của đồ thị, tương tự như miền I hoặc miền II của hình 1.7a gọi là các diện của đồ thị.
7
Hình 1.7:
Định lý sau đây kết quả quan trọng của lý thuyết đồ thị:
Định lý 1.1 (Định lý Euler). [5] Nếu đồ thị có B đỉnh, P cạnh và G diện
thì các số nguyên dương B, P, G liên hệ với nhau bởi hệ thức:
B − P + G = 1 (E)
Chẳng hạn, đối với đồ thị trên hình 1.7a ta có : B = 6, P = 10, G = 5
và 6 − 10 + 5 = 1. Cuối cùng, cần nói thêm rằng đồ thị mà cạnh của nó kèm theo các mũi tên chỉ hướng đi của các cạnh này (ví dụ, xem hình 1.7b) được gọi là các đồ thị định hướng.
Giả sử ta có một phân hoạch nào đó một hình chữ nhật hay một hình vuông thành các hình vuông nhỏ hơn; để xác định ta sẽ nói về phân hoạch hình chữ nhật với các cạnh 32 và 33 thành 9 hình vuông khác nhau từng
đôi biểu diễn trên hình 1.2, mặc dù ở đây đang nói về phân hoạch bất kỳ một hình chữ nhật thành các hình vuông con không nhất thiết phải khác nhau. Như thường lệ, ta sẽ xem các cạnh của hình chữ nhật là nằm ngang hoặc thẳng đứng; khi đó các cạnh của tất cả các hình vuông con
cũng sẽ nằm ngang hoặc thẳng đứng. Ta xét tất cả các đoạn nằm ngang trên hình vẽ của ta, tức là các đoạn A1B1, A2B2, A3B3, A4B4, A5B5, A6B6 (hình 1.8)
8
Hình 1.8:
Mỗi đoạn này được đặt tương ứng với một điểm xác định (có thể xem điểm này trùng với trung điểm của đoạn tương ứng, mặc dù điều này không bắt buộc). Ký hiệu các điểm này qua H1, H2,...và xem chúng là đỉnh của một đồ thị nào đó. Nếu hai điểm tương ứng với các đoạn nằm ngang chứa các cạnh của cùng một hình vuông của phân hoạch thì ta nối các điểm này bằng một đoạn thẳng (hay là bằng một cung của đường cong nào đó). Như vậy, ta nhận được đồ thị 1.9, tương ứng với phân hoạch
hình chữ nhật thành các hình vuông; rõ ràng, các cạnh của đồ thị này tương ứng với các hình vuông của phân hoạch, còn các đỉnh tương ứng với các đoạn nằm ngang xác định bởi phân hoạch của ta.
Tiếp theo, sẽ có lợi cho ta khi làm rõ ý nghĩa của các diện của đồ thị nhận được. Chẳng hạn, xét diện H2H3H5H4 (xem hình 1.10). Diện này tương ứng với một dãy 4 hình vuông của phân hoạch. Các đỉnh cao nhất và thấp nhất H2, H5 của diện được xét tương ứng với các đường thẳng nằm ngang, dọc theo chúng là các hình vuông với các cạnh 10 và 4 (được biểu diễn trên đồ thị bởi các cạnh H2H4 và H2H3) và các hình vuông với các cạnh 1 và 7 (biểu diễn trên đồ thị bởi các cạnh H4H5 và H3H5); đồng thời hình vuông với cạnh 1 có cạnh nằm ngang chung với hình vuông cạnh 10, hình vuông với cạnh 7 có cạnh nằm ngang chung với cạnh 4. Như vậy, chúng ta đi đến một tổ hợp các hình vuông biểu diễn trên hình 1.10, từ
9
Hình 1.9:
Hình 1.10:
hình này rõ ràng rằng tất cả các hình vuông được xét đều kề với đoạn thẳng đứng CD.
Ta quay trở lại trường hợp tổng quát. Giả sử H1H2H3 . . . Hl là một diện tùy ý của đồ thị, tương ứng với một phân hoạch nào đó của một hình chữ nhật thành các hình vuông, tạm thời chưa bắt buộc phải phân biệt từng cặp (hình 1.11. Ta giả sử rằng H1 và Hk (trong đó k ≤ l) là các đỉnh cao nhất và thấp nhất trong các đỉnh của các diện này, như vậy các điểm H1 và Hk tương ứng với các đoạn nằm ngang cao nhất và thấp nhất trong các đoạn tương ứng với các đỉnh H1, H2, H3, . . . Hl. Các cạnh của đồ thị H1H2 và H1Hl, xuất phát từ đỉnh H1 tương ứng với hai hình vuông kề nhau, các đáy trên của chúng thuộc cùng một đường thẳng AB (biểu diễn trên đồ thị bởi điểm H1); hai hình vuông này có cạnh chung thẳng đứng CD (hình 1.11a)).
10
1 bằng nhau (hình 1.12a) thì các đáy
Hình 1.11:
Nếu các hình vuông được xét K1, K (cid:48)
dưới của chúng cũng phải thuộc cùng một đường thẳng nằm ngang A’B’; đồng thời, các cạnh H1H2 và H1Hl phải có hai đỉnh chung, nghĩa là các điểm H2, Hl cần phải trùng nhau (hình 1.12b); cả hai điểm này tương ứng với đường thẳng A’B’); do đó, trong trường hợp này diện được xét của đồ thị suy biến thành “nhị giác” H1H2, có thể đặt tương ứng nó với cạnh thẳng đứng CD. Bây giờ giả sử hình vuông K (cid:48) 1tương ứng với cạnh H1Hl lớn hơn hình vuông K1 (tương ứng với cạnh H1H2) (hình 1.11). Trong trường hợp kề với hình vuông K1 từ phía dưới còn một hình vuông nữa nhận đường thẳng CD làm cạnh thẳng đứng dễ hiểu rằng hình vuông K2 này được biểu diễn trên đồ thị bởi cạnh H2H3.
1 có cạnh nằm ngang chung A’B’(hình 1.12c) thì các mút của các cạnh H2H3 và H1Hl của đồ thị phải trùng nhau (hình 1.12d); trong trường hợp này các đỉnh H3 ≡ Hl tương ứng với đoạn nằm ngang A’B’); như vậy, khi xét diện của đồ thị là tam giác H1H2H3, 3 cạnh của nó tương ứng với 3 hình vuông kề với cạnh thẳng đứng CD. Nếu chẳng hạn, tổng tất cả các cạnh của các hình vuông K1, K2 lớn hơn các cạnh của hình vuông K (cid:48) 1 (hình 1.11) thì tiếp xúc với hình vuông K (cid:48) 1
Nếu các hình vuông K2 và K (cid:48)
11
Hình 1.12:
2 cũng có cạnh nằm trên CD; trên
từ phía dưới còn có một hình vuông K (cid:48) đồ thị, hình vuông này tương ứng với cạnh HlHl−1 (hình 1.11b).
Tiếp tục sự phân tích này, chúng ta khẳng định rằng trong mọi trường hợp đường gấp khúc H1H2H3 . . . và H1HlHl−1 gặp nhau tại điểm Hk, tương ứng với cạnh nằm ngang A’B’ đi qua mút dưới D của đoạn thẳng đứng CD, đồng thời đường gấp khúc H1H2H3 . . . Hk và H1HlHl−1 . . . Hk sẽ tương ứng với một dãy các hình vuông kề về bên trái hoặc bên phải, với đoạn thẳng đứng CD. Như vậy, ta kết luận rằng, mỗi diện của đồ thị tương ứng với một đoạn thẳng đứng nào đó, trong số các đoạn thẳng sinh ra phân hoạch một hình chữ nhật thành các hình vuông. Ngược lại, cũng
rõ ràng là mỗi đoạn thẳng đứng CD (khác với các cạnh bên của hình chữ nhật được phân hoạch) tương ứng với một diện xác định của đồ thị giới hạn bởi các cạnh biểu diễn dãy các hình vuông kề về bên trái hoặc bên phải với cạnh CD.
Tiếp theo ta sẽ luôn vẽ đồ thị sao cho từ hai điểm H và H’ tương ứng với các cạnh nằm ngang AB và A’B’, điểm nằm cao hơn tương ứng với
đoạn nằm cao hơn; ngoài ra, trên các cạnh của đồ thị ta quy ước vẽ các mũi tên chỉ hướng từ trên xuống dưới. Như vậy, ta sẽ luôn xem đồ thị được xét là định hướng. Tiếp theo, bên cạnh mỗi cạnh của đồ thị sẽ đặt các số bằng độ dài cạnh của hình vuông tương ứng với cạnh này. Ví dụ,
12
Hình 1.13:
trên hình 1.13 là đồ thị ở hình 1.9) khôi phục lại, tương ứng với phân hoạch hình chữ nhật thành các hình vuông biểu diễn ở hình 1.8), tuy nhiên, bây giờ đồ thị đã được định hướng, các cạnh của nó đã gắn trọng số.
Dễ dàng thiết lập các liên hệ liên kết các cạnh của các đồ thị khả dĩ tương ứng với các phân hoạch một hình chữ nhật thành các hình vuông. Trước hết, rõ ràng rằng các cạnh đi tới một đỉnh xác định H tương ứng với các hình vuông kề về phía trên với đoạn thẳng nằm ngang AB biểu
diễn bởi điểm H; các cạnh đi ra từ H tương ứng với các hình vuông kề với đoạn AB từ phía dưới. [Như vậy, trên hình 1.13 các đoạn đi tới H3 là H1H3, H2H3 tương ứng với các hình vuông với cạnh 18 và 4 kề từ phía trên với đoạn A3B3, các cạnh đi ra từ H3 là các cạnh H3H5, H3H6 tương ứng với các hình vuông có cạnh là 7 và 15 kề từ phía dưới với đoạn A3B3- xem hình 1.8]. Bởi vì tổng độ dài các cạnh của các hình vuông kề với một đoạn nằm ngang nào đó từ phía trên bằng tổng độ dài các cạnh của hình vuông kề với đoạn này từ phía dưới thì đối với mỗi đỉnh của đồ thị, tổng trọng số của các cạnh đi tới đỉnh này bằng tổng trọng số các cạnh đi ra
từ nó.
Hơn nữa, nếu Hi1, Hi2, . . . , Hil là một diện nào đó của đồ thị và Hi1, Hik (k ≤ l) là các đỉnh cao nhất và thấp nhất của diện này thì các đường gấp khúc Hi1, Hi2, . . . , Hik và Hi1, HilHil−1, . . . , Hik tương ứng với dãy các hình vuông kề từ phía trái và phía phải với cùng một đoạn thẳng đứng.
13
Nhưng rõ ràng rằng tổng độ dài các cạnh của các hình vuông kề về bên trái với một đoạn thẳng đứng nào đó sẽ bằng tổng độ dài các cạnh của hình vuông kề với cạnh đó về phía phải; bởi vậy, đối với mỗi diện của đồ thị tổng trọng số của tất cả các cạnh lập thành đường gấp khúc Hi1, Hi2, . . . , Hil bằng tổng trọng số tất cả các cạnh lập thành đường gấp khúc Hi1, HilHil−1, . . . , Hik, trong đó H1, H2, . . . , Hik, . . . , Hil là các đỉnh của diện đã cho, đồng thời Hil, Hik tương ứng là các đỉnh cao nhất và thấp nhất của diện này (hình 1.14b). (Chẳng hạn, ở đồ thị biểu diễn trên hình 1.13 các đỉnh cao nhất và thấp nhất của diện H2H3H5H4 là các đỉnh H2, H5, đồng thời tổng các trọng số của các đoạn lập thành các đường gấp khúc này là 10+1 và 4+7).
Các điều kiện liên kết trọng số của các cạnh của đồ thị, có thể phát biểu theo một cách khác. Ta sẽ gán cho cạnh H’H với hướng đi ngược với chiều
mũi tên (tức là hướng từ H’ tới H, trong đó H’ nằm dưới điểm H) trọng lượng âm −p, bằng với trọng lượng cũng của cạnh đó (tức là cạnh HH’ với hướng “tự nhiên”) về trị tuyết đối nhưng với dấu ngược lại. Khi đó, điều kiện đưa ra ở trên có thể phát biểu dưới dạng sau: Đối với mỗi đỉnh
H của đồ thị, tổng trọng số của các cạnh xuất phát từ H (không phân biệt là đi tới H hoặc đi ra từ H) bằng 0; đối với mỗi diện Hi1, Hi2, ..., Hil tổng trọng số của các cạnh giới hạn diện này bằng 0 (ta sẽ xem hướng của các cạnh là hướng từ Hi1 tới Hi2, từ Hi2 tới Hi3,...v.v...).
1H (cid:48)
2...H (cid:48)
2, ..., Hj−1H (cid:48)
1, H (cid:48)
1H (cid:48)
j, H (cid:48)
Quy tắc chỉ ra ở trên rất gần với cái gọi là định luật Kirchhoff cho phép tính cường độ dòng điện đi qua phần này hoặc phần khác của một mạch
điện rẽ nhánh. Trong trường hợp phần được xét của mạch không có nguồn, tổng cường độ dòng điện đi ra khỏi một đỉnh H nào đó của mạch rẽ nhánh bằng tổng cường độ các dòng đi tới đỉnh này (hình 1.15a). Mặt khác, nếu điện trở của tất cả các dây dẫn riêng biệt lập thành mạch phức tạp là như nhau thì đối với hai đường bất kỳ HH1H2...HiH (cid:48), HH (cid:48) jH (cid:48) nối hai đỉnh nào đó H, H’ của mạng, tổng cường độ dòng điện đi qua các đoạn dây dẫn HH1, H1H2, ..., Hi−1Hi, HiH (cid:48) bằng tổng cường độ dòng điện đi jH (cid:48) (hình 1.15 b); nếu qua các đoạn dây dẫn HH (cid:48) điện trở của các đoạn dây bằng 1, thì trong cả hai trường hợp tổng cường
14
Hình 1.14:
Hình 1.15:
độ dòng điện bằng hiệu điện thế tại các điểm H và H’).
Như vậy, rõ ràng với định luật Kirchhoff, trùng khớp với các quy tắc liên kết các trọng số của đồ thị tương ứng với phân hoạch một hình chữ
nhật (xem hình 1.14 và 1.15). Bởi vì, các quy tắc Kirchhoff là các mối liên hệ duy nhất liên kết các dòng điện tại các phần riêng biệt của một mạch điện rẽ nhánh, mỗi phân hoạch hình chữ nhật thành các hình vuông (thậm chí không bắt buộc phải khác nhau từng đôi) tương ứng với một
mạch điện xác định. Ví dụ, trên hình 1.16 biểu diễn mạch điện tương ứng với phân hoạch hình chữ nhật thành 9 hình vuông, được biểu diễn trên hình 1.2 hay hình 1.8 (xem đồ thị biểu diễn trên hình 1.13). Trên hình 1.18 biểu diễn phân hoạch hình chữ nhật thành 10 hình vuông (xem hình
15
1.17) và mạch điện tương ứng với nó. Các ví dụ tương tự được đưa ra trên hình 1.19 và 1.20, trong đó các hình vuông của phân hoạch không phải đôi một khác nhau. Mối liên hệ chặt chẽ giữa bài toán về sự phân hoạch hình chữ nhật thành các hình vuông và các mạch điện cho phép sử dụng
Hình 1.16:
Hình 1.17:
các phương pháp tính toán các mạch điện phức tạp đã được biết rõ để tìm các cách phân hoạch mới một hình chữ nhật thành các hình vuông.
16
Hình 1.18:
Hình 1.19:
Hình 1.20:
Mạch điện tương ứng với một phân hoạch đã cho của một hình chữ nhật
thành các hình vuông có thể mô tả như sau. Tưởng tượng một khung dây chữ nhật có dòng điện đi qua được phân thành các hình vuông bởi một
17
cách nào đó. Ta đồng nhất các điện cực với các đáy nằm ngang của khung dây sao cho dòng đi qua khung dây là không đổi. Khi đó các đường dòng có thể xem là thẳng đứng và các đường đẳng thế là các đường nằm ngang. Tổng cường độ dòng điện trong mạch có thể xem bằng độ dài của một
cạnh nằm ngang của khung dây, còn hiệu điện thế giữa đáy trên và đáy dưới bằng độ dài của một cạnh thẳng đứng (như vậy, trong trường hợp phân hoạch một hình vuông thành các hình vuông nhỏ hơn cần phải xem cường độ dòng điện bằng hiệu điện thế). Chúng ta còn xem rằng các hình
vuông riêng biệt tạo thành khung dây là tách rời khỏi nhau bởi các nhát rạch dọc theo các cạnh thẳng đứng của phân hoạch; dọc theo các đường nằm ngang chia cắt khung dây thành các phần chúng ta liên kết các hình vuông riêng biệt bởi các dây dẫn có độ dẫn điện cực lớn (thực tế là vô
hạn) (hình 1.21); từ quan điểm các tính chất điện của lưới, điều kiện cuối cùng có nghĩa là đoạn nằm ngang được đồng nhất với một điểm). Khi đó tất cả các hình vuông mà khung dây được phân ra sẽ đóng vai trò các dây dẫn có điện trở giống nhau (bởi vì dọc theo các dây dẫn như vậy, tỷ
Hình 1.21:
giữa hiệu điện thế và cường độ dòng điện bằng đơn vị), và chúng ta số U I đi đến mạch điện mô tả ở trên tương ứng với phân hoạch của ta.
Bây giờ ta quay lại với các đồ thị tương ứng với các phân hoạch hình chữ nhật thành các hình vuông. Mỗi đồ thị như vậy lập thành một “bộ khung” của mạch điện tương ứng (được hoàn toàn xác định bởi một đồ thị định hướng với các trọng số đã cho của các cạnh). Trong đoạn này
18
chúng ta vẫn chưa sử dụng sự kiện các hình vuông của phân hoạch phải khác nhau từng đôi; chúng ta cũng không loại trừ thậm chí cả các phân hoạch chứa các hình vuông bằng nhau nằm kề nhau và có một cạnh chung (xem hình 1.19 và 1.20). Tuy nhiên, nếu chỉ quan tâm đến vấn đề phân
hoạch một hình chữ nhật thành các hình vuông khác nhau từng đôi thì ngay từ đầu có thể loại khỏi việc xét các đồ thị chứa các “nhị giác” như biểu diễn trên 1.12b, vì chúng ta biết rằng các nhị giác như vậy tương ứng với các cặp hình vuông bằng nhau, kề nhau theo một cạnh thẳng đứng
(xem hình 1.12 a) cũng như các hình 1.20a,b. Tương tự như vậy, chúng ta có thể xem rằng đồ thị được xét không chứa các “đầu gối” HpHqHr lập bởi các cạnh HpHq và HqHr, từ đỉnh chung Hqcủa chúng không đi ra một cạnh nào khác với HqHp và HqHr (hình 1.22a) vì một “đầu gối” như thế rõ ràng tương ứng với hai hình vuông bằng nhau kề nhau theo một cạnh nằm ngang (hình 1.22b) và hình 1.19a,b. Như vậy, tiếp theo chúng ta sẽ xem rằng tại mỗi một trong B − 2 đỉnh (tức là các đỉnh khác với đỉnh trên cùng và dưới cùng) của đồ thị hội tụ không ít hơn 3 cạnh, mỗi một
Hình 1.22:
trong G diện được giới hạn bởi không ít hơn 3 cạnh.
Rõ ràng từ đỉnh trên cùng của đồ thị có thể xuất phát một cạnh duy nhất (xem hình 1.23a,b). Tuy nhiên, tình huống này tương ứng với trường hợp khi chỉ có một hình vuông duy nhất kề với đáy trên của hình chữ
nhật được phân hoạch, đây là trường hợp không đáng quan tâm vì rõ ràng nó dẫn về bài toán phân hoạch một hình chữ nhật bé hơn nhận được từ hình chữ nhật xuất phát bằng cách cắt bỏ hình vuông trên cùng. Bởi vậy, có thể xem rằng từ đỉnh trên cùng của đồ thị xuất phát không ít hơn
hai cạnh; cũng đúng như vậy, ta sẽ xem rằng từ đỉnh dưới cùng của đồ thị xuất phát không ít hơn hai cạnh. Khi đó tổng số P các cạnh của đồ
19
thị sẽ không bé hơn một nửa tổng sau:
3(B − 2) + 2.2 = 3B − 2,
Hình 1.23:
Vì từ mỗi một trong B − 2 đỉnh trong của đồ thị xuất phát không ít hơn
3 cạnh và từ mỗi một trong đỉnh cao nhất và đỉnh thấp nhất xuất phát
không ít hơn 2 cạnh; mặt khác, khi đếm các cạnh theo các đỉnh như vậy, mỗi cạnh được tính hai lần (mỗi cạnh nối hai đỉnh). Vậy ta có:
2P ≥ 3B − 2 ⇔ B ≤ 2P + 2 3
Thế kết quả nhận được vào công thức Euler (E) ta có:
− P + G ≥ 1 ⇔ G ≥ 2P + 2 3 P + 1 3
Bây giờ ta nhận xét rằng, có thể đặt tương ứng đồ thị của phân hoạch hình chữ nhật thành các hình vuông một cách khác với cách vừa mô tả
ở trên. Ta đánh dấu trên các đoạn thẳng đứng (các cạnh của các hình vuông của phân hoạch) C1D1, C2D2, ... các điểm V1, V2... mà ta sẽ chọn làm các đỉnh của đồ thị. Khi đó ta nối các điểm Vi, Vj tương ứng với hai cạnh CiDi, CjDj bởi một đường chỉ trong trường hợp nếu các cạnh của một hình vuông của phân hoạch thuộc các đường thẳng CiDi, CjDj (xem hình 1.24a,b và hình 1.8, 1.9).
Khi đó ta nhận được đồ thị “đối ngẫu” với đồ thị đã được xét trước đây: các đỉnh của đồ thị như vậy tương ứng với các đoạn thẳng đứng của
20
Hình 1.24:
phân hoạch, các cạnh, vẫn như trước, tương ứng với các hình vuông của phân hoạch, còn các diện tương ứng với các đoạn nằm ngang (khác với
đáy trên và đáy dưới) của hình chữ nhật được phân hoạch. Cũng có thể biến đồ thị này thành định hướng, nếu chọn chẳng hạn, hướng duyệt các cạnh là “từ trái qua phải” (tức là tuân theo quy tắc đi qua cạnh của đồ thị theo hướng tương ứng với việc chuyển từ một cạnh thẳng đứng sang
cạnh thẳng đứng nằm bên phải nó). Vẫn như trước, có thể gán cho các cạnh các trọng số bằng độ dài các cạnh của hình vuông tương ứng với các cạnh này. Phương pháp chuyển từ một đồ thị xuất phát sang một đồ thị đối ngẫu với nó vừa mô tả (xem đồ thị biểu diễn trên hình 1.25a,b),
Hình 1.25:
có thể xét như một phương pháp xây dựng một mạch điện rẽ nhánh “đối ngẫu” với một mạch điện đã cho (phương pháp này đã được các nhà điện học biết từ lâu trước khi phát hiện ra mối liên hệ giữa các lưới điện với bài toán chia hình chữ nhật thành các hình vuông).
21
Số các đỉnh, cạnh và diện của đồ thị xuất phát ta vẫn ký hiệu giống như trước bởi B, P và G, còn số các đỉnh, cạnh và diện của đồ thị đối ngẫu với nó được ký hiệu bởi B’, P’, G’. Khi đó rõ ràng G’+2=B, P’=P, B’=G+2 vì số B và G’+2 bằng số các đoạn nằm ngang của phân hoạch
của ta (bao gồm cả hai đáy của hình chữ nhật xuất phát), các số P và P’ bằng số các hình vuông tham gia vào phân hoạch và số G+2 và B’ bằng số các đoạn thẳng đứng (bao gồm cả hai cạnh bên của hình chữ nhật). (Như vậy, trong trường hợp các đồ thị biểu diễn trên hình 1.25
ta có B=G’+2=6, P=P’=9 và G+2=B’=6 hoàn toàn tương ứng với hình 1.2). Cũng đúng như trước, khi đó thiết lập được rằng, nếu phân hoạch xuất phát của hình chữ nhật không chứa hình vuông kề hoàn toàn với một cạnh bên của hình chữ nhật được phân hoạch và nếu đồ thị tương
ứng không chứa “nhị giác”, không chứa “ đầu gối” (bởi vì, nếu trái lại, phân hoạch xuất phát nhất định chứa các cặp hình vuông bằng nhau có cạnh chung) thì
, G(cid:48) ≥ B(cid:48) ≤ 2P (cid:48) + 2 3 P (cid:48) + 1 3
Hai bất đẳng thức cuối cùng có thể viết lại như sau:
G + 2 ≤ ⇔ G ≤ 2P + 2 3 2P − 4 3
và
B − 2 ≥ ⇔ B ≥ P + 1 3 P + 7 3
Như vậy, cuối cùng ta có
≤ B ≤ ; ≤ G ≤ P + 7 3 2P + 2 3 P + 1 3 2P − 4 3
Vì các đại lượng B và G là các số nguyên thì đối với mỗi giá trị của P
(tức là đối với mỗi số n cố định các hình vuông của phân hoạch) ta có chỉ một số hữu hạn các giá trị khả dĩ của B và G, do đó chỉ có một số hữu hạn các đồ thị khả dĩ. Ví dụ, với P=5 (số các cạnh của đồ thị ít hơn 5 là không thể, do bất đẳng thức
≥ G ≥ ) 2P − 4 3 P + 1 3
22
ta có:
4 ≤ B ≤ 4; 2 ≤ G ≤ 2 ⇔ B = 4, P = 2
Với P=6 ta có:
≤ B ≤ 13 3 14 3
Từ đó suy ra rằng đồ thị như vậy không tồn tại vì B là một số nguyên. Với P=7 ta nhận được:
; ≤ B ≤ ≤ G ≤ ⇒ B = 5, G = 3, v.v... 14 3 16 3 8 3 10 3
Bảng dưới đây cho tất cả các giá trị có thể của B và G với P ≤ 14
(B,G) P
(4,2) (5)
(6)
(5,3) (7)
(6,3), (5,4) (8)
(6,4) (9)
(7,4), (6,5) (10)
(11) (8,4), (7,5), (6,6)
(12) (8,5), (7,6)
(13) (9,5), (8,6), (7,7)
(14) (10,5),(9,6), (8,7), (7,8)
1, p(cid:48)
Dùng bảng này việc tìm phân hoạch một hình chữ nhật thành một số không lớn các hình vuông trở thành một công việc không mấy phức tạp nhưng tương đối buồn tẻ. Ví dụ, đồ thị duy nhất khả dĩ tương
ứng với phân hoạch một hình chữ nhật thành 5 hình vuông biểu diễn trên hình 1.26 (so sánh với hình 1.27). Ký hiệu trọng số của các cạnh HH1, HH2, H1H2, H1H (cid:48), H2H (cid:48) bởi các số p1, p2, p, p(cid:48) 2 như chỉ ra trên hình 1.26, ta nhận được hệ đẳng thức sau (bên trái là các đẳng thức
tương ứng với quy tắc Kirchhoff, liên quan đến các đỉnh của đồ thị, bên
23
(cid:48)
phải là các đẳng thức tương ứng với các diện của đồ thị):
(cid:48)
(cid:48)
(cid:48)
(H1) p1 = p (HH1H2) p1 + p = p2
1 + p 2 = p2 + p
2) p
2 + p = p
(cid:48) 1
(H2) p (H1H2H
Từ đó dễ dàng suy ra p = 0, điều này là không thể. Vậy không thể phân
Hình 1.26:
Hình 1.27:
hoạch một hình chữ nhật thành 5 hình vuông khác nhau từng đôi.
Như vậy ta đã đưa bài toán chia hình vuông về bài toán ghép các hình vuông con đôi một khác nhau và chia hình chữ nhật thành các hình vuông không bằng nhau (điều kiện hai cạnh của hình chữ nhật đó phải thông
ước). Việc áp dụng lý thuyết đồ thị, đặc biệt là định lý Euler vào việc giải bài toán cho ta thấy điều thú vị liên quan giữa Hình học và Điện học.
24
Chương 2
Định lý cơ bản về chia hình chữ nhật thành các hình vuông không bằng nhau
2.1 Định lý cơ bản
Định lý 2.1. Hình chữ nhật P chia được thành các hình vuông, trong đó không có hai hình vuông nào bằng nhau, khi và chỉ khi các cạnh của hình chữ nhật P thông ước.
Chứng minh. Một hình chữ nhật với các cạnh thông ước (nghĩa là: tỷ số hai cạnh của nó là một số hữu tỷ) rõ ràng có thể chia thành các hình vuông bằng nhau (ví dụ, xem trên hình 2.1 là cách chia một hình chữ nhật thành các hình vuông bằng nhau khi tỷ số các cạnh là 7:4). Vì
Hình 2.1:
vậy, có thể phát biểu lại định lý như sau: Hình chữ nhật P có thể chia thành các hình vuông con khác nhau từng đôi khi và chỉ khi nó có thể chia thành các hình vuông con bằng nhau.
25
Chứng minh định lý cơ bản gồm hai phần: Điều kiện cần và điều kiện
đủ.
Chứng minh điều kiện cần. Nếu hình chữ nhật P có thể chia thành các hình vuông (không nhất thiết phải khác nhau từng đôi) thì các cạnh của hình chữ nhật này thông ước. Giả sử ta có một phân hoạch nào đó
hình chữ nhật P thành n hình vuông. Ký hiệu các cạnh của hình vuông trong phép phân hoạch này bởi x1, x2, ..., xn, các cạnh của hình chữ nhật P bởi X,Y. Ta cần chứng minh X:Y là số hữu tỷ.
Các mối liên hệ ràng buộc n + 2 đại lượng x1, x2, ..., xn, X, Y có thể nhận được bằng cách sau: tổng độ dài các cạnh của các hình vuông kề với mỗi cạnh của hình chữ nhật bằng độ dài của cạnh đó ( nghĩa là bằng X hoặc Y). Tiếp theo, với mỗi đoạn thẳng đứng hay nằm ngang mà kề với nó từ cả hai phía là một số nguyên các hình vuông của phân hoạch, tổng
độ dài các cạnh của các hình vuông kề với nó từ phía này hoặc phía khác sẽ bằng độ dài của đoạn thẳng này. Tập hợp các liên hệ này có thể xét như một hệ phương trình tuyến tính thuần nhất (tức là không có các số hạng tự do) đối với các ẩn x1, x2, ..., xn, X, Y với hệ số là +1 hoặc −1, nếu tất cả các ẩn được chuyển về một vế (chẳng hạn, vế trái). Phân hoạch
xuất phát của hình chữ nhật P tương ứng với một nghiệm dương của hệ này (một nghiệm dương của hệ được cho bởi n + 2 số dương).
Ta minh họa điều vừa nói bằng một ví dụ phân hoạch một hình chữ nhật thành 10 hình vuông con biểu diễn trên hình 2.2. Trong trường hợp này các liên hệ nói đến sẽ có dạng:
x1 + x2 + x3 = X x1 + x8 = Y
x4 + x5 = x2 x7 + x9 = x8
x6 + x10 = x5 + x3 x2 + x4 = x1 + x7
x8 + x7 = x1 x5 + x6 = x4
x9 = x7 + x4 + x6 x10 = x6 + x9
(X = x8 + x9 + x10) x3 = x2 + x5
(Y = x3 + x10)
26
Hình 2.2:
Chúng lập thành một hệ 11 phương trình thuần nhất với 12 ẩn (trong
ngoặc là các phương trình hệ quả của các phương trình trước).
Hệ phương trình bậc nhất thường được giải bằng cách sau. Từ một phương trình nào đó, một trong các ẩn được biểu diễn qua các ẩn còn lại; biểu thức nhận được được thế vào tất cả các phương trình còn lại của hệ. Khi đó hệ ban đầu được chuyển thành hệ mới bao gồm ít phương trình
hơn và số ẩn ít hơn. Sau đó, trong hệ mới này lại một ẩn nào đó được biểu diễn qua các ẩn còn lại, v.v...Trong quá trình này số các phương trình và số các ẩn giảm dần. Bây giờ ta nhận xét rằng,tất cả các hệ phương trình được suy ra bằng cách trên và hệ ban đầu đều là thuần nhất. Từ đó suy
ra chỉ có thể có 3 khả năng sau:
1. Trong quá trình loại liên tiếp các ẩn từ hệ, cuối cùng chúng ta đi đến một phương trình thuần nhất duy nhất với một ẩn, tức là phương trình dạng ax=0 hay là x=0, trong đó x là một trong các ẩn x1, x2, ..., xn, X, Y . Bởi vì tất cả các ẩn còn lại của hệ trong quá trình loại trừ đều biểu diễn qua các ẩn khác và cuối cùng là qua x bằng một biểu thức thuần nhất thì ta nhận được
x1 = x2 = ... = xn = X = Y = 0.
Rõ ràng, điều này không thể xảy ra đối với hệ của ta, vì ta biết trước rằng hệ có ít nhất một nghiệm dương (tương ứng với phân hoạch đã
cho).
27
2. Trong quá trình loại liên tiếp các ẩn từ hệ, cuối cùng chúng ta đi đến một phương trình thuần nhất duy nhất với hai ẩn: bx − ay = 0 hay là x : y = a : b, trong đó x và y là hai ẩn nào đó trong các ẩn x1, x2, ..., xn, X, Y . Bởi vì trong quá trình loại các ẩn khỏi hệ chúng ta liên tiếp biểu diễn tất cả các ẩn qua các ẩn còn lại và cuối cùng qua x và y, đồng thời tất cả các ẩn này được biểu diễn qua x và y một cách thuần nhất, nghĩa là bằng các công thức dạng px + qy thì khi biết tỷ số x : y = a : b chúng ta có thể tìm tỷ số của mỗi một
trong các ẩn đối với x hoặc là với y. Như vậy, trong trường hợp này nghiệm bất kỳ của hệ thỏa mãn:
x1 : x2 : ... : xn : X : Y = a1 : a2 : ... : an : A : B,
trong đó, a1, a2, ..., an, A, B là các số nào đó được xác định trong quá trình giải hệ. Bây giờ ta nhận xét rằng, hệ phương trình của ta chỉ có các hệ số nguyên (chính xác hơn, tất cả các hệ số khác 0 của hệ xuất phát chỉ là +1 hoặc -1). Bởi vậy, trong mỗi bước của quá trình
giải hệ các hệ số có mặt trong các phương trình của hệ chỉ là tỷ số của các số nguyên, tức là các số hữu tỷ, các số vô tỷ không thể xuất hiện trong quá trình này. Do đó, tất cả các số a1, a2, ..., an, A, B có thể xem là các số hữu tỷ; nói riêng, tỷ số X : Y = A : B sẽ là hữu tỷ.
Ví dụ, chúng ta xét hệ phương trình tương ứng với phân hoạch biểu diễn trên hình 2.2:
(1) x1 + x2 + x3 = X; (2) x4 + x5 = x2; (3) x6 + x10 = x5 + x3;
(4) x8 + x7 = x1; (5) x9 = x7 + x4 + x6; (6) x1 + x8 = Y ;
(7) x7 + x9 = x8; (8) x2 + x4 = x1 + x7; (9) x5 + x6 = x4;
(10) x10 = x6 + x9; (11) x3 = x2 + x5
Từ các phương trình (11), (2), (9), (3), (10), (5), (7), (4), (1), (6) ta
28
tìm được:
x5 = x3 − x2; x4 = x2 − x5 = 2x2 − x3 =; x6 = x4 − x5 = 3x2 − 2x3;
x10 = x5 + x3 − x6 = 4x3 − 4x2; x9 = x10 − x6 = 6x3 − 7x2;
x7 = x9 − x4 − x6 = 9x3 − 12x2; x8 = x7 + x9 = 15x3 − 19x2;
x1 = x8 + x7 = 24x3 − 31x2;
X = x1 + x2 + x3 = 25x3 − 30x2; Y = x1 + x8 = 39x3 − 50x2;
Đặt các giá trị nhận được vào phương trình (8) (là phương trình duy
nhất chưa sử dụng cho đến nay) ta nhận được
3x2 − x3 = 33x3 − 43x2 ⇔ 34x3 = 46x2 ⇔ x2 : x3 = 17 : 23
Từ đó dễ dàng suy ra rằng:
x1 : x2 : x3 : x4 : x5 : x6 : x7 : x8 : x9 : x10 : X : Y
= 25 : 17 : 23 : 11 : 6 : 5 : 3 : 22 : 19 : 24 : 65 : 47.
Như vậy, ta thấy rằng phân hoạch xuất phát chính xác đến một phép
đồng dạng trùng với phân hoạch biểu diễn trên hình 1.17 của hình chữ nhật với tỷ số các cạnh 65:47 thành 10 hình vuông.
3. Trong quá trình loại liên tiếp các ẩn từ hệ, cuối cùng chúng ta đi đến
một phương trình thuần nhất với số ẩn lớn hơn 2 (ta giả sử rằng các ẩn được loại là x1, ..., xr, các ẩn X,Y được giữ lại đến cùng). Ta viết phương trình này như sau:
xr = qr+1xr+1 + qr+2xr+2 + ... + qnxn + Q1X + Q2Y.
Đồng thời, tất cả biến còn lại được biểu diễn qua các biến
xr+1, xr+2, ..., xn, X, Y
29
bởi các công thức
x1 = ar+1xr+1 + ar+2xr+2 + ... + anxn + A1X + A2Y
x2 = br+1xr+1 + br+2xr+2 + ... + bnxn + B1X + B2Y
............................................................................
xr−1 = pr+1xr+1 + pr+2xr+2 + ... + pnxn + P1X + P2Y
Cho các ẩn xr+1, xr+2, ..., xn, X, Y các giá trị tùy ý (kể cả các giá trị làm cho X : Y vô tỷ), có thể nhận được nghiệm bất kỳ của hệ. Tuy nhiên, ta sẽ chỉ ra rằng đối với hệ xuất phát trường hợp này không thể xảy ra. Ta giả sử trái lại,
x1, x2, ..., xr, xr+1, xr+2, ..., xn, X, Y
là một nghiệm của hệ tương ứng với phân hoạch đã cho của hình chữ nhật thành các hình vuông. Thay đổi một chút giá trị Y bởi giá trị Y + ε. Khi đó các giá trị x1, x2, ..., xr biến đổi theo, chúng sẽ biến đổi thành
1 = ar+1xr+1 + ar+2xr+2 + ... + anxn + A1X + A2Y (cid:48) = x1 + A2ε 2 = br+1xr+1 + br+2xr+2 + ... + bnxn + B1X + B2Y (cid:48) = x2 + B2ε
x(cid:48) x(cid:48)
r = qr+1xr+1 + qr+2xr+2 + ... + qnxn + Q1X + Q2Y (cid:48) = xr + Q2ε
1, x(cid:48)
2, ..., x(cid:48)
............................................................................ x(cid:48)
Nếu ta chọn ε đủ bé để tất cả các số Y (cid:48) = Y + ε, x(cid:48) r vẫn còn dương và biến dạng phân hoạch xuất phát của hình chữ nhật P với các cạnh X và Y thành n hình vuông với các cạnh x1, x2, ..., xn sao cho P biến thành một hình chữ nhật P’ sai khác ít với P với các cạnh X và Y’, còn các hình vuông cũ biến thành các hình vuông mới
với các cạnh
1, x(cid:48)
2, ..., x(cid:48)
r, xr+1, xr+2, ..., xn
x(cid:48)
không dẫn đến mâu thuẫn nào với sơ đồ phân bố các hình vuông 1, ..., x(cid:48) (nhắc lại rằng, các số X,Y’, x(cid:48) r, xr+1, xr+2, ..., xn thỏa mãn sơ
30
đồ xuất phát biểu diễn điều kiện kề của các hình vuông với nhau và với các cạnh hình chữ nhật tương ứng với sơ đồ phân bố các hình vuông cho bởi phân hoạch xuất phát). Bây giờ ta sẽ chỉ ra rằng nếu vậy ta sẽ nhận được mệnh đề về sự tồn tại vô hạn các phân hoạch
xấp xỉ nhau của các hình chữ nhật thành các hình vuông, các phân hoạch này nhận được khi ε nhận tất cả các giá trị đủ bé, điều này dẫn đến mâu thuẫn. Thực vậy, vì các hình chữ nhật với các cạnh X,Y được phân thành n hình vuông với các cạnh x1, x2, ..., xn thì
1 + x2
2 + ... + x2
r + x2
r+1 + ... + x2 n.
XY = x2 (*)
(diện tích hình chữ nhật bằng tổng diện tích của tất cả các hình vuông hợp thành). Cũng đúng như thế, hình chữ nhật với các cạnh
X và Y’=Y+ε được phân thành các hình vuông với các cạnh
1 = x1 + A2ε, x(cid:48)
2 = x2 + B2ε, ..., x(cid:48)
r = xr + Q2ε, xr+1, ...., xn
x(cid:48)
(cid:48)
(cid:48)
(cid:48)
thì:
2 1)
2 2)
2 r)
r+1 + ... + x2 n ⇔ X(Y +ε) = (x1 + A2ε)2+(x2 + B2ε)2+...+(xr + Q2ε)2+x2
r+1+...+x2 n
XY (cid:48) = (x + ... + (x + x2 + (x
1 + x2
2 + ... + x2
r + x2
r+1 + ... + x2
Đẳng thức cuối cùng có thể viết lại dưới dạng sau:
n+ 2ε2 + B2
2ε2 + ... + Q2
2ε2 (**)
XY + Xε = x2 2A2x1ε + 2B2x2ε + .... + 2Q2xrε + ... + A2
Dùng đẳng thức (*) rút gọn (**) và chia hai vế đẳng thức nhận được cho ε ta nhận được
2 + B2
2 + ... + Q2
2)ε
2 + B2
2 + ... + Q2
X = 2(A2x1 + B2x2 + ... + Q2xr) + (A2
Bởi vì: A2 2 (cid:54)= 0 (các số A2, B2, ..., Q2 không thể đồng thời bằng 0, vì các đại lượng x1, x2, ..., xr không thể hoàn toàn không phụ thuộc vào Y: tổng độ dài các cạnh của hình vuông kề với cạnh
độ dài Y của hình chữ nhật bằng một số Y hoàn toàn xác định chứ
31
không phải bằng một số tùy ý), từ đẳng thức trên suy ra:
2 + B2
2 + ... + Q2 2
X − 2(A2x1 + B2x2 + ... + Q2xr) ε = A2
Như vậy, ε xác định đơn trị bởi các đại lượng X, x1, ..., xr, A2, ..., Q2. Trong khi theo lý luận của ta ε là một số dương tùy ý đủ nhỏ. Ta nhận được mâu thuẫn.
Như vậy, có thể khẳng định rằng nếu hệ phương trình tuyến tính suy ra từ một phân hoạch nào đó hình chữ nhật P thành các hình vuông thì đối với hệ này trạng thái đặc trưng là trường hợp 2. Một nghiệm của hệ
này tương ứng với phân hoạch xuất phát hoặc là chỉ sai khác phân hoạch xuất phát bởi một phép đồng dạng. Như đã phân tích trong trường hợp 2, khi đó tỷ số X : Y = A : B của hình chữ nhật được phân hoạch bắt buộc phải là số hữu tỷ. Điều kiện cần của định lý được chứng minh.
Chứng minh điều kiện đủ. Nếu các cạnh của hình chữ nhật thông
ước thì hình chữ nhật này có thể chia thành các hình vuông khác nhau từng đôi.
Chỉ cần chứng minh rằng, tồn tại vô hạn các phép phân hoạch khác nhau một hình vuông thành các hình vuông khác nhau từng cặp và không có hình vuông nào tham gia vào hai phân hoạch khác nhau. Thực vậy, mỗi hình chữ nhật với độ dài các cạnh thông ước có thể chia thành một
số các hình vuông bằng nhau. Chẳng hạn, nếu tỷ số các cạnh hình chữ nhật là m : n thì có thể chia hình chữ nhật thành m × n hình vuông bằng nhau (ta gọi các hình vuông con bằng nhau này là các hình vuông con sơ cấp). Đối với các hình vuông con sơ cấp, ta chọn cho mỗi hình một phân
hoạch chia nó thành các hình vuông con không bằng nhau từng đôi (ta gọi các hình vuông con này là các hình vuông con thứ cấp) sao cho hai phân hoạch của hai hình vuông con sơ cấp bất kỳ là khác nhau. Bởi vì, không có hình vuông con thứ cấp nào, trong phân hoạch của một hình
vuông con sơ cấp, tham gia vào phân hoạch của một hình vuông con sơ cấp khác, nên toàn bộ hình chữ nhật được phân thành các hình vuông con khác nhau từng đôi.
32
Như vậy, ta sẽ chứng minh rằng tồn tại vô số các phân hoạch một hình vuông thành các hình vuông con khác nhau từng đôi thỏa mãn điều kiện đã nêu. Chứng minh được chia thành hai giai đoạn:
1) Tồn tại nhiều vô số các phân hoạch khác nhau một hình vuông thành
các hình vuông con khác nhau từng đôi.
Giả sử P0 là một hình chữ nhật nào đó (hình 2.3a). Ta xét một hình chữ nhật, đồng dạng với hình chữ nhật P0 sao cho cạnh lớn của nó bằng cạnh bé của P0. Ghép hình chữ nhật này với hình chữ nhật P0 ta nhận được một hình chữ nhật P1 nào đó (hình 2.3). Làm tương tự với hình chữ nhật P1 ta được hình chữ nhật P2 (hình 2.3b). Làm tương tự với hình P2 ta được hình P3 và v.v...Như vậy ta nhận được một loạt các hình chữ nhật với các cạnh bé giống nhau P0, P1, P2, P3, . . . trong đó hình chữ nhật P1 bao gồm 2 hình chữ nhật đồng dạng với P0, hình chữ nhật P2 bao gồm 4 hình chữ nhật đồng dạng với P0, hình chữ nhật P3 bao gồm 8 hình chữ nhật đồng dạng với P0, v.v . . .; Nói chung hình chữ nhật Pk (trong đó k là số nguyên dương bất kỳ) bao gồm từ 2k hình chữ nhật đồng dạng với P0. Rõ ràng, nếu hình chữ nhật P0 có thể phân thành một loạt các hình vuông khác nhau từng đôithì tất cả các hình chữ nhật đồng dạng với P0 cũng có thể phân thành các hình vuông con khác nhau từng đôi; bởi vậy, tất cả các hình chữ nhật P1, P2, P3, .. có thể phân thành các hình vuông con. Tuy nhiên, chúng ta vẫn chưa thể khẳng định rằng tất cả các hình vuông nhận được từ việc chia các hình chữ nhật P1, P2, P3,...là khác nhau từng đôi.
Bây giờ ta giả sử rằng P0 là hình chữ nhật với tỷ số các cạnh là 422:593 như chỉ ra trong 1.1 (xem hình 1.6a), có thể chia thành các hình vuông
khác nhau từng đôi bằng hai cách khác nhau. Khi đó mỗi hình chữ nhật P1, P2, P3, ... có thể chia thành các hình vuông con khác nhau từng đôi bằng hai cách khác nhau, hoặc là theo cách phân hoạch thứ nhất của P0, hoặc là theo cách phân hoạch thứ hai của P0. Ta sẽ chứng minh rằng mỗi một trong các hình chữ nhật P1, P2, P3, ... được chia thành các hình vuông con khác nhau từng đôi bằng hai cách khác nhau sao cho không có một hình vuông con nào tham gia vào một cách phân hoạch của một
33
Hình 2.3:
hình chữ nhật Pk nào đó lại được gặp lại trong một phân hoạch khác của cùng hình chữ nhật đó.
; Giả sử cạnh bé của hình chữ nhật P0 bằng 1 còn cạnh lớn bằng
593 422 ta ký hiệu nó bởi u0. Ký hiệu cạnh lớn của hình chữ nhật P1 bởi u1, cạnh lớn của hình chữ nhật P2 bởi u2, v.v...(cạnh bé của tất cả các hình chữ nhật này bằng 1). Từ quy luật dựng các hình chữ nhật suy ra rằng với k bất kỳ:
uk = uk−1 + 1 uk−1
(vì hình chữ nhật Pk nhận được bằng cách ghép hình chữ nhật Pk−1 với các cạnh 1 và uk−1 với hình chữ nhật đồng dạng với Pk−1, cạnh lớn của nó bằng 1, tức là hình chữ nhật với các cạnh là , 1; bởi vậy, các cạnh
, (xem hình 2.4). Hiệu của hình chữ nhật Pk bằng 1 và uk = uk−1 + 1 uk−1 1 uk−1
số uk − uk−1 = được ký hiệu qua vk; rõ ràng, vk là cạnh của hình chữ 1 uk−1
nhật cần ghép vào hình chữ nhật Pk−1 để nhận được hình chữ nhật Pk. Hình chữ nhật P1 bao gồm hai hình chữ nhật đồng dạng với P0; cạnh bé . Hình của một hình (hình P0) là 1, còn cạnh bé của hình kia là v1 = 1 u0
chữ nhật P2 bao gồm hai hình chữ nhật đồng dạng với P1; cạnh bé của một hình là 1 (hình P1), còn cạnh bé của hình kia là v2 = . Vì P1 bao 1 u1
34
gồm hai hình chữ nhật đồng dạng với P0 ta kết luận rằng P2 bao gồm bốn hình chữ nhật đồng dạng với P0, các cạnh bé của hai trong chúng ( lập thành hình P1 bằng 1 và P1, các cạnh bé của hai hình chữ nhật còn lại là v2.1 và v2.v1. Tương tự, hình chữ nhật P3 bao gồm hai hình chữ nhật . đồng dạng với P2; các cạnh bé của chúng tương ứng bằng 1 và v2 =
1 u2 Từ đó suy ra rằng P3 bao gồm tám hình chữ nhật đồng dạng với P0; các cạnh bé của bốn trong chúng bằng 1, v1, v2, v2v1, còn các cạnh bé của bốn hình còn lại bằng
v3.1, v3v1, v3v2, v3.v2v1
Hình 2.4:
Cũng đúng như vậy, có thể chứng minh rằng hình chữ nhật P4 bao gồm 16 hình chữ nhật đồng dạng với P0; các cạnh bé của chúng bằng1, v1, v2, v3, v4, v1v2, v1v3, v1v4, v2v3, v2v4, v3v4, v1v2v3, v1v2v4 v1v3v4, v2v3v4 và v1v2v3v4. Kích thước của 2k hình chữ nhật đồng dạng với P0 hợp thành hình chữ nhật Pk được xác định tương tự (k=1,2,3,4,...).
Giả sử x là cạnh của một hình vuông nào đó trong phân hoạch hình chữ nhật Pk. Hình vuông này tham gia vào thành phần của một trong 2k hình chữ nhật đồng dạng với P0 hợp thành hình chữ nhật P0; hệ số đồng dạng ở đây bằng tích nào đó dạng vi1vi2...vin. Ta sẽ xem rằng các nhân tử trong tích này sắp xếp theo thứ tự tăng dần của chỉ số, các chỉ số này khác nhau và mỗi một trong chúng không vượt quá k, tức là 1 ≤ i1 < i2 < ... < in ≤ k; từ đó suy ra số các nhân tử không vượt quá k, nghĩa là n ≤ k. Ta ký hiệu cạnh của hình vuông của phân hoạch hình chữ nhật P0 tương ứng với hình vuông được xét của phân hoạch hình chữ
35
nhật đồng dạng với P0 qua c; khi đó, rõ ràng x = vi1...vinc.
Bây giờ giả sử rằng, đối với một hình chữ nhật Pr nào đó cạnh x của một hình vuông của một trong hai phân hoạch khả dĩ bằng cạnh y của một hình vuông khác trong cùng phân hoạch đó hoặc trong một phân hoạch khác của chính Pr. Giả sử
x = vi1vi2...vinc, y = vj1vj2...vjmd
Trong đó c, d là các cạnh của các hình vuông tương ứng trong phân hoạch của P0, đồng thời 1 ≤ i1 < i2 < ... < in ≤ r 1 ≤ j1 < j2 < ... < jm ≤ r. Như vậy, ta nhận được đẳng thức:
vi1vi2...vinc = vj1vj2...vjmd
Từ đó suy ra rằng:
= (A) d c vi1vi2...vin vj1vj2...vjm
ở đây ta xem rằng tất cả các nhân tử ở tử số và mẫu số đều khác nhau, vì trong trường hợp trái lại ta có thể rút gọn.
Bây giờ ta sẽ chứng minh rằng đẳng thức (A) (tương đương với nó là đẳng thức x=y) không thể xảy ra. Ta cần một số khảo sát sơ bộ để chứng minh khẳng định là cơ sở cho lý luận tiếp theo này. Xuất phát từ số u0 = 593 : 422 hữu tỷ suy ra rằng tất cả các số
, ... , u2 = u1 + , u3 = u2 + u1 = u0 + 1 u0 1 u1 1 u2
hữu tỷ. Nhưng trong trường hợp này tất cả các số
, ... v1 = , v2 = , v3 = 1 u0 1 u1 1 u2
cũng sẽ hữu tỷ; do đó, chúng có thể biểu diễn dưới dạng
, ... v1 = , v2 = , v3 = p1 q1 p2 q2 p3 q3
trong đó pk, qk ( k=1,2,3,...) là các số nguyên dương nguyên tố cùng nhau.
36
Đẳng thức (A) bây giờ có dạng
= . ... : . ... = (B) d c pi1 qi1 pi2 qi2 pin qin pj1 qj1 pj2 qj2 pjm qjm pi1pi2...pinqj1qj2...qjm pj1pj2...pjmqi1qi2...qin
Bây giờ chúng ta cố gắng nắm bắt quy luật, theo đó các số pk, qk được hình thành. Như chúng ta thấy:
= = uk−1 + + vk uk = 1 uk−1 1 vk 1 vk+1
Nhưng
k + q2 p2 k pkqk
= , + = + vk = 1 vk+1 qk+1 pk+1 1 vk qk pk pk qk
Từ đó suy ra rằng
k + q2 p2 k pkqk
= (1) qk+1 pk+1
hay là
k + q2 k
(1a) pk+1 = pkqk, qk+1 = p2
k + q2
k, pkqk nguyên tố cùng nhau ; bởi vậy, đẳng thức (1), do cả hai vế của nó là các phân số
(Do các số pk, qk nguyên tố cùng nhau nên các số p2
tối giản, tương đương với các đẳng thức (1a)). Từ đẳng thức (1a) có thể kết luận rằng:
a. qk+1 > qk
b. Các số qk+1 nguyên tố cùng nhau với mỗi một trong các số
p1, p2, ..., pk, pk+1 và q1, q2, ..., qk.
k + q2
k. Khẳng định thứ hai cần được chứng minh. Ta chỉ cần chứng minh rằng qk+1 nguyên tố cùng nhau với mỗi một trong các số q1, q2, ..., qk và p1, vì theo đẳng thức đầu tiên trong (1a) :
Khẳng định đầu tiên được suy ra từ đẳng thức qk+1 = p2
(2) pi = p1q1q2...qi−1
với i = 2, 3, 4, ..., k + 1 (tuy nhiên, chỉ cần hạn chế trên các giá trị i = 2, 3, ..., k do đã biết trước rằng các số qk+1, pk+1 nguyên tố cùng nhau).
37
Tiếp theo, (2) và đẳng thức thứ hai trong (1a) (trong đó cần đặt k=i) cho ta:
1q2
1q2
2...q2
i−1 + q2 i
(3) qi+1 = p2
Bây giờ dễ dàng chứng minh khẳng định (b). Thực vậy, do (1a)
1 + q2 1
q2 = p2
= v1 = p1 q1
= ), từ đó suy ra q2 nguyên tố cùng nhau với p1và q1. Từ (3) ta 422 593
vì các số p1 = 422, q1 = 593 nguyên tố cùng nhau (chú ý : 1 u0 nhận được:
1q2
1 + q2 2
q3 = p2
vì q2 nguyên tố cùng nhau với p1 và q1, từ đó suy ra rằng q3 nguyên tố cùng nhau với p1, q1 và q2;
1 q2
1 q2
2 + q2 3
q4 = p2
vì q3 nguyên tố cùng nhau với p1, q1 và q2, từ đẳng thức trên suy ra q4 nguyên tố cùng nhau với p1, q1, q2 và q3v.v... Cuối cùng từ đẳng thức (3) (trong đó cần đặt i = k) suy ra nếu qk nguyên tố cùng nhau với p1, q1, q2..., qk−1 (điều này được xác lập ở bước lý luận trước) thì qk+1 nguyên tố cùng nhau với p1, q1, q2, ..., qk−1 và qk. Đây là điều phải chứng minh.
Giả sử rằng đẳng thức (B) (tương đương với (A)) được thỏa mãn. Để xác định ta xem jm > in [lý luận không có gì thay đổi nếu có bất đẳng thức ngược lại, trường hợp jm = in bị loại trừ vì ta xem các nhân tử ở tử số và mẫu số ở vế phải của (A) là phân biệt]. Khi đó, do b) nhân tử qjm ở tử số của phân số nằm ở vế phải công thức (B) không thể rút gọn được
với nhân tử nào của mẫu số của phân số này. Nhưng là tỷ số của hai d c số trong các bộ (I), (II) gồm 26 số nguyên
2, 22, 37, 39, 41, 43, 80, 164, 178, 200, 207, 215, 222 (I)
18, 38, 49, 67, 72, 85, 103, 116, 154, 175, 192, 230, 247 (II)
38
là các cạnh của các hình vuông của một trong hai phân hoạch hình chữ nhật với các cạnh 422 và 593. Vì số lớn nhất trong các số này là 247 thì trong tử số của phân số nằm ở vế trái của liên hệ (B) không thể có số lớn hơn 247. Tuy nhiên, vì qjm > q1 = 593 thì tử số ở vế phải của liên hệ chứa nhân tử lớn hơn 593 (không thể rút gọn với nhân tử nào ở mẫu). Mâu thuẫn nhận được chứng tỏ rằng đẳng thức (B) không thể xảy ra.
Như vậy, ta đã chứng tỏ rằng đẳng thức (B) (nghĩa là cả đẳng thức (A) tương đương với nó) không thể xảy ra. Do đó, không có hai hình vuông
nào trong các hình vuông của cùng một phân hoạch hoặc trong hai phân hoạch khác nhau của hình chữ nhật Pk bằng nhau (k = 0, 1, 2, 3, ...). Từ đó dễ dàng chứng tỏ rằng tồn tại vô số phân hoạch khác nhau một hình vuông thành các hình vuông con khác nhau từng đôi.
Thực vậy, ta chia các cạnh của hình vuông K theo tỷ số các cạnh của hình chữ nhật Pk và phân hình vuông K thành hai hình vuông nhỏ hơn K1, K2 và hai hình chữ nhật P và P’ đồng dạng với Pk (hình 2.5). Sau đó mỗi một trong các hình chữ nhật P và P’ được phân thành các hình vuông khác nhau từng đôi bằng các cách khác nhau. Khi đó toàn bộ hình vuông K được phân thành các hình vuông con khác nhau từng đôi. Như vậy ta nhận được một xích vô hạn các phân hoạch hình vuông K thành
Hình 2.5:
các hình vuông con khác nhau từng đôi tương ứng với các hình chữ nhật P0, P1, P2, ... (phân hoạch đầu tiên ứng với P0 là phân hoạch hình vuông thành 28 hình vuông con không bằng nhau từng đôi biểu diễn trên hình 2.6).
39
Hình 2.6:
2) Tồn tại nhiều vô số các phân hoạch khác nhau một hình vuông thành các hình vuông con khác nhau từng đôi, đồng thời mỗi một hình vuông có mặt trong một phân hoạch nào đó sẽ không có mặt trong một phân hoạch khác.
Để chứng minh khẳng định này, ta sẽ xuất phát từ xích vô hạn các
phân hoạch một hình vuông thành các hình vuông khác nhau từng đôi xây dựng ở trên. Trước hết, ta sẽ chứng minh rằng tỷ số giữa cạnh lớn và cạnh bé của các hình vuông Pk tăng vô hạn khi tăng chỉ số k (chứng minh này là phần cơ bản trong lý luận của đoạn này). Thực vậy, tỷ số uk : 1 giữa các cạnh của hình vuông Pk và tỷ số uk−1 : 1 giữa các cạnh của hình vuông Pk−1 có liên hệ:
uk = uk−1 + 1 uk−1
Từ đó suy ra uk > uk−1 và liên hệ:
= ) = uk = uk−1 + + (uk−2 + 1 uk−1 1 uk−2
... = + + ... + + u0 1 uk−1 1 uk−1 1 uk−2 1 u0
40
lớn hơn Bây giờ giả sử rằng tất cả các số uk bị chặn bởi một số nguyên N nào đó: , do đó: uk < N với mọi k = 0, 1, 2, ... Khi đó tất cả các số 1 N 1 uk
+ + ... + + ... + + + u0 > + u0 > N uN 2 = 1 N 1 N 1 u0 1 uN 2−1 1 uN 2−2
1 N N 2 lần
Mâu thuẫn nhận được chứng tỏ dãy {uk} không bị chặn. Như vậy, ta có thể khẳng định rằng hình chữ nhật P và P’ (xem hình 2.5) có thể làm “mỏng” tùy ý. Từ đó ngay lập tức suy ra khẳng định đòi hỏi. Thực vậy,
ta bắt đầu một phân hoạch xác định hình vuông K thành các hình vuông con khác nhau từng đôi, chẳng hạn, phân hoạch được xác định bởi hình chữ nhật P0 (với tỷ số các cạnh là 422:593, xem hình 1.6). Bây giờ giả sử α là cạnh của hình vuông bé nhất tham gia vào phân hoạch đầu tiên này.
Ta chọn số k đủ lớn để các hình chữ nhật P và P’ đồng dạng với hình chữ nhật Pk có cạnh bé nhỏ hơn α. Rõ ràng rằng không một hình vuông nào của một phân hoạch như vậy có thể bằng một hình vuông của phân hoạch đầu. Thực vậy, các hình vuông tham gia vào phân hoạch các hình
chữ nhật P và P’ sẽ bé hơn hình vuông bé nhất của phân hoạch đầu tiên (vì cạnh của chúng đều bé hơn α), còn các hình vuông K1 và K2 cũng không thể bằng các hình vuông của phân hoạch đầu; một trong các hình vuông này sẽ bé hơn hình vuông bé nhất của phân hoạch đầu, hình vuông
còn lại sẽ lớn hơn hình vuông lớn nhất của phân hoạch đầu.
Tiếp theo, cũng đúng như thế, ký hiệu β là cạnh của hình vuông bé
nhất của phân hoạch thứ hai của hình vuông K thành các hình vuông không bằng nhau từng đôi (tức là phân hoạch tương ứng với hình chữ nhật Pk). Ta xây dựng phân hoạch thứ ba sao cho cạnh bé của các hình chữ nhật P và P’ đồng dạng với hình chữ nhật Pl (trong đó số l được chọn đủ lớn) bé hơn β. Rõ ràng, bằng cách lặp lại chiến thuật này ta có thể tìm được một số tùy ý lớn các phân hoạch khác nhau của hình vuông K thành các hình vuông con khác nhau từng đôi, thỏa mãn điều kiện nêu trong điểm 2) ở trên.
41
Như vậy, ta đã hoàn thành chứng minh định lý cơ bản.
2.2 Bài toán chia hình chữ nhật và dãy Fibonacci
Trong mục 1.1 chúng ta đã chỉ ra phương pháp chia hình chữ nhật thành số tùy ý n ≥ 10 các hình vuông khác nhau từng đôi, hay nói khác đi là ghép một số hình vuông khác nhau từng đôi để được hình chữ nhật
Hình 2.7:
Hình 2.8:
(xem hình 2.7 và hình 2.8).
Trong mục này ta nghiên cứu mối liên hệ giữa bài toán ghép hình vuông
với dãy số Fibonacci.
42
Hình 2.9:
Ví dụ 2.1. Trên hình 2.9 đã chỉ ra cách ghép như sau:
- Đầu tiên ta ghép 2 hình vuông có cạnh bằng 1 ta được hình chữ nhật có kích thước 1 × 2, ký hiệu hình chữ nhật này là P1. Ta dùng ký hiệu 2 hình vuông đầu tiên này là F1, F2, và để cho đơn giản ta dùng luôn ký hiệu này là độ dài cạnh hình vuông F1 = 1, F2 = 1. - Ghép vào cạnh lớn của hình chữ nhật P1 hình vuông F3 = 2. Ta được hình chữ nhật P2 có kích thước 2 × 3. - Lại ghép vào cạnh lớn của hình chữ nhật P2 hình vuông F4 = 3. Ta được hình chữ nhật P3 kích thước 3 × 5. - Lặp lại cách làm như vậy, ta được hình chữ nhật ghép từ nhiều hình vuông đôi một khác nhau (trừ 2 hình vuông đầu tiên là bằng nhau). Với
cách làm đó, ta thấy các cạnh của hình vuông có tính chất:
F1 = F2 = 1, Fn+1 = Fn−1 + Fn, n > 2
Đây chính là dãy Fibonacci mà ta đã biết. Hình chữ nhật Pn được ghép từ n + 1 hình vuông. Diện tích của hình chữ nhật Pn là:
Sn−1 = Fn.Fn+1, n ≥ 2
Nếu tính diện tích hình chữ nhật thứ n là tổng diện tích các hình vuông
con ghép thành, ta nhận được một tính chất của dãy Fibonacci:
1 + F 2 F 2
2 + F 2
3 + ... + F 2
n = Fn.Fn+1
(F )
43
Hình 2.10:
Ví dụ 2.2. Trên hình 2.10a là hình chữ nhật P1 có kích thước p×(p+q).
Ta thực hiện các bước sau: - Ghép vào cạnh lớn của hình chữ nhật P1 một hình vuông K1 có cạnh là H1 = p + q, hình chữ nhật ghép bởi P1 và K1 được ký hiệu là P2. - Ghép vào cạnh lớn của hình chữ nhật P2 một hình vuông K2, có cạnh là H2 = p + 2q, hình chữ nhật ghép bởi P2 và K2 được ký hiệu là P3. - Ghép vào cạnh lớn của hình chữ nhật P3 một hình vuông K3, có cạnh là H3 = 2p + 3q, hình chữ nhật ghép bởi P3 và K3 được ký hiệu là P4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . - Ghép vào cạnh lớn của hình chữ nhật Pn−1 một hình vuông Kn−1, có cạnh là Hn−1, hình chữ nhật ghép bởi Pn−1 và Kn−1 được ký hiệu là Pn. Ta nhắc lại ở đây, dãy Fibonacci là dãy số:
(n = 2, 3, ...) F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2,
(n = 1, 2, 3, ..).
Ta dễ dàng chứng minh được Hn = pFn + qFn+1, Thật vậy, công thức đã đúng với n = 1, giả sử công thức đã đúng đến n − 1, tức là ta đã có: Hn−2 = pFn−2 + qFn−1, Hn−1 = pFn−1 + qFn, ta phải chứng minh công thức đúng với n. Chú ý rằng Hn = Hn−1 + Hn−2.
44
Theo giả thiết quy nạp, ta có:
Hn = Hn−2 + Hn−1 = (pFn−2 + qFn−1) + (pFn−1 + qFn)
(đpcm) = p(Fn−2 + Fn−1) + q(Fn−1 + Fn) = pFn + qFn+1
n = HnHn+1. Ta được công thức:
2 + ... + H 2
1 + H 2
Theo cách dựng hình như trên, ta thấy hình chữ nhật thứ n được ghép từ n − 1 hình vuông và một hình chữ nhật P1. Diện tích hình chữ nhật Pn là: p(p + q) + H 2
1 + H 2
2 + ... + H 2
n = Hn.Hn+1 − p(p + q)
H 2 (H)
Từ công thức (H) trên, biểu diễn Hn qua Fn; Fn+1
1 = p2F 2 2 = p2F 2 3 = p2F 2 4 = p2F 2
1 + 2pqF1F2 + p2F 2 2 2 + 2pqF2F3 + p2F 2 3 3 + 2pqF3F4 + p2F 2 4 4 + 2pqF4F5 + p2F 2 5 ............................................... H 2
n+1
n + 2pqFnFn+1 + p2F 2 n = p2F 2 − − − − − − − − − − − − − − − − − − n (cid:88)
n (cid:88)
n (cid:88)
n (cid:88)
H 2 H 2 H 2 H 2
k = p2
k + 2pq
k+1
k=1
k=1
k=1 k=1 = (pFn + qFn+1)(pFn+1 + qFn+2) − q(p + q)
H 2 F 2 F 2 FkFk+1 + q2
n (cid:88)
Sử dụng công thức (F), ta có:
n+1 − p2F 2 1
k=1
p2FnFn+1 + 2pq FkFk+1 + q2FnFn+1 + q2F 2
= (pFn + qFn+1)(pFn+1 + qFn+2) − q(p + q)
Chuyển vế và rút gọn ta tìm lại được một tính chất của dãy Fibonacci
n − 1
Fn−1Fn+1 − F 2 F1F2 + F2F3 + ... + Fn−1Fn = 2
Như vậy, từ bài toán ghép các hình vuông để nhận được một hình chữ nhật ta thu được đồng nhất thức (F) và (H) liên quan đến dãy Fibonacci.
45
Kết luận
Luận văn đã thu được những kết quả sau:
1. Trình bày một cách khái quát về lý thuyết đồ thị và mạch điện. Trình bày được mối liên hệ giữa bài toán phân hoạch hình vuông với bài toán mạch điện.
2. Trình bày cách chứng minh định lý về điều kiện cần và đủ để phân
hoạch hình chữ nhật thành các hình vuông khác nhau.
3. Luận văn cũng trình bày sự liên quan giữa bài toán phân hoạch hình
chữ nhật với dãy số Fibonacci.
Tuy nhiên, vẫn còn một số vấn đề mà luận văn chưa đề cập tới, chẳng hạn như:
1. Ước lượng số các hình vuông con khi phân hoạch hình chữ nhật. Tức
là cho trước hình chữ nhật có độ dài các cạnh là các số tự nhiên m, n (m và n nguyên tố cùng nhau), cần ước lượng số các hình vuông con nhận được khi phân hoạch hình chữ nhật.
2. Tương tự bài toán trong mặt phẳng là bài toán về hình hộp chữ nhật
và hình lập phương trong không gian.
46
Tài liệu tham khảo
Tài liệu Tiếng Việt
[1] Hoàng Chúng (1997), Đại cương về Toán học hữu hạn, NXB Giáo
dục.
[2] Đào Tam (2006), Bài tập hình học phẳng, NXB Đại học Quốc Gia
Hà Nội.
Tài liệu Tiếng Anh
[3] Đào Tam (2006), Hình học sơ cấp, NXB Đại học Quốc Gia Hà Nội.
Tài liệu Tiếng Nga
[4] Dunkel O. (1957), Memorial Problem Book, New York.
[5] (cid:23)glom I. M. (1968), Kak razrezat kvadrat, Izd. Nauka.
[6] Sprag P. (1939), Primer razlo(cid:25)enia kvadrata na poparno ra-
zliqnie kvadraty, Izd. Nauka.
[7] Sprag P. (1940), O razlo(cid:25)enia prougo(cid:9)nikov na poparno razliq-
nie kvadraty, Izd. Nauka.
[8] Vilkoks F.G.A. (Willcocks T.H.) (1948), Fairly Chess Review , Au-
gust.
[9] Vilkoks F.G.A. (Willcocks T.H.A) (1951), Zametka o nekoto- ryh soverxenyh kvadrirovani(cid:31)h kvadratov (A note of some per- fect squared squares), Canadian Journal of Math, pp304-308.
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
PHẠM THÀNH AN
BÀI TOÁN VỀ CHIA HÌNH VUÔNG
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60 46 01 13
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
TS. NGUYỄN VĂN MINH
Thái Nguyên - 2015
