Luận văn Thạc sĩ Toán học: Một số phương pháp đếm trong các bài toán hình học tổng hợp

ĐẠI HỌC THÁI NGUYÊN

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

THÁI NGUYÊN - NĂM 2016

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

ĐẠI HỌC THÁI NGUYÊN

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

Mục lục

Mở đầu

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

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

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

1.2.1 Bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.2 Nguyên lí Dirichlet . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

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

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

3 Các dạng toán liên quan

3.1 Bài toán về tô màu hình vẽ . . . . . . . . . . . . . . . . . . . . . . .

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

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

Tài liệu tham khảo

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

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

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ệc A có 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ệc A có 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ồm n phầ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

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à Ak n.

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à C k n.

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

k n phần tử được ký hiệu là A n.

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

k n.

là C

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

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:

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 (cid:105) nhất đồ vật (ở đây kí hiệu [α] để chỉ phần nguyên của số α).

(cid:104)N k Chứng minh. (cid:105) Giả sử mọi hộp đều chứa ít hơn vật. Khi đó tổng số đồ vật là: (cid:104)N k

(cid:17) (cid:105) (cid:105)

= N.

< k

− 1

k

(cid:104)N k

(cid:16)(cid:104)N k Đ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 (cid:105) nhất con thỏ. (cid:104)n + m − 1 m Chứng minh. (cid:105) Giả sử trái lại mọi chuồng thỏ không có đến (cid:105) +1

(cid:105) (cid:104)n − 1 m con. (cid:104)n + m − 1 m con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng

(cid:105) = (cid:104)n − 1 m = n − 1 con. Từ đó suy ra tổng số con thỏ không vượt quá m. (cid:104)n − 1 m Đ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:

+ 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

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.

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 n phầ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

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ại n − 1 giao điểm trên mỗi đường thẳng. Do đó số điểm

n =

. giao nhau là C 2

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

n = n(n − 1).

điểm giao nào nằm trên cùng ba đường tròn. Do đó số điểm giao nhau là 2.C 2

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

n = 3n(n − 1).

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

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.

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.

và số cách chọn hai điểm

m (m − 1) 2

n =

. trên d2 là C 2 Số cách chọn hai điểm trên d1 là C 2 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éo A1Ak 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 là

(n − k) (k − 2) =

(cid:2)(n + 2) k − k2 − 2n(cid:3)

a1 (n) =

n−1 (cid:80) k=3

. =

(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à

a1 (n) =

= C 4 n.

n 4

n (n − 1) (n − 2) (n − 3) 24

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 C 3

4.C 3

4n bộ ba điểm, trong số đó có n 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à C 3

4n − 4.C 3

n = 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à C 3 n.

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.

.

n − n(n − 4) − n =

Vậy số tam giác cần tính là C 3

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

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ẳng qn+1 được chia ra với các đường thẳng q1, 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) = khi và chỉ khi với mỗi i = 2, 3, . . . , n đường thẳng

n2 + n + 2 2

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ồm n đườ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ởi n đườ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.

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ạn AB. 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 1 nê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ữ

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à 2 hoặ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 × 2 và 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.

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.

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 ô ở (cid:19) (cid:17) ô màu xanh. cột chẵn. Có tất cả n

+ 1

ô màu đỏ và n

+ 1

(cid:16)n − 1 n (cid:18)n − 1 n

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ạch 3 × 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.

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ền 29 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

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

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ảng 8 × 8 được viết một số nguyên.

Ta có thể chọn bất kì bảng nhỏ 3 × 3 hoặc 4 × 4 và 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.

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?

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 đầu s0, 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.

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

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

1 5 nhất ba điểm trong số 51 điểm đó. Đường tròn ngoại tiếp (a) có bán kính

≤

1 7

2 1 √ 5 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, m là số điểm đặt bất kì, phân biệt. Chứng minh rằng có ít nhất n

(trong trong số m điểm đó nằm trong một hình trong bán kính (cid:114) (cid:105)

α2 (cid:104) m

2. n − 1

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

Lời giải. (cid:105) (cid:104) m hình vuông con bằng nhau có cạnh Chia hình vuông đã cho thành

n − 1

bằng . Theo nguyên lí Dirichlet, tồn tại ít nhất một hình vuông (cid:105)

α2 (cid:114)(cid:104) m

n − 1

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 (cid:114) (cid:105)

α2 (cid:104) m

2. n − 1

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 . (cid:114) (cid:105)

α2 (cid:104) m

2. n − 1

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.

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.

(cid:17) . Các tọa độ của Vậy trung điểm của đoạn AB là O

,

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

e + f 2

b + e 2

đ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

+ 1

điểm khác nhau có các tọa độ nguyên trong không gian. Chứng minh rằng (cid:105) (cid:104) m 8 (cid:105) (cid:104) trong các cặp điểm này có tọa trung điểm của đường nối ít nhất

2

độ 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 (cid:17) .

,

trung điểm của đoạn AB là O (cid:16)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))

(cid:105) nên theo nguyên lí Dirichlet có ít nhất

+ 1 trong m điểm có cùng bộ ba

(cid:104)m 8 chẵn lẻ như nhau. (cid:105)

+ 1

(cid:104) m 8 (cid:105) (cid:104) cặp điểm mà điểm chính giữa của chúng có tọa Vậy có ít nhất

2

độ nguyên.

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.

Ci 2π

Mặt khác, đường tròn với chu vi Ci sẽ có bán kính: Ri = 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à

> 3, nên theo nguyên lý Dirichlet đối ngẫu suy ra có một điểm M

10 π

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

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ạnh 20cm 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ạnh 20cm. 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.

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

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

{M N } và đại lượng d(P ) gọi là đường kính của hình P .

Đặt d(P ) = max M,N ∈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.

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à hình vành khăn. Rõ ràng I có đường kính bằng 2.

1 8

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.

Vì (cid:92)DOA = 450, nên

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

√

(cid:17)

.1.

=

2 2

+ 12 − s. √ 5

5 2 2

=

+ 1 −

.

2 −

.

Từ đó, suy ra: d2 < (cid:16)5 2 24 4 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 (cid:54)= 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 (cid:54)= A, C (cid:54)= 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.

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ông ABCD có tâm O 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 A(cid:48)B(cid:48)C (cid:48)D(cid:48) có tâm O và cạnh a − 2, ở đây A(cid:48)B(cid:48)//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 A(cid:48)B(cid:48)C (cid:48)D(cid:48) chia hình vuông A(cid:48)B(cid:48)C (cid:48)D(cid:48) 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à O(cid:48) và O(cid:48)(cid:48)).

Để ý 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

O(cid:48)O(cid:48)(cid:48) ≥ 2.

(1)

Mặt khác do O(cid:48), O(cid:48)(cid:48) cùng nằm trong một hình vuông nhỏ (cạnh của hình

) nên ta lại có vuông nhỏ đó bằng

a − 2 2

√

O(cid:48)O(cid:48)(cid:48) ≤

2. (2)

a − 2 2

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

√

2 ≥ 2 ⇒ a ≥ 2

2 + 2.

(3)

a − 2 2

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,

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,

√

2 + 2.

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

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âm O đã 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à

(cid:92)A1OA2 + (cid:92)A2OA3 + (cid:92)A3OA4 + (cid:92)A4OA5 + (cid:92)A5OA6 = 3600.

(cid:92)AiOAi+1 ≤

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

Khi đó suy ra: min i=1,6

3600 6

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

(cid:92)AkOAk+1 khi đó: (cid:92)AkOAk+1 ≤ 600.

Vì OAk ≤ 1, OAk+1 ≤ 1, (cid:92)AkOAk+1 ≤ 600 nên từ đó suy ra: (cid:92)AkOAk+1 ≤ max{ (cid:92)AkAk+1O, (cid:92)OAkAk+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 d(cid:48) hoặc song song với d, hoặc là vuông góc với d sao cho d(cid:48) 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à a(cid:48) là hai đường thẳng bất kì vuông góc với nhau. Gọi A(cid:48)B(cid:48) và A(cid:48)(cid:48)B(cid:48)(cid:48) là các hình chiếu của AB lên a và a(cid:48). Khi đó ta có: A(cid:48)B(cid:48) + A(cid:48)(cid:48)B(cid:48)(cid:48) ≥ AB hay A(cid:48)B(cid:48) + A(cid:48)(cid:48)B(cid:48)(cid:48) ≥ 1.

Áp dụng vào bài toán, ta gọi d(cid:48)(cid:48) 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à d(cid:48)(cid:48). Suy ra tổng độ dài hình

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à d(cid:48)(cid:48) 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 d(cid:48) là đường thẳng vuông góc với d tại M. Đường thẳng d(cid:48) chính là đường

thẳng cần tìm.

Nhận xét 2.2. Nếu ở trên thay d bởi d(cid:48)(cid:48) 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 d(cid:48)(cid:48)).

