• Không có kết quả nào được tìm thấy

Một số phương pháp đếm trong các bài toán hình học tổ hợp

N/A
N/A
Protected

Academic year: 2022

Chia sẻ "Một số phương pháp đếm trong các bài toán hình học tổ hợp"

Copied!
74
0
0

Loading.... (view fulltext now)

Văn bản

(1)

DƯƠNG THÚY QUỲNH

MỘT SỐ PHƯƠNG PHÁP ĐẾM TRONG CÁC BÀI TOÁN HÌNH

HỌC TỔ HỢP

LUẬN VĂN THẠC SỸ TOÁN HỌC

THÁI NGUYÊN - NĂM 2016

(2)

TRƯỜNG ĐẠI HỌC KHOA HỌC

DƯƠNG THÚY QUỲNH

MỘT SỐ PHƯƠNG PHÁP ĐẾM TRONG CÁC BÀI TOÁN HÌNH

HỌC TỔ HỢP

LUẬN VĂN

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP

Mã số: 60.46.01.13

Người hướng dẫn khoa học: GS.TSKH. NGUYỄN VĂN MẬU

THÁI NGUYÊN - NĂM 2016

(3)

Mục lục

Mở đầu 1

1 Một số kiến thức chuẩn bị 3

1.1 Các quy tắc đếm cơ bản . . . 3

1.1.1 Quy tắc cộng và quy tắc nhân . . . 3

1.1.2 Tổ hợp và chỉnh hợp . . . 3

1.2 Một số nguyên lý cơ bản . . . 4

1.2.1 Bất biến . . . 4

1.2.2 Nguyên lí Dirichlet . . . 5

1.2.3 Nguyên lí cực hạn . . . 7

2 Phân loại và các phương pháp giải các bài toán đếm trong hình học tổ hợp 9 2.1 Phân loại các bài toán đếm . . . 9

2.1.1 Đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng . . . 9

2.1.2 Đếm đối tượng tạo thành miền trong mặt phẳng . . . 12

2.2 Các phương pháp giải bài toán đếm . . . 14

2.2.1 Phương pháp sử dụng nguyên lí bất biến . . . 14

2.2.2 Phương pháp sử dụng nguyên lí Dirichlet . . . 22

2.2.3 Phương pháp sử dụng nguyên lí cực hạn . . . 38

3 Các dạng toán liên quan 49 3.1 Bài toán về tô màu hình vẽ . . . 49

3.2 Đếm cấu hình . . . 63

3.3 Phối hợp các phương pháp đếm khác nhau . . . 64

Tài liệu tham khảo 71

(4)

Mở đầu

Hình học tổ hợp là một phần quan trọng trong toán học nói chung và trong tổ hợp nói riêng, nó thường xuất hiện trong các đề thi học sinh giỏi và Olympic các cấp. Bài toán tổ hợp nói chung và hình học tổ hợp nói riêng thường là bài toán khó, rất phong phú và linh hoạt về cách giải. Tuy nhiên, ở nước ta hiện nay, tài liệu về tổ hợp chưa nhiều, tài liệu về hình học tổ hợp lại càng ít hơn. Do đó, tôi viết luận văn này với mong muốn sẽ cung cấp thêm cho các em học sinh phổ thông một tài liệu hay và bổ ích, nhằm đáp ứng được phần nào lòng đam mê, yêu thích và khám phá toán học của các học sinh, đồng thời tôi cũng mong rằng đây có thể là tài liệu bổ ích để các đồng nghiệp tham khảo.

Luận văn này đề cập đến một số phương pháp chính để giải quyết các bài toán đếm trong hình học tổ hợp. Ngoài phần mở đầu, phần kết luận, nội dung của luận văn gồm ba chương.

Chương 1 nhắc lại một số kiến thức chuẩn bị, liên quan đến các công thức đếm trong tổ hợp.

Chương 2 đưa ra sự phân loại một số đối tượng đếm trong hình học tổ hợp và nêu ba phương pháp để giải quyết bài toán đếm.

Phương pháp sử dụng nguyên lí bất biến là một phương pháp hiệu quả để giải quyết các bài toán đếm. Ta thường sử dụng nguyên lí bất biến trong những bài toán có một tính chất không thay đổi qua sự tác động, biến đổi của hệ thống.

Phương pháp sử dụng nguyên lí Dirichlet là một phương pháp thông dụng để giải quyết các bài toán hình học tổ hợp. Dùng nguyên lí này trong nhiều

(5)

trường hợp ta dễ dàng chứng minh được sự tồn tại của một đối tượng với tính chất xác định, tuy rằng với nguyên lí này ta thường chỉ chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm được đối tượng cụ thể.

Phương pháp sử dụng nguyên lí cực hạn vào giải các bài toán hình học tổ hợp là một phương pháp được vận dụng cho nhiều lớp bài toán khác nhau.

Nguyên lí này dùng để giải các bài toán mà trong đối tượng phải xét của nó tồn tại các giá trị lớn nhất, giá trị nhỏ nhất theo một nghĩa nào đó và thường kết hợp với những phương pháp khác, đặc biệt là phương pháp phản chứng.

Chương 3 nêu ra một số dạng toán liên quan như là bài toán tô màu, bài toán đếm cấu hình và một số bài toán hình học tổ hợp trong các đề thi học sinh giỏi quốc gia và quốc tế.

Trong mỗi chương các bài tập thường được dẫn dắt theo những chủ đề nhất định. Đồng thời, mỗi bài đều có lời giải chi tiết, ngắn gọn, sáng tạo và bất ngờ. Tác giả hi vọng, chính điều này sẽ giúp người đọc tìm thấy cho mình những kiến thức bổ ích và kích thích sự ham hiểu biết và lòng say mê học toán của người đọc.

Luận văn này được hoàn thành dưới sự hướng dẫn tận tình và nghiêm túc của thầy giáo GS.TSKH Nguyễn Văn Mậu. Tôi xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến thầy.

Tôi xin trân trọng cảm ơn Ban Giám hiệu, Ban chủ nhiệm Khoa Toán Trường Đại học Khoa học, Đại học Thái Nguyên, các thầy cô giảng viên đã quan tâm, tạo điều kiện giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu tại Trường.

Thái Nguyên, ngày 29 tháng 5 năm 2016.

Học viên

Dương Thúy Quỳnh

(6)

Chương 1

Một số kiến thức chuẩn bị

1.1 Các quy tắc đếm cơ bản

1.1.1 Quy tắc cộng và quy tắc nhân

Quy tắc cộng: Nếu công việc A có hai phương án thực hiện (loại trừ lẫn nhau), phương án 1 có n1 cách thực hiện, phương án 2 có n2 cách thực hiện thì công việcAcó n1 +n2 cách thực hiện. Trên ngôn ngữ tập hợp:A∩B = thì |A∪B| = |A|+|B|.

Quy tắc nhân: Nếu công việc A có thể chia thành 2 công đoạn tiếp nối nhau, công đoạn 1 cón1 cách thực hiện, công đọan 2 có n2 cách thực hiện thì công việcAcó n1.n2 cách thực hiện. Trên ngôn ngữ tập hợp:|A.B| = |A|.|B|.

Quy tắc phần bù: |A| = |X| − |A|, trong đó A là phần bù của A trong X.

1.1.2 Tổ hợp và chỉnh hợp

Xét tập hợp X gồmnphần tử. Từ tập hợp cơ bản này, ta có thể xây dựng các đối tượng tổ hợp phong phú.

Tập các tập con của tập X: Tập các tập con của X được ký hiệu làP(X).

Dễ thấy |P(X)| = 2n. Các tập con của một tập hợp là một đối tượng xuất hiện khá nhiều trong các bài toán đếm.

Chỉnh hợp: Chỉnh hợp chập k của một tập hợp là một bộ k phần tử phân

(7)

biệt được sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1,2,3} và k = 2 thì ta có các chỉnh hợp là (1, 2), (1,3), (2, 1), (2, 3), (3, 1), (3, 2). Số các chỉnh hợp chập k của n phần tử được ký hiệu là Akn.

Hoán vị: Hoán vị của n phần tử là chỉnh hợp chập n của n phần tử đó, nói cách khác, là một cách sắp thứ tự các phần tử đó. Hoán vị của X còn có thể định nghĩa như một song ánh từ X vào X. Số các hoán vị của n phần tử được ký hiệu là Pn.

Tổ hợp: Tổ hợp chập k của một tập hợp là một bộ k phần tử phân biệt không sắp thứ tự của tập hợp ấy. Nói cách khác, đó là một tập con k phần tử. Ví dụ nếu X = {1,2,3} và k = 2 thì ta có các tổ hợp là {1,2}, {1,3}, {2,3}. Số các tổ chập k của n phần tử được ký hiệu là Cnk.

