Ứng dụng toán rời rạc trong giải toán trung học phổ thông.

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

ĐẠI HỌC ĐÀ NẴNG

PHAN HỒNG VINH

ỨNG DỤNG TOÁN RỜI RẠC TRONG

GIẢI TOÁN TRUNG HỌC PHỔ THÔNG

Chuyên ngà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, 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: TS. TRỊNH ĐÀO CHIẾN

Phản biện 1: TS. CAO VĂN NUÔI

Phản biện 2: TS. PHẠM HỮU KHÁNH

Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Phương pháp Toán sơ cấp họp tại Đại học Đà Nẵng vào

ngày 18-19 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 các đề thi chọn học sinh giỏi ở một số nước và Olympic

Toán quốc tế thường có một số bài toán bất quy tắc, không mẫu mực

và hầu như khó có một phương pháp nào quen thuộc để giải được.

Đa số bài toán này đều được đặc biệt hóa rồi tổng hợp thêm từ những

kết quả cổ điển và cơ bản của một số lý thuyết chuyên ngành liên

quan, chẳng hạn như Lý thuyết Tổ hợp, Lý thuyết Đồ thị hữu hạn, ...

Dưới góc độ phổ thông, người ta gọi chung các dạng toán này là

Toán rời rạc (hay còn gọi là Toán tổ hợp). Chúng có khi được sơ cấp

hóa từ một kết quả nào đó của toán hiện đại, với một lời giải cũng

hoàn toàn sơ cấp. Cái khó của chúng ta là, làm thế nào để phát hiện

ra những “cái gốc” đó.

Luận văn đề cập đến một phần nhỏ của lớp các kết quả này, đó là

Định lý Hall, Định lý Turan, Định lý Pick, lưới điểm nguyên và tìm

tòi những ứng dụng của chúng để giải hoặc sáng tác một số bài toán

ở phổ thông, đặc biệt đối với hệ chuyên Toán. Đây là 3 định lý

thường ẩn sau rất nhiều bài toán khó trong các đề thi chọn học sinh

giỏi và các đề thi Olympic Toán.

Do đó, việc nghiên cứu của luận văn là cần thiết, có ý nghĩa khoa

học, mang tính thực tiễn và phù hợp với chuyên ngành Phương pháp

toán sơ cấp.

2

2. Mục tiêu và nhiệm vụ nghiên cứu

Đề cập đến việc ứng dụng một số kết quả của Toán rời rạc trong

giải toán Trung học phổ thông, đặc biệt đối với hệ chuyên Toán.

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

Đối tượng nghiên cứu là Định lý Hall, Định lý Turan, Định lý Pick,

lưới điểm nguyên và những ứng dụng của chúng.

Phạm vi nghiên cứu thuộc chuyên ngành Phương pháp toán sơ cấp.

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

Từ các tài liệu sưu tầm được, luận văn sẽ đề cập đến Định lý Hall,

Định lý Turan, Định lý Pick, lưới điểm nguyên và tìm tòi những ứng

dụng của chúng để giải hoặc sáng tác một số bài toán ở phổ thông,

đặc biệt đối với hệ chuyên Toán.

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

Đề tài góp phần nghiên cứu phương pháp giải các bài toán rời rạc

phù hợp với chuyên ngành Phương pháp Toán sơ cấp.

Sau khi bảo vệ được sự góp ý của các thầy cô trong hội đồng, luận

văn có thể dùng làm tài liệu tham khảo cho sinh viên, giáo viên, học

sinh phổ thông và những ai quan tâm đến lĩnh vực này.

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

Luận văn được chia thành ba chương:

3

Chƣơng 1. Định lý Hall

Định lý Hall cho một điều kiện cần và đủ để một họ tập hợp có

hệ đại diện phân biệt. Định lý Hall là một trong những cái gốc của

một số bài toán rời rạc, là đề thi chọn học sinh giỏi của một số nước

trên thế giới, trong đó có Việt nam.

Chƣơng 2. Định lý Turan

Định lý Turan là một dạng tổng quát hóa của Định lý Mantel về

một tính chất tối ưu đặc trưng của đồ thị. Nó đề cập đến một kết quả

về đồ thị nói chung và đồ thị lưỡng phân nói riêng.

Chƣơng 3. Định lí Pick và lƣới điểm nguyên

Định lý Pick là một định lý cổ điển và cơ bản, cho ta công thức tính

diện tích một tam giác nguyên thông qua số các điểm nguyên nằm

trên và bên trong tam giác đó.

Kết luận

Nêu tóm tắt những kết quả mà luận văn đạt được.

Tài liệu tham khảo

4

CHƢƠNG 1