Bài toán 2.36. Cho 2016 điểm M1, M2, . . . , M2016 phâ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

đườ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 . Chứng minh

2 3

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

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:

=

.

2 3

EJ1 J1F

F J2 J2E

P J3 J3Q

QJ4 J4P

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ó

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à

(6)

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

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 (cid:54)= 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.

đường chéo. Ta giả thiết rằng nếu một đa giác có n cạnh, thì có

n(n − 3) 2

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 = . Ta có: s = k(2k − 3) =

2k(2k − 3) 2

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éo d1, 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

mút của một đoạn nào đó trong k đoạn trên. Từ đó suy ra toàn bộ đa giác

nằm hẳn về một nửa mặt phẳng xác định bởi d1. Do d1 là đường chéo, nên điều này mâu thuẫn với tính lồi của đa giác. Vậy giả thiết phản chứng là sai.

Bài toán 2.40. Một hình lập phương có cạnh bằng 15 chứa 11000 điểm.

Chứng minh rằng có một hình cầu bán kính 1 chứa ít nhất 6 điểm trong số

11000 điểm đã cho.

Lời giải.

Chia mỗi cạnh của hình lập phương thành 13 phần bằng nhau. Như thể hình lập phương đã cho được chia thành 133 = 2197 hình lập phương nhỏ.

Do 11000 > 5.2197 = 10985, nên tồn tại ít nhất 1 hình lập phương nhỏ, mà

hình lập phương này chứa ít nhất 6 điểm.

Như đã biết, nếu gọi cạnh hình lâp phương bằng a, thì hình cầu ngoại

√

a

3.

tiếp có bán kính R, với R =

1 2

) là

15 13

(cid:115) (cid:19)2

√

3 =

=

4 = 1. Hình cầu bán kính R

R = Vì thế hình cầu ngoại tiếp hình lập phương nhỏ (cạnh của nó là (cid:114)675 169 (cid:18)15 3 13

15 13

1 2

này dĩ nhiên chứa ít nhất 6 điểm trong số 11000 điểm đã cho.

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

Bài toán 2.41. Chứng minh rằng khi tất cả các cạnh của một tam giác đều

√

nhỏ hơn 1 thì diện tích tam giác nhỏ hơn .

3 4

Lời giải.

Gọi A là góc nhỏ nhất của tam giác ABC, suy ra: (cid:92)BAC ≤ 600.

BH.AC =

AB.AC. sin A.

Ta có: SABC =

1 2

√

AB.AC. sin 600<

.1.1.

=

. Suy ra điều phải

Do đó: SABC <

1 2

3 2

3 4

1 2

chứng minh.

Bài toán 2.42 (VMO 1986-1987. Bảng A). Cho tứ giác lồi ABCD có hai

đường chéo AC và BD cắt nhau tại E. Chứng minh rằng: Nếu các bán kính

của 4 đường tròn nội tiếp các tam giác EAB, EBC, ECD, EDA mà bằng

nhau thì tứ giác ABCD là hình thoi.

Lời giải.

Hoàn toàn không mất tính tổng quát ta có thể giả sử rằng: CE ≤

AE, BE ≤ DE.

Gọi B1 và C1 tương ứng là các điểm đối xứng của B và C qua tâm E, ta có tam giác C1EB1 nằm trong miền tam giác AED. Giả sử đoạn thẳng AD không trùng với đoạn thẳng C1B1.

Khi đó đường tròn nội tiếp tam giác EB1C1 nằm bên trong đường tròn nội tiếp tam giác AED, đồng dạng (phối cảnh) với đường tròn này với tâm đồng

dạng E, hệ số đồng dạng lớn hơn 1.

Như vậy: rAED > rC1EB1 = rCBE (rAED là bán kính đường tròn nội tiếp

tam giác AED). Vô lí, vì trái với giả thiết là: rAED = rCEB. Điều vô lí đó chứng tỏ là A ≡ C1 và D ≡ B1.

Khi đó: EA = EC, EB = ED do đó tứ giác ABCD là hình bình hành.

Trong hình bình hành ABCD có p1r = SAEB = SBEC = p2r (Ở đó p1và p2

=

tương ứng là nửa chu vi của các tam giác AEB và BEC). BC + CE + BE AB + BE + EA 2 2 Suy ra: p1 = p2 ⇔ ⇔ AB = BC (vì AE = CE).

Vậy hình bình hành ABCD có AB = BC nên ABCD là hình thoi.

Bài toán 2.43 (VMO 1992-1993, bảng A). Một nước có 80 sân bay, mà

khoảng cách giữa hai sân bay nào cũng khác nhau. Mỗi máy bay cất cánh từ

một sân bay và bay đến sân bay nào gần nhất. Chứng minh rằng: trên bất

kỳ sân bay nào cũng không thể có quá 5 máy bay đến.

Lời giải.

Từ giả thiết suy ra nếu các máy bay từ các sân bay M và N đến sân bay

O thì khoảng cách M N là lớn nhất trong các cạnh của tam giác M ON , do đó (cid:92)M ON > 60o.

Giả sử rằng các máy bay bay từ các sân bay M1, M2, M3, M4, . . . Mn đến sân bay O thì một trong các góc (cid:92)MiONj (i, j, n = 1, 2, 3, 4, 5 . . . , 80) không lớn hơn

, vì tổng các góc đã cho bằng 360o.

Vậy nên >600, suy ra n < 6. Vậy ta có điều phải chứng minh.

360o n 360o n

Bài toán 2.44 (VMO 1992-1993 bảng B). Trong tam giác ABC có ba góc

nhọn, lấy một điểm P bất kì. Chứng minh rằng khoảng cách lớn nhất trong

các khoảng cách từ điểm P đến các đỉnh A, B, C của tam giác không nhỏ

hơn 2 lần khoảng cách bé nhất trong các khoảng cách từ điểm P đến các

cạnh của tam giác đó.

Lời giải.

Dựng P A1, P B1, P C1 tương ứng vuông góc với các cạnh BC, CA, AB. Vì tam giác ABC có ba góc nhọn nên các điểm A1, B1, C1 tương ứng nằm trong đoạn BC, CA và AB.

Nối P A, P B, P C ta có: (cid:92)AP C1 + (cid:92)C1P B + (cid:92)BP A1 + (cid:92)A1P C + (cid:92)CP B1 +

(cid:92)B1P A = 3600. Suy ra góc lớn nhất trong 6 góc này không thế nhỏ hơn 600. Không mất tính tổng quát, ta giả sử (cid:92)AP C1 là lớn nhất, khi đó (cid:92)AP C1 ≥ 600. Xét ∆AP C1 vuông tại C1, ta có:

.

= cos(cid:92)AP C1 ≤ cos600 =

P C1 AP

1 2

Từ đó ta có: AP ≥ 2.P C1.

Nếu thay P A bằng khoảng cách lớn nhất trong các khoảng cách từ P đến

các đỉnh và thay P C1 bằng khoảng cách ngắn nhất từ P tới các cạnh thì bất đắng thức càng được thỏa mãn.

Bài toán 2.45. Chứng minh rằng: Bốn hình tròn có đường kính là bốn cạnh

của một tứ giác lồi ABCD thì phủ kín miền tứ giác đó.

Lời giải.

Lấy M là một điểm tùy ý của tứ giác lồi ABCD. Có hai khả năng xảy ra:

1) Nếu M nằm trên biên của đa giác (tức M nằm trên một cạnh của tứ

giác ABCD).

Khi đó M nằm trong hình tròn có đường kính là cạnh ấy.

Trong trường hợp này kết luận của bài toán hiển nhiên đúng.

