Luận văn Thạc sĩ Khoa học: Một số bài toán số học - Tổ hợp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:98

Thêm vào BST

Báo xấu

37
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các bài toán số học tổ hợp từ lâu đóng một vai trò quan trọng trong việc rèn luyện tư duy toán học và kỹ năng giải toán. Bài toán số học tổ hợp có một số đặc điểm quan trọng mang tính khác biệt sau: Có thể giảng dạy tại các bậc, lớp khác nhau, không có khuôn mẫu nhất định cho việc giải (Không giống như việc giải phương trình, khảo sát hàm số, tính tích phân...). Do vậy đòi hỏi sự sáng tạo từ phía học sinh. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một số bài toán số học - Tổ hợp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ Trần Thanh Nhã MỘT SỐ BÀI TOÁN SỐ HỌC - TỔ HỢP LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.01.13 Người hướng dẫn khoa học GS. TSKH. HÀ HUY KHOÁI HÀ NỘI, NĂM 2013
1 Mục lục Lời mở đầu 3 Lời cảm ơn 5 1 Một số kiến thức chuẩn bị 6 1.1 Kiến thức tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.6 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.7 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.8 Khai triển nhị thức Newton . . . . . . . . . . . . . . . . . . . 8 1.2 Kiến thức số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Biểu diễn cơ số . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.4 Ước chung lớn nhất, bội chung nhỏ nhất . . . . . . . . . . . 9 1.2.5 Thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.6 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.7 Đồng dư tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.8 Thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.9 Một số định lý quan trọng . . . . . . . . . . . . . . . . . . . . 13 2 Một số bài toán Số học - Tổ hợp 14 2.1 Tính chất số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Biểu diễn số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.1.3 Thuật toán Euclid và một số bài toán liên quan đến ước chung lớn nhất . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2 Bài toán chia kẹo Euler. . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3 Bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4 Cực trị trên tập hợp rời rạc . . . . . . . . . . . . . . . . . . . . . . . 61 2.5 Số phức - Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2 3 Một số bài toán trò chơi 86 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3 Lời mở đầu Toán rời rạc đóng một vai trò quan trọng trong toán học bởi vì nó có nội dung rất phong phú và có nhiều ứng dụng trong đời sống và thực tiễn. Trong các kì thi đại học, thi học sinh giỏi quốc gia, quốc tế, các bài toán tổ hợp xuất hiện nhiều và thường có nội dung rất khó. Nhìn chung, nếu như việc phân loại bài toán nào là số học, đại số, giải tích, hình học là tương đối rõ ràng thì việc phân loại các bài toán tổ hợp khá mơ hồ. Chính vì sự đa dạng này nên việc giảng dạy và học tập chúng là một vấn đề khó khăn. Hơn nữa, trong chương trình toán phổ thông, tài liệu tham khảo về lĩnh vực tổ hợp rất ít, nên luận văn này nhằm góp một phần kiến thức nhỏ bé để hổ trợ cho việc học tập và giảng dạy, và bổ sung thêm tài liệu tham khảo về tổ hợp. Luận văn nhằm mục tiêu giới thiệu một số bài toán có thể gọi thuộc loại "số học - tổ hợp". Thực ra không có một "định nghĩa" nào cho loại bài toán này. Nên luận văn này chỉ giới hạn ở việc đưa ra một số bài toán thường gặp trong các kì thi học sinh giỏi, mà việc giải chúng đòi hỏi những phương pháp của số học và tổ hợp. Bố cục luận văn được chia thành ba chương: Chương 1 : Một số kiến thức chuẩn bị Trong chương này, chúng tôi trình bày một số kiến thức cơ bản về số học (tính chia hết, biểu diễn số, số nguyên tố, bội chung nhỏ nhất, ước chung lớn nhất, đồng dư, thặng dư, một số định lý quan trọng bao gồm: định lý Wilson, định lý Fermat, định lý phần dư Trung Hoa) và một số kiến thức cơ bản về tổ hợp (quy tắc cộng, quy tắc nhân, hoán vị, chỉnh hợp, tổ hợp, nguyên lý bù trừ, nguyên lý Dirichlet, khai triển nhị thức Newton). Chương 2 : Một số bài toán Số học - Tổ hợp Mục đích của chương này trình bày một số bài toán thuộc loại "số học - tổ hợp" theo chủ đề (tính chất số học , bài toán chia kẹo Euler, bất biến, cực trị trên tập hợp rời rạc và số phức), đồng thời trong mỗi bài toán chúng tôi cố gắng phân tích để tiếp cận lời giải và có bình luận. Chương 3: Một số bài toán trò chơi
4 Trong chương cuối cùng, chúng tôi giới thiệu một số bài toán trò chơi và đặc biệt là ứng dụng của "tỉ số vàng" trong lời giải của bài toán trò chơi. Mặc dù bản thân đã cố gắng nhiều trong quá trình thực hiện, nhưng do thời gian có hạn và kiến thức bản thân còn hạn chế nên luận văn không tránh khỏi những thiếu sót. Rất mong nhận được sự chỉ bảo của quý thầy cô và các bạn.
5 Lời cảm ơn Luận văn này được hoàn thành dưới sự hướng dẫn nghiêm khắc và chỉ bảo tận tình của GS. TSKH Hà Huy Khoái. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi muốn bày tỏ lòng biết ơn sâu sắc đến người thầy của mình. Qua đây, tôi xin gửi tới các thầy cô Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, cũng như các thầy cô đã tham gia giảng dạy khóa cao học 2011 − 2013 lời cảm ơn sâu sắc nhất đối với công lao dạy dỗ trong suốt quá trình giáo dục đào tạo tại Nhà trường. Tôi xin được gửi lời cảm ơn chân thành tới gia đình, ban giám hiệu và tập thể giáo viên trường THPT chuyên Lê Quý Đôn tỉnh Bình định đã quan tâm, tạo điều kiện và động viên cổ vũ tôi để tôi có thể hoàn thành nhiệm vụ của mình. Hà nội, tháng 11 năm 2013
6 Chương 1 Một số kiến thức chuẩn bị 1.1 Kiến thức tổ hợp 1.1.1 Quy tắc cộng Nội dung quy tắc: Nếu có m1 cách chọn đối tượng a1 , m2 cách chọn đối tượng a2 ,. . . , mn cách chọn đối tượng an , trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kì cách chọn đối tượng aj nào n P (1 ≤ j ≤ n, i 6= j) thì sẽ có mi cách chọn đối tượng a1 , hoặc a2 ,. . . , hoặc i=1 an . Để sử dụng tốt quy tắc này ta chuyển sang ngôn ngữ tập hợp như sau: Xét {A1 , A2 , ..., An } là một họ các tập hợp con hữu hạn cuả tập A sao cho hai tập bất kì không có phần tử chung, hợp của tất cả các tập con là A, n S A= Ai . Khi đó, ta có i=1 n X |A| = |A1 | + |A2 | + ... + |An | = |Ai |. i=1 1.1.2 Quy tắc nhân Nội dung quy tắc: Cho n đối tượng a1 , a2 , ..., an , nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 , a2 có m3 cách chọn đối tượng a3 , ... cuối cùng với mỗi cách chọn a1 , a2 , ..., an−1 có mn cách chọn đối tượng an . Như vậy sẽ có m1 .m2 ...mn cách chọn đối tượng a1 , rồi a2 ,..., rồi an . Tương tự như quy tắc cộng, ta sẽ chuyển sang ngôn ngữ tập hợp như sau: Giả sử có n tập hợp Ak (1 ≤ k ≤ n) với |Ak | = mk . Khi đó, số cách chọn bộ
7 gồm n phần tử (a1 , a2 , ..., an ) với ai ∈ Ai (1 ≤ i ≤ n) sẽ là n Y |A1 × A2 × ... × An | = m1 × m2 × ... × mn = mk . k=1 1.1.3 Hoán vị Định nghĩa 1.1. (Hoán vị không lặp) Giả sử A là tập hợp hữu hạn gồm n phần tử. Một cách sắp xếp n phần tử khác nhau của tập A theo một thứ tự nào đó được gọi là một hoán vị không lặp của các phần tử trong tập A, hay đơn giản là sự sắp xếp n phần tử của tập A. Khi đó, số hoán vị không lặp của n phần tử kí hiệu Pn và tính theo công thức Pn = n (n − 1) ...1 = n!. Định nghĩa 1.2. (Hoán vị có lặp) Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị có lặp. Kí hiệu P (n1 , n2 , ..., nk ) là số hoán vị có lặp của n phần tử gồm k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần và được tính theo công thức n! P (n1 , n2 , ..., nk ) = . n1 !n2 !...nk ! 1.1.4 Chỉnh hợp Định nghĩa 1.3. (Chỉnh hợp không lặp) Cho tập hợp A gồm n phần tử. Mỗi bộ gồm k (0 ≤ k ≤ n) phần tử được sắp thứ tự của tập A được gọi là một chỉnh hợp không lặp chập k của n phần tử thuộc A. Kí hiệu số chỉnh hợp không lặp chập k của n là Akn , tính bởi công thức n! Akn = . (n − k)! Định nghĩa 1.4. (Chỉnh hợp có lặp) Cho tập hợp X gồm n phần tử. Mỗi dãy có độ dài k phần tử của tập X , mà mỗi phần tử có thể lặp lại nhiều lần và được sắp theo một thứ tự nhất định được gọi là một chỉnh hợp có lặp chập k của n phần tử thuộc tập X . Kí hiệu số chỉnh hợp có lặp chập k của n là Akn , tính bởi công thức Akn = nk .
8 1.1.5 Tổ hợp Định nghĩa 1.5. (Tổ hợp không lặp) Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k (0 ≤ k ≤ n ) phần tử của tập A được gọi là một tổ hợp không lặp chập k của n phần tử thuộc A. Kí hiệu số tổ hợp không lặp chập k của n là Cnk , tính bởi công thức n! Cnk = . k! (n − k)! Định nghĩa 1.6. (Tổ hợp có lặp) Cho tập A = {a1 , a2 , ..., an }. Một tổ hợp có lặp chập m (m không nhất thiết phải nhỏ hơn n) của n phần tử thuộc A là một bộ gồm m phần tử, mà mỗi phần tử này là một trong những phần tử của A. Kí hiệu số tổ hợp có lặp chập m của n là Cnm , tính bởi công thức m Cnm = Cn+m−1 . 1.1.6 Nguyên lý bù trừ Giả sử M1 , M2 , ..., Mn là các tập hợp hữu hạn. Khi đó ta có công thức tổng quát sau đây: n X X |M1 ∪ M2 ∪ ... ∪ Mn | = |Mi | − |Mi ∩ Mj | i=1 1≤i
9 Định lý 1.2. Với m, n là hai số nguyên dương, ta có n X (x1 + x2 + ... + xm ) = P (n1 , n2 , ..., nm ) xn1 1 xn2 2 ...xnmm . n1 ,n2 ,...,nm ≥0 n1 +n2 +...+nm =n 1.2 Kiến thức số học 1.2.1 Tính chia hết Nếu a, b là hai số nguyên và b 6= 0 thì tồn tại duy nhất hai số nguyên q, r; 0 ≤ r ≤ |b| − 1 sao cho a = bq + r. 1.2.2 Biểu diễn cơ số Với b ∈ Z, b > 1 thì với mọi n ∈ Z+ luôn tồn tại biểu diễn duy nhất n = ak bk + ak−1 bk−1 + ... + a1 b + a0 , trong đó a0 , a1 , ..., ak ∈ Z, 0 ≤ ai ≤ b − 1, ak 6= 0. Kí hiệu n = (ak ak−1 ...a1 a0 )b . 1.2.3 Số nguyên tố Định nghĩa 1.7. Số nguyên p > 1 gọi là số nguyên tố nếu nó chỉ có hai ước nguyên dương 1, p. Định lý 1.3. (Định lý cơ bản của số học) Mọi số nguyên n > 1 đều có biểu diễn duy nhất dưới dạng tích các số nguyên tố (không kể thứ tự), tức là n = pα1 1 pα2 2 ...pαk k , trong đó αi ∈ Z+ , p1 < p2 < ... < pk là các số nguyên tố. Định lý 1.4. Tập hợp các số nguyên tố là vô hạn. 1.2.4 Ước chung lớn nhất, bội chung nhỏ nhất Định nghĩa 1.8. Cho n > 1 số nguyên không đồng thời bằng không a1 , a2 , ..., an . Số nguyên dương d lớn nhất có tính chất d chia hết ai , i = 1, 2, ..., n được gọi là ước chung lớn nhất của n số a1 , a2 , ..., an . Kí hiệu ƯCLN(a1 , a2 , ..., an ) hay (a1 , a2 , ..., an ).
10 Định nghĩa 1.9. Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu (a, b) = 1. Định nghĩa 1.10. Cho n > 1 số nguyên khác không a1 , a2 , ..., an . Số nguyên dương d nhỏ nhất có tính chất d chia hết cho ai , i = 1, 2, ..., n được gọi là bội chung nhỏ nhất của n số a1 , a2 , ..., an . Kí hiệu BCNN(a1 , a2 , ..., an ) hay [a1 , a2 , ..., an ]. Định lý 1.5. Tồn tại các số nguyên không đồng thời bằng không x1 , x2 , ..., xn sao cho n P ƯCLN(a1 , a2 , ..., an ) = x i ai . i=1 n P Đặc biệt, một số nguyên N biểu diễn ở dạng xi ai khi và chỉ khi ƯCLN(a1 , a2 , ..., an ) i=1 chia hết N . Định lý 1.6. (Một số kết quả hay sử dụng) 1. Nếu (a, b) = 1 thì (am + bn , as bt ) = 1 trong đó s, t là hai số nguyên không âm và m, n là hai số nguyên dương. ab 2. [a, b] = . (a, b) (a, b) . (a, c) 3. a ≥ . (a, b, c) p a + bp 1 nếu p không chia hết a + b; 4. ,a + b = a+b p nếu p chia hết hết a + b. 5. Tính chất dãy Mersen: (am − 1, an − 1) = a(m,n) − 1 với a > 1 và các số nguyên dương m, n. Định lý 1.7. Nếu a = pa11 pa22 ...pann , b = pb11 pb22 ...pbnn , trong đó p1 , p2 , ..., pn là các số nguyên tố và ai , bi là các số nguyên không âm thì min(a1 ,b1 ) min(a2 ,b2 ) (a, b) = p1 p2 ...pmin(a n n ,bn ) và max(a1 ,b1 ) max(a2 ,b2 ) [a, b] = p1 p2 ...pmax(a n n ,bn ) .
11 1.2.5 Thuật toán Euclid Định lý 1.8. Cho a, b là hai số nguyên dương và a = q1 b + r1 (0 < r1 < b) , b = q2 r1 + r2 (0 < r2 < r1 ) , ... rn−1 = qn+1 rn . Khi đó rn = (a, b) . Định lý 1.9. Thuật toán tìm ước chung lớn nhất của hai số nguyên dương như sau: • Bước 1: xét hai số nguyên dương a, b rồi sang bước hai. • Bước 2: kiểm tra đẳng thức a = b; nếu đúng thì dừng lại và ƯCLN(a, b) = a; nếu sai thì sang bước 3. • Bước 3: nếu a > b thì gán lại a bởi a − b, nếu a < b thì gán lại b bởi b − a rồi chuyển qua bước 1. Thuật toán sẽ dừng sau một số hữu hạn lần (chỉ cần xét đơn biến là tổng của hai số). 1.2.6 Đồng dư Định nghĩa 1.11. Cho a, b, m ∈ Z, m 6= 0. Ta nói a đồng dư b theo modulo m nếu a, b có cùng số dư khi chia cho m. . Kí hiệu a ≡ b (modm) ⇔ (a − b) ..m. Tính chất. • Nếu a ≡ b (modm) và b ≡ c (modm) thì a ≡ c (modm) . • Nếu a ≡ b (modm) và c ≡ d (modm) thì a ± c ≡ b ± d (modm) và ac ≡ bd (modm) .
12 1.2.7 Đồng dư tuyến tính Định nghĩa 1.12. Một đồng dư dạng ax ≡ b (modm) trong đó x là một số nguyên chưa biết và a, b là hai số nguyên, được gọi là đồng dư tuyến tính một biến. Định lý 1.10. Giả sử a, b, m là các số nguyên m > 1 và (a, m) = d. Nếu d không chia hết b thì đồng dư ax ≡ b (modm) vô nghiệm. Nếu d chia hết b thì đồng dư ax ≡ b (modm) có đúng d nghiệm không đồng dư modulo m. Hệ quả. Giả sử a, m là các số nguyên m > 1, nếu (a, m) = 1 thì đồng dư ax ≡ 1 (modm) luôn có nghiệm duy nhất modulo m, nghiệm này gọi là nghịch đảo của a modulo m. 1.2.8 Thặng dư Định nghĩa 1.13. Nếu x ≡ y (modm) thì ta nói y là một thặng dư của x theo modulo m. Định nghĩa 1.14. Tập A = {x1 , x2 , ..., xm } gồm m số nguyên. Giả sử ri (0 ≤ ri ≤ m − 1) là số dư của xi khi chia cho m. Nếu tập hợp số dư {r0 , r1 , ..., rm−1 } trùng với tập hợp {0, 1, ..., m − 1} thì ta nói tập A là một hệ thặng dư đầy đủ theo modulo m. Tính chất. Giả sử tập A = {x1 , x2 , ..., xm } là hệ thặng dư đầy đủ modulo m thì: • Với mọi y ∈ Z tồn tại duy nhất xi ∈ A sao cho y ≡ xi (modm) . • Với mọi số nguyên b thì tập {x1 + b, x2 + b, ..., xm + b} là hệ thặng dư đầy đủ theo modulo m. • Với mỗi c ∈ Z và (c, m) = 1 thì tập {cx1 , cx2 , ..., cxm } là hệ thặng dư đầy đủ modulo m. Định nghĩa 1.15. Tập {r1 , r2 , ..., rn } gọi là một hệ thặng dư thu gọn modulo m nếu (ri , m) = 1 và với mọi x ∈ Z, (x, m) = 1 thì tồn tại duy nhất ri để ri ≡ x (modm) . Nhận xét. • Ta có thể thu được hệ thặng dư thu gọn modulo m bằng cách loại trừ từ một hệ thặng dư đầy đủ các phần tử không nguyên tố cùng nhau với m.
13 • Mọi hệ thặng dư thu gọn modulo m đều có cùng số phần tử, kí hiệu ϕ (m). Định lý 1.11. Nếu n = pα1 1 pα2 2 ...pαk k thì 1 1 1 ϕ (n) = n 1 − 1− ... 1 − . p1 p2 pk Hệ quả. Nếu p là số nguyên tố thì ϕ (p) = p − 1. 1.2.9 Một số định lý quan trọng Định lý 1.12. (Định lý Wilson) p là số nguyên tố khi và chỉ khi (p − 1)! ≡ −1 (modp) . Định lý 1.13. (Định lý Euler) Nếu m là số nguyên dương và (a, m) = 1 thì aϕ(m) ≡ 1 (modm) . Định lý 1.14. (Định lý Fermat) Nếu p là số nguyên tố và (a, m) = 1 thì ap−1 ≡ 1 (modp) . Định lý 1.15. (Định lý phần dư Trung Hoa) Giả sử m1 , m2 , ..., mr là các số nguyên tố cùng nhau đôi một. Khi đó hệ    x ≡ a1 (modm1 ) x ≡ a2 (modm2 )    ... x ≡ ar (modmr )  có nghiệm duy nhất modulo M với M = m1 m2 ...mr .
14 Chương 2 Một số bài toán Số học - Tổ hợp Thông thường để tạo ra một bài toán tổ hợp, chúng ta hay kết hợp các kết quả ở những lĩnh vực khác nhau; chẳng hạn là kết quả số học, hình học, đại số với một kết quả về lý thuyết tổ hợp. Chính vì vậy, việc giải một bài toán tổ hợp gặp rất nhiều khó khăn, bởi vì chúng ta phải biết những kết quả ở những lĩnh vực khác nhau và phải biết kết hợp chúng lại. Trong luận văn này, chúng tôi xét một số bài toán tổ hợp có nội dung là sự kết hợp các kết quả số học và tổ hợp. Trong chương này, chúng tôi giới thiệu một số bài toán "số học - tổ hợp" được sắp xếp theo chủ đề và chúng tôi cũng cố gắng phân tích để tìm lời giải các bài toán một cách tự nhiên nhất và bình luận sau khi giải xong bài toán. 2.1 Tính chất số học Chúng tôi trình bày một số bài toán tổ hợp mà khi giải chúng, ta cần sử dụng nhiều kiến thức về số học (tính chia hết, ước chung nhỏ nhất, bội chung nhỏ nhất, hệ thặng dư đầy đủ và hệ thặng dư thu gọn, định lý phần dư Trung Hoa,...) và các kiến thức về tổ hợp (các quy tắc đếm cơ bản, nguyên lý Dirichlet, nguyên lý bù trừ, phương pháp quỹ đạo,...). 2.1.1 Tính chia hết Bài toán 2.1. (Olympic 30 - 4 - 2011) Chứng minh rằng từ 2011 số nguyên dương bất kì luôn có thể chọn ra được hai số mà tổng hoặc hiệu của chúng chia hết cho 4018. Phân tích - Lời giải. Khi chia một số nguyên dương bất kì cho 4018 thì các số dư phải thuộc tập hợp {0, 1, ..., 4017}. Dựa vào nhận xét trên chia các số dư trên thành từng nhóm như sau:
15 - Nhóm thứ nhất gồm những số khi chia cho 4018 có số dư bằng 0. - Nhóm thứ hai gồm những số khi chia cho 4018 có số dư bằng 1 hoặc 4017. - Nhóm thứ ba gồm những số khi chia cho 4018 có số dư bằng 2 hoặc 4016. ... - Nhóm thứ 2009 gồm những số khi chia cho 4018 có số dư bằng 2008 hoặc 2010. - Nhóm thứ 2010 gồm những số khi chia cho 4018 có số dư bằng 2009. Như vậy, có tất cả là 2010 nhóm, mà lại có 2011 số nguyên dương nên, theo nguyên lý Dirichlet, giữa chúng phải có ít nhất hai số mà có số dư thuộc cùng một nhóm. Đây là hai số cần tìm, vì nếu chúng có số dư bằng nhau thì hiệu của chúng chia hết cho 4018 và nếu chúng có số dư khác nhau thì tổng của chúng chia hết cho 4018. Nhận xét. Rõ ràng trong bài toán này, gợi ý cho xét số dư của 2011 số khi chia cho 4018, nếu hai số có cùng số dư thì hiệu của hai số đó chia hết cho 4018, còn nếu tổng số dư của hai số bằng 4018 thì tổng của hai số đó chia hết cho 4018. Như vậy, chỉ cần ghép các số dư thích hợp và sử dụng nguyên lý Dirichlet. Bài toán 2.2. Cho tập hợp A = {1; 2; ...; 2010}. Chứng minh rằng từ 1006 số bất kì thuộc tập hợp A ta luôn tìm được hai số mà số này chia hết cho số kia. Phân tích - Lời giải. Giả sử 1006 đó là a1 , a2 , ..., a1006 . Ta phân tích 1006 số dưới dạng như sau: a1 = 2m1 b1 ; ...; a1006 = 2m1006 b1006 , trong đó bi là các số dương, lẻ thuộc tập A. Vì trong tập A chỉ có 1005 số lẻ mà lại có 1006 số lẻ bi nên theo nguyên lý Dirichlet tồn tại hai số trùng nhau. Giả sử đó là bi = bj . Khi đó tương ứng ta có hai số ai = 2mi .bi ; aj = 2mj .bi thỏa mãn yêu cầu bài toán. Nhận xét. Bài toán chứng minh sự tồn tại là dấu hiệu để ta nghĩ đến nguyên lý Dirichlet, hơn nữa chúng ta phải biết biểu diễn số tự nhiên ni = 2mi bi . Với cách suy luận tương tự, ta có thể giải bài toán sau: Bài toán 2.3. Cho 2010 số tự nhiên bất kỳ. Chứng minh rằng trong số các số đó, có một số chia hết cho 2010 hoặc có một số số mà có tổng chia hết
16 cho 2010. Phân tích - Lời giải. i P Đặt Si = ak i = 1; 2010 . Nếu có một số hạng của dãy chia hết 2010 k=1 thì bài toán được chứng minh. Ngược lại, các số Si chia cho 2010 có số dư thuộc tập {1, 2, ..., 2009}, vì có 2010 số Si , nhưng chỉ có 2009 số dư nên theo nguyên lý Dirichlet phải có hai số có cùng số dư. Giả sử đó là Si và Sj với . (j > i). Suy ra (Sj − Si ) ..2010. Bài toán 2.4. Hỏi có bao nhiêu cách sắp xếp các số 21, 31, 41, 51, 61, 71, 81 sao cho tổng của bốn số liên tiếp bất kì chia hết cho 3. Phân tích - Lời giải. Ta chỉ cần xét dãy đã cho theo modulo 3, do đó dãy này có thể viết lại 0, 1, 2, 0, 1, 2, 0. Giả sử a1 , a2 , ..., a7 là một cách xếp thỏa mãn yêu cầu bài toán. Khi đó 0 ≡ (a1 + a2 + a3 + a4 ) + (a4 + a5 + a6 + a7 ) ≡ (a1 + a2 + a3 + a4 + a5 + a6 + a7 ) + a4 ≡ a4 (mod3) . Suy ra a1 + a2 + a3 ≡ 0 (mod3), do đó a1 , a2 , a3 phải là hoán vị của 0, 1, 2 . Mặt khác (a1 + a2 + a3 + a4 ) ≡ (a2 + a3 + a4 + a5 ) (mod3) nên a1 ≡ a5 (mod3). Tương tự, ta chứng minh a5 , a6 , a7 được xác định duy nhất bởi a1 , a2 , a3 . Do đó, số cách sắp xếp cần tìm chính là số cách xếp số 0 vào vị trí thứ 4 các số 0, 1, 2 vào ba vị trí đầu tiên của dãy đã cho. Dễ thấy số cách xếp thỏa mãn là 23 .3.3!. Nhận xét. Vì liên quan đến tổng chia hết cho 3 nên ta chỉ cần xét số dư các số theo modulo 3. Thêm một số lý luận đơn giản về tính chia hết thì ta có thể đến được tất cả các cách sắp xếp. Bài toán 2.5. Cho S là tập hợp tất cả các điểm trong không gian có tọa độ (x, y, z) sao cho x, y, z là số nguyên và 0 ≤ x ≤ 2, 0 ≤ y ≤ 3, 0 ≤ z ≤ 4. Lấy ngẫu nhiên hai điểm bất kì của tập S . Tính xác suất để chọn hai điểm mà tọa độ trung điểm của đoạn thẳng đó cũng thuộc tập S . Phân tích - Lời giải. Vì có 3 cách chọn x, 4 cách chọn y và 5 cách chọn z nên |S| = 3.4.5 = 60. 2 Do |S| = 60 nên có C60 = 1770 cách chọn hai điểm. Để tọa độ trung điểm
17 của đoạn thẳng nối hai điểm thuộc S thì tọa độ tương ứng của hai điểm đó có cùng tính chẵn lẻ. Dễ dàng đếm được có: • 2.2.3 = 12 điểm có cả ba tọa độ đều chẵn. • 1.2.2 = 4 điểm có cả ba tọa độ đều lẻ. • 1.2.3 = 6 điểm chỉ có x tọa độ lẻ. • 2.2.3 = 12 điểm chỉ có y tọa độ lẻ. • 2.2.2 = 8 điểm chỉ có z tọa độ lẻ. • 2.2.2 = 8 điểm chỉ có x tọa độ chẵn. • 1.2.2 = 4 điểm chỉ có y tọa độ chẵn. • 1.2.3 = 6 điểm chỉ có z tọa độ chẵn. Do đó số cách chọn hai điểm sao cho tọa độ trung điểm cũng thuộc S là: 2 C12 + C42 + C62 + C12 2 + C82 + C82 + C42 + C62 = 230. 230 23 Vậy xác suất bằng = . 1770 177 Nhận xét. Sử dụng tính chất số học khá đơn giản là: "Tổng của hai số tự nhiên là số chẵn khi hai số đó cùng chẵn hoặc cùng lẻ" và sử dụng phép đếm cơ bản tìm ra đáp số. Bài toán 2.6. (Olympic 30 - 4 - 2012) Cho hình vuông kích thước 8 × 8 được chia thành 64 ô vuông đơn vị. Hỏi có thể viết tất cả các số 1, 2, ..., 64 vào 64 ô vuông (mỗi ô chứa đúng một số) sao cho tổng của 4 số nằm trong 4 ô của mỗi một hình bất kì sau đây đều chia hết cho 4? Hình 2.1: hình vẽ Phân tích - Lời giải. Giả sử ta có thể viết được các số 1, 2, ..., 64 vào các ô của bảng hình vuông kích thước 8 × 8 sao cho tổng của 4 số trong 4 ô vuông của mỗi hình bất kì
18 đều chia hết cho 4. Gọi a1 , a2 , a3 , a4 , a5 là 5 số trong hình chữ thập +, trong đó a5 là số ở tâm, còn các số đánh theo thứ tự ngược chiều kim đồng hồ. Từ giả thiết bài toán đã cho, ta có các tổng a1 + a2 + a3 + a5 , a2 + a3 + a4 + a5 , a3 + a4 + a1 + a5 , a4 + a1 + a2 + a5 luôn chia hết cho 4. Do đó . . (3 (a1 + a2 + a3 + a4 ) + 4a5 ) ..4 ⇒ (a1 + a2 + a3 + a4 ) ..4. Từ đó suy ra a5 ≡ ai (mod4) (i = 1, 2, 3, 4) . Như vậy các số a1 , a2 , a3 , a4 , a5 đều có cùng số dư khi chia cho 4. Bằng lí luận tương tự như trên suy ra có nhiều hơn 16 số trong bảng hình vuông có cùng số dư khi chia cho 4. Tập hợp số {1, 2, ..., 64} chỉ có thể chia thành 4 tập con, mỗi tập con gồm 16 phần tử có cùng số dư khi chia cho 4. Điều này dẫn đến mâu thuẫn. Vậy không thể viết các số thỏa mãn yêu cầu bài toán. Nhận xét. Để ý số trung tâm của một hình chữ thập sẽ có cùng số dư với các số kề nó nên sẽ có nhiều số dư, chính điều này gợi ý cho xem trong các số đã cho có bao nhiêu số có cùng số dư theo modulo 4, so sánh suy ra điều mâu thuẫn. Bài toán 2.7. Có tồn tại hay không một cách sắp xếp 2013 số nguyên dương đôi một khác nhau trên một đường tròn sao cho với hai số nguyên đứng kề nhau thì thương của số lớn và số nhỏ là một số nguyên tố. Phân tích - Lời giải. Giả sử tồn tại một cách xếp và các số nguyên dương đó là a1 , a2 , ..., a2013 . Gọi ni là số các số nguyên tố (kể cả trùng nhau) trong phân tích ra thừa số nguyên tố của ai . Vì thương của hai số kề nhau ai , ai+1 là một số nguyên tố nên trong phân tích ra thừa số nguyên tố của ai , ai+1 thì ni , ni+1 hơn kém nhau một đơn vị, vì vậy ni và ni+1 khác tính chẵn lẻ. Do đó, ni và ni+1 khác tính chẵn lẻ. Suy ra n1 , n3 , ..., n2013 cùng tính chẵn lẻ. Vì a1 , a2013 kề nhau nên n1 , n2013 khác tính chẵn lẻ. Điều này dẫn đến mâu thuẫn. Vậy không tồn tại cách xếp thỏa mãn bài toán. Nhận xét. Thương của hai số là một số nguyên tố, gợi ý cho ta nghĩ đến phân tích các số ra thừa số nguyên tố. Dựa vào tính chẵn lẻ của số lượng số nguyên tố dễ dàng khẳng định không thể sắp xếp. Bài toán 2.8. Cho tập 4 .. n o 4 T = (x, y) |0 ≤ 2x < y ≤ 100; x, y ∈ N & (x + y ).49 .
19 Tìm |T | là số phần tử của tập T. Phân tích - Lời giải. Ta có 7 là số nguyên tố dạng 4k + 3, điều này gợi nhớ lại một kết quả quen thuộc trong số học sau đây: Bổ đề. Cho p là số nguyên tố dạng 4k + 3. Khi đó a, b là hai số nguyên thỏa mãn a2 + b2 chia hết cho p thì cả hai a, b đều chia hết cho p. Chứng minh. Nếu a chia hết cho p thì từ điều kiện a2 + b2 chia hết cho p suy ra b chia hết cho p. Nếu a không chia hết cho p thì từ điều kiện a2 + b2 chia hết cho p suy ra b không chia hết cho p. Do p là số nguyên tố nên (a, p) = (b, p) = 1. Theo định lý Fermat, ta có 2k+1 ap−1 − 1 = a2 − 1 ≡ 0 (modp) , và 2k+1 bp−1 − 1 = b2 − 1 ≡ 0 (modp) , suy ra 2k+1 2k+1 a2 + b2 − 2 ≡ 0 (modp) . Mặt khác 2k+1 2k+1 a2 + b2 ≡ a2 + b2 (modp) . Từ các điều trên, suy ra 2 chia hết cho p là vô lí. Vậy a, b chia hết cho p. Trở lại bài toán. . . Ta có (x4 + y 4 )..49 suy ra (x4 + y 4 )..7. Theo bổ đề thì x2 , y 2 chia hết cho 7 do . đó x, y đều chia hết cho 7. Ngược lại nếu x, y chia hết cho 7 thì (x4 + y 4 )..49. Từ 0 đến 100 có 15 số chia hết cho 7 đó là 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98. Vì 0 ≤ 2x < y ≤ 100 nên x ∈ {0, 7, 14, 21, 28, 35, 42} . Nếu x = 0 có 14 cách chọn y. Nếu x = 7 thì có 12 cách chọn y (y ∈ {21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98}). Nếu x = 14 thì có 10 cách chọn y (y ∈ {35, 42, 49, 56, 63, 70, 77, 84, 91, 98}). Nếu x = 21 thì có 8 cách chọn y (y ∈ {49, 56, 63, 70, 77, 84, 91, 98}). Nếu x = 28 thì có 6 cách chọn y (y ∈ {63, 70, 77, 84, 91, 98}). Nếu x = 35 thì có 4 cách chọn y (y ∈ {77, 84, 91, 98}). Nếu x = 42 thì có 2 cách chọn y (y ∈ {91, 98}). Vậy |T | = 2 + 4 + 6 + 8 + 10 + 14 = 56. Nhận xét. Để giải bài toán này, ta chỉ cần biết kết quả số học quen thuộc ở phổ thông, kết hợp với phép đếm cơ bản.