Số ramsey và ứng dụng giải toán sơ cấp

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

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN XUÂN THẮNG

SỐ RAMSEY VÀ ỨNG DỤNG GIẢI TOÁN SƠ CẤP

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 2012

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.TSKH. TRẦN QUỐC CHIẾN

Phản biện 1: PGS.TS. HUỲNH THẾ PHÙNG

Phản biện 2: TS. NGUYỄN DUY THÁI SƠN

Luận văn được bảo vệ tại Hội đồng bảo vệ 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 01 tháng 07 năm 2012

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.

MỞ ĐẦU

1. Lý do chọn đề tài.

Tổ hơp l ̣ à ngành khoa hoc xu ̣ ất hiên kh ̣ á sớm vào đầu thế kỷ

17, cho đến nay đãđươc ̣ áp dung trong nhi ̣ ều linh v ̃ ưc kh ̣ ác nhau như

lý

thuyết số, hinh h ̀ oc, đ ̣ ai ṣ ố, xác suất thống kê, quy hoach th ̣ ưc ̣

nghiêm, khoa h ̣ oc ṃ áy tính, hóa hoc̣ …Các bà

i toán tổ hơp đư ̣ ơc phân ̣

thành các dang: b ̣ à

i toán tồn tai, b ̣ à

i toán đếm, bà

i toán liêt kê v ̣ à bà

i

toán tối ưu. Bà

i toán tồn tai thư ̣ ờng có nôi dung h ̣ ấp dẫn và khó giải

quyết , thường xuyên xuất hiên trong c ̣ ác kỳ

thi học sinh giỏi quốc

gia và quốc tế. Môt công c ̣ u ̣hữu hiêu để gi ̣ ải quyết dang to ̣ án này là

số Ramsey. Số Ramsey là một ứng dụng quan trọng của nguyên lý

Dirichlet, để vận dụng đươc n ̣ ó

trong viêc gi ̣ ải toán thì đò

i hỏi phải

hiểu nó môt c̣ ách sâu sắc và vân d ̣ ung n ̣ ó môt c̣ ách linh hoat trong ̣

từng bà

i toán cu ̣ thể. Hiên nay chưa c ̣ ó môt t ̣ à

i liêu tr ̣ ình bày môt ̣

cách hê ̣thống kiến thức về số Ramsey và ứng dung gi ̣ ải toán sơ cấp.

Chinh v ́

ì

lẻ đó

tôi chon đ̣ ề tà

i này nghiên cứu vớ

i mong muốn hoc t ̣ âp ̣

và

tích lũy cho bản thân kiến thức về số Ramsey và ứng dung gi ̣ ải

toán sơ cấp, bản luận văn này bổ sung thêm về tài liệu về tổ hợp cho

học sinh phổ thông; đặc biệt là dành cho những em học sinh có năng

khiếu môn toán. Chúng tôi hi vọng luận văn này sẽ đáp ứng được

phần nào lòng yêu thích khám phá toán học của các em. Đồng thời

đây cũng là tài liệu tham khảo quan trọng cho đồng nghiệp.

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

Nghiên cứu về số Ramsey và viêc ̣ ứng dung nó để gi ̣ ải các

bài toán tồn tại trong toán sơ cấp.

3. Mục tiêu và nhiệm vụ của việc nghiên cứu.

3.1. Mục tiêu nghiên cứu:

- Hiểu được số Ramsey và các tính chất cơ bản của nó.

- Vân d ̣ ung linh ho ̣ at ṣ ố Ramsey để giải quyết các bà

i toán

tồn tại trong toán sơ cấp.

3.2. Nhiêm v ̣ ụnghiên cứu:

- Hê ̣thống môt ṣ ố kiến thức cơ bản về bà

i toán tồn tai.̣

- Nắm vững và vân d ̣ ung số Ramsey đ ̣ ể phân lớp các ứng

dụng của các số Ramsey thường gặp trong việc giải các bài toán tồn

tại trong toán sơ cấp.

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

Tham khảo, phân tich, t ́ ổng hơp, h ̣ ê ̣thống: Tham khảo các

nguồn tà

i liêu kh ̣ ác nhau có

liên quan đến bà

i toán tồn tai ṿ à ứng

dung gi ̣ ải toán sơ cấp, phân tích tư liêu thu th ̣ âp đư ̣ ơc sau đ ̣ ó

tổng

hơp, h ̣ ê ̣thống lai vi ̣ ết đề tà