Chỉnh hợp lặp: Chỉnh hợp lặp chập k của một tập hợp là một bộ k phần tử không nhất thiết phân biệt được sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1,2,3} và k = 2 thì ta có các chỉnh hợp lặp là {1,1}, {1,2}, {1,3}, {2,1}, {2,2}, {2,3}, {3,1}, {3,2}, {3,3}. Số các chỉnh hợp lặp chập k của n phần tử được ký hiệu là Akn.

Tổ hợp lặp: Tổ hợp lặp chập k của một tập hợp là một bộ k phần tử không nhất thiết phân biệt không sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1,2,3} và k = 2 thì ta có các tổ hợp lặp là {1,1}, {1,2}, {1,3}, {2,2}, {2,3}, {3,3}. Số các tổ hợp lặp chập k của n phần tử được ký hiệu là Ckn.

1.2 Một số nguyên lý cơ bản

1.2.1 Bất biến

a) Khái niệm bất biến

Giả sử ta có một hệ thống (X) các đại lượng và các phép biến đổi theo thứ tự. Tính chất P được gọi là bất biến sau s bước trong hệ thống (X) nếu cứ sau s bước biến đổi ta đều nhận lại được tính chất P.

b) Ứng dụng nguyên lý bất biến

(8)

Bất biến là những đại lượng (hay tính chất) không thay đổi trong quá trình chúng ta thực hiện các phép biến đổi. Chẳng hạn khi thực hiện phép tịnh tiến thì khoảng cách giữa hai điểm sẽ không thay đổi. Với phép vị tự thì khác, khoảng cách có thể sẽ thay đổi nhưng sẽ có một bất biến khác, đó là tỉ lệ giữa hai đoạn thẳng.

Có hai mẫu bài toán tổng quát thường được giải quyết bằng bất biến Bài toán tổng quát 1.1. Có một tập hợp các trạng thái X và tập hợp các phép biến đổi T từ X vào X. Có hai trạng thái a và b thuộc X, hỏi có thể dùng hữu hạn các phép biến đổi thuộc T để đưa trạng thái a về trạng thái b được không?

Bài toán tổng quát 1.2. Có một tập hợp các trạng thái X và tập hợp các phép biến đổi T từ X vào X. Cần chứng minh rằng bắt đầu từ một trạng thái a bất kì, sau một số hữu hạn các phép biến đổi từ T, ta sẽ đi đến trạng thái kết thúc (trong nhiều trường hợp đó là trạng thái ổn định, tức là sẽ không thay đổi khi tiếp tục tác động các phép biến đổi từ T).

1.2.2 Nguyên lí Dirichlet a) Nguyên lí Dirichlet

Nguyên lí Dirichlet - còn gọi là nguyên lí chuồng chim bồ câu (The Pi- geonhole Principle) - hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật vào ngăn kéo (The Drawer Principle). Nguyên lí này được nhà toán học người Đức Johann Dirichlet phát biểu đầu tiên năm 1834 khi ông đề cập tới nó với tên gọi "nguyên lí ngăn kéo". Vì vậy, một tên gọi thông dụng khác của nguyên lý chuồng bồ câu chính là "nguyên lí ngăn kéo Dirichlet"

hay đôi khi gọi gọn là "nguyên lí Dirichlet". Trong một số ngôn ngữ như tiếng Pháp, tiếng Ý và tiếng Đức, nguyên lí này cũng vẫn được gọi bằng tên

"ngăn kéo" chứ không phải "chuồng bồ câu".

Nguyên lí Dirichlet cơ bản:

(9)

Nếu nhốt n+ 1 con thỏ vào n cái chuồng thì bao giờ cũng có ít nhất một chuồng chứa ít nhất hai con thỏ, với n là số nguyên dương.

Nguyên lí Dirichlet tổng quát:

Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất

hN k

i

đồ vật (ở đây kí hiệu [α] để chỉ phần nguyên của số α).

Chứng minh.

Giả sử mọi hộp đều chứa ít hơn hN

k i

vật. Khi đó tổng số đồ vật là:

khN k

i−1 < khN k

i

= N.

Điều này mâu thuẫn với giả thiết là có N đồ vật cần xếp.

Nguyên lí Dirichlet mở rộng.

Nếu nhốt n con thỏ vào m ≥ 2 cái chuồng thì tồn tại một chuồng có ít nhất

hn+ m−1 m

i

con thỏ.

Chứng minh.

Giả sử trái lại mọi chuồng thỏ không có đến

hn+ m−1 m

i

=

hn−1 m

i +1 con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng

hn−1 m

i con.

Từ đó suy ra tổng số con thỏ không vượt quá m.hn−1 m

i

= n−1 con.

Điều này vô lí vì có n con thỏ. Vậy giả thiết phản chứng là sai. Nguyên lí Dirichlet mở rộng được chứng minh.

b) Ứng dụng nguyên lí Dirichlet

Nguyên lí Dirichlet là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của toán học. Nó đặc biệt có nhiều áp dụng trong lĩnh vực khác nhau của toán học. Nguyên lí này trong nhiều trường hợp người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm được vật cụ thể, nhưng trong thực tế nhiều bài toán ta chỉ cần chỉ ra sự tồn tại là đủ rồi. Đôi khi có những bài toán người ta đã dùng rất nhiều phương pháp khác nhau để giải mà vẫn chưa đi đến được kết quả, nhưng nhờ nguyên lí Dirichlet mà bài toán trở nên dễ dàng giải quyết.

Để sử dụng nguyên lí Dirichlet ta phải làm xuất hiện tình huống nhốt

"thỏ" vào "chuồng" và thoả mãn các điều kiện:

(10)

+ Số "thỏ" phải hiều hơn số "chuồng";

+ "Thỏ" phải được nhốt hết vào các "chuồng", nhưng không bắt buộc

"chuồng" nào cũng phải có "thỏ".

Thường phương pháp Dirichlet được áp dụng kèm theo phương pháp phản chứng. Ngoài ra nó còn có thể áp dụng với các phép biến hình.

1.2.3 Nguyên lí cực hạn a) Nguyên lý cực hạn

Nguyên lí cực hạn được phát biểu đơn giản như sau:

Nguyên lí 1: Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có thể chọn được số bé nhất và số lớn nhất.

Nguyên lí 2: Trong một tập khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất.

b) Ứng dụng nguyên lý cực hạn

Sử dụng nguyên lí cực hạn là một phương pháp được vận dụng cho nhiều lớp bài toán khác, đặc biệt nó có ích khi giải các bài toán tổ hợp nói chung và hình học nói riêng.

Trong quá trình tìm kiếm lời giải nhiều bài toán hình học, sẽ rất có lợi nếu chúng ta xem xét các phần tử biên, phần tử tới hạn (cực biên) nào đó, tức là phần tử mà tại đó mỗi đại lượng hình học có thể nhận giá trị lớn nhất hoặc giá trị nhỏ nhất, chẳng hạn như cạnh lớn nhất, cạnh nhỏ nhất của một tam giác, góc lớn nhất hoặc góc nhỏ nhất của một đa giác . . .

Những tính chất của các phần tử biên, phần tử tới hạn nhiều khi giúp chúng ta tìm kiếm được lời giải thu gọn của bài toán.

Nguyên lí cực hạn thường được sử dụng kết hợp với các phương pháp khác, đặc biệt là phương pháp phản chứng, được vận dụng trong trong trường hợp tập các giá trị cần khảo sát là tập hợp hữu hạn (nguyên lí 1) hoặc có thể có vô hạn nhưng tồn tại một phần tử lớn nhất hoặc nhỏ nhất (nguyên lí 2). Khi vận dụng nguyên lí này, ta phải tiến hành các bước sau:

Bước 1: Chứng minh rằng trong tất cả các giá trị cần khảo sát luôn tồn

(11)

tại giá trị lớn nhất hoặc giá trị nhỏ nhất.

Bước 2: Xét bài toán trong trường hợp riêng khi nó nhận giá trị này (nhỏ nhất hoặc lớn nhất).

Bước 3: Chỉ ra một mâu thuẫn, chỉ ra một giá trị còn nhỏ hơn (hay lớn hơn) giá trị ta đang khảo sát.

Theo nguyên lí của phương pháp phản chứng, ta sẽ suy ra điều phải chứng minh.

(12)

Chương 2

Phân loại và các phương pháp giải các bài toán đếm trong hình học tổ hợp

2.1 Phân loại các bài toán đếm

2.1.1 Đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng Bài toán 2.1. Một lưới tạo bởi m đường thẳng ngang và n đường thẳng đứng. Có bao nhiêu đỉnh phân biệt trong lưới này?

Lời giải.

Mỗi đường thẳng ngang chứa n điểm (đó là giao điểm của đường thẳng đó với những đường thẳng đứng) và có m đường thẳng như vậy. Do đó tổng số điểm giao là m.n.