ĐỊNH LÝ HALL

Trong chương này, luận văn sẽ tập trung tìm hiểu nội dung định lý

Hall và một số hệ quả của định lý. Từ đó áp dụng Định lý Hall để

giải một số bài toán trong chương trình toán Trung học phổ thông,

đặc biệt đối với hệ Chuyên toán.

1.1. ĐỊNH LÝ HALL

Định lý 1.1. ( Định lý Hall )

Gọi

, 1,2,..., A i n i



là tập hợp các cô gái mà chàng trai thứ

i

quen. Khi đó với mọi

i i n 1 2 ,i ,..., 1,2,..., k  

thỏa mãn

1 2

...

k

A A A k i i i 

(Điều kiện Hall) khi và chỉ khi tồn tại

a a a A A A 1 2 1 2 , ,..., ...

n n    

sao cho

i j a a 

với

i j  .

Đây cũng là nội dung của Định lý Hall (Định lý này được phát biểu

bởi Philip Hall năm 1935 và nó được biết đến đầy đủ với chứng

minh và các kết quả của Marshal Hall năm 1948) còn gọi là Định lý

đám cưới.

Một bộ

a a a 1 2 , ,...,

n 

như vậy được gọi là một hệ đại diện phân

biệt cho hệ tập hợp

1 2 , ,..., A A An

phần tử

a A i i 

gọi là đại diện của

5

Ai

. Như vậy nếu hệ tập hợp

A A A 1 2 , ,...,

n 

thỏa mãn Điều kiện Hall

thì tồn tại một SDR cho hệ đó và điều ngược lại nếu một hệ có

SDR

thì nó thỏa mãn Điều kiện Hall. Một

SDR

nếu có nói chung là không

duy nhất.

Cho

 ijn

A a 

, kí hiệu

1 1 2 2      

...

n

n n

S

perA a a a   



  .

Xét họ các tập

1 2 , ,..., A A An

là các tập con của

1,2,..., n

. Ma trận

liên thuộc của hệ này là

A a   ij

được xác định như sau:

1,

0,

j

ij

j

i A

a

i A

 

 

  

Rõ ràng

perA

chính bằng số

SDR

của họ

1 2 , ,..., A A An

do

1 1 2 2      

...

n n

a a a

  

bằng 1 khi và chỉ khi

  i  i A 

với mọi

i

tức là

   1 , 2 ,...,    n

là

SDR

của

1 2 , ,..., A A An

.

Bổ đề 1.1. Cho

1 2 A A A n , ,..., , 1 n 

là tập con của tập

X

. Giả

sử

 

1

1

n

i

i

a





là

SDR

của

 

1

1

n

i

i

A





. Với

J n 1,2,..., 

có chứa phần

tử

n

thì có đúng

1 j J j A J   

cách chọn phần tử

a X 

để hợp

với

1 2 1 , ,..., a a an

và sắp lại để tạo thành một

SDR a a a 1 2

  

, ,...,

n 

của

  1

n

i

i

A



, với

i a



đại diện cho

Ai

, i J  .

6

Định lý 1.2. Xét hệ   1

n

i

i

A



các tập con của tập

X

. Nếu như:

i/

A m i

 , i n 1,2, ,

ii/ Mỗi phần tử của

X

có mặt đúng

m

lần trong

  1

n

i

i

A



thế

thì hệ trên có một

SDR .

Định lý 1.3. Xét hệ   1

n

i

i

A



thỏa mãn Điều kiện Hall. Với

m A A A  min , , ,  1 2 n 

thế thì số

SDR

tối thiểu của hệ này là

 min , m n

m . (Ở đây ta sử dụng kí hiệu chỉnh hợp

   1 1    k

n n n n k    

) .

1.2. MỘT SỐ HỆ QUẢ CỦA ĐỊNH LÝ HALL

Một số kết quả trong phần này có thể được xem như các hệ quả của

Định lý Hall.

Trước hết, ta hãy đề cập đến khái niệm ma trận ngẫu nhiên kép.

Ma trận ngẫu nhiên kép là ma trận vuông với các số hạng không

âm sao cho tổng các số hạng trên mỗi hàng và tổng các số hạng trên

mỗi cột đều bằng 1.

Ma trận thế là ma trận nhận được bằng cách hoán vị các dòng của

ma trận đơn vị. Đối với ma trận cấp

n

, nếu như đánh số các dòng

của ma trận đơn vị thì một ma trận thế nhận được bằng cách hoán đổi

các dòng sẽ tương ứng với một phép thế cấp

n

. Do đó số các ma trận

thế bằng

n !.

7

Ta có Định lý sau đây

Định lý 1.4. (Định lý Birkhoff – Von Neumann)

