Ứng dụng nguyên lý dirichlet trong việc giải một số bài toán của chương trình trung học phổ thông.

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN THỊ MỸ HƯƠNG

ỨNG DỤNG NGUYÊN LÝ DIRICHLET

TRONG VIỆC GIẢI MỘT SỐ BÀI TOÁN

CỦA CHƯƠNG TRÌNH TRUNG HỌC

PHỔ THÔNG

Chuyên ngành : Phương pháp Toán sơ cấp

Mã số : 60.46.40

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2015

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: PGS.TS Trần Đạo Dõng

Phản biện 1: PGS.TSKH. Trần Quốc Chiến

Phản biện 2: GS.TSKH. Nguyễn Văn Mậu

Luận văn sẽ được bảo vệ tại hội đồng chấm luận văn tốt

nghiệp Thạc sĩ Khoa học, họp tại Đại Học Đà Nẵng vào ngày

11 tháng 01 năm 2015.

Có thể tìm hiểu luận văn tại:

• Trung tâm thông tin học liệu, Đại Học Đà Nẵng.

• Thư viện trường Đại học Sư Phạm, Đại Học Đà Nẵng.

1

MỞ ĐẦU

1. Tính cấp thiết của đề tài

Nguyên lý Dirichlet do nhà toán học người Đức Johann

Peter Gustav Lejeune Dirichlet (1805 − 1859) đề xuất, tuy

đơn giản nhưng có nhiều ứng dụng trong lập luận giải toán.

Có nhiều phát biểu của nguyên lý Dirichlet trong đó phiên

bản đầu tiên là: nếu nhốt n + 1 con thỏ vào n lồng (n là

số nguyên dương) thì tồn tại một lồng chứa ít nhất 2 con

thỏ. Nguyên lý này còn được phát biểu dưới nhiều dạng:

tập hợp, đại số, hình học, số học, đồ thị, ...

Có nhiều bài toán thường là chỉ cần chứng minh sự tồn

tại của sự vật hay hiện tượng, mà không cần chỉ ra tường

minh sự vật, hiện tượng đó. Do đó, nguyên lý Dirichlet tưởng

chừng đơn giản như vậy, nhưng nó là một công cụ hết sức

hiệu quả dùng để chứng minh sự tồn tại của một đối tượng

với tính chất xác định.

Trong các kỳ thi học sinh giỏi cấp tỉnh, cấp quốc gia

và các kỳ thi Olympic toán quốc tế và khu vực thường có

ít nhất một bài toán liên quan tới nguyên lý Dirichlet và

thường là dạng toán khó.

Xuất phát từ nhu cầu phát triển ứng dụng và tính thời

sự của việc nghiên cứu nguyên lý Dirichlet, chúng tôi quyết

định chọn đề tài với tên gọi: "Ứng dụng nguyên lý Dirich￾let trong việc giải một số bài toán của chương trình

trung học phổ thông" để tiến hành nghiên cứu. Chúng

tôi hy vọng tạo được một tài liệu tham khảo tốt cho những

người muốn tìm hiểu về ứng dụng của nguyên lý Dirichlet.

2

2. Mục tiêu nghiên cứu của đề tài

Mục tiêu của đề tài nhằm nghiên cứu một số ứng dụng

của nguyên lý Dirichlet trong việc giải một số lớp bài toán

của chương trình trung học phổ thông.

3. Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu của đề tài là các nguyên lý đếm

trong lý thuyết tổ hợp.

• Phạm vi nghiên cứu của đề tài là ứng dụng của nguyên

lý Dirichlet trong việc giải một số lớp bài toán của

chương trình trung học phổ thông.

4. Phương pháp nghiên cứu

• Thu thập các bài báo khoa học và tài liệu của các tác

giả nghiên cứu liên quan đến nguyên lý Dirichlet và

các ứng dụng của nó.

• Tham gia các buổi seminar của thầy hướng dẫn để

trao đổi các kết quả đang nghiên cứu. Trao đổi qua

email, blog, forum với các chuyên gia về các ứng dụng

của nguyên lý Dirichlet.

5. Bố cục đề tài

Luận văn được phân làm hai chương:

• Ở chương 1 giới thiệu các dạng phát biểu của nguyên