Bài toán 2.2. Mỗi cạnh AB và CD của hình chữ nhật ABCD được chia thành m phần bằng nhau, còn mỗi cạnh BC và AD được chia thành nphần bằng nhau. Bằng cách nối các điểm tương ứng ở các cạnh đối nhau tạo ra một lưới hình chữ nhật. Hãy tìm số giao điểm tạo bởi đường chéo AC và những đường lưới.

Lời giải.

Ta có m+ 1 đường thẳng ngang và n+ 1 đường thẳng đứng. Đường chéo

(13)

cắt tất cả các đường thẳng đã cho nhưng có một số điểm trùng vào điểm lưới.

Dễ thấy điểm trùng với điểm lưới là điểm nằm trên cả đường thẳng ngang và đường thẳng đứng, như vậy những giao là m+ n+ 1−(m, n) (trong đó (m, n) là ước chung lớn nhất của m và n).

Bài toán 2.3. Số giao điểm lớn nhất là bao nhiêu khi ta vẽ n đường thẳng trong cùng một mặt phẳng?

Lời giải.

Số giao điểm lớn nhất chỉ xuất hiện khi và chỉ khi các đường thẳng đôi một có giao điểm phân biệt, nhưng không có ba đường nào đồng quy. Trong trường hợp này tồn tạin−1 giao điểm trên mỗi đường thẳng. Do đó số điểm giao nhau là Cn2 = n(n−1)

2 .

Bài toán 2.4. Số giao điểm lớn nhất là bao nhiêu khi ta vẽ n đường tròn trong cùng một mặt phẳng ?

Lời giải.

Lập luận tương tự bài toán trên, số giao điểm là lớn nhất khi và chỉ khi các đường tròn đôi một có hai giao điểm phân biệt, nhưng không tồn tại điểm giao nào nằm trên cùng ba đường tròn. Do đó số điểm giao nhau là 2.Cn2 = n(n−1).

Bài toán 2.5. Số giao điểm lớn nhất là bao nhiêu khi ta vẽ n hình tam giác (hình vuông) trong cùng một mặt phẳng?

Lời giải.

Vì mỗi cạnh của một tam giác chỉ có thể giao với nhiều nhất hai cạnh của một tam giác khác nên những cạnh của hai tam giác bất kì không thể có nhiều hơn 6 giao điểm. Như vậy nếu mọi cặp tam giác có 6 điểm chung và không có điểm chung nào là điểm chung của hơn 2 tam giác thì ta có thể nhận được 6.Cn2 = 3n(n−1).

Bằng phương pháp tương tự, ta nhận được kết quả số điểm giao lớn nhất là 4n.(n−1) với những hình vuông.

(14)

Bài toán 2.6. Cho hai đường thẳng d1 và d2 song song. Lấy các điểm A1, A2, . . . , Am nằm trên d1 và các điểm B1, B2, . . . , Bn nằm trên d2. Ta dựng tất cả giao điểm của các đoạn thẳng AiBj, i = 1, . . . , m; j = 1, . . . , n. Từ các đoạn thẳng đó ta có thể nhận được số giao điểm lớn nhất là bao nhiêu?

Lời giải.

Nếu số giao điểm là lớn nhất thì không tồn tại ba đương thẳng đồng quy trong cấu trúc này. Do đó nếu chọn hai điểm trên d1 và hai điểm trên d2 thì chúng xác định một giao điểm.

Số cách chọn hai điểm trên d1 là Cm2 =m(m−1)

2 và số cách chọn hai điểm trên d2 là Cn2 = n(n−1)

2 .

Như vậy số giao điểm là m.n.(m −1).(n−1)

4 .

Bài toán 2.7. Có n−giác lồi A1A2. . . An. Xác định số giao điểm của các đường chéo của đa giác A1A2. . . An nằm trong đa giác đó.

Lời giải.

Ta xét một đường chéo cố định A1Ak (k = 3,4, . . . , n− 1) và xác định số giao điểm trên đường chéo này. Trong một nửa mặt phẳng xác định bởi đường thẳng A1Ak có k−2điểm và nửa mặt phẳng còn lại chứa n−k điểm của n−2 đỉnh còn lại của đa giác lồi A1A2. . . An.

Do đó đường chéoA1Ak giao với những đường chéo khác tại (n−k)(k−2) điểm nên số giao điểm trên tất cả các đường chéo xuất phát từ A1

a1(n) =

n−1

P

k=3

(n−k) (k −2) =

n−1

P

k=3

(n+ 2)k−k2 −2n

=(n−1) (n−2) (n−3)

6 .

Nếu ta cộng tất cả các số giao điểm này của tất cả các đỉnh A1, A2,. . . , An của đa giác thì ta đếm số điểm giao 4 lần. Do đó tổng số tất cả các giao điểm của tất cả các đường chéo là

n

4a1(n) = n(n−1) (n−2) (n−3)

24 = Cn4.

(15)

Bài toán 2.8. Phần trong của mỗi cạnh hình vuông ta chọn n điểm khác nhau. Tìm số tất cả các tam giác mà đỉnh của nó là những điểm ta vừa lấy.

Lời giải.

Từ 4n điểm đã chọn ta được tổng cộng C4n3 bộ ba điểm, trong số đó có 4.Cn3 bộ ba điểm không tạo thành tam giác, do bộ ba điểm đó đều nằm trên cùng một cạnh của hình vuông. Do đó số tam giác được tạo thành là C4n3 −4.Cn3 = 2n2(5n−3).

Bài toán 2.9. Cho n−giác lồi H. Tìm tất cả số tam giác mà đỉnh là đỉnh của H và cạnh là đường chéo của H.

Lời giải.

Từ số tất cả các tam giác có đỉnh của H ta trừ đi số tam giác có một cạnh hoặc hai cạnh là cạnh của đa giác đã cho. Tổng số tất cả các tam giác có đỉnh của H là Cn3.

Số tam giác có một cạnh là cạnh của đa giác là n(n− 4), vì mỗi cạnh trong n cạnh của đa giác có thể chọn đỉnh thứ ba của tam giác trong n−4 đỉnh còn lại.

Số tam giác có hai cạnh là cạnh của đa giác là n, vì mỗi tam giác có hai cạnh kề nhau của đa giác, tức là tương ứng với bộ 3 đỉnh liên tiếp của đa giác đã cho.

Vậy số tam giác cần tính là Cn3 −n(n−4)−n= n(n−4) (n−5)

6 .

2.1.2 Đếm đối tượng tạo thành miền trong mặt phẳng

Bài toán 2.10. Trong mặt phẳng, cho n đường thẳng phân biệt. Gọi P(n) là số miền mặt phẳng mà các đường thẳng trên tạo ra. Tìm giá trị lớn nhất của số P(n).

Lời giải.

Dễ thấy P(1) = 2.

Giả sử biết số lớn nhất P(n) miền mặt phẳng có thể được chia ra bởi các đường thẳng đã cho q1, q2,. . . ,qn. Bằng cách thêm vào một đường thẳng nữa

(16)

qn+1, số những phần trong mặt phẳng tăng lên bằng số những phần mà đường thẳngqn+1 được chia ra với các đường thẳngq1,q2,. . . ,qn. Tồn tại nhiều nhất n những giao điểm như vậy trên đường thẳng qn+1, như vậy nó chia đường thẳng nhiều nhất thành n+ 1 phần. Hai trong chúng là nửa đường thẳng và còn lại là những đoạn thẳng. Do đó có quan hệ P(n+ 1) ≤ P (n) + n+ 1.

Để xác định công thức P(n) theo biến n, ta dùng kỹ thuật sau P(1) = 2,

P(2) ≤P(1) + 2, P(3) ≤P(2) + 3,

. . . . P(n) ≤P(n−1) +n.

Cộng hai vế của các bất đẳng thức trên ta được

P(n) ≤ 1 + (1 + 2 + 3 +· · ·+n) = 1 + n(n+ 1)

2 = n2 +n+ 2

2 .

Giá trịP(n) = n2 +n+ 2

2 khi và chỉ khi với mỗi i = 2,3, . . . , nđường thẳng qi có đúng i−1 giao điểm với những đường thẳng trước nó q1, q2, . . . , qn−1. Điều này xảy ra khi hệ gồmnđường thẳng đã cho không có hai đường thẳng nào song song và không có ba đường thẳng nào đồng quy.

Bài toán 2.11. Trong mặt phẳng, cho n đường tròn phân biệt. Gọi K(n) là số miền mặt phẳng được chia ra bởi n đường tròn phân biệt đó.Tìm giá trị lớn nhất của K(n).

Lời giải.

Dễ thấy K(1) = 2.

Giả sử đã biết số có khả năng lớn nhất K(n) miền mặt phẳng được chia ra bởinđường tròn phân biệt. Ta thêm đường tròn thứn+ 1 vào mặt phẳng, nó sẽ có nhiều nhất 2n giao điểm với những đường tròn đã cho và nó xác định nhiều nhất 2n cung trên đường tròn mới thêm vào. Mỗi cung chia miền chứa nó ra thêm một miền mới, do đó K(n+ 1) ≤ K(n) + 2n.

