Nguyên lý dirichlet 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

DỊCH THỊ THÙY LINH

NGUYÊN LÝ DIRICHLET VÀ

ỨNG DỤNG GIẢI TOÁN SƠ CẤP

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

Mã số : 60.46.01.13

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

Đà Nẵng, 2015

CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI

ĐẠI HỌC ĐÀ NẴNG

Hƣớng dẫn khoa học : PGS. TSKH TRẦN QUỐC CHIẾN

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

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

Luận văn đã đƣợ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 tại Đại Học Đà Nẵng vào ngày 12

tháng 12 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. Lý do chọn đề tài

Trong toán học việc tìm ra kết quả cụ thể của một bài toán đôi

khi rất khó khăn,trong những trƣờng hợp nhƣ thế ta chỉ cần chỉ ra sự

tồn tại là đủ rồi. Đặc biệt việc chỉ ra một cấu hình thỏa mãn tính chất

nào đó có ý nghĩa quan trọng về mặt lí thuyết cũng nhƣ thực tế. Bài

toán tồn tại đƣợc nghiên cứu từ rất lâu và gớp phần đáng kể thúc đẩy

sự phát triển của lí thuyết tổ hợp cũng nhƣ nhiều nghành toán học

khác.

Nguyên lý Dirichlet nhiều khi ngƣời ta hay gọi là nguyên lí

ngăn kéo hay chuồng bồ câu là một nguyên lí có nội dung khá đơn

giản, song nó lại 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. Dùng nguyên lí này ta dễ 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. Nó

đặc biệt có nhiều ứng dụng trong lĩnh vực lại có thể áp dụng rộng rãi

trong việc chứng mình các bài toán tổ hợp, số học, đại số và là công

cụ tạo nên nhiều kết quả đẹp trong hình học.

Chính vì lí do đó mà em chọn đề tài “Nguyên lý dirichlet và

ứng dụng giải các bài toán sơ cấp” cho luận văn thạc sĩ của mình.

2. Mục tiêu nghiên cứu

Nghiên cứu nguyên lý Dirichlet,các tính chất và nguyên lí mở

rộng, đối ngẫu của nó.Đồng thời nghiên cứu ứng dụng của các

nguyên lí này vào việc giải các bài toán về số học, hình học, tổ hợp...

trong toán sơ cấp.

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

3.1. Đối tƣợng nghiên cứu

Nguyên lý Dirichlet, nguyên lí Dirichlet mở rộng , nguyên lý

Dirichlet đối ngẫu, ứng dụng của các nguyên lí này vào giải toán.

2

3.2. Phạm vi nghiên cứu

Nguyên lý Dirichlet trong giải toán sơ cấp

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

- Nghiên cứu các cơ sở lí luận, cơ sở khoa học nhằm cho một

cái nhìn tổng quát nhất về nội dung nguyên lý Dirichlet và nhận diện

bài toán để có thể giải quyết đƣợc bằng nguyên lí Dirichlet

- Phân tích và tổng hợp các dạng bài tập nhằm xây dựng đƣợc

một hệ thống bài tập đi từ dễ tới khó, từ cụ thể tới tổng quát có ứng

dụng nguyên lí Dirichlet

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

Giúp bạn đọc tiếp cận với một phƣơng pháp chứng minh toán

học hữu hiệu, thú vị. Và hi vọng cung cấp một tài liệu bổ ích cho các

em ham mê tìm tòi toán học.

6. Kết cấu của đề tài

Ngoài phần mở đầu và kết luận luận văn gồm có 2 chƣơng

Chƣơng 1: KIẾN THỨC CƠ SỞ, trình bày sơ lƣợc đại cƣơng

về tổ hợp, nội dung nguyên lý Dirichlet, các tính chất và định lý liên

quan đến nguyên lý.

Chƣơng 2: ỨNG DỤNG NGUYÊN LÝ DIRICHLET VÀO

GIẢI TOÁN SƠ CẤP, trình bày một số bài toán ứng dụng nguyên lý

Dirichlet trong lý thuyết tổ hợp, số học , hình học ….vv.

3

CHƢƠNG 1

KIẾN THỨC CƠ SỞ

1.1. ĐẠI CƢƠNG VỀ TỔ HỢP

1.1.1. Sơ lƣợc lịch sử

Có thể nói tƣ duy tổ hợp ra đời từ rất sớm. Vào thời nhà Chu –

Trung Quốc ngƣời ta đã biết đến những hình vuông thần bí. Thời cổ

Hy Lạp – thế kỉ thứ 4 trƣớc Công nguyên, nhà triết học Kxenokrat đã

biết cách tính số các từ khác nhau lập từ bảng chữ cái cho trƣớc. Nhà

toán học Pitagor và học trò đã tìm ra đƣợc nhiều số có tính chất đặc

biệt.

Tuy nhiên có thể nói rằng, lý thuyết tổ hợp đƣợc hình thành

nhƣ một ngành toán học mới vào thế kỉ 17 bằng một loạt công trình

nghiên cứu của các nhà toán học xuất sắc nhƣ Pascal, Fermat, Euler,

Leibnitz, …

Các bài toán tổ hợp có đặc trƣng bùng nổ tổ hợp với số cấu

hình tổ hợp khổng lồ. Việc giải chúng đòi hỏi một khối lƣợng tính

toán khổng lồ (có trƣờng hợp mất hàng chục năm). Vì vậy trong thời