i này.

5. Kết quả dự kiến:

Trình bày môt c̣ ách hê ̣thống kiến thức vềsố Ramsey và ứng

dung của số Ramsey để giải các bài toán tồn tại trong toán sơ cấp. ̣

6. Ý nghĩa khoa học và thực tiễn của đề tài.

6.1. Ý nghia khoa h ̃ oc:̣

Hê ̣thống các kiến thức về bà

i toán tồn tai, số Ramsey v ̣ à

ứng dung gi ̣ ải toán sơ cấp.

6.2. Ý nghia th ̃ ưc ti ̣ ên: ̃

Đề tà

i hoàn thành trở thành tà

i liêu tham kh ̣ ảo bổ ich cho ́

giáo viên , hoc sinh ̣ ở trường THPT, sinh viên ở các trường đai ḥ oc ̣

và cao đẳng , các ban yêu to ̣ án, đăc bi ̣ êt l ̣ à các đối tương d ̣ ay b ̣ ồi

dưỡng và

tham gia các kỳ

thi học sinh giỏi quốc gia và quốc tế.

7. Cấu trúc của luận văn:

Ngoài phần mở đầu, kết luận và tài liệu tham khảo trong luận

văn gồm có 3 chương như sau:

Chương 1. ĐAI CƯƠNG V ̣ Ề TỔ HƠP VÀ ĐỒ THỊ. ̣

Chương 2. LÝ THUYẾT VỀ SỐ RAMSEY

Chương 3. ỨNG DUNG GI ̣ ẢI TOÁN SƠ CẤP.

Chương 1. ĐẠI CƯƠNG VỀ TỔ HƠP VÀ ĐỒ THỊ ̣

1.1. Sơ lược lịch sử:

Ví du ̣1. Xé

t sư ̣ bố trí

các quân cờ

trên bàn cờ vua. Mỗi thế

cờ có

thể coi là môt c̣ ấu hình tổ hơp. ̣ Ở đây ta có

thể đinh ngh ̣ iã

A là

tâp ḥ ơp c ̣ ác quân cờ

trắng

B là

tâp ḥ ơp c ̣ ác quân cờ đen

S làsơ đồsắp xếp các quân cờ

trên bàn cờ

R là hê ̣thống các điều kiên đư ̣ ơc x̣ ác đinh b ̣ ằng luât c̣ ờ vua

Vídu ̣2. Bà

i toán tháp Hà Nôị

A là

tâp ḥ ơp n đ ̣ iã

S làsơ đồsắp xếp các đia trên ̃ 3 coc̣

R

1

là điều kiên ̣ mỗi lần chuyển 1 đia t ̃ ừ môt c̣ oc sang c ̣ oc kh ̣ ác

R

2

là điều kiên đ̣ ia ñ ằm dướ

i lớn hơn đia ñ ằm trên

Cấu hình tổ hơp l ̣ à môt c̣ ách sắp xếp các đia trên 3 c ̃ oc thỏa c ̣ ác

điều kiên Ṛ

1

và

R

2

.

1.2. Các dạng bài toán tổ hợp:

1.2.1. Bài toán đếm

Nôi dung b ̣ à

i toán đếm là

trả lờ

i câu hỏi “Có bao nhiêu cấu

hình thuôc d ̣ ang đang x ̣ é

t ?”. Phương pháp đếm cấu hình tổ hơp ̣

thường dưa ṿ ào môt ṣ ố quy tắc, nguyên lý đếm và phân rãđưa về các

cấu hinh t ̀ ổ hơp đơn gi ̣ ản. Khi viêc x̣ ác đinh ch ̣ inh x ́ ác số cấu hình tổ

hơp g ̣ ăp kh ̣ ó khăn hay chưa giải quyết đươc tr ̣ on v ̣ en, ngư ̣ ờ

i ta

thường đăt ra b ̣ à

i toán đánh giá số các cấu hinh ̀

tổ hơp đ ̣ ó bằng cách

xác đinh c ̣ ân trên v ̣ à cân dư ̣ ớ

i của nó

. Bà

i toán đếm đươc ̣ áp dung c ̣ ó

hiêu qu ̣ ả vào những công viêc mang t ̣ inh ch ́ ất đánh giá như tính xác

xuất của môt ṣ ựkiên, t ̣ ính đô ̣phức tap c ̣ ủa môt thu ̣ ât tọ án.