Một ma trận là ngẫu nhiên kép nếu và chỉ nếu nó được biểu diễn

qua một tổ hợp lồi tuyến tính các ma trận thế. Có nghĩa là

X n

khi và chỉ khi tồn tại biểu diễn

n

S

X I 

 

, với

I

là ma trận

thế tương ứng với phép thế



và

1

n

S



 .

Định lý 1.5. Ta có kết quả sau

L n n n     ! 1 ! 2!1!  

Định lý 1.6. (Van der Waerden) Nếu ma trận

A

ngẫu nhiên kép,

thế thì

!

er

n

n

p A

n



, đẳng thức xảy ra khi và chỉ khi mỗi số hạng của

A

đều bằng

1

n

.

Định lý 1.7. Nếu

1 2 , , , A A An

là tập con của

1,2, ,n

và thỏa

mãn :

i/

A m i



ii/ Mỗi phần tử của

n

chứa trong đúng

m

tập hợp của

1 2 , , , A A An

Khi đó số

SDR

của hệ

1 2 , , , A A An

tối thiểu là

!

n

n

n m

n

.

8

1.3. ÁP DỤNG ĐỊNH LÝ HALL TRONG GIẢI TOÁN

Bài toán 1.1. Có 1000 hộp bi, mỗi hộp chứa đúng 10 viên bi. Biết

rằng không có 11 viên bi nào cùng màu. Chứng minh rằng có thể lấy

ra từ mỗi hộp một viên bi sao cho tất cả 1000 viên bi lấy ra đều có

màu khác nhau.

Lời giải.

Ta cần chứng minh, với

k

hộp bất kì

1 k n

thì số màu các

viên bi trong

k

hộp đó phải lớn hơn hoặc bằng

k

màu.

Thật vậy, giả sử tồn tại

0

k

hộp

1  k n 0 

nào đó mà số màu

trong

0 10k

viên bi đó bằng

k0 1.

Vì không có 11 viên bi nào cùng màu nên số viên bi cùng màu tối

đa là 10. Tuy nhiên chỉ có

0

k 1

màu trong

0

k

hộp, suy ra số viên bi

tối đa trong

0

k

hộp là

10 1 k0  

viên bi (mâu thuẫn).

Do đó theo Định lý Hall thì ta có điều phải chứng minh. □

Bài toán 1.2. Cho bảng ô vuông

n n . Trong mỗi ô vuông con của

bảng có điền một số thực không âm sao cho tổng các số nằm trên

mỗi hàng, mỗi cột bất kì trên bảng là 1. Chứng minh rằng ta có thể

chọn ra

n

ô vuông con không có hai ô nào cùng hàng hay cột mà

trong mỗi ô đó đã được điền một số thực dương.

Lời giải.

Ta xét quan hệ: Hàng

i

và cột

j

là kề nhau nếu ô giao giữa hàng

i

và cột

j

được điền một số thực dương.

9

Ta cần chứng minh, với

k

hàng bất kì

1 k n

thì quan hệ với ít

nhất

k

cột.

Thật vậy, giả sử

k

hàng nào đó

1 k n

quan hệ chỉ với

m k  1

cột.

Xét bảng hình chữ nhật

k m .

Ta có tổng các số trên mỗi hàng bằng 1, suy ra tổng các số của

bảng bằng

k .

Mặt khác, tổng các số trên mỗi cột bằng 1, suy ra tổng các số của

bảng bằng

m k  1 . Điều này mâu thuẫn giả thiết.

Do đó theo Định lý Hall, ta có điều phải chứng minh. □

Bài toán 1.3. Cho

2n

đại biểu đến từ

n

quốc gia, mỗi quốc gia có

đúng 2 đại biểu. Biết rằng họ ngồi trên một bàn tròn. Chứng minh

rằng ta có thể chia họ thành hai nhóm, mỗi nhóm gồm

n

đại biểu

đến từ

n

quốc gia mà không có 3 người nào ngồi cùng nhau liên

tiếp.

Lời giải.

Ta đánh số

2n

người đó theo thứ tự theo chiều quay của kim đồng

hồ. Sau đó chia họ thành

n

cặp

1,2 , 3,4 ,..., 2 1,2 .     n n  

Bây giờ ta chứng minh có thể lấy từ mỗi cặp một người sao cho

n

người được lấy ra đến từ

n

quốc gia khác nhau.

Thật vậy ta có mỗi cặp gồm 2 người và mỗi quốc gia có 2 đại biểu

cho nên theo bài toán 1.1 ta có thể chọn ra từ mỗi cặp một người sao

cho

n

người đó đến từ

n

quốc gia khác nhau.