Header Page 1 of 145.
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG


BÙI NGUYÊN SƠN

ÁP DỤNG PHƢƠNG PHÁP PHÂN HOẠCH
ĐỂ 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 2016

Footer Page 1 of 145.


Header Page 2 of 145.
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. Trương Công Quỳnh.
Phản biện 2: TS. Hoàng Quang Tuyến.

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 chuyên ngành Phương pháp Toán sơ cấp

Trong lý thuyết về phân hoạch tập hợp, việc phân hoạch trên
những tập rời rạc, đặc biệt trên tập số nguyên đóng một vai trò quan
trọng. Nhiều kết quả cổ điển xuất sắc đã ra đời từ lý thuyết này.
Những kết quả ấy còn độc đáo ở chỗ việc chứng minh chúng nhiều
khi chủ yếu chỉ sử dụng một số tính chất cơ bản của Số học cùng với
những suy luận logic, mà không phải áp dụng những công cụ mạnh
chẳng hạn của Giải tích và Đại số.
Có thể xem các bài toán về phân hoạch tập hợp như là một bộ
phận của Toán Rời rạc, chủ yếu được nghiên cứu ở bậc Đại học và

Footer Page 3 of 145.


Header Page 4 of 145.

2

Sau đại học, chưa được giới thiệu một cách bài bản trong chương
trình Toán phổ thông, đặc biệt ở hệ Chuyên Toán.
Một cách hình thức, có thể chia những bài toán này theo 2
dạng:
- Dạng toán yêu cầu nêu phân hoạch của tập hợp. Đó là các
bài toán dạng “hiện”, mà phân hoạch tập hợp là yêu cầu trong đề bài.
Chẳng hạn bài toán sau đây:
“Giả sử c là số hữu tỉ dương và khác 1 . Chứng minh rằng có thể
phân hoạch tập các số nguyên dương thành hai tập khác nhau A và

B sao cho

x


Header Page 5 of 145.

3

ích cho học sinh, sinh viên, giáo viên phổ thông, đặc biệt đối với hệ
Chuyên Toán.
2. Mục tiêu nghiên cứu
Luận văn đề cập đến lý thuyết và một số áp dụng của phương
pháp phân hoạch tập hợp trong việc giải một số bài toán khó ở phổ
thông, đặc biệt đối với bài toán Số học.
Luận văn có thể là một tài liệu tham khảo hữu ích cho học
sinh, sinh viên, giáo viên phổ thông, đặc biệt đối với hệ Chuyên
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.
3. Đối tượng và phạm vi nghiên cứu
3.1. Đối tượng nghiên cứu
Phương pháp phân hoạch trên tập hợp nào đó nói chung và trên
tập số nguyên dương nói riêng.
3.2. Phạm vi nghiên cứu
Thuộc chuyên ngành Phương pháp toán sơ cấp. Luận văn
không quá đi sâu vào lý thuyết phân hoạch mà sơ cấp hóa nó, áp
dụng phương pháp phân hoạch để giải một số bài toán khó của toán
phổ thông.

Footer Page 5 of 145.




5

loại I, số Stirling loại II, Bài toán chia kẹo Euler, thuật toán “ba lô”,
thuật toán “tham ăn”…
Chương 2. Phân hoạch nguyên
Là phân hoạch trên tập số nguyên, với một tập hợp xác định
gồm các số nguyên nào đó, các bài toán cần phân hoạch tập hợp này
thành một số tập hợp con rời nhau sao cho chúng thỏa mãn một tính
chất nào đó là những dạng toán quen thuộc và quan trọng. Chẳng
hạn, cần phân hoạch một tập hợp các số nguyên xác định thành hai
tập hợp con rời nhau sao cho tổng các số trong hai tập hợp con đó
bằng nhau. Đây là những dạng toán thường là rất khó.
Chương này đề cập đến việc phân hoạch trên tập số nguyên,
giải quyết một số bài toán khó ở cả dạng “ẩn” và “hiện”.
Chương 3. Phân hoạch tập hợp
Chương này đề cập đến phương pháp phân hoạch và số cách
phân hoạch trên tập hợp nào đó nói chung thỏa mãn một vài tính chất
cụ thể. Đó có thể là bài toán nêu rõ yêu cầu phân hoạch ( dạng “
hiện”) chẳng hạn bài toán:
“Tìm số các phân hoạch tập hợp 1, 2,..., n thành 3 tập con
A1 , A2 , A3 (các tập này có thể rỗng) sao cho các điều kiện sau thỏa