2) Nếu M nằm bên trong tứ giác lồi ABCD. Khi đó ta có

(cid:92)AM B + (cid:92)BM C + (cid:92)CM D + (cid:92)DM A = 3600.

Theo nguyên lí cực hạn, tồn tại

max (cid:92)AM B, (cid:92)BM C, (cid:92)CM D, (cid:92)DM A = (cid:92)BM C.

Khi ấy:

(cid:92)BM C ≥ 900.

(8)

Từ (8) suy ra M nằm trong (hoặc cùng lắm là nằm trên) đường tròn

đường kính BC. Vậy dĩ nhiên M bị phủ bởi đường tròn này.

Như thế do M là điểm tùy ý của tứ giác ABCD, ta suy ra bốn hình tròn

nói trên phủ kín tứ giác lồi đã cho. Điều phải chứng minh.

Bài toán 2.46. Bên trong đường tròn tâm O bán kính R = 1 có 8 điểm

phân biệt. Chứng minh rằng: tồn tại ít nhất hai điểm trong số chúng mà

khoảng cách giữa hai điểm này nhỏ hơn 1.

Lời giải.

Nhận xét: ít nhất 7 điểm trong số 8 điểm đã cho là khác tâm O. Ta gọi

các điểm đó là A1, A2, A3, A4, A5, A6, A7, A8.

Ta có góc nhỏ nhất trong số các góc đỉnh O và hai điểm còn lại là (cid:92)AiOAk (i (cid:54)= k, 1 ≤ i, k ≤ 8) là không lớn hơn

< 600.

3600 7

Giả sử (cid:92)A1OA2 là góc bé nhất. Xét ∆A1OA2.

Vì (cid:92)A1OA2 < 600 nên (cid:104)OA2>A1A2 OA1>A1A2 (cid:104) (cid:92)OA1A2>600 (cid:92)A1A2O>600 ⇒

Mà OA1 ≤ 1 hoặc OA2 ≤ 1 nên A1A2 < 1.

Bài toán 2.47. Trong mặt phẳng, cho 2016 đường thẳng phân biệt, trong

đó ba đường thẳng bất kì trong số chúng thì đồng quy. Chứng minh rằng cả

2016 đường thẳng đã cho đồng quy tại một điểm.

Lời giải.

Ta sẽ đi giải quyết bài toán bằng phương pháp phản chứng: Giả sử ngược

lại các đường thẳng đã cho không đi qua một điểm. Ta xét các giao điểm tạo

nên bởi 2016 đường thẳng đã cho. Xét tất cả các khoảng cách khác 0 hạ từ

các giao điểm này tới các đường thẳng đã cho. Giả sử A là một giao điểm

trong số đó và gọi AQ là khoảng cách nhỏ nhất trong số đó vẽ từ A đến (cid:96)

đường thẳng (cid:96) trong số 2016 đường thẳng.

Qua A theo giải thiết, phải có ít nhất là 3 đường thẳng, và 3 đường thẳng

này cắt (cid:96) lần lượt tại B, C và D.

Vẽ AQ ⊥ (cid:96), thì hai trong ba điểm B, C, D phải nằm cùng một phía của điểm

Q, chẳng hạn là C và D. Không mất tính tổng quát, giả sử QC < QD; vẽ

CP ⊥AD , vẽ QK⊥AD. Suy ra: CP < QK < AQ. Vô lý, vì trái với giả

thiết giả sử AQ là khoảng cách bé nhất. Điều vô lí trên chứng tỏ rằng 2016

đường thẳng đã cho đồng quy tại một điểm.

Bài toán tổng quát 2.4 (Tổng quát hóa bài toán). Trong mặt phẳng, cho

n (n ≥ 3) đường thẳng phân biệt, trong đó ba đường thẳng bất kì trong số

chúng thì đồng quy. Chứng minh rằng cả n đường thẳng đã cho đồng quy

tại một điểm.

Bài toán 2.48. Trên mặt phẳng cho 2 × 2016 điểm, trong đó không có bất

kỳ 3 điểm nào thẳng hàng. Người ta tô 2016 điểm bằng màu đỏ và tô 2016

điểm còn lại bằng màu xanh. Chứng minh rằng: bao giờ cũng tồn tại một

cách nối tất cả các điểm màu đỏ với tất cả các điểm màu xanh bởi 2016 đoạn

thẳng không có điểm nào chung.

Lời giải.

Ta nhận thấy rằng luôn tồn tại cách nối 2016 cặp điểm với nhau bằng

2016 đoạn thẳng và vì có 2016 cặp điểm nên số cách nối là hữu hạn và nếu

dùng tổ hợp thì ta có thể tính được con số chính xác các cách nối. Và hiển

nhiên là trong hữu hạn cách nối đó ta luôn tìm ra được một cách nối có tổng

độ dài các đoạn thẳng là ngắn nhất. Ta chứng minh cách nối đó là cách mà

chúng ta cần tìm.

Thật vậy: Giả sử ngược lại ta có hai đoạn thẳng AX và BY mà cắt nhau

tại điểm O (giả sử A và B tô màu đỏ, còn X và Y tô màu xanh).

Khi đó, nếu ta thay đoạn thẳng AX và BY bằng hai đoạn AY và BX, các

đoạn còn lại giữ nguyên thì ta có cách nối này có tính chất: AY + BX <

(AO + OY ) + (BO + OX) = (AO + OX) + (BO + OY ) ⇒ AY + BX <

AX + BY.

Như vậy, việc thay hai đoạn thẳng AX và BY bằng hai đoạn thẳng AY

và BX, ta nhận được một cách nối mới có tổng độ dài đoạn thẳng là nhỏ

hơn. Vô lý, vì trái với giả thiết là đã chọn cách nối có tổng các độ dài là bé

nhất.

Điều vô lí đó chứng tỏ cách nối có tổng độ dài các đoạn thẳng là ngắn

nhất là không có điểm chung.

Bài toán 2.49. Trên mặt phẳng đã cho 2016 điểm phân biệt, khoảng cách

giữa chúng đôi một khác nhau. Nối mỗi điểm trong số 2016 điểm này với

điểm gần nhất. Chứng minh rằng: với mỗi cách nối đó không thể nhận được

một đường gấp khúc khép kín.

Lời giải.

Giả sử ngược lại, với cách nối đó chúng ta nhận được một đường gấp khúc

khép kín.

Gọi AB là mắt lớn nhất của đường gấp khúc khép kín này. Tức là đoạn

thẳng lớn nhất trong các đoạn thẳng tạo nên đường gấp khúc trên.

Giả sử AC và BD là hai mắt kề với mắt AB. Ta có:

AC < AB nên B không là điểm gần nhất của A.

BD < AB nên A không là điểm gần nhất của B.

Chứng tỏ rằng A và B không được nối với nhau. Vô lí!

Điều đó chứng tở rằng chúng ta không thể nhận được một đường gấp khúc

khép kín từ cách nối trên.

Bài toán 2.50. Trên mặt phẳng cho 2016 điểm phân biệt thỏa mãn: ba điểm

bất kì trong số chúng đều thẳng hàng. Chứng minh rằng: 2016 điểm đã cho

là thẳng hàng.

Lời giải.

Giả sử ngược lại là 2016 điểm đã cho không thẳng hàng.

Dựng qua mỗi cặp điểm trong số 2016 điểm này một đường thẳng. Số các

đường thẳng được nối như vậy là hoàn toàn xác định, hữu hạn. Xét các

khoảng cách khác 0 nhỏ nhất từ 2016 điểm đã cho đến các đường thẳng vừa

dựng. Số các khoảng cách như vậy tồn tại và hữu hạn.

Gọi khoảng cách từ A đến đường thẳng BC là bé nhất (A, B, C là 3 trong

số 2016 điểm đã cho). Theo giả thiết, trên BC cón có 1 điểm thứ 3 là D

khác B và C.

Vẽ AQ⊥BC, khoảng cách AQ là bé nhất (theo giả sử) nên ta có trong

ba điểm B, C, D phải có ít nhất hai điểm nằm về cùng một phía của điểm

Q, giả sử đó là hai điểm A và D.

Giả sử: CQ < DQ vẽ CR⊥AD, dễ thấy CR < AQ (vô lí).