lý Dirichlet, các số Ramsey, định lý Erd¨os - Szekeres,

một số ứng dụng trong lý thuyết số và các ví dụ minh

họa.

3

• Đến chương 2 trình bày ứng dụng của nguyên lý Dirich￾let trong việc giải một số lớp bài toán của chương trình

trung học phổ thông như: lớp bài toán số học, lớp bài

toán rời rạc và đại số tổ hợp, lớp bài toán hình học tổ

hợp và trong một số lớp bài toán tô màu.

6. Ý nghĩa khoa học và thực tiễn

• Tổng quan các kết quả của các tác giả đã nghiên cứu

liên quan tới "nguyên lý Dirichlet và các ứng dụng

trong việc giải một số lớp bài toán của chương trình

trung học phổ thông" nhằm xây dựng một tài liệu

tham khảo cho những ai muốn nghiên cứu về nguyên

lý Dirichlet và các ứng dụng.

• Chứng minh chi tiết và làm rõ một số mệnh đề, cũng

như đưa ra một số ví dụ minh họa nhằm làm cho người

đọc dễ dàng tiếp cận vấn đề được đề cập.

4

CHƯƠNG 1

NGUYÊN LÝ DIRICHLET

Trong chương đầu chúng tôi giới thiệu các dạng phát biểu của

nguyên lý Dirichlet và một số định lý liên quan sẽ được sử dụng

trong chương tiếp theo của luận văn.

1.1. CÁC DẠNG PHÁT BIỂU NGUYÊN LÝ DIRICH￾LET

Mục này trình bày nguyên lý Dirichlet cơ bản và các dạng

phát biểu của nguyên lý Dirichlet trong một số lĩnh vực toán học.

1.1.1. Nguyên lý Dirichlet.

Nguyên lý 1.1.1. Nguyên lý Dirichlet cơ bản.

Nếu có k + 1 (hoặc nhiều hơn) đồ vật đặt vào trong k hộp (k là

số nguyên dương) thì tồn tại một hộp có ít nhất hai đồ vật.

Nguyên lý 1.1.2. Nguyên lý Dirichlet tổng quát.

Nếu có N đồ vật được đặt vào k hộp (N, k là số nguyên dương)

thì sẽ tồn tại hộp chứa ít nhất 

N

k



đồ vật.