mãn.
1) Sau khi sắp xếp các phần tử của A1 , A2 , A3 theo thứ tự tăng
dần, thì 2 phần tử liên tiếp luôn có tính chẵn, lẻ khác nhau.

Footer Page 7 of 145.



tập hợp và một số lý thuyết quan trọng liên quan đến phân hoạch và
được dùng nhiều trong chứng minh ở các chương sau.
1.1. SỐ STIRLING LOẠI I VÀ LOẠI II
1.1.1. Chu trình của hoán vị
Trong các bài toán về phân hoạch tập hợp, ta không thể nào
không nhắc đến số Stirling. Đây là cơ sở để xây dựng các bài toán
đếm một cách khá vững chắc, đồng thời kết hợp với các công cụ đại
số và giải tích khác sẽ giúp xây dựng được nhiều lý thuyết khác.
Chu trình trong một hoán vị a1 , a2 , a3 ,..., an
của các số
1, 2, 3,..., n , là một tập con của các số này mà chúng đổi vị trí cho
nhau tạo thành một vòng. Ta xét hoán vị sau
123456789 
142357698 ,
f
trong hoán vị này,
f  2   4, f  4   3, f  3  2

nên có thể nói  2; 3; 4  tạo thành một chu trình. Các số không đổi
qua phép hoán vị được coi là một chu trình riêng biệt và do đó, trong
hoán vị trên có tất cả 5 chu trình:
1 ,  4; 2; 3 ,  5  ,  7; 6  ,  9; 8  .
1.1.2. Số Stirling loại I
Số hoán vị của n phần tử mà có đúng k chu trình, đặt là
s  n, k  . Công thức truy hồi

Footer Page 9 of 145.


Header Page 10 of 145.


khi n  0;
khi n  1;
khi n  1.


Header Page 11 of 145.

9

CHƯƠNG 2
PHÂN HOẠCH NGUYÊN
Chương này đề cập đến việc phân hoạch trên tập số nguyên
đồng thời giải quyết một số bài toán khó ở cả dạng “ẩn” và “hiện”.
2.1. PHÂN HOẠCH NGUYÊN DẠNG “ HIỆN”
2.1.1. Phân hoạch tập các số tự nhiên thành 2 tập hợp có
tổng các phần tử bằng nhau
Bổ đề 2.1. Từ n số nguyên cho trước, luôn chọn được một vài
số để tổng của chúng chia hết cho n .
Định lí 2.1. (P. Erdos, A. Ginzburg, A. Ziv) Từ 2n  1 số
nguyên dương cho trước, luôn chọn được n số sao cho tổng của
chúng chia hết cho n .
Bổ đề 2.2. Nếu trong n  1 số nguyên dương cho trước không
tồn tại một nhóm số có tổng chia hết cho n thì n  1 số đó có cùng số
dư khi chia cho n .
Bài toán 2.1. Tồn tại hay không giá trị K nhỏ nhất để với mọi
số nguyên dương k  K , tập hợp A luôn có thể phân hoạch thành 2
tập con có tổng các phần tử mỗi tập bằng N?

Footer Page 11 of 145.

Footer Page 12 of 145.


Header Page 13 of 145.

11

N 
Định lý 2.3. Cho A  2 N , k  với N  2 và k     2 . Gọi H
2

là tập con hoàn chỉnh có số phần tử lớn nhất của A. Nếu H biểu diễn
được đến 3 thì A phân hoạch được thành 2 tập có tổng các phần tử
bằng N.
N 
Định lý 2.4. Cho A  2 N , k  với N  2, k     2 và
2
(a1 , a2 , a3 ) (1; 1; 1), (1; 1; 2),(1; 1; 3), (1; 2; 2), (1; 2; 3) .

Khi đó, tập hợp A có thể phân hoạch được thành hai tập con có tổng
các phần tử bằng N.
Bổ

đề

2.8.

Cho tập

A 2N , k 


phần tử bằng N.
Hệ quả 2.1. Cho tập A  2 N , k  với N  6m  2, m  1 và
k  4m  3 . Tập A  2 N , k  có thể phân hoạch được thành 2 tập con