Điều đó chứng tỏ rằng 2016 điểm đã cho thẳng hàng.

Bài toán tổng quát 2.5 (Tổng quát hóa bài toán). Trong mặt phẳng, cho

n (n ≥ 3) điểm phân biệt thỏa mãn: ba điểm bất kì trong số chúng đều thẳng

hàng. Chứng minh rằng: n điểm đã cho là thẳng hàng.

Bài toán 2.51. Trên mặt phẳng cho 2016 điểm không thẳng hàng. Chứng

minh rằng: tồn tại một đường tròn đi qua ba trong số 2016 điểm đã cho mà

đường tròn này không chứa bất kì điểm nào trong số 2013 điểm còn lại.

Lời giải.

ta sẽ có C 2 Nối hai điểm bất kì trong số 2016 điểm đã cho bằng một đoạn thẳng. Vậy 2016 đoạn thẳng như vậy. Gọi AB là đoạn thẳng có độ dài bé nhất.

Vẽ đường tròn tâm O đường kính AB.

Suy ra 2014 điểm còn lại nằm ngoài đường tròn tâm O. Gọi C là điểm trong số 2014 điểm còn lại đó thỏa mãn góc (cid:92)ACB là lớn nhất trong số các góc nhìn 2 điểm A và B.

Xét ∆ABC. Ta có đường tròn (C) ngoại tiếp ∆ABC không chứa điểm

nào trong số 2013 điểm còn lại.

Bài toán 2.52. Trong không gian cho n điểm phân biệt (n ≥ 4 , n là hữu

hạn) thỏa mãn: không có bốn điểm nào trong chúng đồng phẳng và thể tích

của mỗi tứ diện tạo ra bởi bốn đỉnh là bốn điểm trong n điểm đã cho không

lớn hơn 1. Chứng minh rằng tất cả n điểm đó có thể được phủ bởi một tứ

diện có thể tích bằng 27.

Lời giải.

Do n là hữu hạn, nên số lượng các tứ diện tạo thành cũng là hữu hạn.

Theo nguyên lí cực hạn, tồn tại tứ diện (mà ta sẽ gọi là A1B1C1D1) có thể tích lớn nhất. Từ các đỉnh A1, B1, C1, D1 ta xác định tứ diện ABCD sao cho A1, B1, C1, D1 tương ứng là trọng tâm của các tam giác BDC, ACD, ABD, ABC. Từ đó ta có:

=

.

(9)

1 27

VA1B1C1D1 VABCD

Theo giả thiết ta lại có: VA1B1C1D1 ≤ 1, nên từ (9), ta có:

(10)

VABCD ≤ 27.

Bây giờ ta chứng minh rằng tất cả các điểm đã cho nằm trong tứ diện

ABCD. Giả sử trái lại điều khẳng định này không đúng, tức là tồn tại điểm

M (trong số các điểm đã cho), sao mà M không thuộc tứ diện ABCD.

Khi đó tồn tại ít nhất một đỉnh của tứ diện ABCD (không mất tính tổng

quát ta xét trường hợp đó là đỉnh B, các trường hợp khác xét hoàn toàn

tương tự) sao cho B và M nằm trong hai nửa không gian xác định bởi mặt

phẳng (ACD).

Có thể thấy ngay:

(11)

VM A1C1D1 > VB1A1C1D1.

Bất đẳng thức (11) đúng chứng tỏ rằng M A1C1D1 là tứ diện tạo bởi bốn đỉnh trong các điểm đã cho có thể tích lớn hơn thể tích của tứ diện VB1A1C1D1. Điều này mâu thuẫn với định nghĩa của tứ diện A1B1C1D1. Điều vô lí trên chứng tỏ rằng giả thiết phản chứng là sai.

Vậy: Trong không gian cho một số hữu hạn các điểm mà không có bốn

điểm nào trong chúng cùng nằm trên một mặt phẳng sao cho thể tích của

mỗi tứ diện tạo ra bởi đỉnh là những điểm cho không lớn hơn 1. Luôn tồn

tại một tứ diện có thể tích bằng 27 phủ kín tất cả các điểm.

Chương 3

Các dạng toán liên quan

3.1 Bài toán về tô màu hình vẽ

Bài toán 3.1. Tô màu các đỉnh của 2n-giác lồi bằng hai màu xen kẽ nhau.

Tìm số đường chéo có hai đầu mút là hai đỉnh của đa giác khác màu nhau.

Lời giải.

Trong đa giác đã cho tồn tại n đỉnh cùng một màu. Với mỗi đỉnh A trong

n đỉnh cùng màu đó có hai đỉnh liền kề A khác màu với A, như vậy chỉ còn

n − 2 đỉnh khác màu với A để nối với A tạo thành đường chéo. Do đó số

đường chéo tạo được từ 2n đỉnh là 2n(n − 2) đường, nhưng mỗi đường chéo

được nối 2 lần, do đó số đường chéo có hai đỉnh khác màu nhau là n(n − 2).

Bài toán 3.2. Cho một lưới ô vuông tạo bởi 3 đường nằm ngang và 9 đường

thẳng đứng. Giả sử mỗi nút lưới trong mặt phẳng được tô bằng một trong

hai màu đen và trắng. Chứng minh tồn tại một hình chữ nhật có các đỉnh

cùng màu.

Lời giải.

Giả sử ta có một lưới ô vuông tạo bởi 3 đường nằm ngang và 9 đường

thẳng đứng, mỗi nút lưới được tô bởi một màu trắng hoặc đen như hình vẽ.

Xét 3 nút lưới của một đường dọc, mỗi nút có hai cách tô màu nên mỗi

bộ ba nút trên đường dọc ấy có 2.2.2 = 8 cách tô màu. Có 9 đường dọc, mỗi

đường có 8 cách tô màu nên theo nguyên lý Dirichlet tồn tại hai đường có

cách tô màu như nhau. Chẳng hạn hai bộ ba điểm đó là A, B, C và X, Y, Z

Vì 3 điểm A, B, C chỉ được tô bởi hai màu nên tồn tại hai điểm cùng màu,

chẳng hạn B và C khi đó hình chữ nhật ABY Z có 4 đỉnh cùng một màu.

Bài toán 3.3. Trong mặt phẳng cho sáu điểm, trong đó không có ba điểm

nào thẳng hàng. Mỗi đoạn thẳng nối từng cặp điểm được tô màu đỏ hoặc

xanh. Chứng minh rằng tồn tại ba điểm trong số sáu điểm đã cho, sao cho

chúng là các đỉnh của một tam giác mà các cạnh của nó được tô cùng một

màu (ta gọi đó là tam giác đơn sắc).

Lời giải.

Xét A là một trong số sáu điểm đã cho. Khi đó xét năm đoạn thẳng (mỗi

đoạn thẳng nối điểm A với năm điểm còn lại). Vì mỗi đoạn thẳng được tô

chỉ màu đỏ hoặc màu xanh, nên theo nguyên lí Dirichlet có ít nhất ba trong năm đoạn nói trên cùng màu. Giả sử đó là các đoạn AB, AB(cid:48), AB(cid:48)(cid:48) và có thể

cho rằng chúng cùng màu xanh. Chỉ có hai khả năng xảy ra:

1) Nếu ít nhất một trong ba đoạn BB(cid:48), B(cid:48)B(cid:48)(cid:48), B(cid:48)(cid:48)B màu xanh, thì tồn tại

một tam giác với ba cạnh xanh và kết luận của bài toán đúng trong trường

hợp này.

2) Nếu không phải như vậy, tức là BB(cid:48), B(cid:48)B(cid:48)(cid:48), B(cid:48)(cid:48)B màu đỏ, thì ba điểm phải tìm là B, B(cid:48), B(cid:48)(cid:48) vì BB(cid:48)B(cid:48)(cid:48) là tam giác có ba cạnh màu đỏ. Vậy ta được

điều phải chứng minh.

Ta đưa ra một ví dụ minh họa đẹp mắt cho bài toán như sau:

Bài toán 3.4. Chứng minh rằng từ sáu số vô tỉ tùy ý có thể chọn ra được

ba số (ta gọi ba số đó là a, b, c) sao cho a + b, b + c, c + a cũng là số vô tỉ.

Lời giải.