(17)

Từ đây ta cho từng giá trị của n và cộng theo vế ta được K(n) ≤ 2 + 2 + 4 + 6 +· · ·+ 2(n−1) = n2 −n+ 2.

Đẳng thức chỉ xảy ra nếu hệ thống nđường tròn đôi một cắt nhau tại hai điểm phân biệt và không có hai đường tròn nào cùng đi qua một điểm.

Để xây dựng một cấu trúc hình như thế, ta chọn một đoạn thẳng bất kì AB có độ dài d, xét hệ gồm n đường tròn nhau có bán kính d và tâm của chúng khác nhau, cùng nằm bên trong đoạnAB. Hai đường tròn bất kì trong hệ thống này có đúng hai giao điểm chung phân biệt vì khoảng cách giữa hai tâm nhỏ hơn d. Nếu ba đường tròn cùng đi qua một điểm M thì tâm của những đường tròn này tạo thành một bộ ba điểm cùng nằm trên một đường thẳng và có cùng khoảng cách tới M, điều này không thể xảy ra. Do đó giá trị lớn nhất của K(n) bằng n2 −n+ 2.

2.2 Các phương pháp giải bài toán đếm

2.2.1 Phương pháp sử dụng nguyên lí bất biến

Bài toán 2.12. Trên bảng đen ta viết 2015 dấu cộng (+) và 2016 dấu trừ (−). Mỗi lần thực hiện, cho phép xóa đi hai dấu tùy ý và viết thay vào đó một dấu cộng nếu hai dấu xóa đi là như nhau, và dấu trừ nếu ngược lại. Lặp lại phép tính đó 4030 lần. Hỏi trên bảng còn lại dấu gì?

Lời giải.

Giả sử thay dấu cộng bởi số 1, thay dấu trừ bởi số −1. Khi đó phép toán đã cho tương đương với việc thay hai số tùy ý bởi tích của chúng. Phép tính này không làm thay đổi tích của tất cả các số đã cho. Như vậy tích của tất cả các số đã cho là một bất biến trong quá trình lặp lại phép toán. Tại trạng thái xuất phát, tích này bằng 1nên ở trạng thái cuối cùng, tích đó cũng phải bằng 1. Sau 4030 lần thực hiện, ta chỉ còn một số trên bảng, số đó phải là 1. Do đó dấu còn lại trên bảng là dấu (+).

Bài toán 2.13. Cho một bảng hình vuông có cạnh 10cm được chia ra thành 100 ô vuông nhỏ với cạnh 1cm. Ta đặt lên bảng hình vuông đó 25 hình chữ

(18)

nhật như nhau, mỗi hình chữ nhật có chiều dài 4cm, chiều rộng 1cm và được chia thành 4 ô vuông có cạnh là 1cm. Có thể sắp xếp những hình chữ nhật trên bảng hình vuông sao cho chúng phủ toàn bộ bảng hình vuông hay không?

Lời giải.

Ta tô bảng vuông bằng màu đen trắng như hình vẽ:

Ta nhận được 25 ô đen và 75 ô trắng. Ta chú ý là đặt những hình chữ nhật trên bảng vuông sao cho mỗi ô vuông của hình chữ nhật trùng với một ô vuông nào đó của bảng vuông. Hình chữ nhật này sẽ phủ lên hoặc là2hoặc là 0 ô vuông đen. Từ đó suy ra khi đặt tất cả 25 hình chữ nhật trên bảng vuông, chúng sẽ phủ kín một số chẵn những ô vuông đen. Bởi vì số lượng của ô vuông đen đã tô là 25, nó không phải là một số chẵn. Như vậy không thể phủ bằng 25 hình chữ nhật trên hình vuông đã cho.

Bài toán 2.14. Một nền nhà hình chữ nhật được lát kín bằng những viên gạch men kích thước 2×2và 1×4. Khi sửa nền nhà, người ta phải dỡ tất cả các viên gạch men đã lát, nhưng không may bị vỡ mất một viên kích thước 2×2. Vì không có loại gạch men kích thước 2×2 nên người ta phải thay viên bị vỡ bởi các viên kích thước 1×4. Chứng minh rằng bây giờ nền nhà không thể được lát kín bởi các viên gạch ấy.

Lời giải.

(19)

Chia nền nhà thành các hình vuông kích thước 1×1 và tô đen các ô ở dòng lẻ, cột lẻ. Ta thấy mỗi viên gạch 1×4 chiếm 4 ô trên nền nhà sẽ chứa một số chẵn các ô đen, còn các viên gạch 2×2 chiếm đúng một ô đen. Do lúc đầu tất cả gạch lát kín nền nhà nên số viên gạch 2×2 có cùng tính chẵn lẻ với số ô được tô đen.

Vì vậy, nếu số các viên gạch 2×2 bớt đi một đơn vị, tức là tính chẵn lẻ bị thay đổi (khác với tính chẵn lẻ của các ô đen). Do đó nền nhà không thể được lát kín.

Bài toán 2.15. Cho một bàn cờ vua 8×8. Hỏi rằng quân mã có thể đi từ nước đầu tiên ở ô dưới cùng bên trái và kết thúc ở ô trên cùng bên phải hay không? (với điều kiện nó phải đi qua tất cả các ô trên bàn cờ và mỗi ô chỉ đi qua đúng một lần).

Lời giải.

Để đi qua tất cả các ô trên bàn cờ, từ ô dưới cùng bên trái đến ô trên cùng bên phải, mỗi ô chỉ đi qua một lần, quân mã phải đi tất cả 63 nước. Do ở mỗi nước đi, quân mã sẽ chuyển từ ô đen sang ô trắng hoặc ngược lại, nên sau 63 nước đi, ô cờ mà quân mã đứng sẽ đổi màu so với vị trí ban đầu. Vì ô dưới cùng bên trái và ô trên cùng bên phải luôn cùng đen hoặc cùng trắng nên không thể tồn tại một cách đi thỏa mãn đề bài.

Bài toán 2.16. Dùng những viên gạch 2×2 và 3×3 để lát sân kích thước n×n. Xác định điều kiện của sân n×n (n ≥2) để lát được mà không phải cắt gạch.

Lời giải.

(20)

Với n chẵn, ta có thể dùng toàn gạch 2×2 để lát được.

Với n lẻ. Ta xét các trường hợp sau:

+ Trường hợp 1: n chia hết cho 3. Có thể lát được bằng cách dùng toàn gạch 3×3.

+ Trường hợp 2: n không chia hết cho 3. Chia sân thành bảng ô vuông kích thước 1×1. Ta tô màu đỏ cho các ô ở cột lẻ, tô màu xanh cho các ô ở cột chẵn. Có tất cả nn−1

n + 1 ô màu đỏ và n

n−1 n + 1

ô màu xanh.

Nhận thấy rằng: mỗi viên gạch 2 ×2 luôn phủ 2 ô màu đỏ và hai ô màu xanh, và mỗi viên gạch3×3 phủ 6 ô màu đỏ và 3 ô màu xanh hoặc 3 ô màu đỏ và 6 ô màu xanh. Nếu sân bị phủ kín thì hiệu của tổng số ô màu đỏ và tổng số ô màu xanh chia hết cho 3. Tuy nhiên, thực tế trong bảng hiệu đó là n không chia hết cho 3. Điều mâu thuẫn này chứng tỏ trường hợp này sân không thể được lát kín.

Vậy kích thước sân là 2k ×2k hoặc 3k×3k.

Bài toán 2.17. Các dấu cộng (+) và dấu trừ (−) được viết vào các ô trong một bảng 6×6 như trong hình vẽ. Mỗi lần thực hiện, cho phép đảo ngược tất cả các dấu trong cùng một hàng, trong cùng một cột, hoặc dọc theo một đường bất kì song song với một trong hai đường chéo của bảng (đặc biệt có thể dỏ dấu của các ô ở góc). Có thể hay không, bằng cách thực hiện các phép tính trên đây, nhận được một bảng không có dấu trừ?

Lời giải.

(21)

Giả sử thay dấu cộng bởi số 1, thay dấu trừ bởi số −1. Khi đó phép toán đã cho tương đương với việc thay 1 bởi −1, thay −1 bởi 1 ở tất cả các ô trong cùng một hàng, trong cùng một cột, hoặc dọc theo một đường bất kì song song với một trong hai đường chéo của bảng (đặc biệt có thể dỏ dấu của các ô ở góc).

Xét tập hợp các ô đánh dấu x trong bảng:

Rõ ràng khi thực hiện phép tính cho phép, số các ô có thể đảo dấu trong tập hợp này là một số chẵn. Do đó tích tất cả các số của các ô trong tập hợp này là bất biến. Tại trạng thái xuất phát, tích này bằng −1. Do đó ta không thể nhận được một bảng không có dấu trừ nào.