Ở đây, ký hiệu ]x[ là giá trị của hàm trần tại số thực x, biểu

diễn số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. Khái niệm

này đối ngẫu với [x] là giá trị của hàm sàn hay hàm phần nguyên

tại số thực x, biểu diễn số nguyên lớn nhất có giá trị nhỏ hơn hoặc

bằng x.

5

1.1.2. Nguyên lý Dirichlet dạng tập hợp và tập hợp

mở rộng.

Nguyên lý Dirichlet thực chất là một định lý về tập hợp hữu

hạn. Chúng ta có thể phát biểu chính xác nguyên lý này dưới dạng

sau đây:

Nguyên lý 1.1.3. (Nguyên lý Dirichlet dạng tập hợp).

Cho A và B là hai tập hợp không rỗng có số phần tử hữu hạn, mà

số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với

một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một

phần tử của B, thì tồn tại ít nhất hai phần tử của A mà chúng

tương ứng với cùng một phần tử của B.

Nguyên lý 1.1.4. (Nguyên lý Dirichlet dạng tập hợp mở

rộng).

Giả sử A và B là hai tập hợp hữu hạn và S(A), S(B) lần lượt ký

hiệu là số lượng các phần tử của A, B. Nếu với một quy tắc nào

đó cho tương ứng mỗi phần tử của A với một phần tử của B thì

tồn tại ít nhất 

S (A)

S (B)



phần tử của A tương ứng với cùng một

phần tử của B.

Bên cạnh đó, trong lĩnh vực hình học nguyên lý Dirichlet còn

được phát biểu cho những đối tượng khác nhau như sau:

1.1.3. Nguyên lý Dirichlet trong hình học.

Nguyên lý 1.1.5. (Nguyên lý Dirichlet cho đoạn thẳng).

Cho ∆1, ∆2, . . . , ∆n là các đoạn thẳng sao cho đoạn thẳng ∆i nằm

trong đoạn thẳng ∆ với mọi i = 1, . . . , n và tổng độ dài các đoạn

thẳng ∆1, ∆2, . . . , ∆n lớn hơn độ dài đoạn thẳng ∆. Khi đó tồn

tại ít nhất hai đoạn thẳng trong số n đoạn thẳng ∆1, ∆2, . . . , ∆n

6

có chung điểm trong.

Nguyên lý 1.1.6. (Nguyên lý Dirichlet cho thể tích).

Cho A1, A2, . . . , An là các vật thể sao cho Ai ⊆ A với i = 1, n

và v (A), v (A1), v (A2), . . . , v (An) lần lượt là thể tích các vật thể

A, A1, A2, . . . , An sao cho

v (A) < v (A1) + v (A2) + · · · + v (An).

Khi đó, tồn tại ít nhất hai vật thể trong n vật thể A1, A2, . . . , An

có chung điểm trong. (Điểm P được gọi là điểm trong của hình

phẳng A nếu tồn tại hình tròn tâm P nằm trọn trong A).

Nguyên lý 1.1.7. (Nguyên lý Dirichlet cho diện tích).

Cho A1, A2, . . . , An là các hình phẳng sao cho Ai ⊆ A với i = 1, n

và s (A), s (A1), s (A2), . . . , s (An) lần lượt là diện tích các hình

phẳng A, A1, A2, . . . , An sao cho

s (A) < s (A1) + s (A2) + · · · + s (An).

Khi đó, tồn tại ít nhất hai hình phẳng trong n hình phẳng A1, A2,

. . . , An có chung điểm trong.

Nguyên lý 1.1.8. (Nguyên lý Dirichlet cho trường hợp

vô hạn).

Nếu chia một tập hợp vô hạn các quả táo vào hữu hạn ngăn kéo

thì tồn tại ít nhất một ngăn kéo chứa vô hạn quả táo.

1.2. SỐ RAMSEY

Qua một ví dụ cụ thể, trong phần này chúng tôi tìm hiểu về

định nghĩa số Ramsey và ứng dụng nguyên lý Dirichlet để chứng

minh một vài định lý liên quan đến số Ramsey.

7

1.2.1. Ví dụ mở đầu.

Ví dụ 1.2.1. Trong một bàn tiệc có 6 người, ta luôn tìm được

hoặc 3 người đôi một quen nhau hoặc 3 người đôi một không quen

nhau.

1.2.2. Định nghĩa số Ramsey.

Định nghĩa 1.2.2. Cho hai số nguyên dương l và s, khi đó n

được gọi là số Ramsey khi và chỉ khi n là số nhỏ nhất thỏa mãn

tính chất: với n điểm trên mặt phẳng, nếu nối chúng đôi một với

nhau bởi các đoạn thẳng màu xanh hoặc màu đỏ thì luôn có hoặc

l điểm được nối bởi các đoạn màu xanh hoặc s điểm được nối bởi

các đoạn màu đỏ. Ký hiệu là: r(l, s) = n, còn được gọi là có tính

chất (l, s) − Ramsey.

Định lý 1.2.3. Nếu l = s = 3 thì r(3, 3) không thể bằng 5. Nói

cách khác, với 5 điểm trên mặt phẳng đôi một nối nhau bởi các

đoạn thẳng màu xanh hoặc màu đỏ chúng ta không thể tìm thấy

một tam giác có cả ba cạnh cùng màu xanh hoặc cả ba cạnh cùng

màu đỏ.

Mệnh đề 1.2.4. Với l là một số nguyên dương, khi đó chúng

ta có r(2, l) = l.

Mệnh đề 1.2.5. Với mỗi cặp (l, s) của các số nguyên dương,

số Ramsey r(l, s) là tồn tại. Hơn nữa, nếu l, s ≥ 2 thì r(l, s) ≤

r(l − 1, s) + r(l, s − 1).

1.3. ĐỊNH LÝ ERDOS - SZEKERES ¨

Một trong những ứng dụng quan trọng khác của nguyên lý

Dirichlet là với dãy số. Cho A = (a1, a2, . . . , an) là dãy gồm n số