Xét trên mặt phẳng sáu điểm sao cho không có ba điểm nào thẳng hàng.

Với mỗi điểm ta sẽ gắn cho nó một số vô tỉ. Như vậy sáu điểm được gắn sáu

số vô tỉ đã cho. Hai điểm mang số a và b sẽ được nối với nhau bằng một đoạn

thẳng màu đỏ nếu a + b là số vô tỉ, còn sẽ có màu xanh khi a + b là số hữu

tỉ.

Theo đề bài, tồn tại ít nhất một tam giác cùng màu. Giả sử tam giác đó

có ba đỉnh được gắn số là a, b, c. Chỉ có hai khả năng xảy ra:

1) Nếu tam giác đó là tam giác xanh. Khi ấy a + b, b + c, a + c là 3 số hữu

tỉ. Lúc này (a + b) + (b + c) − (c + a) = 2b cũng là một số hữu tỉ. Điều này

vô lí vì b là số vô tỉ.

2) Nếu tam giác đỏ là tam giác đỏ. Khi ấy a + b, b + c, a + c là 3 số vô tỉ.

Ta được điều phải chứng minh.

Nhận xét 3.1. Bài toán bề ngoài có vẻ không liên quan gì tới hình học

nhưng lại có thể quy về bài toán hình học với một lời giải đẹp mắt như vậy.

Ta có các bài toán tương tự sau:

Bài toán 3.5. Trên mặt phẳng cho 18 điểm, sao cho không có 3 điểm nào

thẳng hàng. Nối từng cặp điểm với nhau và tô màu cho mọi đoạn thẳng thu

được một trong hai màu xanh và đỏ. Chứng minh rằng luôn tìm được một tứ

giác mà các đỉnh của nó nằm trong tập điểm đã cho sao cho cạnh và đường

chéo của nó cùng màu.

Lời giải.

Giả sử Ai (i = 1, 18) là 18 điểm đã cho. Xuất phát từ A1 có 17 đoạn thẳng A1Ai (i = 2, 18). 17 đoạn thẳng đó chỉ có hai màu xanh hoặc đỏ, nên theo nguyên lí Dirichlet tồn tại ít nhất 9 đoạn thằng cùng màu. Không giảm

tính tổng quát giả sử đó là các đoạn thẳng A1A2, A1A3, . . . , A1A10 và chúng cùng màu đỏ. Xét chín điểm A2, A3, . . . , A10 chỉ có thể xảy ra hai trường hợp sau:

1) Hoặc là tồn tại điểm Aj (2 ≤ j ≤ 10) sao cho trong tám đoạn thẳng AjAk (2 ≤ k ≤ 10, k (cid:54)= j) có ít nhất bốn đoạn màu đỏ. Không mất tính tổng quát có thể cho là A2A3, A2A4, A2A5, A2A6 màu đỏ. Đến đây lại chỉ còn hai khả năng:

- Hoặc là mọi đoạn thẳng A3A4, A3A5, A3A6, A4A5, A4A6, A5A6, đều màu

xanh. Khi đó A3A4A5A6 là tứ giác xanh thỏa mãn yêu cầu.

- Hoặc là tồn tại một đoạn thẳng AiAj (3 ≤ i < j ≤ 6) màu đỏ. Khi đó

A1A2AiAj (3 ≤ i < j ≤ 6) là tứ giác đỏ thỏa mãn yêu cầu bài toán.

2) Hoặc là với mọi điểm Aj (2 ≤ j ≤ 10) thì trong tám đoạn thẳng AjAk (2 ≤ k ≤ 10, k (cid:54)= j) có tối đa ba đoạn màu đỏ mà thôi. Khi đó phải tồn

tại một điểm (chẳng hạn A2) mà trong các đoạn A2Ak (3 ≤ k ≤ 10, k (cid:54)= j) có tối đa hai đoạn màu đỏ thôi (thật vậy, nếu với mọi Aj (2 ≤ j ≤ 10) mà có đúng ba đoạn AjAk (2 ≤ k ≤ 10, k (cid:54)= j) màu đỏ, thì số đoạn thẳng

màu đỏ nối trong nội bộ 9 điểm đó là

9.3 2

là số nguyên. Vô lí.) Vì A2Ak (3 ≤ k ≤ 10, k (cid:54)= j) có tối đa hai đoạn màu đỏ mà thôi, nên trong số các

đoạn A2A3, A2A4, A2A5, . . . , A2A10 có ít nhất sáu đoạn màu xanh. Không mất tính tổng quát ta cho A2A5, A2A6, . . . , A2A10 màu xanh.

Xét sáu điểm A5, A6, A7, A8, A9, A10. Đó là sáu điểm mà trong đó không có ba điểm nào thẳng hàng và mỗi đoạn thẳng nối hai điểm chỉ có hai màu

xanh hoặc đỏ. Theo bài trên thì luôn luôn tồn tại ít nhất một tam giác mà

ba đỉnh chọn trong {A5, A6, A7, A8, A9, A10} sao cho ba cạnh cùng màu.

Lại có hai khả năng:

a) Nếu tồn tại tam giác AiAjAk (5 ≤ i < j < k ≤ 10) màu xanh. Khi đó tứ giác A2AiAjAk (5 ≤ i < k ≤ 10) là tứ giác xanh thỏa mãn yêu cầu đề bài.

b) Nếu tồn tại tam giác AiAjAk (5 ≤ i < j < k ≤ 10) màu đỏ, thì

A1AiAjAk là tứ giác cần tìm.

Như vậy ta luôn chứng mình được tồn tại một tứ giác mà các đỉnh của

nó nằm trong tập hợp điểm đã cho sao cho cạnh và đường chéo cùng màu.

Ta có bài toán phức tạp hơn:

Bài toán 3.6. Cho sáu điểm phân biệt trên mặt phẳng, sao cho không có ba

điểm nào trong chúng thẳng hàng. Các đoạn thẳng nối từng cặp điểm được

tô màu đỏ hoặc màu xanh. Chứng minh rằng tồn tại hai tam giác mà các

đỉnh của chúng thuộc tập hợp sáu điểm đã cho sao cho các cạnh của chúng

cùng màu.

Lời giải.

Lưu ý rằng trong bài toán này chỉ đòi hỏi: chứng minh rằng có ít nhất một

tam giác cùng màu.

Số tất cả các tam giác tạo thành từ sáu điểm đã cho là: C 3

= 20

6 =

6! 3!3!

tam giác.

Gọi x là số các tam giác mà ba cạnh cùng màu, khi đó số các tam giác

mà ba cạnh không cùng màu sẽ là 20 − x.

Nếu hai đường cùng màu xuất phát từ một điểm thì ta có một góc đồng

màu. Trong mỗi tam giác cùng màu ta có ba góc đồng màu, còn trong tam

giác không cùng màu chỉ có đúng một góc đồng màu.

Vì thế số góc đồng màu là:

góc

3x + (20 − x) = 20 + 2x

(12)

r + C 2

5−r. (Ở đây ta quy ước sử dụng kí hiệu C k

n=0 nếu 0 ≤ n < k)

5−r ≥ C 2 r ≥ C 2

4 = 6. 4 = 6.

r = 0 còn 5 − r ≥ 4 ⇒ C 2 5−r = 0 mà r ≥ 4 ⇒ C 2 r + C 2

r + C 2

5−r ≥ 4.

Xét tại điểm A1. Giả sử xuất phát từ A1 có r đoạn thẳng màu đỏ và 5 − r đoạn thẳng màu xanh. Khi đó có thể thấy ngay tại điểm A1 số góc đồng màu là C 2 Nếu 0 ≤ r ≤ 1 ⇒ C 2 Nếu 0 ≤ 5 − r ≤ 1 ⇒ C 2 Xét khi 2 ≤ r ≤ 3 ⇒ C 2 5−r = 4. Tóm lại ta luôn chứng minh được C 2

Điều đó có nghĩa là tại mỗi điểm Ai(i = 1, 6) số góc đồng màu có đỉnh

tại Ai luôn lớn hơn hoặc bằng 6.4 = 24.

Kết hợp với (12) ta có: 20 + 2x ≥ 24 ⇒ x ≥ 2.