Bài toán 2.18. Điền29 số nguyên dương đầu tiên vào các ô vuông con trong bảng 6×5 như sau:

Mỗi lần thực hiện, cho phép thay đổi vị trí các ô trong bảng theo qui tắc sau: Mỗi lần lấy một số ở ô kề với ô trống rồi chuyển số đó sang ô trống. Hỏi

(22)

sau một số hữu hạn phép chuyển số nói trên từ bảng số ban đầu ta có thể nhận được bảng số sau hay không?

Lời giải.

Giả sử nhờ phép chuyển số theo qui tắc của đề bài, từ bảng 1 ta nhận được bảng 2. Ta coi ô trống của mỗi bảng là ô được điền số 0. Với mỗi bảng nhận được trong quá trình chuyển số, ta liệt kê tất cả các số trong bảng theo thứ tự từ trái qua phải, từ trên xuống dưới. Khi đó, với mỗi bảng số sẽ có một hoán vị của 30 số tự nhiên đầu tiên. Và do đó, giả sử trên cho thấy, từ hoán vị

I(1,2,3, . . . ,11,12,0,13,14,15, . . . ,29) ta có thể nhận được hoán vị II(29,2,3, . . . ,11,12,0,13,14,15, . . . ,28,1)

nhờ việc thực hiện liên tiếp một số hữu hạn lần phép chuyển chỗ các số hạng trong hoán vị theo qui tắc (*): mỗi lần, lấy một số hạng khác 0 của hoán vị rồi đổi vị trí của số hạng đó và 0 cho nhau. Giả sử (a1, a2, . . . , a30) là một hoán vị của 30 số tự nhiên đầu tiên. Ta gọi cặp số ai, aj là cặp số ngược của hoán vị trên nếu ai > aj và i < j. Dễ thấy sau một số lần thực hiện phép đổi chỗ các số hạng theo qui tắc (*) đối với hoán vị (a1, a2, . . . , a30) thì cặp số ngược của hoán vị đó sẽ tăng lên hoặc giảm đi một số lẻ đơn vị. Ta có số cặp số ngược của hoán vị I là 12 và số cặp số ngược của hoán vị II là 67.

Do đó từ hoán vị I chỉ có thể nhận được hoán vị II sau một số lẻ lần thực hiện phép đổi chỗ các số hạng. Do đó từ bảng 1 nhận được bảng 2 thì số lần chuyển số phải là số lẻ.

(23)

Tô màu tất cả các ô vuông con trong bảng 6×5 như bàn cờ bởi hai màu đen trắng. Khi đó sau mỗi lần chuyển số, số 0 sẽ được chuyển từ ô có màu này sang ô có màu kia. Do số 0 ở bảng 1 và bảng 2 nằm ở hai ô cùng màu nên từ bảng 1 ta chỉ có thể nhận được bảng 2 sau một số chẵn lần chuyển số (mâu thuẫn). Vậy từ bảng 1 ta không thể nhận được bảng 2 theo qui tắc trên.

Bài toán 2.19. Trên một bảng ô vuông 8×8 bao gồm 32 ô trắng và 32 ô đen. Nếu một người chơi thay tất cả các ô trắng thành ô đen và ô đen thành ô trắng cùng một lúc trong một hàng hoặc một cột bất kì thì có thể thực hiện hữu hạn bước thay đổi như vậy để trên bảng chỉ còn đúng một ô đen hay không?

Lời giải.

Giả sử trên một hàng hoặc một cột trước khi thực hiện thay đổi có đúng k ô đen thì sau khi thực hiện một lần thay đổi, số ô đen trong hàng hoặc cột đó sẽ là 8− k. Do đó sự thay đổi số ô đen trong hàng hoặc cột đó là (8−k)−k = 8−2k. Do 8−2k là một số chẵn nên tính chẵn lẻ của số các ô đen là bất biến khi thực hiện biến đổi. Vì vậy, ban đầu bảng có 32 ô đen nên không thể đưa tới bảng chỉ còn lại đúng 1 ô đen.

Bài toán 2.20. Tại mỗi ô vuông trong bảng8×8 được viết một số nguyên.

Ta có thể chọn bất kì bảng nhỏ 3×3hoặc 4×4và tăng tất cả số trong bảng nhỏ lên 1 đơn vị. Với cách làm như vậy liệu có thể nhận được những số chia hết cho 3 trong tất cả ô vuông của bảng 8×8 sau một số hữu hạn lần thực hiện không?

Lời giải.

Câu trả lời là không.

Thật vậy: Tô màu đen cho các ô trong bảng như hình vẽ.

Gọi s là tổng các số chứa trong các ô màu đen trong bảng.

Nhận xét 2.1. Mỗi hình vuông kích thước 3×3 luôn chứa 6 hoặc 9 ô màu đen, còn mỗi hình vuông kích thước 4×4 luôn chứa 12 ô màu đen.

(24)

Suy ra sau một thao tác tổng các số trong các ô màu đen chia cho 3 luôn có số dư không đổi. Do đó nếu ngay từ đầu tổng s không chia hết cho 3, thì trong các ô được tô màu đen luôn tồn tại một ô có chứa các số không chia hết cho 3.

Vậy không thể nhận được những số chia hết cho 3 trong tất cả ô vuông của bảng 8×8 sau một số hữu hạn lần thực hiện.

Bài toán 2.21. Các số 1,2,· · · ,2011 được viết trên một đường tròn. Mỗi lần thực hiện, ta xóa hai số tùy ý và thay vào đó ta viết phần dư của tổng hai số đó khi chia cho 13. Lặp lại phép tính này cho đến khi trên đường tròn chỉ còn một số. Hỏi số đó là số nào?

Lời giải.

Ta có thặng dư dương bé nhất môđulô 13 của tổng các số đã viết là một bất biến khi thực hiện phép toán trên. Mặt khác, ở trạng thái ban đầu, ta có

1 + 2 + 3 +· · ·+ 2011 = 2024072 ≡ 11 (mod 13).

Vậy số cuối cùng còn lại trên đường tròn là số 11.

Bài toán 2.22. Một hình tròn được chia thành 10 cung. Trên mỗi cung, người ta đặt một miếng bìa. Có thể di chuyển hai miếng bìa tùy ý sang cung kề bên, nhưng phải di chuyển hai miếng theo chiều ngược nhau. Thực hiện liên tiếp việc di chuyển nói trên, có thể dồn được tất cả các miếng bìa vào cùng một cung hay không?

(25)

Lời giải.

Ta đánh số các cung tròn lần lượt từ 1 đến 10 theo chiều ngược kim đồng hồ. Ở trạng thái ban đầus0, mỗi cung có một miếng bìa. Giả sử ở trạng thái s nào đó, số miếng bìa ở cung thứ k là ak(s).

Đặt r(s) = (1.a1(s) + 2.a2(s) +· · ·+ 10.a10(s)) ≡5 (mod 10).

Ta thấy đại lượng này không thay đổi trong quá trình di chuyển các miếng bìa theo cách đã cho. Do ở trạng thái ban đầu r(s0) = (1 + 2 +· · ·+ 10) ≡5 (mod 10) nên không thể đưa về trạng thái t mà tất cả các miếng bìa đều nằm ở một cung vì khi đór(t) = 0. Vậy không thể dồn được tất cả các miếng bìa vào một cung.

Bài toán 2.23. Một hình tròn được chia thành 6 rẻ quạt. Ta viết vào các rẻ quạt này các số 1,0,1,0,0,0 theo thứ tự nguợc chiều kim đồng hồ. Thực hiện thao tác lặp sau: tăng số của hai rẻ quạt cạnh nhau lên 1 đơn vị. Khi thực hiện các thao tác trên có thể đưa đến kết quả các số trong các rẻ quạt đều bằng nhau không?

Lời giải.

Theo chiều ngược kim đồng hồ, ta kí hiệu các số trong các rẻ quạt hiện thời lần lượt là a1, a2, a3, a4, a5, a6.

Khi đó đại lượng S = a1 −a2+a3 −a4 +a5−a6 là một bất biến. Vì lúc khởi đầu S = 2 nên ta không thể đưa đến kết quả các số trong các rẻ quạt đều bằng nhau vì khi đó S = 0.

2.2.2 Phương pháp sử dụng nguyên lí Dirichlet

Bài toán 2.24. Chứng minh rằng một đường thẳng chỉ có thể cắt nhiều nhất hai cạnh của một tam giác ở phần trong của các cạnh này.

Lời giải.

Một đường thẳng d bất kì luôn chia mặt phẳng ra làm hai miền, cho nên theo nguyên tắc Dirichlet, tồn tại một miền chứa ít nhất hai đỉnh, không mất tổng quát ta giả sử đó là hai đỉnh A và B. Khi đó cạnh AB nằm hoàn toàn trong nửa mặt phẳng này và không thể cắt d được.