gian dài, khi mà các ngành toán học nhƣ phép tính vi phân, phép tính

tích phân, phƣơng trình vi phân, …phát triển nhƣ vũ bão, thì dƣờng

nhƣ nó nằm ngoài sự phát triển và ứng dụng của toán học. Tình

thế thay đổi từ khi xuất hiện máy tính và sự phát triển của toán học

hữu hạn. Nhiều vấn đề tổ hợp đã đƣợc giải quyết trên máy tính. Từ

chỗ chỉ nghiên cứu các trò chơi, tổ hợp đã trở thành ngành toán học

phát triển mạnh mẽ, có nhiều ứng dụng trong các lĩnh vực toán học,

tin học,…

Chúng ta sẽ đi vào nghiên cứu, tìm hiểu một số bài toán nổi

tiếng trong lịch sử.

4

 Bài toán tháp Hà Nội

Bài toán này do Edouard Lucas đƣa ra vào cuối thế kỉ 19(ông

cũng là ngƣời đƣa ra dãy Fibonacci). Bài toán phát biểu nhƣ sau:

Có 3 cọc, cọc thứ nhất có n đĩa kích thƣớc khác nhau, xếp chồng

nhau, đĩa nhỏ nằm trên đĩa lớn. Hãy chuyển các đĩa từ cọc thứ nhất

sang cọc thứ ba, sử dụng cọc trung gian thứ hai sao cho luôn đảm bảo

đĩa nhỏ nằm trên đĩa lớn. Hãy đếm số lần di chuyển đĩa. Tìm phƣơng

án di chuyển tối ƣu.

Số lần di chuyển là

2 1 n



Khi n=64 ta có số lần di chuyển là 18 446 744 073 709 551

615

 Bài toán xếp n cặp vợ chồng

Bài toán này cũng do Lucas đƣa ra năm 1891. Bài toán phát

biểu nhƣ sau: Có n cặp vợ chồng cần xếp vào bàn tròn sao cho

không có cặp nào ngồi gần nhau. Có bao nhiêu cách xếp nhƣ vậy?

Bài toán này dẫn đến việc ngiên cứu một khái niệm quan trọng

là số phân bố và mãi đến năm 1934 mới có lời giải.

Số cách xếp là

2 n

.n!.U

trong đó

Un

là số phân bố. Bảng sau

cho thấy sự bùng nổ tổ hợp ghê gớm của số phân bố.

n = 4 5 6 7 8 9 10 11

Un= 2 13 80 579 4 738 43 387 439 729 4 890741

 Bài toán đƣờng đi quân ngựa trên bàn cờ

Cho bàn cờ vua với kích thƣớc 8 x 8 = 64 ô. Tìm đƣờng đi của

quân ngựa qua tất cả các ô, mỗi ô chỉ 1 lần, và quay về ô xuất phát.

Ngƣời ta chứng minh tổng quát đƣợc rằng:

Trên bàn cờ vuông có số cạnh chẵn lớn hơn hoặc bằng 6 bao

giờ cũng tồn tại đường đi.

5

Đƣờng đi của Euler (1759) có tính chất: hiệu các ô đối xứng

qua tâm bàn cờ bằng 32.

37 62 43 56 35 60 41 50

44 55 36 61 42 49 34 59

63 38 53 46 57 40 51 48

54 45 64 39 52 47 58 33

1 26 15 20 7 32 13 22

16 19 8 25 14 21 6 31

27 2 17 10 29 4 23 12

18 9 28 3 24 11 30 5

Đƣờng đi của Beverle (1848) có tính chất: tổng các ô trên

cột và hàng bằng 260.

1 30 47 52 5 28 43 54

48 51 2 29 44 53 6 27

31 46 49 4 25 8 55 42

50 3 32 45 56 41 26 7

33 62 15 20 9 24 39 58

16 19 34 61 40 57 10 23

63 14 17 36 21 12 59 38

18 35 64 13 60 37 22 11

6

 Hình vuông la tinh

Hình vuông la tinh cấp n là hình vuông gồm các số 1, 2, …, n –

1, n thỏa mãn

tổng mỗi hàng và tổng mỗi cột đều bằng nhau và bằng :

1

1 2

2

n(n )

.... n



   

Hình vuông la tinh chuẩn cấp n là hình vuông la tinh cấp n

có dòng đầu và cột đầu là 1, 2, …, n.

Bảng sau đây là hình vuông la tinh chuẩn cấp 7.

1 2 3 4 5 6 7

2 3 4 5 6 7 1

3 4 5 6 7 1 2

4 5 6 7 1 2 3

5 6 7 1 2 3 4

6 7 1 2 3 4 5

7 1 2 3 4 5 6

Công thức tính số hình vuông la tinh đến nay vẫn còn bỏ ngỏ.

Tuy nhiên, ta có thể lập chƣơng trình liệt kê tất cả hình vuông la

tinh chuẩn. Dƣới đây là một số giá trị:

n = 1 2 3 4 5 6 7

ln = 1 1 1 4 56 9 408 16 942 080

( ln là số hinh vuông la tinh chuẩn cấp n).

 Hình lục giác thần bí

Năm 1910 Cifford Adams đƣa ra bài toán hình lục giác thần

bí sau: Trên 19 ô lục giác hãy điền các số từ 1 đến 19 sao cho tổng

theo sáu hƣớng của lục giác bằng nhau (= 38).