Vậy luôn luôn tồn tại ít nhất hai tam giác cùng màu (đỉnh của các tam

giác này thuộc vào tập sáu điểm đã cho).

Ta được điều phải chứng minh.

Bài toán 3.7. Cho hình chóp đáy là đa giác 9 cạnh. Tất cả 9 cạnh bên và

27 đường chéo của đa giác đáy được tô bằng một trong hai màu xanh hoặc

đỏ. Chứng minh rằng tồn tại ba đỉnh của hình chóp sao cho chúng là những

đỉnh của hình tam giác với các cạnh được tô cùng màu.

Lời giải.

Xét 9 cạnh bên. Vì 9 cạnh này chỉ được tô bằng một trong hai màu

xanh hoặc đỏ nên theo nguyên lí Dirichlet tồn tại 5 cạnh bên được tô cùng

một màu. Không mất tính tổng quát ta có thể giả sử đó là các cạnh bên

SA, SB, SC, SD, SE được tô cùng màu đỏ, và các điểm A, B, C, D, E xếp

theo chiều kim đồng hồ. Xét đa giác ABCDE.

Có hai khả năng xảy ra:

1) Nếu AB là đường chéo của đáy. Khi đó dĩ nhiên BD, DA cũng là các

đường chéo của đáy.

Lại có các trường hợp sau:

a) Nếu cả ba đoạn AB, BD, DA được tô cùng màu xanh. Khi đó A, B, D

là ba đỉnh cần tìm, vì tam giác ABD là tam giác với ba cạnh xanh.

b) Nếu một trong các đoạn AB, BD, DA được tô màu đỏ. Giả sử đoạn

BD màu đỏ, thì tam giác SBD là tam giác với ba cạnh đỏ. Lúc này S, B, D

là ba đỉnh cần tìm.

2) Nếu AB là cạnh đáy. Khi đó dĩ nhiên AC, CE chắc chắn là đường chéo

của mặt đáy.

a) Nếu AE là đường chéo mặt đáy thì ta quay lại trường hợp 1) vừa xét,

với ACE là tam giác với ba cạnh là 3 đường chéo đáy.

b) Nếu AE là cạnh đáy. Khi đó rõ ràng AC, AD là các đường chéo đáy.

- Nếu CD là đường chéo mặt đáy, ta quay về trường hợp 1).

- Nếu CD là cạnh bên. Lại xét các trường hợp sau:

+ Nếu BC là đường chéo mặt đáy, thì tam giác BCE là tam giác với ba

đường chéo đáy, quay về trường hợp 1).

+ Nếu BC là cạnh đáy. Khi đó xét tam giác BDE và quay về trường hợp

1).

Vậy bài toán đã giải quyết hoàn toàn.

Bài toán 3.8. Cho P1, P2, .., P7 là bảy điểm phân biệt trong không gian, trong đó không có bốn điểm nào đồng phẳng. Mỗi đoạn thẳng nối từng cặp

điểm được tô một trong hai màu đỏ hoặc đen. Chứng minh rằng: có hai tam

giác đơn sắc mà các đỉnh của chúng là một trong bảy điểm đã cho sao cho

chúng không có chung cạnh.

Lời giải.

Dựa vào cách chứng minh của bài toán (3.3) suy ra có ít nhất một tam

giác đơn sắc, chẳng hạn là tam giác P1P2P3 là tam giác đỏ (tức là tam giác với ba cạnh đỏ).

Bây giờ xét sáu điểm {P2, P3, P4, P5, P6, P7}. Lại theo bài (3.3) suy ra có

một tam giác đơn sắc. Có hai khả năng xảy ra:

1) Nếu tam giác đơn sắc này không chứa cạnh P2P 3. Khi đó rõ ràng tam

giác đơn sắc này không có chung cạnh với tam giác đỏ P1P2P3. Bài toán được giải trong trường hợp này.

(cid:48).

2) Nếu tam giác đơn sắc này chứa cạnh P2P3. Vì P2P3 là cạnh đỏ, nên ta chọn trong {P4, P5, P6, P7} một điểm sao cho cùng với hai điểm P2, P3 tạo nên một tam giác đơn sắc màu đỏ. Không mất tính tổng quát ta giả sử đó

là điểm P1

(cid:48) ∈ {P4, P5, P6, P7} sao cho P2

- Tương tự ta xét 6 điểm {P1, P3, P4, P5, P6, P7} và như trên ta chỉ quan (cid:48)P3P1 là tam

tâm đến trường hợp có điểm P2 giác đỏ.

- Khi xét 6 điểm {P1, P3, P4, P5, P6, P7} và chỉ quan tâm đến trường hợp

(cid:48) ∈ {P4, P5, P6, P7} sao cho P3

(cid:48)P2P1 là tam giác đỏ.

(cid:48) ∈ {P4, P5, P6, P7} sao cho

(cid:48), P3

(cid:48), P2

có điểm P3

(cid:48)P1P2, là ba tam giác đỏ.

(cid:48)P3P1, P3

Như thế ta xây dựng được ba điểm P1

(cid:48)P2P3, P2 Bây giờ lại có hai khả năng xảy ra:

ba tam giác P1

(cid:48), P2 (cid:48), P3 (cid:48)P3P1, P3

(cid:48) là ba điểm phân biệt. (chú ý rằng bốn tam giác P1P2P3, (cid:48)P1P2, đều là tam giác đỏ).

1. Nếu P1 (cid:48)P2P3, P2

P1

(cid:48)P2

(cid:48) có ít nhất một cạnh đỏ (chẳng hạn là cạnh (cid:48)P3 và P1P2P3 là hai tam giác đơn sắc mà (cid:48)P2

Lại có hai khả năng xảy ra: (cid:48)P3 (cid:48)là cạnh đỏ). Khi đó P1 a) Nếu tam giác P1 (cid:48)P2

P1 không không cạnh chung nào (cùng là tam giác đỏ). (cid:48)P3

(cid:48) là tam giác đen. Khi đó P1

(cid:48)P2

(cid:48)P3 và P1P2P3 là

(cid:48)P2 hai tam giác đơn sắc không có cạnh chung nào.

(cid:48)P2

b) Nếu tam giác P1

(cid:48) có điểm trùng nhau. Khi đó không mất tính tổng quát (cid:48)P3 (cid:48)P1P2P3 là tứ diện đỏ (tức (cid:48). Khi đó ta có tứ diện P1 (cid:48) ≡ P2 ta có thể giả sử P1 là tứ diện có 6 cạnh đều là đỏ). Còn lại ba điểm ta gọi là Pi, Pj, Pk. Lại xét tiếp các khả năng sau:

2. Nếu P1

a) Tồn tại một trong ba đỉnh sao cho trong bốn đoạn thẳng Pi, Pj, Pk. sao (cid:48), PiP1, PiP2, PiP3 có ít nhất hai đoạn đỏ. Giả sử đó (cid:48)P2P3 cùng

cho trong bốn đoạn PiP1 là PiP1, PiP2 là đỏ. Kho đó ta có hai tam giác đơn sắc PiP1P2, P1 đỏ không có cạnh chung.

P1

b) Với mọi đỉnh Pi, Pj, Pk. khi nối các đỉnh ấy với bốn đỉnh của tứ diện (cid:48)P1P2P3 ta được tối đa một đoạn màu đỏ mà thôi. Khi đó tồn tại một đỉnh của tứ diện (chẳng hạn P1) sao cho P1Pi, P1Pj, P1Pk

đều màu đen. Lại có hai khả năng xảy ra:

- Nếu PiPjPk là tam giác đỏ thì PiPjPk và P1P2P3 là hai tam giác đơn

sắc cùng đó không có cạnh chung.

- Nếu tồn tại một cạnh đen (chẳng hạn PiPj). Khi đó PiPjPk là tam giác đen. Lúc này PiPjPk và P1P2P3 là hai tam giác đơn sắc (một đen, một đỏ) không có cạnh chung.

Bài toán 3.9. Cho hình đa giác đều 9 cạnh. Mỗi đỉnh của nó được tô màu

bằng một trong hai màu trắng hoặc đen. Chứng minh rằng tồn tại hai tam

giác phân biệt có diện tích bằng nhau, mà các đỉnh của mỗi tam giác được

tô cùng một màu.

Lời giải.