có tổng các phần tử bằng nhau.
Hệ quả 2.2. Cho tập A  2 N , k  với N  6m  4; k  4m  4 .
Tập A  2 N , k  có thể phân hoạch được thành 2 tập con có tổng các
phần tử bằng nhau.
Hệ quả 2.3. Cho tập A  2 N , k  với N  6m; k  3m  2 . Tập
A  2 N , k  có thể phân hoạch được thành 2 tập con có tổng các phần

tử bằng nhau.
Định lý 2.7. Cho một tập A có k phần tử là số nguyên dương
không lớn hơn N và tổng của các số này bằng 2N. Khi đó, tồn tại giá

Footer Page 14 of 145.


Header Page 15 of 145.

13

trị K nhỏ nhất để với mọi k  K , tập A luôn phân hoạch được thành
2 tập con có tổng các phần tử mỗi tập bằng N, trong đó:


K= N+1 khi N lẻ



thì A  B  , A  B 

Footer Page 15 of 145.

*

.


Header Page 16 of 145.

14

2.1.4. Các bài toán chọn lọc khác
Bài toán 2.1. Chứng minh rằng nếu gọi f  r , n  là số phân
hoạch của n thành dạng b0  b1  b2  ...  bs với 0  i  s  1 và
bi  rbi 1 , r là một số nguyên dương nào đó thì tồn tại số nguyên

dương n mà f  r , n  khác số phân hoạch của n thành các phần từ
một tập hợp các số nguyên bất kỳ, trừ khi r  1 .
Bài toán 2.2. Gọi f(n), g(n) lần lượt là số phân hoạch của n
thành số chẵn phần và số lẻ phần. Chứng minh rằng
f  n   g  n    1

m

1
nếu n  m  3m  1 và bằng f  n   g  n 
2


số tự nhiên thành 100 tập khác rỗng sao cho với bất kỳ 3 số tự nhiên
a, b, c thỏa mãn a  99b  c thì 2 trong số chúng thuộc cùng một tập
hợp.
Bài toán 2.6. Giả sử c là số hữu tỷ dương và khác 1. Chứng
minh rằng có thể phân hoạch tập các số nguyên dương thành 2 tập
khác nhau A, B sao cho

x
 c với mọi x, y cùng nằm trong A hoặc
y

cùng nằm trong B.
Bài toán 2.7. Có bao nhiêu cách chia 15 đồ vật đôi một khác
nhau cho 5 người, sao cho trong số đó có đúng 2 người không nhận
được đồ vật nào?
2.2. PHÂN HOẠCH NGUYÊN DẠNG “ ẨN ”
Bài toán 2.8. Cho bảng ô vuông  aij  với i  1, n, j  1, n và
điền các số từ 1 đến n2 theo thứ tự từ trái sang phải, từ trên xuống
dưới. Người ta viết ghép các hàng của bảng này theo thứ tự từ trái

Footer Page 17 of 145.


Header Page 18 of 145.

16

sang phải được một dãy X. Tiếp tục ghép các cột của bảng này thành
dạng hàng ngang cũng từ trái sang phải được dãy Y. Một phép biến
đổi cho phép đổi chỗ 2 số cho nhau. Hỏi ít nhất cần bao nhiêu phép

17



0 x , y  n ,
x  2 y n

Cxx y  Fn 1 .

Bài toán 2.12. Cho số nguyên dương k. Dãy số

 xn  , n  1,

2, 3,... được xác định như sau:

(i) x1  1 .
(ii) Với mỗi số nguyên dương n  1 thì xn 1 là số nguyên
dương bé nhất không thuộc tập

 x1; x2 ; x3 ;...; xn ; x1  k ; x2  2k ; x3  3k ;...; xn  nk .
Chứng minh rằng tồn tại số thực a sao cho xn   na  với mọi
n

*

.

Bài toán 2.13. Xét dãy các số 3, 6, 7, 9, 10, 11, 12,... là có
thể biểu diễn thành tổng của ít nhất hai số nguyên dương liên tiếp.
Gọi f  n  là số hạng thứ n của dãy. Chứng minh rằng

 Ánh xạ bất kỳ: việc phân chia là tùy ý, không có ràng
