jupiter_is_coming
New Member
Download Luận văn Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp
Mục lục
Trang
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Chương 1 Các kiến thức cơ bản 1
1.1 Nguyên lý Dirichlet cơ bản . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Nguyên lý Dirichlet mở rộng . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Nguyên lí Dirichlet dạng tập hợp . . . . . . . . . . . . . . . . . . . . 2
1.4 Nguyên lí Dirichlet dạng tập hợp mở rộng . . . . . . . . . . . . . . . 2
Chương 2 Ứng dụng nguyên lý Dirichlet vào bài toán hình học tổ hợp 4
Chương 3 Ứng dụng nguyên lí Dirichlet vào số học 25
Chương 4 Ứng dụng nguyên lí Dirichlet vào các bài toán khác 42
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
cùng màu với điểm A. Các lập luận đó thực chất chỉ ra rằng nếu AA1 =
√
3, thì
các điểm A và A1 được tô cùng màu. Do đó tất cả các điểm nằm trên đường tròn
tâm A bán kính
√
3 có cùng một màu. Rõ ràng trên đường tròn đó luôn tìm được
hai điểm có khoảng cách giữa chúng bằng 1.
Ta được mâu thuẫn, vậy luôn tìm được hai điểm cùng màu có khoảng cách giữa
chúng bằng 1.
Ví dụ 2.20 Cho 11 điểm khác nhau trong hình cầu thể tích V .Chứng minh rằng
qua tâm của hình cầu có thể dựng hai mặt phẳng sao cho chúng cắt hình cầu thành
một "miếng" với thể tích
V
6
, mà phần trong của nó không chứa trong phần trong
bất cứ một điểm nào đã cho.
Lời giải:
Chia hình cầu thành hai bán cầu bằng một mặt phẳng đi qua tâm và hai điểm
từ các điểm đã cho. Một bán cầu chứa trong phần trong nhiều nhất là 4 điểm từ
các điểm còn lại. Chia nửa hình cầu bằng hai mặt phẳng, mà mỗi mặt phẳng đi
qua tâm hình cầu và hai điểm trong 4 điểm còn lại. Như vậy nửa hình cầu chia làm
ba "miếng"không chứa điểm nào bên trong, ít nhất thể tích của một miếng lớn hơn
1
3
thể tích của bán hình cầu.
Ví dụ 2.21 Trong không gian cho 37 "điểm nguyên" và không có ba điểm nào
thẳng hàng. Chứng minh rằng chọn được từ đó ba điểm để trọng tâm của tam giác
lập thành từ ba điểm này cũng là điểm nguyên.
Lời giải:
Mỗi "điểm nguyên" (x; y; z) trong không gian cho tương ứng với bộ ba:
(g(x); g(y); g(z)), ở đây g(x); g(y); g(z)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 20
tương ứng là các số dư trong phép chia cho 3 của x, y, z.
Vì g(x) ∈ {0, 1, 2}, nên theo nguyên lí Dirichlet, tồn tại ít nhất 13 điểm (trong
số 37 điểm) có cùng giá trị g(x).Lấy 13 điểm trong số các điểm này. Giả sử chúng
là (x1; y1; z1), . . . , (x13; y13; z13) và ta có g(x1) = g(x2) = · · · = g(x13).
Để ý rằng g(yi) ∈ {0, 1, 2} , ∀i = 1, 13, nên lại theo nguyên lí Dirichlet, tồn tại ít
nhất 5 điểm (trong số 13 điểm đã nêu trên) có cùng giá trị g(y). Lấy 5 điểm trong
số các điểm này.
Giả sử chúng là:
(x1; y1; z1), . . . , (x5; y5; z5),
ở đây: {
g(x1) = g(x2) = · · · = g(x5)
g(y1) = g(y2) = · · · = g(y5)
Lại có g(z1) ∈ {0, 1, 2} , ∀i = 1, 5, chỉ xảy ra hai trường hợp sau :
1. Tồn tại ba điểm trong chúng, giả sử g(z1) = 0; g(z2) = 1; g(z3) = 2 thế thì ba
điểm (x1; y1; z1); (x2; y2; z2); (x3; y3; z3) đều có:
g(x1) + g(x2) + g(x3)
...3
g(y1) + g(y2) + g(y3)
...3
g(z1) + g(z2) + g(z3)
...3
Vì thế tam giác với ba đỉnh này rõ ràng có trọng tâm là "điểm nguyên".
2. Nếu năm giá trị g(zi), ∀i = 1, 5 chỉ nhận không qua hai trong ba giá trị {0, 1, 2}.
Khi đó theo nguyên lí Dirichlet tồn tại ít nhất ba điểm có cùng giá trị g(z).
Bây giờ ta thu được ba điểm (x˜1; y˜1; z˜1), (2˜; y˜2; z˜2), (x˜3; y˜3; z˜3) mà:
g(x˜1) = g(x˜2) = g(x˜3)
g(y˜1) = g(y˜2) = g(y˜3)
g(z˜1) = g(z˜2) = g(z˜3)
Tam giác thu được có trọng tâm là "điểm nguyên".
Ví dụ 2.22 Cho đa giác đều 100 cạnh nội tiếp trong đường tròn (C). Mỗi đỉnh
được gán một trong các số 1, 2, 3, . . . , 49. Chứng minh rằng trên (C) tồn tại hai
cung AB và CD với các tính chất sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 21
1. Các điểm A,B,C,D là các đỉnh của đa giác đều đã cho.
2. Các dây cung AB và CD song song với nhau.
3. Nếu A,B,C,D được gắn tương ứng với các số a, b, c, d thì a + b = c+ d.
Lời giải:
A
B
C
D
Hình 2.14
Vì đa giác đều 100 cạnh nội tiếp trong (C), nên có đúng 50 đường kính khác
nhau mà các đầu mút của các đường kính này đều là các đỉnh của đa giác đều 100
cạnh cho trước. Giả sử AB là một trong các đường kính ấy và giả sử A tương ứng
với số a,B tương ứng với số b. Bây giờ ta gán cho đường kính AB số |a− b|. Do
a, b ∈ {1, 2, 3, . . . , 49} nên dễ thấy: 0 ≤ |a− b| ≤ 48.
Như vậy mỗi một trong 50 đường kính vừa xét tương ứng với một trong các số
1, 2, . . . , 48. Theo nguyên lí Dirichlet có ít nhất hai đường kính (trong số 50 đường
kính) được đặt tương ứng với cùng một số. Không giảm tổng quát có thể cho đó là
đường kính AC và BD. Cũng không giảm tổng quát có thể đánh giá là các đỉnh A,B,C,D
tương ứng với các số a, b, c, d, trong đó c ≤ a và b ≤ d (Nếu không phải như thế thì
chỉ việc đổi tên các đầu mút của đường kính).
Theo giả thiết thì đường kính AC ứng với số a− c, còn đường kính BD ứng với
số d− b.
Từ: a− c = d− b ⇒ a+ b = c + d.
Rõ ràng ABCD là hình chữ nhật, do đó AB//CD.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 22
Ví dụ 2.23 Cho dãy vô hạn các số tự nhiên u1, u2, . . . được xác định theo công
thức truy hồi sau: {
u1 = 3
un+1 = (n+ 1)un − n + 1, n = 1, 2, . . .
Giả sử n là số tự nhiên bất kì và tập M gồm un điểm sao cho không có ba điểm
nào thẳng hàng. Mỗi đoạn thẳng nối hai điểm khác nhau trong M được tô bằng
một trong n màu cho trước. Chứng minh rằng tồn tại ba điểm trong M là đỉnh của
một tam giác cùng màu.
Lời giải:
Ta chứng minh bằng quy nạp theo n.
• Với n = 1, ta có u1 = 3 và kết luận của bài toán hiển nhiên đúng (vì ở đây
chỉ có 1 màu do n = 1).
Với n = 2, ta có u2 = 2u1 − 1 + 1 = 6. Ta có bài toán với 6 điểm và dùng 2
màu. Bài toán này đã được giải (xem ví dụ 2.1). Vậy kết luận cũng đúng khi
n = 2.
• Giả sử kết luận của bài toán đúng với n, tức là nếu tập M gồm un điểm sao
cho không có ba điểm nào thẳng hàng và dùng n màu để tô các đoạn thẳng.
Khi đó tồn tại tam giác cùng màu.
• Xét với n + 1, tức là tập M gồm un+1 điểm bất kì (không có ba điểm nào
thẳng hàng), và dùng n+ 1 màu để tô các đoạn thẳng.
Lấy A là một trong các điểm của tập M . Điểm này có thể nối với un+1 − 1
điểm còn lại của tập M bằng un+1 − 1 đoạn thẳng bôi màu. Theo công thức
xác định dãy ta có:
un+1 − 1 = (n+ 1)un − n + 1− 1 = (n + 1)(un − 1) + 1. (2.6)
Từ (2.6) theo nguyên lí Dirichlet có ít nhất un đoạn thẳng có chung đỉnh A
được bôi màu.Giả sử AB1, AB2, . . . , ABun được bôi cùng màu và giả sử đó là
màu α, thì tam giác ABiBj cùng màu α, (α thuộc vào một trong n + 1 màu
đã cho ).
Có các khả năng sau xảy ra:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 23
1. Nếu một trong các đoạn thẳng BiBj(i 6= j, 1 ≤ i < j ≤ un) được bôi màu
α, thì tam giác ABiBj cùng màu α. Bài toán đã được giải xong trong
trường hợp n + 1.
2. Các đoạn thẳng BiBj , 1 ≤ i < j ≤ un có màu khác với α. Xét un điểm
B1, B2, . . . , Bun. Rõ ràng không có ba điểm nào trong chúng thẳng hàng.
Chúng dùng tối đa (n + 1)− 1 = n màu để tô (do không dùng màu α).
Theo giả thiết quy nạp tồn tại tam giác cùng màu.
Vậy kết luận của bài toán cũng đúng với n + 1.
Ví dụ 2.24 Trong mặt phẳng, cho tập A gồm n điểm (n ≥ 2). Một số cặp điểm
được nối với nhau bằng đoạn thẳng. Chứng minh rằng trong tập A đã cho, có ít
nhất hai điểm được nối với cùng số lượng các điểm khác thuộc A.
Lời giải:
Giả sử a ∈ A. Ta kí hiệu S(a) là số lượng các điểm của A nối với a thành đoạn
thẳng. Thí dụ trong hình vẽ bên thì:
S(a = 2), S(b) =...
Download miễn phí Luận văn Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp
Mục lục
Trang
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Chương 1 Các kiến thức cơ bản 1
1.1 Nguyên lý Dirichlet cơ bản . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Nguyên lý Dirichlet mở rộng . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Nguyên lí Dirichlet dạng tập hợp . . . . . . . . . . . . . . . . . . . . 2
1.4 Nguyên lí Dirichlet dạng tập hợp mở rộng . . . . . . . . . . . . . . . 2
Chương 2 Ứng dụng nguyên lý Dirichlet vào bài toán hình học tổ hợp 4
Chương 3 Ứng dụng nguyên lí Dirichlet vào số học 25
Chương 4 Ứng dụng nguyên lí Dirichlet vào các bài toán khác 42
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Tóm tắt nội dung:
tôcùng màu với điểm A. Các lập luận đó thực chất chỉ ra rằng nếu AA1 =
√
3, thì
các điểm A và A1 được tô cùng màu. Do đó tất cả các điểm nằm trên đường tròn
tâm A bán kính
√
3 có cùng một màu. Rõ ràng trên đường tròn đó luôn tìm được
hai điểm có khoảng cách giữa chúng bằng 1.
Ta được mâu thuẫn, vậy luôn tìm được hai điểm cùng màu có khoảng cách giữa
chúng bằng 1.
Ví dụ 2.20 Cho 11 điểm khác nhau trong hình cầu thể tích V .Chứng minh rằng
qua tâm của hình cầu có thể dựng hai mặt phẳng sao cho chúng cắt hình cầu thành
một "miếng" với thể tích
V
6
, mà phần trong của nó không chứa trong phần trong
bất cứ một điểm nào đã cho.
Lời giải:
Chia hình cầu thành hai bán cầu bằng một mặt phẳng đi qua tâm và hai điểm
từ các điểm đã cho. Một bán cầu chứa trong phần trong nhiều nhất là 4 điểm từ
các điểm còn lại. Chia nửa hình cầu bằng hai mặt phẳng, mà mỗi mặt phẳng đi
qua tâm hình cầu và hai điểm trong 4 điểm còn lại. Như vậy nửa hình cầu chia làm
ba "miếng"không chứa điểm nào bên trong, ít nhất thể tích của một miếng lớn hơn
1
3
thể tích của bán hình cầu.
Ví dụ 2.21 Trong không gian cho 37 "điểm nguyên" và không có ba điểm nào
thẳng hàng. Chứng minh rằng chọn được từ đó ba điểm để trọng tâm của tam giác
lập thành từ ba điểm này cũng là điểm nguyên.
Lời giải:
Mỗi "điểm nguyên" (x; y; z) trong không gian cho tương ứng với bộ ba:
(g(x); g(y); g(z)), ở đây g(x); g(y); g(z)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 20
tương ứng là các số dư trong phép chia cho 3 của x, y, z.
Vì g(x) ∈ {0, 1, 2}, nên theo nguyên lí Dirichlet, tồn tại ít nhất 13 điểm (trong
số 37 điểm) có cùng giá trị g(x).Lấy 13 điểm trong số các điểm này. Giả sử chúng
là (x1; y1; z1), . . . , (x13; y13; z13) và ta có g(x1) = g(x2) = · · · = g(x13).
Để ý rằng g(yi) ∈ {0, 1, 2} , ∀i = 1, 13, nên lại theo nguyên lí Dirichlet, tồn tại ít
nhất 5 điểm (trong số 13 điểm đã nêu trên) có cùng giá trị g(y). Lấy 5 điểm trong
số các điểm này.
Giả sử chúng là:
(x1; y1; z1), . . . , (x5; y5; z5),
ở đây: {
g(x1) = g(x2) = · · · = g(x5)
g(y1) = g(y2) = · · · = g(y5)
Lại có g(z1) ∈ {0, 1, 2} , ∀i = 1, 5, chỉ xảy ra hai trường hợp sau :
1. Tồn tại ba điểm trong chúng, giả sử g(z1) = 0; g(z2) = 1; g(z3) = 2 thế thì ba
điểm (x1; y1; z1); (x2; y2; z2); (x3; y3; z3) đều có:
g(x1) + g(x2) + g(x3)
...3
g(y1) + g(y2) + g(y3)
...3
g(z1) + g(z2) + g(z3)
...3
Vì thế tam giác với ba đỉnh này rõ ràng có trọng tâm là "điểm nguyên".
2. Nếu năm giá trị g(zi), ∀i = 1, 5 chỉ nhận không qua hai trong ba giá trị {0, 1, 2}.
Khi đó theo nguyên lí Dirichlet tồn tại ít nhất ba điểm có cùng giá trị g(z).
Bây giờ ta thu được ba điểm (x˜1; y˜1; z˜1), (2˜; y˜2; z˜2), (x˜3; y˜3; z˜3) mà:
g(x˜1) = g(x˜2) = g(x˜3)
g(y˜1) = g(y˜2) = g(y˜3)
g(z˜1) = g(z˜2) = g(z˜3)
Tam giác thu được có trọng tâm là "điểm nguyên".
Ví dụ 2.22 Cho đa giác đều 100 cạnh nội tiếp trong đường tròn (C). Mỗi đỉnh
được gán một trong các số 1, 2, 3, . . . , 49. Chứng minh rằng trên (C) tồn tại hai
cung AB và CD với các tính chất sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 21
1. Các điểm A,B,C,D là các đỉnh của đa giác đều đã cho.
2. Các dây cung AB và CD song song với nhau.
3. Nếu A,B,C,D được gắn tương ứng với các số a, b, c, d thì a + b = c+ d.
Lời giải:
A
B
C
D
Hình 2.14
Vì đa giác đều 100 cạnh nội tiếp trong (C), nên có đúng 50 đường kính khác
nhau mà các đầu mút của các đường kính này đều là các đỉnh của đa giác đều 100
cạnh cho trước. Giả sử AB là một trong các đường kính ấy và giả sử A tương ứng
với số a,B tương ứng với số b. Bây giờ ta gán cho đường kính AB số |a− b|. Do
a, b ∈ {1, 2, 3, . . . , 49} nên dễ thấy: 0 ≤ |a− b| ≤ 48.
Như vậy mỗi một trong 50 đường kính vừa xét tương ứng với một trong các số
1, 2, . . . , 48. Theo nguyên lí Dirichlet có ít nhất hai đường kính (trong số 50 đường
kính) được đặt tương ứng với cùng một số. Không giảm tổng quát có thể cho đó là
đường kính AC và BD. Cũng không giảm tổng quát có thể đánh giá là các đỉnh A,B,C,D
tương ứng với các số a, b, c, d, trong đó c ≤ a và b ≤ d (Nếu không phải như thế thì
chỉ việc đổi tên các đầu mút của đường kính).
Theo giả thiết thì đường kính AC ứng với số a− c, còn đường kính BD ứng với
số d− b.
Từ: a− c = d− b ⇒ a+ b = c + d.
Rõ ràng ABCD là hình chữ nhật, do đó AB//CD.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 22
Ví dụ 2.23 Cho dãy vô hạn các số tự nhiên u1, u2, . . . được xác định theo công
thức truy hồi sau: {
u1 = 3
un+1 = (n+ 1)un − n + 1, n = 1, 2, . . .
Giả sử n là số tự nhiên bất kì và tập M gồm un điểm sao cho không có ba điểm
nào thẳng hàng. Mỗi đoạn thẳng nối hai điểm khác nhau trong M được tô bằng
một trong n màu cho trước. Chứng minh rằng tồn tại ba điểm trong M là đỉnh của
một tam giác cùng màu.
Lời giải:
Ta chứng minh bằng quy nạp theo n.
• Với n = 1, ta có u1 = 3 và kết luận của bài toán hiển nhiên đúng (vì ở đây
chỉ có 1 màu do n = 1).
Với n = 2, ta có u2 = 2u1 − 1 + 1 = 6. Ta có bài toán với 6 điểm và dùng 2
màu. Bài toán này đã được giải (xem ví dụ 2.1). Vậy kết luận cũng đúng khi
n = 2.
• Giả sử kết luận của bài toán đúng với n, tức là nếu tập M gồm un điểm sao
cho không có ba điểm nào thẳng hàng và dùng n màu để tô các đoạn thẳng.
Khi đó tồn tại tam giác cùng màu.
• Xét với n + 1, tức là tập M gồm un+1 điểm bất kì (không có ba điểm nào
thẳng hàng), và dùng n+ 1 màu để tô các đoạn thẳng.
Lấy A là một trong các điểm của tập M . Điểm này có thể nối với un+1 − 1
điểm còn lại của tập M bằng un+1 − 1 đoạn thẳng bôi màu. Theo công thức
xác định dãy ta có:
un+1 − 1 = (n+ 1)un − n + 1− 1 = (n + 1)(un − 1) + 1. (2.6)
Từ (2.6) theo nguyên lí Dirichlet có ít nhất un đoạn thẳng có chung đỉnh A
được bôi màu.Giả sử AB1, AB2, . . . , ABun được bôi cùng màu và giả sử đó là
màu α, thì tam giác ABiBj cùng màu α, (α thuộc vào một trong n + 1 màu
đã cho ).
Có các khả năng sau xảy ra:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Nguyên lí Dirichlet và ứng dụng giải toán sơ cấp 23
1. Nếu một trong các đoạn thẳng BiBj(i 6= j, 1 ≤ i < j ≤ un) được bôi màu
α, thì tam giác ABiBj cùng màu α. Bài toán đã được giải xong trong
trường hợp n + 1.
2. Các đoạn thẳng BiBj , 1 ≤ i < j ≤ un có màu khác với α. Xét un điểm
B1, B2, . . . , Bun. Rõ ràng không có ba điểm nào trong chúng thẳng hàng.
Chúng dùng tối đa (n + 1)− 1 = n màu để tô (do không dùng màu α).
Theo giả thiết quy nạp tồn tại tam giác cùng màu.
Vậy kết luận của bài toán cũng đúng với n + 1.
Ví dụ 2.24 Trong mặt phẳng, cho tập A gồm n điểm (n ≥ 2). Một số cặp điểm
được nối với nhau bằng đoạn thẳng. Chứng minh rằng trong tập A đã cho, có ít
nhất hai điểm được nối với cùng số lượng các điểm khác thuộc A.
Lời giải:
Giả sử a ∈ A. Ta kí hiệu S(a) là số lượng các điểm của A nối với a thành đoạn
thẳng. Thí dụ trong hình vẽ bên thì:
S(a = 2), S(b) =...