(26)

Bài toán 2.25. Trong hình vuông cạnh bằng 1, đặt 51 điểm bất kì, phân biệt. Chứng minh rằng có ít nhất 3 trong số 51 điểm đó nằm trong một hình tròn bán kính 1

7. Lời giải.

Chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnh bằng 1

5.Theo nguyên lý Dirichlet, tồn tại ít nhất một hình vuông con a chứa ít nhất ba điểm trong số 51 điểm đó. Đường tròn ngoại tiếp (a) có bán kính

1 5√

2 ≤ 1 7.

Vậy ba điểm nói trên nằm trong hình tròn đồng tâm với đường tròn (a) có bán kính 1

7.

Bài toán tổng quát 2.1 (Tổng quát hóa bài toán). Dựa vào bài giải bài toán trên ta có thể tổng quát hóa bài toán trên với α là kích thước của cạnh hình vuông,mlà số điểm đặt bất kì, phân biệt. Chứng minh rằng có ít nhấtn trong số m điểm đó nằm trong một hình trong bán kính α2

r 2.

h m n−1

i (trong đó kí hiệu [a] là phần nguyên của a).

Lời giải.

Chia hình vuông đã cho thànhh m n−1

i

hình vuông con bằng nhau có cạnh bằng α2

rh m n−1

i

. Theo nguyên lí Dirichlet, tồn tại ít nhất một hình vuông

con có chứa ít nhất n điểm trong số m điểm đó.

Đường tròn ngoại tiếp (C) có bán kính α2 r

2.

h m n−1

i.

Vậy n điểm trên nằm trong hình tròn đồng tâm với đường tròn (C) có bán kính α2

r

2.h m n−1

i .

Bài toán 2.26. Cho (xi, yi, zi) (i = 1,2,3,4,5,6,7,8,9)là một tập hợp gồm 9 điểm khác nhau có các tọa độ nguyên trong không gian.

(27)

Chứng minh rằng trung điểm của đường nối ít nhất một trong các cặp điểm này có tọa độ nguyên.

Lời giải.

Gọi tọa độ hai điểm bất kì trong không gian là A(a, b, c) và B(d, e, f).

Vậy trung điểm của đoạn AB là O

a+d

2 ,b+e

2 ,e+ f 2

. Các tọa độ của điểm O nguyên nếu và chỉ nếu a và d; b và e; c và f cùng chẵn hoặc cùng lẻ.

Vì có 23 = 8 bộ ba chẵn lẻ khác nhau

((c, c, c); (l, l, l); (c, c, l); (c, l, l); (c, l, c); (l, c, c); (l, c, l); (l, l, c))

nên theo nguyên lí Dirichlet có ít nhất 2 trong 9 điểm có cùng bộ ba chẵn lẻ như nhau.

Vậy có ít nhất một cặp điểm mà điểm chính giữa của chúng có tọa độ nguyên.

Bài toán tổng quát 2.2 (Tổng quát hóa bài toán). Cho tập hợp gồm m điểm khác nhau có các tọa độ nguyên trong không gian. Chứng minh rằng trung điểm của đường nối ít nhất

h hm

8

i + 1 2

i

trong các cặp điểm này có tọa độ nguyên.

Lời giải.

Gọi tọa độ hai điểm bất kì trong không gian là A(a, b, c) vàB(d, e, f) Vậy trung điểm của đoạn AB là Oa+d

2 ,b+e

2 ,e+f 2

.

Các tọa độ của điểm O nguyên nếu và chỉ nếu a và d; b và e; c và f cùng chẵn hoặc cùng lẻ. Vì có 23 = 8 bộ ba chẵn lẻ khác nhau

((c, c, c); (l, l, l); (c, c, l); (c, l, l); (c, l, c); (l, c, c); (l, c, l); (l, l, c))

nên theo nguyên lí Dirichlet có ít nhất hm

8 i

+ 1 trong m điểm có cùng bộ ba chẵn lẻ như nhau.

Vậy có ít nhất h hm

8

i + 1 2

i

cặp điểm mà điểm chính giữa của chúng có tọa độ nguyên.

(28)

Bài toán 2.27. Trong một hình vuông có cạnh là 1 chứa một số đường tròn phân biệt. Tổng tất cả chu vi của chúng là 10. Chứng minh rằng tồn tại một đường thẳng cắt ít nhất 4 đường tròn trong những đường tròn đó.

Lời giải.

Chọn một cạnh hình vuông chẳng hạn là CD rồi chiếu vuông góc các đường tròn xuống cạnh đó. Dễ thấy rằng hình chiếu của một đường tròn bán kính R sẽ là một đoạn thẳng có độ dài 2R. Gọi C1, C2, . . . , Cn là chu vi của nđường tròn đã cho. Khi đó theo giả thiết, ta được:C1+C2+· · ·+Cn = 10.

Mặt khác, đường tròn với chu vi Ci sẽ có bán kính: Ri = Ci

.

Vậy hình chiếu của hình tròn với chu vi Ci sẽ là đoạn thẳng với độ dài là:

2Ci

2π = Ci

π .

Tổng độ dài hình chiếu của n đường tròn trên cạnh đã cho là:

C1

π + C2

π +· · ·+ Cn

π = 10 π . Mà 10

π > 3, nên theo nguyên lý Dirichlet đối ngẫu suy ra có một điểm M nào đó thuộc CD là điểm trong chung của ít nhất 4 đoạn thẳng đã chiếu xuống. Khi đó, đường thẳng đi quaM vuông góc với CD cắt ít nhất 4 trong những đường tròn đó. Ta được điều phải chứng minh.

(29)

Bài toán 2.28. Trong một cái bát hình vuông cạnh 18 cm có 128 hạt vừng.

Chứng minh rằng tồn tại hai hạt vừng có khoảng cách tới nhau nhỏ hơn 2cm.

Lời giải.

Lấy mỗi hạt vừng làm tâm dựng hình tròn bán kính 1cm. Các hình tròn này nằm hoàn toàn trong hình vuông có cạnh20cm thu được từ hình vuông đã cho bằng cách tịnh tiến bốn cạnh của nó một khoảng 1cm ra phía ngoài.

Tổng diện tích của các hình tròn bán kính 1cm này là 128π > 402,112>

400. Do đó tổng diện tích các hình tròn này lớn hơn diện tích hình vuông cạnh20cm. Vì vậy tồn tại ít nhất hai đường tròn giao nhau tại hai giao điểm phân biệt, nghĩa là khoảng cách giữa hai tâm của hai đường tròn đó nhỏ hơn tổng hai bán kính của chúng.

Vậy tồn tại hai hạt vừng có khoảng cách tới nhau nhỏ hơn 2cm.

Bài toán 2.29. Trong hình chữ nhật 3×4 đặt 6 điểm phân biệt. Chứng minh rằng trong số đó luôn tìm được hai điểm có khoảng cách giữa chúng không lớn hơn √

5. Lời giải.

Chia hình chữ nhật đã cho thành năm hình đa giác ABCD, DCKEF, KF N M, N F EQR, QEDAS.

(30)

Vì có 6 điểm nên theo nguyên lí Dirichlet tồn tại một trong năm hình trên, mà hình này chứa ít nhất hai trong 6 điểm đã cho. Ta đưa vào khái niệm sau:

Giả sử P là một hình.

Đặt d(P) = max

M,N∈P {M N} và đại lượng d(P) gọi là đường kính của hình P. Dễ thấy cả năm hình trên đều có đường kính bằng√

5. (Thí dụ: d(ABCD) = AC = d(DCKF E) = CE = KE = CF = DK = √

5). Từ đó suy ra luôn tìm được 2 điểm trong số 6 điểm đã cho có khoảng cách không lớn hơn √

5. Đó là điều phải chứng minh.

Từ đó ta có các bài toán tương tự như sau

Bài toán 2.30. Bên trong tam giác đều ABC cạnh 1 đặt 5 điểm. Chứng minh rằng tồn tại 2 điểm có khoảng cách nhỏ hơn 0,5.

Lời giải.

Các đường trung bình của tam giác đều cạnh 1 sẽ chia nó ra làm 4 tam giác đều cạnh 0,5.

Do đó trong một tam giác nhỏ đó có ít nhất 2 điểm đã cho, và các điểm đó không thể rơi vào các đỉnh của tam giác ABC. Vậy khoảng cách giữa hai điểm đó nhỏ hơn 0,5.

Bài toán 2.31. Trong một hình tròn đường kính bằng 5 có 10 điểm. Chứng minh rằng tồn tại ít nhất hai điểm mà khoảng cách giữa chúng bé hơn hoặc bằng 2.

(31)

Lời giải.