Gọi chín đỉnh của đa giác là A1, A2, . . . , A9 đều được tô bằng hai màu. Nên theo nguyên lí Dirichlet có ít nhất năm đỉnh trong số đó được tô cùng

một màu. Giả sử có năm đỉnh được tô màu trắng, năm đỉnh này tạo ra:

= 10

C 3

5 =

5! 3!2!

Tam giác màu trắng (tam giác màu trắng là tam giác có ba đỉnh cùng màu

trắng). Gọi ∆ là tập hợp các đỉnh của đa giác đã cho, tức là:

∆ = {A1, A2, . . . , A9}

Gọi O là tâm của đa giác đều đã cho (vì là đa giác đều nên luôn tồn tại tâm). Xét phép quay các góc 00, 400, 800, 1200, 1600, 2000, 2400, 2800, 3200 xung

quanh tâm O. Rõ ràng ứng với mỗi phép quay này tập ∆ biến thành chính

nó (tức là tập các đỉnh của đa giác đều không thay đổi qua phép quay trên.

Mặc dù khi quay thì điểm này biến thành điểm kia). Sau 9 phép quay trên

thì có 10 tam giác trắng biến thành 90 tam giác trắng, mà mỗi tam giác này

đều có các đỉnh thuộc tập hợp ∆. Chú ý rằng số các tam giác khác nhau có

đỉnh trong ∆ là:

C 3

= 84.

9 =

9! 6!3!

Vì 84 < 90, nên theo nguyên lí Dirichlet tồn tại hai tam giác trắng ∆ và ∆(cid:48) sao cho các phép quay tương ứng cùng một tam giác. Vì phép quay

∆.

bảo toàn hình dáng và độ lớn của hình (nói riêng bảo toàn diện tích), tức là S∆ = S(cid:48)

Bài toán 3.10. Cho mỗi điểm trên mặt phẳng được tô bằng một trong hai

màu xanh, đỏ. Chứng minh rằng tồn tại một tam giác mà ba đỉnh và trọng

tâm cùng màu.

Lời giải.

Lấy năm điểm tùy ý sao cho không có ba điểm nào thẳng hàng trên mặt

phẳng. Khi đó vì chỉ dùng có hai màu để tô các đỉnh, mà theo nguyên lí

Dirichlet phải tồn tại ba điểm trong số đó cùng màu. Giả sử đó là ba điểm

A, B, C có màu đỏ. Như vậy ta có tam giác ABC với ba đỉnh màu đỏ.

Gọi G là trọng tâm tam giác ABC. Chỉ có hai khả năng xảy ra:

1) Nếu G có màu đỏ. Khi đó A, B, C, G cùng đỏ và bài toán đã được giải.

2) Nếu G có màu xanh. Kéo dài GA, GB, GC các đoạn AA(cid:48) = 3GA, BB(cid:48) = 3GB, CC (cid:48) = 3GC.

Khi đó, nếu gọi M, N, P tương ứng là các trung điểm của BC, CA, AB

thì A(cid:48)A = 3AG = 6GM nên A(cid:48)A = 2AM.

Tương tự B(cid:48)B = 2BN, CC (cid:48) = 2CP. Do đó các tam giác A(cid:48)BC, B(cid:48)AC, C (cid:48)AB tương ứng nhận A, B, C là trọng

tâm.

Mặt khác, ta cũng có các tam giác ABC và A(cid:48)B(cid:48)C (cid:48) có cùng trọng tâm G.

Có hai trường hợp sau có thể xảy ra: a) Nếu A(cid:48), B(cid:48), C (cid:48) cùng xanh. Khi đó tam giác A(cid:48)B(cid:48)C (cid:48) và trọng tâm G có

cùng màu xanh.

b) Nếu ít nhất một trong các điểm A(cid:48), B(cid:48), C (cid:48) có màu đỏ. Không mất tính

tổng quát giả sử A(cid:48) đỏ. Khi đó tam giác A(cid:48)BC và trọng tâm A màu đỏ.

Vậy trong mọi khả năng luôn tồn tại một tam giác mà ba đỉnh và trọng

tâm cùng màu.

3.2 Đếm cấu hình

Bài toán 3.11. Xác định số những hình chữ nhật mà ta có thể nhìn thấy

trên những hình sau đây (hình chữ nhật có các cạnh song song với các đường

lưới)

Lời giải.

Ta chú ý tới vị trí của hình chữ nhật. Mỗi hình chữ nhật có thể chiếu vào

các trục tọa độ Ox, Oy. Do đó định nghĩa một hình chữ nhật gồm hai cặp

số (a;b) và (c;d) với a, b ∈ { 0, 1, 2, . . . , n } , c, d ∈ {0, 1, 2, . . . , m}, n là số

cách, nghĩa cột, m là số hàng. Như vậy có thể làm là

.

n (n + 1) 2

m (m + 1) 2

hình chữ nhật. Do đó hình chữ nhật thứ nhất là tồn tại

nm (n + 1) (m + 1) 4

có 60 hình chữ nhật, hình chữ nhật thứ hai có 945 hình chữ nhật.

Bài toán 3.12. Xác định số hình vuông với cạnh song song với lưới, có khả

năng xảy ra của hình sau đây Số những hình vuông với đỉnh trên các nút

lưới đã cho là bao nhiêu?

Lời giải.

a) Ta nhóm hình vuông theo độ dài của cạnh. Tồn tại 16 hình vuông đơn

vị, 9 hình vuông 2 x 2, 4 hình vuông 3 x 3 và một hình vuông 4 x 4. Như vậy ta có 12 + 22 + 32 + 42 = 30 hình vuông mà cạnh của chúng song song

với đường lưới. Để đếm tất cả các hình vuông ta phải đồng nhất chúng trên

hình. Vì ta có thể thấy tồn tại bốn loại hình vuông khác nhau trên hình. Số

hình vuông đồng dạng với loại 1 là 9, số hình vuông đồng dạng với loại 2 là

1, loại 3 có 2.4 = 8 hình vuông, loại 4 chỉ có 2 hình vuông. Như vậy có 20

hình vuông.

b) Dùng kĩ thuật như trên ta cũng nhận được 1.4 + 2.5 + 3.6 + 4.7 + 5.8

+ 6.9 = 154 hình vuông song song với đường lưới. Còn những hình vuông có

cạnh không song song với đường lưới là 1.4 + 3.6 + 5.8 + 2.(7.4 + 1.4 + 6.3

+ 5.2 + 5.2 + 4.1) = 210.

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

Bài toán 3.13 (VMO 1992). Một bảng hình chữ nhật kẻ ô vuông có 1991

hàng và 1992 cột (nghĩa là bảng gồm 1991 × 1992 ô vuông). Kí kiệu ô vuông

nằm ở giao của hàng thứ m (kể từ trên xuống dưới) và cột thứ n (kể từ trái

qua phải) là (m; n). Tô màu các ô vuông của bảng theo cách sau: lần thứ

nhất tô 3 ô (r; s), (r + 1; s + 1), (r + 2; s + 2), với r, s là hai số tự nhiên

cho trước thỏa mãn 1 ≤ r ≤ 1989 và 1 ≤ s ≤ 1990. Từ lần thứ 2 mỗi lần tô

đúng 3 ô chưa có màu nằm cạnh nhau hoặc trong cùng một hàng hoặc trong

cùng một cột. Hỏi bằng cách đó có thể tô được tất cả các ô vuông của bảng

đã cho hay không.

Lời giải.

Ta giả sử có thể tô hết các ô trong bảng. Khi đó tất cả có 664.1991 lần

tô. Điền số các ô như sau: Tại ô (m; n) ta điền số m.n. Gọi S là tổng các số

ở các ô đã điền.

Ta có S = (1 + 2 + · · · + 1991) (1 + 2 + · · · + 1992) ≡ 0 (mod 3).

(mod 3)

Mặt khác, gọi Si tổng các số ở 3 ô điền lần thứ i với 1 ≤ i ≤ 664.1991. Ta có:  

S1 = rs + (r + 1) (s + 1) + (r + 2) (s + 2) ≡ 2

(mod 3), 2 ≤ i ≤ 664.1991



Si ≡ 0

(vì Si là tổng 3 số có dạng ab, (a + 1) b, (a + 2) b). Suy ra S ≡ 2 (mod3).