buộc gì (có thể 1 hộp có nhiều bóng mà cũng có thể
có hộp không có quả nào, nhưng tất nhiên là 1 quả
bóng thì chỉ có thể chia vào 1 hộp).
 Đơn ánh: mỗi hộp chỉ chứa nhiều nhất 1 quả bóng.
Toàn ánh: mỗi hộp chứa ít nhất 1 quả bóng. Ở đây không xét
song ánh vì khi đó mỗi hộp chỉ chứa đúng 1 quả bóng và bài toán
không còn nhiều ý nghĩa. Quy ước Cba  0 với b  a .

Footer Page 20 of 145.


Header Page 21 of 145.

19

Trường hợp 1: Các quả bóng đôi một khác nhau và các hộp
đôi một khác nhau.
 Ánh xạ bất kỳ: mỗi quả bóng đều có thể xếp vào một
hộp tùy ý. Kết quả là k n .


Đơn ánh: Nếu n  k thì không có cách xếp thỏa mãn
vì theo Nguyên lý Dirichlet, sẽ có 1 hộp chứa nhiều
hơn 1 quả bóng, kết quả là 0. Nếu n  k , ta thấy quả
bóng đầu tiên có thể đặt vào k hộp, quả thứ 2 có thể
đặt vào k  1 hộp còn lại và cứ thế. Kết quả là
k  k  1 k  2  ... k  n  .

 Toàn ánh: Vấn đề tương tự như việc phân hoạch tập

hoạch tập hợp 1, 2, 3,..., n thành không quá k tập
con. Kết quả là
S  n, 1  S  n, 2   ...  S  n, k  .

 Đơn ánh: Tương tự trên, nếu n  k thì kết quả là 0.
Nếu n  k thì rõ ràng chỉ có 1 cách xếp. Kết quả là 1.
 Toàn ánh: Hộp nào cũng phải có bóng nên nó đúng với
bài toán tính số Stirling loại II. Kết quả là S  n, k  .
Trường hợp 4: Các quả bóng đều giống nhau và các hộp đều
giống nhau.
 Ánh xạ bất kỳ: Tương ứng với bài toán phan hoạch số
n thành không quá k thành phần. Kết quả là
p1  n   p2  n   ...  pk  n  .

Footer Page 22 of 145.


Header Page 23 of 145.

21

 Đơn ánh: Tương tự trên, nếu n  k thì kết quả là 0.
Nếu n  k thì rõ ràng chỉ có 1 cách xếp. Kết quả là 1.


Toàn ánh: Tương ứng với bài toán phân hoạch số n
thành đúng k thành phần. Kết quả là pk  n  .

3.1.2. Các bài toán chọn lọc
Bài toán 3.1. Tìm số các phân hoạch tập hợp 1, 2,..., n

Bài toán 3.5. Ở một ngôi làng nọ, mỗi người hoặc luôn nói
thật hoặc luôn nói dối. Xét 5 người trong làng xếp thành 1 hàng và 1
người khách đến thăm làng hỏi mỗi người trong họ rằng có bao
nhiêu người nói thật trong hàng. Mỗi người sẽ cho khách một số từ 0
đến 5. Hỏi có bao nhiêu multiset các câu trả lời mà người khách có
thể nhận được? (multiset là tập mà mỗi phần tử có thể xuất hiện
nhiều hơn 1 lần).
Bài toán 3.6. Cho A là tập hợp gồm 16 số nguyên dương đầu
tiên. Hãy tìm số nguyên dương k nhỏ nhất có tính chất: trong mỗi tập
con có k phần tử của tập hợp A đều tồn tại hai số phân biệt a và b
sao cho a 2  b 2 là một số nguyên tố.
Bài toán 3.7. Cho p và q là hai số nguyên tố lẻ. Chứng minh
p 1
2

q 1

 iq  2  jp   p  1  q  1 

     q    2  2  .


i 1  p 
j 1 
 

Footer Page 24 of 145.


Header Page 25 of 145.

tử

của

S

sao

cho

từ

các

quan

Ai  Aj  , Ai  Ak  , Aj  Ak  

ta

suy

ra

Ai  Aj  Ak   . Chứng minh rằng m  2n1  1 .

Footer Page 25 of 145.

hệ
được