Thật vậy, trong đường tròn tâm O đường kính 5, vẽ đường tròn đồng tâm với nó có đường kính 2. Chia hình tròn đã cho thành 9 phần như hình vẽ, đó là đường tròn đường kính 2 và 8 phần bằng nhau II, III, . . . , IX mà mỗi phần là 1

8 hình vành khăn. Rõ ràng I có đường kính bằng 2.

Xét chẳng hạn như hình trên, có thể thấy ngay đường kính của III là d= AD = BC.

(32)

Vì DOA\ = 450, nên

d2 = DA2 = DO2 + AO2 −2DO.OA.cos 450

= 5 2

+ 12 −s.5 2.1.

√2

2

= 24

4 + 1− 5√ 2 2 . Từ đó, suy ra: d2 < 29

4 − 5 2.

Theo nguyên lí Dirichlet tồn tại ít nhất hai điểm rơi vào một trong các miền I, II, III, . . . , IX có đường kính bằng 2, còn các miền II, . . . , IX có đường kính bằng nhau và bằng d (với d ≥2), từ đó suy ra tồn tại hai trong số 10 điểm đã cho mà khoảng cách giữa chúng nhỏ hơn hoặc bằng 2. Đó là điều phải chứng minh.

Bài toán 2.32. Trên mặt phẳng cho 25 điểm. Biết rằng trong ba điểm bất kì trong số đó luôn luôn tồn tại hai điểm cách nhau một khoảng nhỏ hơn 1.

Chứng minh rằng tồn tại hình tròn bán kính 1 chứa ít nhất 13 điểm đã cho.

Lời giải.

Lấy A là một trong số 25 điểm đã cho. Xét hình tròn O1(A,1) tâm A bán kính 1. Chỉ có hai khả năng sau có thể xảy ra:

1) Nếu tất cả các điểm đã cho nằm trong O1(A,1) thì kết luận của bài toán hiển nhiên đúng.

2) Tồn tại điểm B 6= A (B thuộc trong số 25 điểm đã cho), sao cho B /∈ O1(A,1). Vì B /∈ O1(A,1) nên AB > 1.

Xét hình tròn O2(B,1) tâm B, bán kính 1. Lấy C là điểm bất kì trong số 25 điểm đã cho sao cho C 6= A, C 6= B. Theo giả thiết (và dựa vào AB > 1), ta có min{CA, CB} < 1.

Vì thế C ∈ O1(A,1), hoặc C ∈ O2(B,1).

Điều này chứng tỏ rằng các hình tròn O1(A,1), O2(B,1) chứa tất cả 25 điểm đã cho.

Do đó theo nguyên lí Dirichlet, ít nhất 1 trong hai hình tròn trên chứa 13 điểm đã cho. Đó là điều phải chứng minh.

(33)

Bài toán tổng quát 2.3 (Tổng quát hóa bài toán). Cho 2n+ 1 điểm trên mặt phẳng (với n≥ 3). Biết rằng trong ba điểm bất kì trong số đó luôn luôn tồn tại hai điểm cách nhau một khoảng nhỏ hơn 1. Khi đó tồn tại hình tròn bán kính 1 chứa ít nhất n+ 1 điểm đã cho.

Bài toán 2.33. Tìm hình vuông có kích thước bé nhất, để trong hình vuông đó có thể sắp xếp năm hình tròn bán kính 1, sao cho không có hai hình tròn nào trong chúng có điểm chung.

Lời giải.

Giả sử hình vuôngABCD có tâmO và cạnh a, chứa năm hình tròn không cắt nhau và đều có bán kính bằng 1. Vì cả năm hình tròn này đểu nằm trọn trong hình vuông, nên các tâm của chúng nằm trong hình vuông A0B0C0D0 có tâm O và cạnh a−2, ở đây A0B0//AB.

Các đường thẳng nối các trung điểm của các cạnh đối diện của hình vuông A0B0C0D0 chia hình vuông A0B0C0D0 thành 4 hình vuông nhỏ. Theo nguyên lí Dirichlet tồn tại một trong 4 hình vuông nhỏ mà trong hình vuông này chứa ít nhất 2 trong số 5 tâm hình tròn nói trên (không mất tính tổng quát ta giả sử là O0 và O00).

Để ý rằng vì không có 2 hình tròn nào (trong số 5 hình tròn) cắt nhau, nên

O0O00 ≥2. (1)

Mặt khác do O0, O00 cùng nằm trong một hình vuông nhỏ (cạnh của hình vuông nhỏ đó bằng a−2

2 ) nên ta lại có O0O00 ≤ a−2

2

2. (2)

Từ (1) và (2) suy ra:

a−2 2

2 ≥2 ⇒a ≥2√

2 + 2. (3)

Vậy mọi hình vuông cạnh a thỏa mãn yêu cầu đề bài, ta đều có (3). Bây giờ xét hình vuông ABCD có a = 2√

2 + 2. Xét năm hình tròn có tâm là O,

(34)

A’, B’, C’, D’ như hình trên, thì mọi yêu cầu của đề bài thỏa mãn. Tóm lại, hình vuông có kích thước bé nhất cần tìm là hình vuông với cạnh 2√

2 + 2. Bài toán 2.34. Chứng minh rằng trong một hình tròn bán kính 1, không thể chọn được quá 5 điểm mà khoảng cách giữa hai điểm tùy ý trong chúng đều lớn hơn 1.

Lời giải.

Chia hình tròn tâmO đã cho thành 6 hình quạt bằng nhau (tâm các hình quạt đều là tâm O).

Ta biết rằng khoảng cách giữa hai điểm bất kì trong một hình quạt nhỏ hơn hoặc bằng 1, vì thế từ giả thiết suy ra tại mỗi hình quạt có không quá 1 điểm rơi vào.

Giả thiết phản chứng chọn được quá 5 điểm thỏa mãn yêu cầu đề bài. Vì lí do trên nên số điểm không thể quá 7 (vì nếu số điểm chọn được mà lớn hơn hoặc bằng 7 thì theo nguyên lí Dirichlet có ít nhất hai điểm được chọn nằm trong một cung hình quạt), mà điều này mâu thuẫn với nhận xét trên.

Vậy từ giả thiết phản chứng suy ra tồn tại sáu điểm và mỗi điểm nằm trong một hình quạt sao cho khoảng cách giữa hai điểm tùy ý trong chúng đều lớn hơn 1 mà

A\1OA2 +A\2OA3 +A\3OA4 +A\4OA5 +A\5OA6 = 3600.

(35)

Khi đó suy ra: min

i=1,6

A\iOAi+1 ≤ 3600

6 = 600 (ở đây đặt A7 ≡ A1).

Xét tam giác AkOAk+1 (với k ∈ {1,2,3, . . . ,6}) và m in

i=1,6

A\iOAi+1 = Ak\OAk+1 khi đó: Ak\OAk+1 ≤ 600.

Vì OAk ≤ 1, OAk+1 ≤ 1,Ak\OAk+1 ≤600 nên từ đó suy ra:

Ak\OAk+1 ≤ max{Ak\Ak+1O,OA\kAk+1}.

Từ đó theo mối liên hệ giữa cạnh và góc trong tam giác AkOAk+1, thì AkAk+1 ≤ max{OAk, OAk+1} ≤ 1.

Điều này mâu thuẫn với AkAk+1 > 1 (vì hệ sáu điếm A1, A2, . . . , A6 thỏa mãn yêu cầu đề bài). Từ đó ta thấy giả thiết phản chứng là sai. Điều đó có nghĩa là không thể chọn quá 5 điểm thỏa mãn yêu cầu để bài. Ta được điều phải chứng minh.

Bài toán 2.35. Cho hình tròn có bán kính n, ở đây n là số nguyên dương.

Trong hình tròn có 4n đoạn thẳng đều có độ dài bẳng 1. Cho trước một đường thẳng d. Chứng minh rằng tồn tại đường thẳng d0 hoặc song song với d, hoặc là vuông góc với d sao cho d0 cắt ít nhất hai đoạn thẳng đã cho.

Lời giải.

Giả sử AB là đoạn thẳng có độ dài bằng 1, a và a0 là hai đường thẳng bất kì vuông góc với nhau. Gọi A0B0 và A00B00 là các hình chiếu của AB lên a và a0. Khi đó ta có: A0B0+A00B00 ≥ AB hay A0B0 +A00B00 ≥1.

Áp dụng vào bài toán, ta gọi d00 là đường thẳng bất kì vuông góc với d.

Chiếu vuông góc tất cả 4n đoạn thẳng lên d và d00. Suy ra tổng độ dài hình

(36)

chiếu của tất cả 4n đoạn thẳng không bé hơn 4n.

Vì vậy, theo nguyên lí Dirichlet trong hai đường thẳng d và d00 có ít nhất một đường thẳng mà tổng độ dài của hình chiếu các đoạn thằng lên nó không bé hơn 2n. Không mất tính tổng quát ta có thể giả sử đó là d.