Điều mâu thuẫn này chứng tỏ điều giả sử sai. Vậy không thể tô tất cả các

ô trong bảng đã cho.

Bài toán 3.14 (VMO 2001). Cho một bảng ô vuông kích thước 2000 × 2001

(bảng gồm 2000 hàng và 2001 cột). Hãy tìm số nguyên dương k lớn nhất

sao cho ta có thể tô màu k ô vuông con của bảng thỏa mãn điều kiện: hai ô

vuông con nào được tô màu cũng không có đỉnh chung.

Lời giải.

Ta qui ước: thứ tự của các hàng được tính từ trên xuống dưới và thứ tự

các cột được tính từ trái qua phải.

Kí hiệu (i; j) là ô vuông nằm ở hàng i, cột j; k (T ) là số ô được tô màu ở

cách tô màu T .

Xét một cách tô màu T thỏa mãn điều kiện bài toán.

Ta thấy, nếu ô (i; j), (1 ≤ i ≤ 1999, 1 ≤ j ≤ 2001) được tô màu thì các ô

(i + 1; j) và các ô kề với nó trong cùng một hàng không được tô màu. Điều

này cho phép ta thực hiện phép biến đổi sau đối với T :

Xóa màu ở tất cả các ô (i; j) mà i lẻ và tô màu các ô (i + 1; j). Rõ ràng,

sau khi thực hiện phép biến đổi nói trên với T , ta thu được một cách tô màu

T’ thỏa mãn đề bài và: + k (T (cid:48)) = k (T ) + Tất cả các ô ở hàng thứ 2i − 1 với i = 1, 2, 3, . . . , 103 đều không được

tô màu.

Từ điều kiện của đề suy ra trong một hàng có không quá 1001 ô được tô

màu. Do đó k (T ) ≤ 1001.103.

Ta xét cách tô màu sau: Tô tất cả các ô (2i; 2j − 1) với i = 1, 2, . . . , 103, j = 1, 2, . . . , 1001. Ta

thấy cách tô màu này thỏa mãn điều kiện bài toán và số ô được tô màu là 1001.103.

Vậy số nguyên k lớn nhất cần tìm là kmax = 1001.103.

Bài toán 3.15 (VMO 2006). Cho m, n là các số nguyên lớn hơn 3 và bảng

ô vuông kích thước m × n (bảng gồm m hàng và n cột). Cho phép đặt bi vào

các ô vuông con của bảng theo cách sau: mỗi lần đặt 4 viên bi vào 4 ô vuông

con (mỗi ô 1 viên) mà 4 ô vuông đó tạo thành một trong các hình dưới đây:

Hỏi bằng cách thực hiện một số lần hữu hạn phép đặt bi nói trên, ta có

thể đặt bi vào tất cả các ô vuông con của bảng sao cho số bi trong mỗi ô

vuông con đều bằng nhau hay không, nếu:

1. m = 2004 và n = 2006.

2. m = 2005 và n = 2006.

Lời giải.

1. Nhận thấy: Bằng cách thực hiện hai lần phép đặt bi, ta có thể đặt

vào mỗi ô vuông con của bảng 4 × 2 một viên bi. Có thể phân chia bảng

2004 × 2006 thành các bảng 4 × 2. Từ đó bằng cách thực hiện một số hữu

hạn phép đặt bi của đề bài, ta có thể đặt bi vào tất cả các ô vuông con của

bảng 2004 × 2006 sao cho số bi trong mỗi ô đều bằng nhau (bằng 1).

2. Giả sử sau một số hữu hạn lần phép đặt bi của đề bài, ta đặt được vào

mỗi ô vuông con của bảng 2005 × 2006 k viên bi. Tô màu tất cả các ô vuông

con thuộc hàng lẻ của bảng bởi màu đen và coi các ô không được tô màu

có màu trắng. Khi đó, số các ô màu đen bằng 2006.1003 và số ô màu trắng

bằng 2006.1002.

Ta thấy, ở mỗi lần đặt bi, đều đặt đúng hai viên bi vào các ô màu đen và

đúng hai viên bi vào các ô màu trắng. Do đó sau mỗi lần đặt bi, số bi trong

các ô màu đen và số bi trong các ô màu trắng luôn bằng nhau. Suy ra, khi

ở mỗi ô có k viên bi, ta phải có 2006.1003k = 2006.1002k hay k = 0. Điều

vô lí này chứng tỏ giả sử ban đầu là sai. Vì thế, không thể đặt bi vào các ô

vuông con của bảng sao cho số bi trong mỗi ô vuông con đều bằng nhau.

Bài toán 3.16 (Vietnam TST 1993). Gọi hình chữ nhật 2 × 3 (hoặc 3 × 2)

bị cắt bỏ một ô vuông 1 × 1 ở góc được gọi là hình chữ nhật khuyết đơn.

Hình chữ nhật 2 × 3 (hoặc 3 × 2) bị cắt bỏ hai hình vuông ở hai góc đối

diện được gọi là hình chữ nhật khuyết kép. Người ta ghép một số hình vuông

2 × 2, một số hình chữ nhật khuyết đơn và một số hình chữ nhật khuyết kép

sao cho không có hai hình nào chờm lên nhau để tạo thành một hình chữ

nhật kích thước 1993 × 2000. Gọi s là tổng số hình vuông 2 × 2 và hình chữ

nhật khuyết kép trong mỗi cách ghép nói trên. Tìm giá trị lớn nhất của s.

Lời giải.

Gọi y là số hình chữ nhật khuyết đơn. Ta có đẳng thức về diện tích

4s + 5y = 2000.1993

(13)

Điền số 0 vào các ô (2k, 2t) với 1 ≤ k ≤ 996, 1 ≤ t ≤ 1000 , ta thấy có

996.1000 số 0 được điền. Ta thấy:

+ Hình vuông 2 × 2 và hình chữ nhật khuyết kép chứa đúng một số 0

+ Hình chữ nhật khuyết đơn chứa x số 0 (với x = 1 hoặc x = 2).

Suy ra

996.1000 = 1.s + x.y ≥ s + y

(14)

Từ (13) và (14) suy ra 2000.1993 = 5(s + y) − s ≤ 5.996.1000 − s. Do đó

s ≤ 994000.

Ta xét các hình ghép thỏa mãn với s = 994000.

Kết luận

Luận văn đã trình bày và đạt được một số kết quả sau:

- Trình bày cách giải các bài toán đếm trong hình học tổ hợp thông qua

việc phân loại các đối tượng đếm trong hình học.

- Trình bày các nguyên lí cơ bản như nguyên lí bất biến, nguyên lí Dirichlet,

nguyên lí cực hạn và các phương pháp vận dụng các nguyên lí đó để giải các

bài toán hình học tổ hợp.

- Trình bày được một số dạng toán liên quan, đặc biệt là đã tiếp cận được

một số bài toán khó về hình học tổ hợp trong các kì thi chọn học sinh giỏi

quốc gia và quốc tế.

Tài liệu tham khảo

[1] Trần Nam Dũng (2010), Bài giảng các phương pháp và kĩ thuật chứng

minh bằng nguyên lí Dirichlet, Kỷ yếu "Chương trình gặp gỡ toán học

2010", do ĐHQG TP.HCM tổ chức.

[2] Nguyễn Hữu Điển (2005), Một số chuyên đề hình học tổ hợp, NXB Giáo

dục.

[3] Vũ Đình Hòa (2006), Chuyên đề bồi dưỡng học sinh giỏi hình học tổ hợp,

NXB Giáo dục.

[4] Nguyễn Văn Mậu, Trần Nam Dũng, Vũ Đình Hòa, Đặng Huy Ruận,

Đặng Hùng Thắng (2008), Chuyên đề chọn lọc tổ hợp và toán rời rạc,

NXB Giáo dục.

[5] Nguyễn Văn Mậu (chủ biên) (2010), Kỷ yếu "Các chuyên đề Olympic

Toán chọn lọc", Ba Vì.

[6] Jiri Herman Radan Kucera Jaromir Simsa (Translated by Karl Dilcher),

Counting and Configurations, Problems in Combinatorics, Arithmetic,

and Geometry, Canadian Mathematical Society (Societe mathematioue

du Canada).