Mặt khác, mỗi đoạn thẳng đầu nằm trọn trong hình tròn bán kính n (đường kính 2n), nên hợp các hình chiếu của chúng trên d có độ dài không vượt quá 2n.

Vì vậy, theo nguyên lí dirichlet trên d tồn tại ít nhất một điểm M thuộc vào hình chiếu của ít nhất hai đoạn thẳng trong số 4n đoạn thẳng đã cho.

Gọi d0 là đường thẳng vuông góc với d tại M. Đường thẳng d0 chính là đường thẳng cần tìm.

Nhận xét 2.2. Nếu ở trên thay d bởi d00 thì đường thẳng phải tìm sẽ có dạng song song với d (vì nó vuông góc với d00).

Bài toán 2.36.Cho 2016 điểmM1, M2, . . . , M2016phân biệt trên mặt phẳng.

Vẽ một đường tròn bán kính 1 tùy ý. Chứng minh rằng tồn tại điểm S trên đường tròn sao cho SM1 + SM2 +· · ·+SM2016 ≥2016.

Lời giải.

Xét một đường kính S1S2 tùy ý của đường tròn, ở đây S1, S2 là hai đầu của

(37)

đường kính. Vì S1S2 = 2, nên ta có:













S1M1 +S2M1 ≥S1S2 = 2, S1M2 +S2M2 ≥S1S2 = 2,

· · ·

S1M2016+S2M2016 ≥2.

Cộng từng vế của 2016 bất đẳng thức trên ta có:

S1M1+S1M2+· · ·+S1M2016+S2M1+S2M2+· · ·+S2M2016 ≥ 4032. (4)

Từ (4) và theo nguyên lí Dirichlet suy ra trong hai tổng của vế trái của (4), có ít nhất một tổng lớn hơn hoặc bằng 2016. Giả sử

S1M1 +S1M2 +· · ·+S1M2016 ≥2016 khi đó lấy S = S1. Đó là điều phải chứng minh.

Bài toán 2.37. Cho chín đường thẳng cùng có tính chất là mỗi đường thẳng chia hình vuông thành hai tứ giác có tỉ số diện tích bằng 2

3. Chứng minh rằng tồn tại ít nhất ba đường thẳng trong số đó cùng đi qua một điểm.

Lời giải.

Các đường thẳng đã cho không thể cắt các cạnh kề nhau của hình vuông, bởi vì nếu thế chúng chia hình vuông thành một tam giác và ngũ giác (chứ không phải là chia hình vuông thành hai tứ giác).

(38)

Vì lẽ đó, mọi đường thẳng (trong số chín đường thẳng) đều cắt hai cạnh đối của hình vuông và dĩ nhiên không đi qua một đỉnh nào của hình vuông cả.

Giả sử một đường thẳng cắt hai cạnh đối BC và AD tại các điểm M và N.

Gọi E, F, P, Q tương ứng là các trung điểm của AB, CD, BC, AD. Gọi J1, J2, J3, J4 là các điểm sao cho J1, J2 nằm trên EF, J3, J4 nằm trên PQ và thỏa mãn:

EJ1

J1F = F J2

J2E = P J3

J3Q = QJ4 J4P = 2

3.

Khi đó từ đó lập luận trên ta suy ra mỗi đường thẳng có tính chất thỏa mãn yêu cầu của đề bài phải đi qua một trong 4 điểm J1, J2, J3, J4 nói trên. Vì có

(39)

chín đường thẳng nên theo nguyên lí dirichlet phải tồn tại ít nhất một trong 4 điểm J1, J2, J3, J4 sao cho nó có ít nhất ba trong 9 đường thẳng đã cho đi qua.

Vậy có ít nhất 3 đường thẳng trong 9 đường thẳng đã cho đi qua một điểm.

Bài toán 2.38. Trong mặt phẳng cho tập hợp A có n điểm (n≥ 2). Một số cặp điểm được nối với nhau bằng đoạn thẳng. Chứng minh rằng tập hợp A đã cho, có ít nhất hai điểm đươc nối với cùng số lượng các điểm khác thuộc A.

Lời giải.

Giả sử a ∈ A Ta kí hiệu S(a) là số lượng các điểm của A nối với a mà S(a) = 2, S(b) = 3, S(c) = 1, S(d) = 2, S(e) = 2.

Bài toán đã cho trở thành: Chứng minh rằng tồn tại a1, a2 ∈ A, mà S(a1) = S(a2). Rõ ràng với mọi a ∈ A, ta có

0≤ S(a) ≤1. (5)

Mặt khác, dễ thấy không tồn tại hai điểm a ∈ A, b ∈ A mà

S(a) =n−1 và S(b) = 0. (6)

(40)

Thật vậy: nếu có (6), thì từ S(a) =n−1, ta suy ra a nối với tất cả n−1 điểm còn lại, tức là a cũng nối với b. Điều đó có nghĩa là S(b) ≥ 1, và dẫn đến mâu thuẫn với S(b) = 0.

Gọi S là tập hợp các giá trị mà các đại lượng S(a) nhận, a ∈ A, tức là:

S = {m/m = S(a), a ∈ A}.

Như vậy từ (5) suy ra tập hợp S có tối đa n giá trị. Tuy nhiên từ (6) suy ra n−1 và 0 không đồng thời thuộc S, vì thế tập S tối đa nhận (n−1) giá trị.

Theo nguyên lí Dirichlet suy ra tồn tại ít nhất a1 ∈ A, a2 ∈ A(a1 6= a2), mà S(a1) = S(a2).

Bài toán 2.39. Chứng minh rằng trong mọi đa giác lồi với số cạnh chẵn, tồn tại đường chéo không song song với một cạnh nào của đa giác.

Lời giải.

Ta giả thiết rằng nếu một đa giác có n cạnh, thì có n(n−3)

2 đường chéo.

Xét một đa giác lồi bất kì với số cạnh là chẵn (đa giác lồi 2k cạnh k≥ 2).

Khi đó số đường chéo của nó là s = 2k(2k−3)

2 . Ta có: s = k(2k −3) = 2k(k−2) +k, hay suy ra:

s > 2k(k−2). (7)

Giả sử ngược lại đa giác này có tính chất: mỗi đường chéo của nó đều song song với một cạnh nào đó của đa giác. Đa giác này có 2k cạnh, vì thế từ (7) suy ra tồn tại ít nhất (k - 1) đường chéo d1, d2, d3, . . . , dk−1 mà các đường chéo này cùng song song với một cạnh a nào đó của tam giác đã cho (thật vậy, nếu ngược lại mỗi cạnh tối đa là song song k −2 đường chéo thì tối đa ta chỉ có 2k.(k−2) đường chéo và s ≤ 2k(k - 2). Điều này mâu thuẫn với (7).

Như thế ta có k đường thẳng song song với nhau d1, d2, d3, . . . , dk−1, a.

Mặt khác đa giác đã cho là đa giác lồi nên các đường chéod1, d2, d3, . . . , dk−1 cùng nằm trên một nửa mặt phẳng bờ xác định cạnh a.

Không mất tính tổng quát có thế cho d1 là đường chéo xa nhất đối với a.

Ta có tất cả k đoạn thẳng phân biệt, nên mỗi đỉnh của đa giác đều là đầu

Tài liệu tham khảo

Tài liệu liên quan

Ở khối lập phương A: mặt trước tô màu đỏ, mặt trên tô màu xanh, mặt bên phải tô màu vàng2. Em cho biết ở khối lập phương B, mặt trước tô

+ Để khai thác tính chất đường trung bình trong tam giác, ta chú ý tới các yếu tố trung điểm có sẵn trong đề bài từ đó xây dựng thêm một trung điểm mới để thiết lập đường

Sau đây chúng tôi đưa ra một số ví dụ minh hoạ với lời giải theo hướng tiếp cận sử dụng khoảng cách để tính góc giữa đường thẳng với mặt phẳng.. Áp dụng cho

Em có nhận xét gì về độ dài đoạn AM và độ dài đoạnMB?. Độ dài đoạn thẳng AM bằng độ dài đoạn thẳng MB và bằng

Cho đường tròn đường kính AB cố định, M là một điểm chạy trên đường tròn.. Trên tia đối tia MA lấy điểm I sao cho MI

Trong mặt phẳng cho n điểm, trong đó không có 3 điểm nào thẳng hàng và trong tất cả các đường thẳng nối hai điểm bất kì, không có hai đường thẳng nào song

Bài báo đưa ra một số kỹ thuật học máy cho chấm điểm tín dụng đã và đang được các tổ chức tài chính và ngân hàng sử dụng; đưa ra kết quả thử nghiệm các kỹ thuật học máy

Chứng minh rằng thế nào cũng có một số hoặc tổng một số các số liên tiếp nhau trong dãy trên chia hết cho 10. Không có 3 đường thẳng nào đồng qui. Tính số giao