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

ĐẠ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

Mục lục

Lời mở đầu

Lời cảm ơn

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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.6 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.7 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . 1.1.8 Khai triển nhị thức Newton . . . . . . . . . . . . . . . . . . . 1.2 Kiến thức số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Biểu diễn cơ số . . . . . . . . . . . . . . . . . . . . . . . . . . Số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 1.2.4 Ước chung lớn nhất, bội chung nhỏ nhất . . . . . . . . . . . 1.2.5 Thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . 1.2.6 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.7 Đồng dư tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . 1.2.8 Thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.9 Một số định lý quan trọng . . . . . . . . . . . . . . . . . . . .

6 6 6 6 7 7 8 8 8 8 9 9 9 9 9 11 11 12 12 13

2 Một số bài toán Số học - Tổ hợp

14 14 14 30

chung lớn nhất

2.1 Tính chất số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Tính chia hết 2.1.2 Biểu diễn số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Thuật toán Euclid và một số bài toán liên quan đến ước . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Bài toán chia kẹo Euler. . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Cực trị trên tập hợp rời rạc . . . . . . . . . . . . . . . . . . . . . . . 2.5 Số phức - Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 47 53 61 75

3 Một số bài toán trò chơi

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86 96 97

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

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.

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

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

mi cách chọn đối tượng a1, hoặc a2,. . . , hoặc

n (cid:80) i=1

(1 ≤ j ≤ n, i (cid:54)= j) thì sẽ có an.

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

A =

Ai. Khi đó, ta có

n (cid:83) i=1

n (cid:88)

|A| = |A1| + |A2| + ... + |An| =

|Ai|.

i=1

1.1.2 Quy tắc nhân

Để 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ộ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ộ

n (cid:89)

|A1 × A2 × ... × An| = m1 × m2 × ... × mn =

mk.

k=1

1.1.3 Hoán vị

gồm n phần tử (a1, a2, ..., an) với ai ∈ Ai (1 ≤ i ≤ n) sẽ là

Pn = n (n − 1) ...1 = n!.

Đị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

Đị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.

P (n1, n2, ..., nk) =

n! n1!n2!...nk!

1.1.4 Chỉnh hợ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, tính bởi công thức

n =

n! (n − k)!

Đị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à Ak

n, tính bởi công thức

n = nk.

Đị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à Ak

1.1.5 Tổ hợp

n, tính bởi công thức

C k

n =

n! k! (n − k)!

Đị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à C k

n , tính bởi công thức

C m

n = C m

n+m−1.

1.1.6 Nguyên lý bù trừ

Đị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à C m

Giả sử M1, M2, ..., Mn là các tập hợp hữu hạn. Khi đó ta có công thức

n (cid:88)

tổng quát sau đây:

|M1 ∪ M2 ∪ ... ∪ Mn| =

|Mi| −

|Mi ∩ Mj|

i=1

1≤i

(cid:88)

|Mi ∩ Mj ∩ Mk| − .... + (−1)n+1 |M1 ∩ M2 ∩ ... ∩ Mn| .

1≤i

1.1.7 Nguyên lý Dirichlet

(cid:88)

+ 1 đồ vật.

1.1.8 Khai triển nhị thức Newton

Có n đồ vật được xếp vào m ngăn kéo. Khi đó tồn tại ít nhất một ngăn (cid:21) kéo chứa ít nhất (cid:20)n − 1 m

n (cid:88)

C k

(x + y)n =

nxn−kyk.

k=0

Định lý 1.1. Với số tự nhiên n ≥ 1 ta có

Định lý 1.2. Với m, n là hai số nguyên dương, ta có

(x1 + x2 + ... + xm)n =

P (n1, n2, ..., nm) xn1

2 ...xnm m .

1 xn2

n1,n2,...,nm≥0 n1+n2+...+nm=n

(cid:88)

1.2 Kiến thức số học

1.2.1 Tính chia hết

0 ≤ r ≤ |b| − 1 sao cho

a = bq + r.

1.2.2 Biểu diễn cơ số

Nếu a, b là hai số nguyên và b (cid:54)= 0 thì tồn tại duy nhất hai số nguyên q, r;

n = akbk + ak−1bk−1 + ... + a1b + a0,

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

1.2.3 Số nguyên tố

trong đó a0, a1, ..., ak ∈ Z, 0 ≤ ai ≤ b − 1, ak (cid:54)= 0. Kí hiệu n = (akak−1...a1a0)b.

Đị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.

n = pα1

1 pα2

2 ...pαk k ,

Đị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à

trong đó αi ∈ Z+, p1 < p2 < ... < pk là các số nguyên tố.

1.2.4 Ước chung lớn nhất, bội chung nhỏ nhất

Định lý 1.4. Tập hợp các số nguyên tố là vô hạn.

Đị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).

Đị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].

xiai.

Đị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 (cid:80) i=1

ƯCLN(a1, a2, ..., an) =

xiai khi và chỉ khi ƯCLN(a1, a2, ..., an)

n (cid:80) i=1

Đặc biệt, một số nguyên N biểu diễn ở dạng

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, asbt) = 1 trong đó s, t là hai số nguyên

không âm và m, n là hai số nguyên dương.

ab (a, b)

2. [a, b] =

(a, b) . (a, c) (a, b, c)

3. a ≥

, a + b

(cid:19) 4. = (cid:26)1 nếu p không chia hết a + b; p nếu p chia hết hết a + b. (cid:18)ap + bp 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

n , trong đó p1, p2, ..., pn là

n , b = pb1

2 ...pbn

2 ...pan

1 pb2

1 pa2 Định lý 1.7. Nếu a = pa1 các số nguyên tố và ai, bi là các số nguyên không âm thì

...pmin(an,bn)

(a, b) = pmin(a1,b1) 1

pmin(a2,b2) 2

số nguyên dương m, n.

...pmax(an,bn)

[a, b] = pmax(a1,b1) 1

pmax(a2,b2) 2

và

1.2.5 Thuật toán Euclid

a = q1b + r1 (0 < r1 < b) ,

b = q2r1 + r2 (0 < r2 < r1) ,

...

rn−1 = qn+1rn.

Định lý 1.8. Cho a, b là hai số nguyên dương và

rn = (a, b) .

Khi đó

• 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.

Đị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:

1.2.6 Đồng dư

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ố).

...m.

• 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) .

Định nghĩa 1.11. Cho a, b, m ∈ Z, m (cid:54)= 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) Tính chất.

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.

1.2.8 Thặng dư

Đị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.

Đị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.

• 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ư

Đị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 c ∈ Z và (c, m) = 1 thì tập {cx1, cx2, ..., cxm} là hệ thặng dư

đầy đủ theo modulo m.

đầy đủ modulo m.

• 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.

Đị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.

• Mọi hệ thặng dư thu gọn modulo m đều có cùng số phần tử, kí hiệu

ϕ (m).

2 ...pαk

k (cid:19) (cid:18)

1 pα2 (cid:18)

thì Định lý 1.11. Nếu n = pα1

1 −

...

1 −

ϕ (n) = n

1 p1

1 p2

1 pk

(cid:19) (cid:18) (cid:19)

1.2.9 Một số định lý quan trọng

Hệ quả. Nếu p là số nguyên tố thì ϕ (p) = p − 1.

Đị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 = m1m2...mr.

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

2.1.1 Tính chia hết

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,...).

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:

4017.

- 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

4016. ... - Nhóm thứ 2009 gồm những số khi chia cho 4018 có số dư bằng 2008

- Nhóm thứ ba gồm những số khi chia cho 4018 có số dư bằng 2 hoặc

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.

a1 = 2m1b1; ...; a1006 = 2m1006b1006,

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:

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 = 2mibi. 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

(cid:0)i = 1; 2010(cid:1). Nếu có một số hạng của dãy chia hết 2010 Đặt Si = cho 2010. Phân tích - Lời giải. i (cid:80) k=1

...2010. 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)

0 ≡ (a1 + a2 + a3 + a4) + (a4 + a5 + a6 + a7)

≡ (a1 + a2 + a3 + a4 + a5 + a6 + a7) + a4 ≡ a4 (mod3) .

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 đó

(a1 + a2 + a3 + a4) ≡ (a2 + a3 + a4 + a5) (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

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. Do |S| = 60 nên có C 2 60 = 1770 cách chọn hai điểm. Để tọa độ trung điểm

• 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.

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ó:

C 2

12 + C 2

8 + C 2

4 + C 2

6 = 230.

Do đó số cách chọn hai điểm sao cho tọa độ trung điểm cũng thuộc S là:

4 + C 2 230 1770

6 + C 2 23 177

Vậy xác suất bằng

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ố.

Hình 2.1: hình vẽ

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?

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ì

đề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. ...4 ⇒ (a1 + a2 + a3 + a4)

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

T =

(x, y) |0 ≤ 2x < y ≤ 100; x, y ∈ N & (x4 + y4)

(cid:110) (cid:111) ...49 .

ap−1 − 1 = (cid:0)a2(cid:1)2k+1 − 1 ≡ 0 (modp) ,

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ó

bp−1 − 1 = (cid:0)b2(cid:1)2k+1 − 1 ≡ 0 (modp) ,

và

suy ra

(cid:0)a2(cid:1)2k+1 + (cid:0)b2(cid:1)2k+1 − 2 ≡ 0 (modp) .

Mặt khác

(cid:0)a2(cid:1)2k+1 + (cid:0)b2(cid:1)2k+1 ≡ 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.

...49 suy ra (x4 + y4)

...7. Theo bổ đề thì x2, y2 chia hết cho 7 do ...49.

0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.

Ta có (x4 + y4) đó x, y đều chia hết cho 7. Ngược lại nếu x, y chia hết cho 7 thì (x4 + y4) Từ 0 đến 100 có 15 số chia hết cho 7 đó là

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.

Bài toán 2.9. Trên mặt phẳng tọa độ, có một con cào cào ở gốc tọa độ O(0, 0). Với N là một số nguyên dương cho trước, con cào cào có thể nhảy từ điểm nguyên A đến điểm nguyên B nếu độ dài AB bằng N . Hỏi con cào cào có thể nhảy đến bất kỳ điểm nguyên nào trên mặt phẳng sau hữu hạn bước nhảy không nếu:

1. N = 2013;

2. N = 2017.

1. Ta chứng minh với N = 2013 câu trả lời là không thể. Giả sử con cào

(Trong đó điểm nguyên là điểm có cả hai tọa độ đều là số nguyên). Phân tích - Lời giải.

...3, (y − t) ...3 hay x ≡ z (mod3) ; y ≡ t (mod3) .

2. Cách 1. Câu trả lời là có thể.

cào đang ở điểm A(x, y) và nó nhảy đến điểm (z, t). Do yêu cầu bài toán nên (x − z)2 + (y − t)2 = 20132. Vì 2013 chia hết cho 3 nên (x − z) Do ban đầu con cào cào đứng ở điểm (0, 0) nên sau mỗi bước nhảy, nó sẽ nhảy đến điểm có tung độ và hoành độ đều chia hết cho 3. Như vậy con cào cào không thể nhảy đến điểm nguyên có một trong hai tọa độ không chia hết cho 3. Nói riêng, con cào cào không thể nhảy đến điểm (1, 1).

20172 = a2 + b2 = b2 + a2

Vì 2017 là số nguyên tố dạng 4k + 1 nên tồn tại x, y nguyên dương sao cho 2017 = x2 + y2. Cụ thể, dùng phương pháp thử dần ta tìm được 2017 = 92 + 442. Từ đó, áp dụng hằng đẳng thức (cid:0)x2 + y2(cid:1)2 = (cid:0)x2 − y2(cid:1)2 + (2xy)2 ta tìm được biểu diễn 20172 = a2 + b2 với a = 792 và b = 1855. Như vậy, ta tìm được a, b nguyên dương sao cho

(ka + lb + mN, la + kb + nN )

trong đó (a, b) = 1, (a, N ) = 1, (b, N ) = 1. Do đó con cào cào có thể nhảy đến các điểm có tọa độ

ka + lb + mN = x0, la + kb + nN = y0.

với k, l, m, n nguyên. Bây giờ ta chứng minh với mọi cặp số nguyên (x0, y0) thì luôn tồn tại k, l, m, n sao cho

ka + lb ≡ x0(modN ) và la + kb ≡ y0(modN ).

Điều này tương đương với việc chứng minh tồn tại k, l sao cho

(1)

ka2 + lab ≡ ax0 (modN ) ,

Ta sẽ chọn k, l thỏa mãn

(2)

lab + kb2 ≡ by0 ( mod N ) .

và

2lab ≡ ax0 + by0(modN ).

Dễ thấy vì a2 + b2 ≡ 0(modN ) nên nếu được k, l như vậy thì phải có

• Do (2ab, N ) = 1 nên tồn tại l sao cho

2lab ≡ ax0 + by0(modN ).

• Do (cid:0)a2, N (cid:1) = 1 nên tồn tại k sao cho

ka2 ≡ −lab + ax0 (modN ) .

Ta xây dựng nghiệm của (1) và (2) dựa vào các điều kiện này:

lab + kb2 ≡ lab − ka2 = 2lab − ax0 ≡ by0 (modN ).

Khi đó

ka + lb ≡ x0(modN ) và la + kb ≡ y0(modN ).

Như vậy, ta đã tìm được k, l thỏa mãn (1), (2). Vì (a, N ) = 1 và (b, N ) = 1 nên từ (1), (2) suy ra

Vậy con cào cào có thể nhảy đến tất cả các điểm nguyên.

Cách 2. Cũng như lời giải trên, với N = 2017, ta tìm được a, b nguyên

dương sao cho N 2 = a2 + b2. Với mỗi điểm nguyên ta dựng một hình chữ nhật "Cơ sở" có các cạnh song song với hai trục tọa độ và độ dài hai cạnh là a, b. Khi đó tọa độ các đỉnh của hình chữ nhật là nguyên và độ dài đường chéo bằng 2017. Ta chứng minh nếu con cào cào đang đứng ở một đỉnh của hình chữ nhật thì có thể nhảy đến một đỉnh bất kỳ của hình chữ nhật đó. Thật vậy, con cào cào có thể nhảy đến đỉnh đối diện của hình chữ nhật do khoảng cách đường chéo bằng 2017. Ta sẽ chứng minh nó nhảy đến đỉnh kề với nó. Giả sử nó đang đứng ở đỉnh A của hình chữ nhật ABCD với AB = b ta chỉ ra cách nhảy đến D. Dựng liên tiếp 2017 hình chữ nhật dọc theo AB như hình vẽ.

Hình 2.2: hình vẽ

Hình 2.3: hình vẽ

Khi đó AN = 2017b. Con cào cào nhảy dọc theo cạnh AB đúng b bước đến được đỉnh N. Con cào cào từ đỉnh N nhảy theo đường chéo hình chữ nhật 2017 bước sẽ về D (đpcm). Tương tự như vậy ta chứng minh được con cào cào sẽ nhảy đến vị trí của đỉnh B. Bây giờ ta chứng minh nếu con cào cào đứng tại điểm A(x, y) thì nó có thể nhảy đến điểm B(x + 1, y). Do (b, 2017) = 1 nên tồn tại c nguyên dương sao cho bc ≡ 1(mod2017) hay tồn tại k nguyên dương thỏa bc = 2017k + 1. Theo hướng dương của trục Ox ta dựng dãy c hình chữ nhật liên tiếp nhau như hình vẽ.

Khi đó độ dài đoạn AN = 2017k + 1. Theo chứng minh trên con cào cào từ một đỉnh của hình chữ nhật có thể nhảy đến các đỉnh khác của hình chữ nhật đó nên nó có thể nhảy từ đỉnh A đến đỉnh N . Tại N con cào cào nhảy theo hướng N A đúng k bước thì nó sẽ đến điểm B(x + 1, y). Chứng minh tương tự ta có con cào cào có thể nhảy đến các điểm (x − 1, y), (x, y − 1), (x, y + 1). Như vậy con cào cào có thể nhảy đến tất cả các điểm nguyên trên mặt phẳng tọa độ. Nhận xét. Trong câu 1, chỉ cần biết kiến thức số học cơ bản: "Tổng bình phương của hai số chia hết cho 3 khi và chỉ khi cả hai số đó chia hết cho 3", thay số 3 bằng số nguyên tố p = 4k + 3. Mấu chốt của câu 2, chúng ta phải biết kiến thức số học sau: "Số nguyên tố p được phân tích thành tổng bình phương của hai số chính phương khi và chỉ khi p = 4k + 1". Với nhận xét trên thì trong câu 2 ta có thể thay số 2017 bằng một số nguyên

tố bất kì có dạng p = 4k + 1. Bài toán 2.10. (VMO-2013) Tìm số các bộ sắp thứ tự (cid:0)a, b, c, a(cid:48), b(cid:48), c(cid:48)(cid:1) thỏa mãn:

 

ab + a(cid:48)b(cid:48) ≡ 1 (mod15) bc + b(cid:48)c(cid:48) ≡ 1 (mod15) ca + c(cid:48)a(cid:48) ≡ 1 (mod15)



với a, b, c, a(cid:48), b(cid:48), c(cid:48) là các số thuộc tập hợp {0, 1, ..., 14}. Phân tích - Lời giải. Trước hết, theo định lý phần dư Trung Hoa, ta có: Nếu x ≡ a (mod3) , (0 ≤ a ≤ 2) và x ≡ a (mod5) , (0 ≤ a ≤ 4) thì tồn tại duy nhất số c, 0 ≤ c ≤ 14 sao cho x ≡ c (mod15). Do đó, ta sẽ đếm số các bộ (cid:0)a, b, c, a(cid:48), b(cid:48), c(cid:48)(cid:1) mà

 

ab + a(cid:48)b(cid:48) ≡ 1 (mod3) bc + b(cid:48)c(cid:48) ≡ 1 (mod3) ca + c(cid:48)a(cid:48) ≡ 1 (mod3)



với a, b, c, a(cid:48), b(cid:48), c(cid:48) ∈ {0, 1, 2}. Giả sử số bộ này là A. Tiếp theo, ta đếm số bộ (cid:0)a, b, c, a(cid:48), b(cid:48), c(cid:48)(cid:1) mà

 

ab + a(cid:48)b(cid:48) ≡ 1 (mod5) bc + b(cid:48)c(cid:48) ≡ 1 (mod5) ca + c(cid:48)a(cid:48) ≡ 1 (mod5) với a, b, c, a(cid:48), b(cid:48), c(cid:48) ∈ {0, 1, 2, 3, 4}. Giả sử bộ này là B. Khi đó ứng với mỗi bộ A và mỗi bộ B thì sẽ tương ứng một bộ 6 số thỏa mãn đề bài, tức là ta cần tìm tích AB.



Đếm số bộ A. Trước hết ta thấy rằng (cid:0)ab, a(cid:48)b(cid:48)(cid:1) , (cid:0)bc, b(cid:48)c(cid:48)(cid:1) , (cid:0)ca, c(cid:48)a(cid:48)(cid:1) đều không cùng chia hết cho 3 nên dễ thấy rằng abc, a(cid:48)b(cid:48)c(cid:48) cũng không cùng chia hết cho 3 (nếu không thì sẽ có một trong 3 bộ kia chia hết cho 3, mâu thuẫn). Giả sử abc không chia hết cho 3, do chỉ có hai số dư 1, 2 nên sẽ có hai trong ba số a, b, c đồng dư với nhau theo modulo 3. Tiếp tục giả sử đó là a, b nên ab ≡ 1 (mod3). Khi đó, tương ứng a(cid:48)b(cid:48) ≡ 0 (mod3) . Nếu a(cid:48) chia hết cho 3 thì lại suy ra tiếp c(cid:48)a(cid:48) chia hết cho 3 hay ca ≡ 1 (mod3), tức là a ≡ c (mod3). Vì b, c đồng dư nhau theo modulo 3 nên tương ứng nên bc chia 3 dư 1, dẫn đến b(cid:48)c(cid:48) chia hết cho 3 và suy ra thêm một trong hai số b(cid:48), c(cid:48) chia hết cho 3. Từ đó, do tính bình đẳng của a, b, c và a(cid:48), b(cid:48), c(cid:48) ta suy ra rằng cả ba số a, b, c không chia hết cho 3 và đồng dư với nhau theo modulo 3; trong các số a(cid:48), b(cid:48), c(cid:48) thì có hai số chia hết cho 3 số còn lại tùy ý.

A = 2.2.7 = 28.

Có hai cách chọn bộ (a, b, c) và 7 cách chọn bộ (cid:0)a(cid:48), b(cid:48), c(cid:48)(cid:1) (vì có một cách chọn bộ (0, 0, 0), có ba cách chọn bộ (0, 0, 1) và hoán vị của nó, ba cách chọn bộ (0, 0, 2) và hoán vị của nó). Tương tự trường hợp a(cid:48)b(cid:48)c(cid:48) không chia hết cho 3. Do đó, số bộ trong trường hợp này là:

Đếm các bộ B. Các số dư khi chia cho 5 là 0, 1, 2, 3, 4 và ta thấy các tích

1 × 2 ≡ 2, 1 × 3 ≡ 3, 1 × 4 ≡ 4, 2 × 2 ≡ 4,

2 × 3 ≡ 1, 2 × 4 ≡ 3, 3 × 3 ≡ 4, 3 × 4 ≡ 2, 4 × 4 ≡ 1. Tương tự như trên các số abc, a(cid:48)b(cid:48)c(cid:48) không cùng chia hết cho 5. Ta xét các trường hợp sau đây:

của các bộ sau sẽ có số dư tương ứng khi chia cho 5 được liệt kê bên dưới:

• Nếu a(cid:48) chia cho 5 dư 1 thì b(cid:48), c(cid:48) chia cho 5 dư 1 và dẫn đến bc chia hết cho 5 và có thêm một trong hai số chia hết cho 5. Khi đó, các bộ (a, b, c) mà hai trong ba số đó chia hết cho 5 và (cid:0)a(cid:48), b(cid:48), c(cid:48)(cid:1) = (1, 1, 1) thỏa mãn đề bài. Có tất cả 13 × 1 = 13 bộ như thế.

• Nếu a(cid:48) chia cho 5 dư 4 thì b(cid:48), c(cid:48) chia cho 5 dư 4 và dẫn đến bc chia hết cho 5 và có thêm một trong hai số chia hết cho 5. Khi đó, các bộ (a, b, c) mà hai trong ba số đó chia hết cho 5 và (cid:0)a(cid:48), b(cid:48), c(cid:48)(cid:1) = (4, 4, 4) thỏa mãn đề bài. Có tất cả 13 × 1 = 13 bộ như thế.

• Nếu a(cid:48) chia cho 5 dư 2 thì b(cid:48), c(cid:48) chia cho 5 dư 3 và dẫn đến bc chia cho 5 dư 2 . Khi đó, các bộ (a, b, c) = (0, 1, 2), (0, 3, 4) và (cid:0)a(cid:48), b(cid:48), c(cid:48)(cid:1) = (2, 3, 3) thỏa mãn đề bài. Có tất cả 6 × 2 = 12 bộ như thế.

• Nếu a(cid:48) chia cho 5 dư 3 thì b(cid:48), c(cid:48) chia cho 5 dư 2 và dẫn đến bc chia cho 5 dư 2. Khi đó, các bộ (a, b, c) = (0, 1, 2), (0, 3, 4) và (cid:0)a(cid:48), b(cid:48), c(cid:48)(cid:1) = (3, 2, 2) thỏa mãn đề bài. Có tất cả 6 × 2 = 12 bộ như thế.

Trường hợp 1. Nếu abc hoặc a(cid:48)b(cid:48)c(cid:48) chia hết cho 5, giả sử abc chia hết cho 5 và tiếp tục giả sử a chia hết cho 5 thì a(cid:48)b(cid:48) và a(cid:48)c(cid:48) chia cho 5 dư 1. Ta xét tiếp các trường hợp sau đây:

2 × (13 + 13 + 12 + 12) = 100

Trong trường hợp này số bộ thỏa mãn:

(2, 2, 2) , (2, 2, 3) , (2, 2, 4) , (2, 3, 3) ,

(2, 4, 4) , (3, 3, 3) , (3, 3, 4) , (3, 4, 4) .

Trường hợp 2. Cả hai số abc và a(cid:48)b(cid:48)c(cid:48) đều không chia hết cho 3. Khi đó, ta thấy ab, bc, ca chỉ có thể chia cho 5 dư 2, 3, 4 vì nếu chia cho 5 dư 1 thì có bộ a(cid:48)b(cid:48), b(cid:48)c(cid:48), c(cid:48)a(cid:48) chia hết cho 5 mâu thuẫn. Ta thấy các số dư của (ab, bc, ca) khi chia cho 5 không thể là một trong các bộ sau:

• Nếu (ab, bc, ca) = (2, 3, 4) thì (cid:0)a(cid:48)b(cid:48), b(cid:48)c(cid:48), c(cid:48)a(cid:48)(cid:1) = (4, 3, 2) thì ta thu được

Thật vậy, chẳng có bộ (2, 2, 2), ta có ab = bc = ca = 2, dẫn đến 2c2 = 4, vô lí. Tương tự với các trường hợp còn lại. Do đó, các bộ số dư này chỉ có thể (2, 3, 4), (4, 4, 4).

(4, 3, 1, 1, 4, 2) , (1, 2, 4, 1, 4, 2) , (4, 3, 1, 4, 1, 3) , (1, 2, 4, 4, 1, 3) .

(cid:0)a, b, c, a(cid:48), b(cid:48), c(cid:48)(cid:1) tương ứng với một trong bốn trường hợp sau:

• Nếu (ab, bc, ca) = (4, 4, 4) thì (cid:0)a(cid:48)b(cid:48), b(cid:48)c(cid:48), c(cid:48)a(cid:48)(cid:1) = (2, 2, 2) không thỏa

Có tất cả 6.4 = 24 bộ thỏa mãn (ứng với mỗi hoán vị của ba số đầu thì tồn tại duy một dãy thứ tự cho 3 số sau và các hoán vị của các bộ khác nhau).

mãn.

B = 100 + 24 = 124.

Vậy tổng số bộ cần tìm trong trường hợp 2 bằng 24. Từ đó tính được tổng số bộ trong trường hợp 2 là:

28 × 124 = 3472.

Từ đó tính được tổng số bộ cần tìm là:

Nhận xét. Đây là bài toán dạng số học - tổ hợp khó. Bài toán này phải biết cách sử dụng định lý phần dư Trung hoa về số dư dưới góc độ ánh xạ "phục hồi" φ : Zpq → Zp × Zq. Một số thuộc Zpq được xác định một cách duy nhất qua cặp số dư của nó khi chia cho p và q. Từ đó chuyển các bài toán trên Zpq về các bài toán trên Zp và Zq.

Bài toán 2.11. (Bungary 99, vòng 4) Tìm tất cả các số có n chữ số dạng a1a2...an với ai ∈ {0, 1, ..., 9} , i = 1, n và thỏa mãn

(a1a2 + a2a3 + ... + an−1an)

...2.

...2. ...2 thì a2 tùy ý và nếu a1 không chia hết cho 2 thì a2

...2.

...2 hay ...2 thì a1, a3 tùy ý và nếu a2 không chia hết cho 2 thì (a1 + a3)

Phân tích - Lời giải. Như chúng ta biết, tổng của hai số chia hết cho 2 khi chúng có cùng tính chẵn, lẻ và tích của hai số chia hết cho 2 khi trong hai số đó phải có ít nhất một số chẵn. Từ điều kiện bài toán, gợi ý cho chúng ta sử dụng phương pháp thiết lập hệ thức truy hồi. Với mọi số tự nhiên n ≥ 2, gọi Sn là số tất cả các số có n chữ số thỏa mãn điều kiện bài toán và An tập hợp các số thỏa mãn bài toán. Với n = 2, nếu a1 Do đó S2 = 40 + 25 = 65. Với n = 3, theo đề bài a1a2 + a2a3 = a2 (a1 + a3) Nếu a2 a1, a3 cùng tính chẵn, lẻ. Do đó S3 = 5.9.10 + 5.4.5 + 5.5.5 = 675. Với n ≥ 4 xét các số a1a2...an thỏa mãn điều kiện bài toán.

Trường hợp an−1 chẵn.

Giả thiết ta có

(a1a2 + a2a3 + ... + an−1an)

...2,

suy ra

(a1a2 + a2a3 + ... + an−3an−2)

...2.

Ngược lại, với mỗi an−1, an cố định, một số trong trường hợp này tương ứng với một số a1a2...an−2 ∈ An−2. Do đó có Sn−2 số thỏa mãn với mỗi an−1, an cố định. Có 5.10 = 50 cách chọn 2 số an−1, an. Vậy khi an−1 chẵn có 50.Sn−2 số thỏa mãn.

Trường hợp an−1 lẻ.

an−1an ≡ − (a1a2 + ... + an−2an−1) (mod2) .

Với mỗi cách chọn (a1, a2, ..., an−1) luôn tồn tại 5 cách chọn an sao cho

Sn = 50Sn−2 + 225.10n−3, n ≥ 4.

Vậy khi an−1 lẻ có 9.10n−3.5.5 = 225.10n−3 số. Cuối cùng ta có công thức truy hồi

√

Giải phương trình sai phân ta được

−

10n.

Sn =

9 20

9 + 2 √ 10

−9 + 2 √ 10

(cid:16)√ (cid:17)n (cid:16) (cid:17)n

Bài toán 2.12. Tìm tất cả các tập hợp A = {a1, a2, ..., an; n > 2012} gồm những số nguyên và có tính chất sau: 2012 ∈ A, đồng thời mỗi tập con tùy

2011 (cid:88)

xi + x ≡

xi + y (mod4) ⇔ x ≡ y (mod4) , xi ∈ A.

i=1

ý gồm 2012 số thuộc A đều có thể chia thành 4 nhóm có số phần tử bằng nhau và tổng các số trong mỗi nhóm bằng nhau. Phân tích - Lời giải. Điều kiện bài toán cho ta thấy rằng, tổng của 2012 số tùy ý thuộc A là một số chia hết cho 4. Thay từ tập hợp phần tử một phần tử bất kỳ bởi một phần tử khác tùy ý không thuộc tập đã chọn, tính chất tổng chia hết cho 4 vẫn không thay đổi. Từ đó suy ra mọi phần tử của tập A đều đồng dư nhau modulo 4. Thật vậy, với x, y ∈ A ta có

Dĩ nhiên ta nẩy sinh ra dự đoán rằng, các phần tử của A đều bằng nhau. Để kiểm tra dự đoán này, ta xét phần tử nhỏ nhất của A: a. Khi đó tập hợp B = {a1 − a, a2 − a, ..., an − a} rõ ràng thỏa mãn tính chất đã nêu trong bài toán như đối với tập hợp A. Do đó, mọi phần tử của B cũng đồng dư nhau modulo 4, và vì B chứa phần tử bằng 0 nên suy ra mọi phần tử của B đều chia hết cho 4. Từ đây, suy luận “quy nạp lùi” quen thuộc cho ta lời giải: Tập

b 4

cũng có tính chất hợp nhận được từ B bằng cách thay phần tử b ∈ B bởi

nêu trong bài ra; và do đó các phần tử của tập hợp này cũng chia hết cho 4. Tiếp tục quá trình, dễ suy ra mọi phần tử của B đều bằng 0. Như vậy, mọi phần tử của A đều bằng 2012.

n + 1 = 2k13l1, n + 2 = 2k23l2, n + 3 = 2k33l3, n + 4 = 2k43l4,

Bài toán 2.13. (IMO-1970) Tìm tất cả các số nguyên dương n có tính chất sau: có thể phân hoạch tập hợp 6 số {n, n + 1, n + 2, n + 3, n + 4, n + 5} thành hai tập hợp, sao cho tích của các số thuộc tập này bằng tích của các số thuộc tập kia. Phân tích - Lời giải. Ta nhận thấy rằng trong 5 số nguyên liên tiếp phải có một và chỉ một số chia hết cho 5. Vì vậy, nếu tập hợp 6 số {n, n + 1, n + 2, n + 3, n + 4, n + 5} với tính chất đã nêu trong đề bài, thì tập hợp đó phải có đúng hai số chia hết cho 5, dĩ nhiên đó là các số n và n + 5, còn các số n + 1, n + 2, n + 3, n + 4 không chia hết cho 5. Mặt khác, nếu một số trong 6 số của tập hợp trên chia hết cho một số nguyên tố p ≥ 7, thì 5 số còn lại sẽ không chia hết cho p, vì vậy tập hợp không có tính chất đòi hỏi. Từ đây suy ra các số còn lại chỉ chứa các thừa số nguyên tố là 2 và 3, tức là

trong đó k1, l1, ..., k4, l4 là những số nguyên không âm. Nếu n + 1 chia hết cho 3 thì n + 4 chia hết cho 3 và n + 2, n + 3 không chia hết cho 3, vậy l2 = l3 = 0 và n + 2 = 2k2, n + 3 = 2k3. Khi đó, n + 2 và n + 3 là hai số nguyên dương liên tiếp và là số chẵn, điều này mâu thuẫn. Lí luận tương tự, ta thấy rằng n + 2 hoặc n + 3 chia hết cho 3, đều dẫn đến mâu thuẫn. Mâu thuẫn ấy chứng tỏ rằng không có số nguyên dương n nào thỏa mãn điều kiện bài toán.

Bài toán 2.14. (THTT) Cho X là một tập con của tập {1, 2, 3, ..., 2010} thỏa mãn đồng thời các điều kiện sau đây:

1. |X| = 62.

2. Với mọi x ∈ X đều tồn tại a, b ∈ X ∪ {0; 2011} (a, b đều khác x) sao

a + b 2

cho x =

/∈ X.

|x − y| ≥ 11 và

x + y 2

Chứng minh rằng có hai phần tử x, y của X sao cho

|x − y| ≥ 11 và

/∈ X.

x + y 2

xk + x62 2

Phân tích - Lời giải. Giả sử X có 62 phần tử x1, x2, ..., x62 đã được sắp thứ tự x1 < x2 < ... < x62. Ta chứng minh bài toán bằng phản chứng. Giả sử không tồn tại hai phần tử x, y của X sao cho

Ta chứng minh rằng mọi phần tử của X đều có cùng tính chẵn lẻ. Vì X ⊂ {1, 2, ..., 2010} nên xi+1 ≥ xi + 1 với i = 1, 2, ..., 61. Do đó x62 − xk ≥ 11, với k = 1, 2, ..., 51. Suy ra xk (k = 1, 2, ..., 51) cùng tính chẵn lẻ với x62, vì nếu /∈ X trái không như vậy, tức tồn tại xk khác tính chẵn lẻ x62, thì với giả thiết. Lập luận tương tự, ta thấy xl (l = 12, 13, ..., 62) cùng tính chẵn lẻ với x1. Từ đó suy ra mọi phần tử của X có cùng tính chẵn lẻ. Tiếp theo với giả thiết (2) của bài toán thì tồn tại a, b ∈ X ∪ {0; 2011}, (a (cid:54)= b) sao cho

x62 =

a + b 2

. Vì x62 > x1, i = 1, 2, ..., 61 nên tồn tại xp, với p = 1, 2, ..., 61

xp + 2011 2

i = 2, 3, ..., 61 nên tồn tại xq sao cho x1 =

sao cho x62 = kéo theo xp là một số lẻ. Tương tự, do x1 < xi với

0 + xq 2

, kéo theo xq là một số

|x − y| ≥ 11 và

/∈ X.

chẵn. Vậy xp, xq là hai phần tử của X khác tính chẵn lẻ, trái với kết quả khẳng định trên, tức là điều giả sử sai. Kết luận: Có hai phần tử x, y của X sao cho x + y 2

• Bài toán có thể thay |X| = 33.

• Bài toán tổng quát sau không cần điều kiện 2.

Nhận xét.

|x − y| ≥

− 1 và

x + y 2

Cho X là một tập con của tập {1, 2, 3, ..., n}, |X| = k, (k ∈ N, k ≥ 2) . Chứng minh rằng có hai phần tử x, y của X sao cho (cid:21) không thuộc X. (cid:20)k 2

Bài toán 2.15. (THTT) Chứng minh rằng từ 2n − 1 số nguyên bất kì luôn tìm được n số có tổng chia hết cho n. Phân tích - Lời giải. Với n nhỏ, bài toán có thể chứng minh dễ dàng bằng cách xét các trường hợp. Ví dụ: Với n = 3, ta chia 5 số nguyên vào 3 ô đó là: Ô chia 3 dư 0, ô chia 3 dư 1, ô chia 3 dư 2. Nếu mỗi ô đều chứa ít nhất một số thì chọn từ 3 ô, mỗi ô một số, ta được 3 số cần tìm. Nếu có một ô nào đó rỗng thì ít nhất một ô chứa 3 số và đó là 3 số cần tìm. Với n = 5 ta có thể lặp lại cách chứng minh tương tự, tuy nhiên số trường hợp sẽ xét nhiều hơn.

s1 =

, s2 =

, ..., s5 =

a1 + a2 + a3 3

a3 + a4 + a5 3

a13 + a14 + a15 3

Nếu n là hợp số, chẳng hạn n = 9, ta có thể sử dụng cách làm như sau: áp dụng kết quả với n = 3, từ 17 số {a1, a2, ..., a17}, dĩ nhiên có thể chọn ra 3 số có tổng chia hết cho 3. Không mất tính tổng quát, giả sử đó là a1 + a2 + a3. Tiếp theo, từ 13 số a4, a5, ..., a17, ta có thể chọn được 3 số có tổng chia hết cho 3, giả sử a4 + a5 + a6. Tương tự như vậy, ta có thể chọn được các bộ ba có tổng chia hết cho 3, mà bằng cách đánh số lại nếu cần, giả sử đó là (a7, a8, a9) , (a10, a11, a12) , (a13, a14, a15). Xét các số

a1 + a2 + ... + a9 = 3 (s1 + s2 + s3) ≡ 0 (mod9) .

Theo cách xây dựng, 5 số s1, s2, ..., s5 là các số nguyên. Áp dụng kết quả với n = 3, ta suy ra tồn tại 3 số trong 5 số này có tổng chia hết cho 3. Không mất tính tổng quát, giả sử đó là s1, s2, s3. Khi đó

(ai1 + ai2 + ... + aip)p−1 ≡ 1 (modp) .

Bằng cách làm tương tự, ta thấy rằng nếu bài toán đã đúng với n = p và n = q thì nó cũng đúng với n = pq. Vậy chỉ cần chứng minh bài toán đúng với n = p là số nguyên tố. Giả sử ngược lại, tồn tại 2p − 1 số nguyên a1, a2, ..., a2p−1 sao cho mọi tổng gồm p phần từ đều không chia hết cho p. Khi đó theo định lý nhỏ Fermat, ta có

Từ đó

(ai1 + ai2 + ... + aip)p−1 ≡ C p

2p−1 (modp) .

1≤i1

i2...ask

i1as2

(cid:88)

(p − 1)! s1!s2!...sk!

Do C p 2p−1 không chia hết cho p. Vì thế, sẽ suy ra mâu thuẫn nếu chứng minh được rằng vế trái chia hết cho p. Để chứng minh điều này bằng cách chứng minh trong khai triển tổng vế trái, hệ số của as1 ik (với s1+s2+...+sk = p − 1) chia hết cho p. Để có được số hạng như vậy, cần chọn thêm p − k phần tử ai(k+1), ..., aip để bổ sung thành p số và xét biểu thức (ai1 + ai2 + ... + aip)p−1. Khai triển biểu thức này, ta sẽ được hệ số của as1 i2...ask

ik bằng i1as2

i2...ask

2p−1−k cách bổ sung, do đó hệ số của as1

ik trong khai triển vế trái

. Chú ý rằng 1 ≤ k ≤ p − 1 nên C p−k

2p−1−k

i1as2

i2...ask

(p − 1)! là C p−k 2p−1−k chia hết cho p. s1!s2!...sk! Từ đó, tất cả các số hạng as1 ik trong khai triển ở vế trái đều có hệ số chia hết cho p, tức là vế trái chia hết cho p. Mâu thuẫn. Chứng tỏ điều giả sử sai. Bài toán được chứng minh với n = p và như vậy với n bất kì.

2.1.2 Biểu diễn số

Có C p−k

p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, p8 = 19, p9 = 23.

Bài toán 2.16. (IMO 1985) Xét tập hợp M gồm 1985 số nguyên dương phân biệt, sao cho không có số nào có ước số nguyên tố lớn hơn 23. Chứng minh rằng M chứa một tập con gồm 4 phần tử mà tích của 4 phần tử này là lũy thừa bậc 4 của một số nguyên. Phân tích - Lời giải. Có 9 số nguyên tố không vượt quá 23 là

k = a2pα1

1 pα2

2 ...pα9 9 ,

Viết các số k của tập M dưới dạng

a1b1 = c2

1, a2b2 = c2

2, ..., a513b513 = c2

513.

trong đó a ∈ N và αi ∈ {0, 1} . Do số bộ phân biệt (x1, x2, ..., x9) với xi ∈ {0, 1} là 29 = 512 nên nếu 513 phần tử phân biệt của M thì theo nguyên tắc Dirichlet, tồn tại hai bộ (α1, α2, ..., α9) trùng nhau. Tương ứng với hai bộ đó ta được hai số trong M có tích là số chính phương. Giả sử hai số đó là a1, b1. Loại bỏ hai phần tử a1, b1 và xét 513 phần tử của M trong các số còn lại ta suy ra có hai phần tử a2, b2 có tích là số chính phương. Tiếp tục quá trình trên ta nhận được 513 cặp (a1, b1) , (a2, b2) , ..., (a513, a513) mà mỗi cặp có tích hai phần tử là một số chính phương. Bây giờ đặt

B là lập phương của một số tự nhiên.

Xét 513 số c1, c2, ..., c513. Vì các ci cũng chỉ có các ước nguyên tố không vượt quá 23 nên ta suy ra có hai số cm, cn có tích là một số chính phương. Khi đó 4 số am, bm, an, bn có tích là lũy thừa bậc 4 của một số nguyên. Nhận xét. Thường để chứng minh tích của các số là lũy thừa của một số tự nhiên, ta hay phân tích các số ra thừa số nguyên tố, vì yêu cầu chứng minh sự tồn tại nên ta nghĩ ngay đến nguyên lý Dirichlet. Với cách làm hoàn toàn tương tự, ta có bài toán sau đây:

p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, p6 = 13, p7 = 17, p8 = 19, p9 = 23, p10 = 29, p11 = 31, p12 = 37, p13 = 41, p14 = 43, p15 = 47, p16 = 53, p17 = 59, p18 = 61, p19 = 67, p20 = 71, p21 = 73, p22 = 79, p23 = 83, p24 = 89, p25 = 97.

1 pα2

2 ...pα25

25 trong đó αi ∈ {0, 1, 2}.

• Nếu A ∩ B = ∅ thì tAt2

Bài toán 2.17. (THTT) Cho S là tập hợp gồm 43 phần tử là các số nguyên dương không vượt quá 100. Với mỗi tập con X của S, đặt tX là tích các phần tử của X. Chứng minh rằng tồn tại hai tập A, B không giao nhau của S sao cho tAt2 Phân tích - Lời giải. Có tất cả 25 số nguyên tố bé hơn 100 đó là

• Nếu hai trong ba tập đó có hai tập không phải là tập con của nhau và giao nhau khác rỗng, chẳng hạn đó là A, B thì đặt A1 = A\B; B1 =

Với mỗi tập con X của S, ta viết tX duy nhất dưới dạng tX = x3.mX trong đó mX = pα1 Như vậy có nhiều nhất 325 giá trị có thể của mX. Mặt khác số các tập con khác rỗng của S là 243 − 1 > 325.2, nên theo nguyên lý Dirichlet tồn tại ba tập con khác rỗng A, B và C của S sao cho mA = mB = mC = k. Giả sử tA = a3k, tB = b3k, tB = b3k. B = (cid:0)ab2k(cid:1)3 bài toán được giải.

B\A, ta có A1 ∩ B1 = ∅, A1 (cid:54)= ∅, B1 (cid:54)= ∅. Chú ý rằng các phần tử của A ∩ B xuất hiện đúng 3 lần trong tích tAt2

B nên

tAt2

t3 A∩B.

B = tA1t2 B1

B là lập phương của một số tự nhiên nên

tA1t2 B1

tAt2 B t3 A∩B

Do tAt2

tAt2

tBt2 C.

• Nếu A ⊂ B ⊂ C thì đặt A1 = A\B, B1 = B\C. Khi đó A1 ∩ B1 = ∅, A1 (cid:54)= ∅, B1 (cid:54)= ∅. Do đó B = tA1tB(tB1tC)2 = tA1t2 B1

là lập phương của một số tự nhiên.

tA1t2 B1

a3b6 b3c6 =

Suy ra (cid:19)3

tAt2 B tBt2 C

(cid:18)ab c2

là lập phương của một số tự nhiên.

Tóm lại, bài toán được chứng minh hoàn toàn.

[a, b, c] = 233557711.

Bài toán 2.18. Có bao nhiêu bộ sắp thứ tự (a, b, c) với a, b, c là các số nguyên dương thỏa mãn

a = 2a13a25a37a4; b = 2b13b25b37b4; c = 2c13c25c37c4,

(Kí hiệu [a, b, c] là bội chung nhỏ nhất của ba số a, b, c). Phân tích - Lời giải. Vì 2, 3, 5, 7 là các số nguyên tố nên giả sử

[a, b, c] = 233557711

trong đó 0 ≤ a1, b1, c1 ≤ 3; 0 ≤ a2, b2, c2 ≤ 5; 0 ≤ a3, b3, c3 ≤ 7; 0 ≤ a4, b4, c4 ≤ 11. Khi đó

max {a1, b1, c1} = 3, max {a2, b2, c2} = 5, max {a3, b3, c3} = 7, max {a4, b4, c4} = 11.

khi và chỉ khi

Đếm tất cả các bộ có thứ tự gồm các số nguyên không âm (a1, b1, c1) sao cho max {a1, b1, c1} = 3.

Cách 1: Đếm trực tiếp.

A = {(x, y, z) ∈ Z × Z × Z|x = 3, 0 ≤ y, z ≤ 3} .

B = {(x, y, z) ∈ Z × Z × Z|y = 3, 0 ≤ x, z ≤ 3} .

C = {(x, y, z) ∈ Z × Z × Z|z = 3, 0 ≤ x, y ≤ 3} .

Đặt

|A| = |B| = |C| = 16, |A ∩ B| = |B ∩ C| = |C ∩ A| = 4, |A ∩ B ∩ C| = 1.

Khi đó, A ∪ B ∪ C là tập hợp tất cả các bộ có thứ tự gồm các số nguyên không âm (a1, b1, c1) sao cho max {a1, b1, c1} = 3. Dễ dàng tính được

|A ∪ B ∪ C| = (|A| + |B| + |C|)−(|A ∩ B| + |B ∩ C| + |C ∩ A|)+|A ∩ B ∩ C|

= 3.16 − 3.4 + 1 = 37.

Theo nguyên lý bù trừ ta có:

Vậy số tất cả các bộ có thứ tự gồm các số nguyên không âm (a1, b1, c1) sao cho max {a1, b1, c1} = 3 bằng 37. Tương tự: Số tất cả các bộ có thứ tự gồm các số nguyên không âm (a2, b2, c2) sao cho max {a2, b2, c2} = 5 bằng 91. Số tất cả các bộ có thứ tự gồm các số nguyên không âm (a3, b3, c3) sao cho max {a3, b3, c3} = 7 bằng 169. Số tất cả các bộ có thứ tự gồm các số nguyên không âm (a4, b4, c4) sao cho max {a4, b4, c4} = 11 bằng 397. Theo quy tắc nhân số tất cả các bộ số nguyên dương (a, b, c) thỏa mãn bài toán bằng 37.91.169.397 = 225902131.

Cách 2: Đếm phần bù.

- Số tất cả các bộ có thứ tự gồm các số nguyên (a1, b1, c1) trong đó a1, b1, c1 ∈ {0, 1, 2, 3} bằng 43. - Số tất cả các bộ có thứ tự gồm các số nguyên (a1, b1, c1) trong đó a1, b1, c1 ∈ {0, 1, 2} bằng 33. Như vậy, số tất cả các bộ có thứ tự gồm các số nguyên không âm (a1, b1, c1) sao cho max {a1, b1, c1} = 3 bằng 43 − 33 = 37. Tương tự: Số tất cả các bộ có thứ tự gồm các số nguyên không âm (a2, b2, c2) sao cho max {a2, b2, c2} = 5 bằng 91.

Số tất cả các bộ có thứ tự gồm các số nguyên không âm (a3, b3, c3) sao cho max {a3, b3, c3} = 7 bằng 169. Số tất cả các bộ có thứ tự gồm các số nguyên không âm (a4, b4, c4) sao cho max {a4, b4, c4} = 11 bằng 397. Theo quy tắc nhân số tất cả các bộ số nguyên dương (a, b, c) thỏa mãn bài toán bằng 37.91.169.397 = 225902131. Nhận xét. Rõ ràng trước tiên phải tìm BCNN của các số tự nhiên, còn lại chúng ta có thể đếm trực tiếp hoặc phần bù. Hoàn toàn tương tự chúng ta có bài toán tổng quát.

[a1, a2, ..., an] = pα1

1 pα2

2 ....pαm m ,

(cid:0)i = 1, n(cid:1) là các số nguyên dương thỏa mãn Bài toán 2.19. (Tổng quát) Có bao nhiêu bộ có thứ tự (a1, a2, ..., an) với ai

ai = pxi1

1 pxi2

2 ...pxim m ,

trong đó p1, p2, ..., pm là các số nguyên tố đôi một khác nhau và α1, α2, ..., αm là các số nguyên dương. Phân tích - Lời giải. Vì p1, p2, ..., pm là các số nguyên tố nên giả sử

[a1, a2, ..., an] = pα1

1 pα2

2 ....pαm m

trong đó 0 ≤ xik ≤ αk, i = 1, n, k = 1, m. Khi đó

max (cid:8)xik|i = 1, n(cid:9) = αk; k = 1, m.

khi và chỉ khi

(α1 + 1)n − αn 1 .

Đếm tất cả các bộ gồm các số nguyên không âm có thư tự (x11, x21, ..., xn1) thỏa mãn max {x11, x21, ..., xn1} = α1. Đếm phần bù như bài toán trên, số các bộ (x11, x21, ..., xn1) bằng

[(α1 + 1)n − αn

1 ] . [(α2 + 1)n − αn

2 ] ... [(αm + 1)n − αn

m] .

Tương tự ta đếm được các bộ còn lại. Theo quy tắc nhân số bộ thỏa mãn bài toán là:

x y

Bài toán 2.20. Giả sử c là số hữu tỉ dương khác 1. Chứng minh rằng có thể phân hoạch tập hợp các số nguyên dương thành hai tập khác nhau A, B sao (cid:54)= c với mọi x, y cùng nằm trong tập A hoặc cùng nằm trong tập B. cho

p q

Phân tích - Lời giải. Đặt c = , với p, q là hai số nguyên tố cùng nhau.

Trước hết ta thấy rằng các số không chia hết cho p và không chia hết cho q thì đặt chúng thuộc tập hợp A hoặc thuộc tập B đều được, chúng không ảnh hưởng gì đến tính chất của tập hợp. Bây giờ ta xét tất cả các số chia hết cho p hoặc q, chúng có dạng k.pmqn với k là số không chia hết cho p và q và m + n > 0. Chia các số đó thành các nhóm dựa vào bậc m + n của chúng. Ta nhận thấy các số có bậc khác nhau thì có thể ở chung một tập hợp. Vấn đề bây giờ còn lại là chia các số có cùng bậc vì chính các số này ở chung một tập hợp thì sẽ gây ra vấn đề. Nhận thấy là cần tránh thương của chúng có p bậc 1 (lẻ), nên chỉ với việc chia các số có cùng bậc thành các số có bậc p chẵn chung một tập hợp và bậc p lẻ chung một tập hợp. Ví dụ với bậc 5: Nếu k.p2q3, kp4q, kq5 ở tập A thì k.pq4, kp3q2, kp5 ở tập B với k không chia hết cho p và q,... Theo cách chia như trên ta thấy đã phân hoạch toàn bộ tập hợp số nguyên dương thành hai tập thỏa mãn yêu cầu bài toán. Nhận xét. Để tìm được lời giải bài toán trên xét p = 2 và q = 3, làm rõ ràng trong trường hợp này ta tìm được lời giải tổng quát trên.

Bài toán 2.21. Sau giờ học, các em học sinh xếp hàng để nhận xe đạp ở nhà gửi xe. Giá tiền gửi mỗi xe là 1000 đồng. Giả sử có k em học sinh có tờ 1000 đồng, m em học sinh có tờ 2000 đồng. Hỏi có bao nhiêu cách xếp hàng lấy xe sao cho không em nào phải chờ để lấy tiền trả lại? (với giả thiết người giữ xe không có tiền lẻ nào). Phân tích - Lời giải.

Cách 1. Sử dụng phương pháp song ánh.

Đây là một bài toán thuộc loại “hai khả năng”: Mỗi em học sinh hoặc có tờ 100 đồng, hoặc có tờ 2000 đồng. Như vậy, để dễ thấy bản chất của bài toán, ta có thể lập tương ứng mỗi hàng học sinh với một dãy gồm hai chữ số 0, 1. Giả sử, ứng với học sinh có tờ 1000 trong hàng, ta viết chữ số 0; ứng với học sinh có tờ 2000 đồng, ta viết số 1. Như vậy, mỗi hàng học sinh tương ứng một dãy gồm k chữ số 0 và m chữ số 1. Để tồn tại cách xếp mà không có em nào phải chờ lấy tiền trả lại, điều kiện cần là k ≥ m. Cũng tương tự như trong nhiều bài toán tổ hợp khác, khi đếm số phần tử

C k

m+k − C k+1 m+k.

thỏa mãn bài ra là khó, ta đếm “phần bù” của nó, tức là những phần tử không thỏa mãn bài ra. Như vậy, ở đây ta sẽ xét xem có bao nhiêu hàng mà có học sinh nào đó đến lượt mình phải chờ lấy tiền trả lại. Theo cách tương ứng của chúng ta, một hàng như vậy sẽ tương ứng một – một với một dãy gồm k số 0, m số 1, trong đó tồn tại vị trí 2s + 1 sao cho tại đó có số 1, đồng thời ở 2s vị trí đầu, số số 0 và số số 1 là như nhau. Ta gọi một hàng như vậy là hàng "xấu". Nếu bạn là người giữ xe thì bạn sẽ làm như thế nào trong tình huống đó? Hiển nhiên là gọi tên một bạn nào đó có tờ 1000 đồng lên đứng trước hàng! Phương pháp “thực tiễn” này gợi cho ta lập tương ứng mỗi hàng xấu gồm k chữ số 0, m chữ số 1 với một hàng gồm k + 1 chữ số 0, m chữ số 1, với chữ số 0 đứng đầu. Đồng thời trong 2s + 2 vị trí đầu tiên, số chữ số 0 và số chữ số 1 là như nhau. Nếu ta đổi số 0 thành số 1, số 1 thành số 0 ở vị trí đầu, một hàng như trên sẽ tương ứng một hàng gồm k + 1 chữ số 0, m chữ số 1, với chữ số 1 đứng đầu tiên. Lại bỏ đi số 1 đứng tiên này, ta được một hàng gồm k + 1 chữ số 0 và m − 1 chữ số 1. Vậy, mỗi hàng xấu gồm k chữ số 0, m chữ số 1 sẽ được tương ứng với một hàng gồm k + 1 chữ số 0, m − 1 chữ số 1 theo cách trên đây. Dễ thấy rằng, tương ứng trên là một – một. Thật vậy, xét một hàng tùy ý gồm k + 1 chữ số 0, m − 1 chữ số 1. Ta thêm số 1 vào đầu hàng, để được k + 1 chữ số 0, m chữ số 1. Do điều kiện k ≥ m nên trong hàng này phải tồn tại vị trí 2s + 1 mà từ đó trở lên, số số 0 bằng số số 1. Ta đổi số 0 thành số 1 và ngược lại ở các vị trí từ đó trở lên, để được một hàng gồm k + 1 chữ số 0, m chữ số 1, với chữ số 0 đứng đầu tiên. Bỏ số 0 đầu tiên này ta được một hàng "xấu". Từ những tương ứng trên ta suy ra rằng, số các hàng xấu gồm k chữ số 0, m chữ số 1 bằng số các hàng tùy ý với k + 1 chữ số 0, m − 1 chữ số 1, tức là bằng C k+1 m+k. Như vậy, số cách xếp hàng sao cho không học sinh nào phải chờ lấy tiền trả lại là

m+n.

Cách 2. Sử dụng phương pháp quỹ đạo.

Bổ đề 1. Số đường đi ngắn nhất trên lưới nguyên từ điểm O(0, 0) đến điểm B(m, n) bằng C m Bổ đề 2. Số đường đi ngắn nhất trên lưới nguyên từ điểm O(0, 0) đến điểm B(m, n) cắt đường thẳng y = x − 1 bằng số đường đi từ điểm A(1, −1) đến điểm B bằng C n+1 m+n.

Trở lại bài toán.

m+k.

m+k−1.

Gọi si số tờ tiền 1000 đồng có trong túi người giữ xe khi i đi ra.

C k

m+k − C k+1 m+k.

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

Dễ thấy s0 = 0 và sm+k = 0. Hơn nữa si+1 = si ± 1 (vì nếu em nào ra mang tờ tiền 1000 đồng thì cộng 1, mang tờ 2000 đồng thì trừ 1). Nhận thấy để không có ai phải chờ trả tiền lại thì si ≥ 0 ở tại mọi thời điểm. Đếm trực tiếp bài toán này khó nên ta có đếm phần bù. Số cách xếp hàng có thể chính bằng số đường đi ngắn nhất từ điểm O(0, 0) đến điểm B(m, k) bằng C k Số cách xếp hàng không thỏa mãn bài toán bằng số đường đi ngắn nhất trên lưới nguyên từ điểm O(0, 0) đến điểm B(m, k) cắt đường thẳng y = x − 1 bằng số đường đi từ điểm A(1, −1) đến điểm B bằng C k+1 Như vậy, số cách xếp hàng sao cho không học sinh nào phải chờ lấy tiền trả lại là

Phần này chúng tôi xét một số bài toán tổ hợp, mà để giải quyết chúng

thì phải cần các kiến thức về ước chung lớn nhất.

R1R2 R1 + R2

là

một mạch điện có điện trở tương đương là với ƯCLN(a, b) = 1 thì cần bao Bài toán 2.22. Hai điện trở R1, R2 nếu được mắc nối tiếp thì điện trở tương đương là R1 + R2, còn nếu mắc song song thì điện trở tương đương . Biết rằng tất cả các điện trở đều có giá trị bằng 1, hỏi để mắc a b

a + b b

, còn nếu mắc song song thì được thì sẽ được điện trở tương đương

a a + b

nhiêu điện trở đơn vị (việc mắc là tùy ý)? Phân tích - Lời giải. Ta thấy rằng khi mắc nối tiếp các điện trở đơn vị vào mạch điện có giá trị a b điện trở tương đương .

a b

Kí hiệu, bộ (a, b) cho phân số thì có thể thấy từ một bộ (a, b), ta sẽ đưa

về một trong hai bộ (a + b, b) hoặc (a, a + b). Ngược lại, một bộ (a, b) được sinh ra từ bộ (a − b, b) nếu a > b hoặc (a, b − a) nếu b > a. Rõ ràng, do ƯCLN(a, b) = 1 nên theo thuật toán Euclid a = b chỉ xảy ra cuối cùng khi a = b = 1. Do đó, một bộ (a, b) được sinh ra một cách duy

nhất từ một bộ nào đó. Rõ ràng đây chính là các bước thực hiện các bước của thuật toán Euclid. Vì thế nên số điện trở cần tìm chính bằng số các bước của thuật toán Euclid với hai số nguyên dương a, b cộng thêm 1. Ví dụ. (7, 3) → (3, 4) → (3, 1) → (2, 1) → (1, 1) thuật toán Euclid được hiện qua 4 bước nên cần tổng cộng 5 điện trở.

(1) Các bộ có dạng (a, 1) với a > 1 sẽ không bao giờ xuất hiện trong dãy. Thật vậy, điều này dễ thấy do để có được bộ (a, 1) thì phải lần lượt có các bộ sau: (a − 1, 1), (a − 2, 1), ..., (2, 1). Tuy nhiên, quá trình trên không thể tiếp tục được nữa vì bộ (2, 1) không xuất hiện trong dãy ban đầu, nên các bộ có dạng (a, 1) sẽ không bao giờ xuất hiện trong dãy. Do đó, trước hết, ta sẽ loại đi bộ (2012, 1); ngoài ra, còn có bộ (1006, 1007) vì nó không có sẵn trong dãy ban đầu mà được sinh ra từ dãy (1006, 1).

(2) Các số có dạng (x, 2013 − x) với ƯCLN(x, 2013) = 1 không thuộc điều kiện (1) ở trên sẽ xuất hiện trong dãy và xuất hiện đúng 1 lần. Thật vậy, chẳng hạn để chứng minh sự xuất hiện của bộ (x, 2013 − x) trong dãy đã cho, ta chứng minh rằng nó sẽ được tạo thành từ bộ (y, y + 1) nào đó trong dãy ban đầu. Do ƯCLN(x, 2013 − x) = 1 và các bộ được sinh ra theo quá trình thực hiện thuật toán Euclid nên sau một số lần thực hiện thao tác với bộ số trên, ta sẽ được bộ có 1 trong 2 dạng:

Bài toán 2.23. (VMO-2013) Cho một dãy các số 1, 2, ..., 1000. Ở mỗi lượt, người ta xác định tất cả các cặp số đứng cạnh nhau và điền vào giữa hai số đó tổng của chúng. Hỏi sau khi thực hiện một số lần thì số 2013 xuất hiện trong dãy là bao nhiêu? Phân tích - Lời giải. Ta thấy rằng ở tại một thời điểm nào đó, ta kí hiệu bộ (x, y) là hai số đứng cạnh nhau thì các số sinh ra sau đó nằm giữa chúng, là các tổ hợp tuyến tính của x và y. Cụ thể là, từ bộ (x, y) là hai số đứng cạnh nhau, ta được hai bộ (x, x + y) và (x + y, y). Do ƯCLN(x, y) = ƯCLN(x, x + y) = ƯCLN(x + y, y) và ban đầu có tất cả các số nguyên dương liên tiếp (hai số cạnh nhau thì nguyên tố cùng nhau) nên tất cả các số đứng cạnh nhau sau đó cũng phải nguyên tố cùng nhau. Nếu ở một bước nào đó, từ bộ (x, y) ta sinh ra ngay một số 2013 thì rõ ràng, ta phải có x + y = 2013 hay các số 2013 sinh ra được từ (x, 2013 − x) với 0 < x < 2013. Do ƯCLN(x, y) = 1 nên cũng phải có ƯCLN(x, 2013) = 1. Đây cũng chính là điều kiện để sinh ra được số 2013. Để tìm điều kiện đủ, ta sẽ làm rõ những bước sau:

• (y, y + 1) đã có xuất hiện trong dãy đã cho. Thật vậy, do (y, y + 1) (cid:54)= (1006, 1007) nên bộ (x, y) ở trên được sinh ra ít nhất sau một lần thực hiện thao tác, tức là (x, y) ≡ (y, 2y + 1) hoặc (x, y) ≡ (2y + 1, y) hoặc các bộ có hệ số lớn hơn. Tuy nhiên, ta thấy rằng 2y + 1 + y = 3y + 1 = 2013, suy ra y < 2013 chứng tỏ bộ (y, y + 1) đã có xuất hiện trong dãy ban đầu.

• (1, y) với y > 1, bộ này hiển nhiên sẽ xuất hiện trong dãy đã cho sau

y − 2 lần thực hiện thao tác.

φ (2013) = φ (3) φ (11) φ (61) = 1200.

Hơn nữa, quá trình thao tác trên là duy nhất nên nhận xét được chứng minh. Số các số x thỏa mãn ƯCLN(x, 2013) = 1 và 0 < x < 2013 rõ ràng là

Vậy số các số 2013 cần tìm là 1200 − 2 = 1198.

và các điểm A, B có các thành phần khi tam giác OAB có diện tích bằng Bài toán 2.24. (Chọn đội tuyển Việt Nam - 2011) Trên mặt phẳng tọa độ có một con cào cào ở điểm (1, 1). Nó có thể nhảy từ điểm A sang điểm B 1 2 tọa độ nguyên dương.

1. Tìm các điểm (m, n) sao cho con cào cào có thể nhảy đến điểm đó sau

hữu hạn bước.

2. Chứng minh rằng con cào cào có thể nhảy đến (m, n) kể trên sau ít

nhất |m − n| bước.

⇔ |ad − bc| = 1,

SOAB =

1 2

Phân tích - Lời giải. Dễ thấy, con cào cào nhảy từ điểm A(a, b) đến điểm B(c, d) thì

vì vậy

ƯCLN(a, b) = 1; ƯCLN(c, d) = 1.

Nên dự đoán các điểm (m, n) con cào cào nhảy đến thì m, n phải nguyên tố cùng nhau. Từ điều cần chứng minh ở câu (2) và nhận xét trên thì trước hết ta phải chứng minh nhận xét sau:

Hình 2.4: hình vẽ

|mb − na| = 1; |a − b| ≤ |m − n| − 1. (∗)

Với (m, n) là cặp số nguyên tố cùng nhau thì tồn tại a, b nguyên tố cùng nhau sao cho

Thật vậy, không mất tính tổng quát, giả sử m > n. Xét các số có dạng mb − 1, 1 ≤ b ≤ n. Dễ thấy ta có n số như vậy và b (cid:54)= b(cid:48) thì mb − 1 (cid:54)= mb(cid:48) − 1 (modn), nên các số này lập thành một hệ thăng dư ...n. Ta cũng thấy rằng đầy đủ theo modulo n, suy ra tồn tại b sao cho mb − 1 b ≤ n − 1 vì b = n không thỏa mãn.

⇒ a <

= m và mb − na = 1. Khi đó

mb − 1 n

mn n

|n(b − a)| = |(m − n) n + (m − n) (b − n) − 1| < |(m − n) n|,

Đặt a =

|b − a| < |m − n| .

suy ra

1. Từ nhận xét trên, xuất phát từ điểm (1, 1) con cào cào chỉ có thể nhảy đến điểm (m, n) mà ƯCLN(m, n) = 1. Hơn nữa, với ƯCLN(m, n) = 1 thì theo (∗) con cào cào có thể nhảy đến điểm có tọa độ (m, n). Vậy các điểm cần tìm là (m, n) với m, n nguyên tố cùng nhau.

2. Xét điểm nguyên dương (m, n) mà ƯCLN(m, n) = 1, |m − n| = 1 thì

Do đó |b − a| ≤ |m − n| − 1. Nhận xét được chứng minh. Trở lại bài toán.

con cào cào có thể nhảy đến điểm này chỉ sau một bước nhảy. Ta lại xét điểm ƯCLN(m, n) = 1, |m − n| > 1 thì từ (∗) tồn tại hai số m(cid:48), n(cid:48) sao cho

(cid:12)mn(cid:48) − nm(cid:48)(cid:12) (cid:12) (cid:12) = 1, (cid:12) (cid:12)m(cid:48) − n(cid:48)(cid:12) (cid:12) ≤ |m − n| − 1.

Lập lại quá trình này, ta thấy con cào cào có thể nhảy đến điểm (m, n) sau không quá |m − n| bước.

Bài toán 2.25. Cho S là tập hợp các số thực thỏa mãn các tính chất:

∈ S và

∈ S. Chứng minh rằng S là tập hợp

1. 1 ∈ S.

1 1 + x

x 1 + x

2. Nếu x ∈ S thì

tất cả các số hữu tỷ thuộc khoảng (0, 1).

Phân tích - Lời giải.

x 1 + x

1 1 + x Dễ dàng kiểm tra

(ga

◦f ) (x) =

1 a + 1 + x

và g(x) = Đặt f (x) =

= (g◦f ) (0) .

1 2

với a là số nguyên không âm. Hơn nữa, ta có

Suy ra

◦f (cid:1) (cid:0)ga2−1

◦f (cid:1) ... (cid:0)gan−2

◦f (cid:1) (0) =

a1 +

a2 + ... +

an−1 +

1 an

= [0, a1, a2, ..., an],

(cid:0)ga1−1

trong đó a1, a2, ..., an là các số nguyên dương và an ≥ 2. Bài toán trở thành chứng minh rằng mọi số hữu tỷ trong (0, 1) điều được viết dưới dạng trên. Điều này hiển nhiên vì tính chất của liên phân số.

Bài toán 2.26. (IMO-1985) Cho n là số tự nhiên, k là một số nguyên tố với n; 1 ≤ k ≤ n − 1, M là tập hợp {1, 2, ..., n}. Mỗi phần tử của M được tô bởi một trong hai màu trắng hoặc xanh.Ta giả sử:

1. Với mỗi i thuộc M thì i và n − i có cùng màu.

2. Với mỗi i thuộc M , i (cid:54)= k, i và |i − k| có cùng màu.

mr ≡ rk (modn) , r = 1, 2, ..., n − 1.

Chứng minh rằng tất cả các phần tử của M đều có cùng màu. Phân tích - Lời giải. Để chứng tỏ tất cả các phần tử của M có cùng màu ta sẽ hoán vị chúng sao cho từ điều kiện cho trước của đầu bài suy ra mỗi phần tử của tập hợp đã hoán vị có cùng màu với tập hợp ban đầu của nó. Xét n − 1 bội số đầu tiên của k và rút gọn chúng theo modulo n bằng cách đặt:

(a) mr = mr−1 + k, nếu mr−1 + k < n; (b) mr = mr−1 + k − n, nếu mr−1 + k > n.

Vì (n, k) = 1 nên rk không đồng dư với 0 theo modulo n, hơn nữa ik ≡ jk (modn) khi và chỉ khi i = j nên tập hợp {m1, m2, ..., mn−1} là một hoán vị của M . Vì mr ≡ rk (modn) và mr−1 ≡ (r − 1) k (modn) nên mr ≡ mr−1+k ( mod n), do đó ta có hai khả năng sau đây:

Trong trường hợp (a), do điều kiện thứ hai của đầu bài, mr có cùng màu với |mr − k| = mr−1. Trong trường hợp (b), cũng do điều kiện thứ hai của đầu bài mà mr có cùng màu với |mr − k| = n − mr−1, do điều kiện thứ nhất, nó lại cùng màu với mr−1. Tóm lại, tất cả các phần tử của M đều có cùng màu.

Bài toán 2.27. (VMO - 2006) Xét tập hợp số S có 2006 phần tử. Ta gọi một tập con T của S là một tập con "bướng bỉnh" nếu với hai số u, v tùy ý (có thể u = v) thuộc T luôn có u + v không thuộc T . Chứng minh rằng:

1. Nếu S là tập hợp gồm 2006 số nguyên dương đầu tiên thì mỗi tập con

"bướng bỉnh" của S đều có không quá 1003 phần tử.

2. Nếu S là tập hợp gồm 2006 số nguyên dương tùy ý thì tồn tại một tập

con "bướng bỉnh" của S có 669 phần tử.

1. Xét A là tập con "bướng bỉnh" gồm n phần tử a1, a2, ..., an với a1 < a2 < ... < an của S = {1, 2, ..., 2006} . Khi đó B = {a2 − a1, a3 − a1, ..., an − a1} là một tập con gồm n − 1 phần tử của S. Do A là tập "bướng bỉnh" nên A ∩ B = ∅. Từ đó suy ra

n + (n − 1) ≤ 2006 ⇒ n ≤ 1003.

2. Giả sử tập hợp đã cho là S = {a1, a2, ..., a2006}. Gọi P là tích tất cả các

Phân tích - Lời giải.

ai. Dễ thấy tồn tại số nguyên tố p có dạng p = 3r + 2 (với

2006 (cid:81) i=1

ước số lẻ của

số nguyên dương r) là ước của 3P + 2. Số nguyên tố p này nguyên tố cùng nhau với tất cả các số ai (i = 1, 2, ..., 2006) đã cho. Với mỗi số ai ∈ S, dãy ai, 2ai, ..., (p − 1) ai là một hoán vị của 1, 2, ..., p − 1 theo modulo p nên tồn tại tập hợp Ai gồm r + 1 số nguyên x ∈ {1, 2, ..., p − 1} để xai theo modulo p thuộc tập hợp A = {r + 1, r + 2, ..., 2r + 1} . Với mỗi x ∈ {1, 2, ..., p − 1}, kí hiệu Sx = {ai|xai ∈ A}, ta có

|S1| + |S2| + ... + |Sp−1| =

|Ai| = 2006 (r + 1) .

ai∈S

(cid:88)

> 668.

|Sx0| ≥

2006 (r + 1) 3r + 1

Do đó tồn tại x0 sao cho

Chọn tập B là tập con gồm 669 phần tử của Sx0, khi đó B là một tập con "bướng bỉnh" của S. Thật vậy, nếu chọn u, v, w ∈ B (u có thể bằng v), thì x0u, x0v, x0w đều thuộc A. Do đó x0u + x0v (cid:54)= x0w (modp) cho nên u + v (cid:54)= w. Nhận xét. Câu 1 của bài toán đơn giản, nhưng câu 2 khó câu này sử dụng hệ thặng dư và tính chất của nó, hơn nữa ta phát hiện được tập hợp "bướng bỉnh" có thể xem là cực đại.

Bài toán 2.28. (THTT) Cho các số nguyên không âm a1 < a2 < ... < a101 < 5050. Chứng minh rằng tồn tại bốn số phân biệt ak, ah, am, an sao cho

(ak + ah − am − an)

...5050.

ak + ah ≡ am + an (mod5050) ,

Phân tích - Lời giải. Xét các tổng ai + aj (1 ≤ i < j ≤ 101), có tất cả C 2 101 = 5050 tổng như vậy. Giả sử không tồn tại bốn số k, h, m, n với k < h, m < n, {k, h} (cid:54)= {m, n} sao cho

thì S = {ai + aj|1 ≤ i < j ≤ 101} là hệ thặng dư đầy đủ modulo 5050. Từ đó

(ai + aj) ≡ (0 + 1 + ... + 5049) ≡ 12748725 (mod5050) .

1≤i

(cid:88)

(1)

(ai + aj) là một số lẻ.

1≤i

Suy ra (cid:80)

Mặt khác

(ai + aj) = 100 (a1 + a2 + ... + a101)

(2)

(cid:80) 1≤i

là một số chẵn. Ta thấy (1) và (2) mâu thuẫn. Vậy tồn tại hai tổng ak + ah, am + an với k < h, m < n, {k, h} (cid:54)= {m, n} sao cho ak + ah ≡ am + an (mod5050). Do đó, tồn tại bốn số phân biệt ak, ah, am, an sao cho

(ak + ah − am − an)

...5050.

∈ A

(cid:21) Bài toán 2.29. (THTT) Cho a là một số tự nhiên lớn hơn 1. Xét tập hợp khác rỗng A ⊂ N thỏa mãn điều kiện: Nếu k ∈ A thì k + 2a ∈ A và (cid:20)k a

1. Trước hết ta chứng minh số 0 ∈ A. Thật vậy giả sử trái lại, gọi k (k > 0)

(kí hiệu [x] chỉ phần nguyên của x). Chứng minh rằng A = N. Phân tích - Lời giải.

< k do a > 1. Vì

≤

∈ A nên mâu

k a

(cid:21) (cid:21) là phần tử bé nhất của A thì (cid:20)k a (cid:20)k a

∈ A. Vậy A chứa tất cả các số

(cid:21) thuẫn với việc k là phần tử bé nhất của A. Vì 0 ∈ A nên 0 + 2a = 2a ∈ A. Suy ra 2a + 2a = 4a ∈ A. Tương tự với k ∈ N ta có 2ka ∈ A. Suy ra 2k = (cid:20)2ka a

2. Bây giờ giả sử n ∈ N bất kì. Trong hai số na và na + 1 phải có một số chẵn. Gọi số đó là 2k. Khi đó na ≤ 2k < na + a = (n + 1) a (do a > 1).

chẵn.

∈ A. Vậy A = N.

(cid:21) Suy ra n = (cid:20)2k a

Chúng ta có bài toán tương tự sau.

Bài toán 2.30. (THTT) Cho một tập hợp khác rỗng S ⊂ Z thỏa mãn các điều kiện sau

1. Tồn tại hai phần tử a, b ∈ S mà (a, b) = (a − 2, b − 2) = 1.

2. Nếu x, y ∈ S thì x2 − y ∈ S (x, y không nhất thiết khác nhau).

• Nếu m, n ∈ A thì m + n ∈ A, m − n ∈ A (suy ra từ định nghĩa).

(Trong đó (a,b) ước số chung lớn nhất của hai số nguyên a, b). Chứng minh rằng S = Z. Phân tích - Lời giải. Kí hiệu A = (cid:8)a|a ∈ Z thỏa mãn ∀y ∈ S ⇒ y + a ∈ S, y − a ∈ S(cid:9). Rõ ràng 0 ∈ A.

• Nếu m, n ∈ A thì tồn tại x, y ∈ Z sao cho xm + yn = d với d = (a, b).

Do đó suy ra từ nhận xét trên d ∈ A.

x2 − t ∈ S ⇒ y2 − (cid:0)x2 − t(cid:1) ∈ S ⇒ t − (cid:0)x2 − y2(cid:1) ∈ S.

Ta sẽ chứng minh 1 ∈ A (và hệ quả thì 1 ∈ A, dẫn đến S = Z ). Giả sử x, y, t ∈ S. Từ giả thiết (2) ta có

Tương tự t + (cid:0)x2 − y2(cid:1) ∈ S. Bởi vậy x2 − y2 ∈ A. Xét a, b ∈ S thỏa mãn (1). Theo nhận xét trên thì a2 − b2 ∈ A. Theo giả thiết a2 − b ∈ S, a2 − a ∈ S ta suy ra

(cid:0)a2 − b(cid:1)2 − (cid:0)a2 − a(cid:1) = (a − b) (cid:0)2a2 − a − b(cid:1) ∈ A.

2a2 (a − b) = (a − b) (cid:0)2a2 − a − b(cid:1) + (cid:0)a2 − b2(cid:1) ∈ A.

Suy ra

Tương tự 2b2 (b − a) ∈ A. Vì (a, b) = 1 nên

(cid:0)2a2 (a − b) , 2b2 (b − a)(cid:1) = 2 (a − b) ∈ A.

(a, b) = 1 ⇒ (a, a − b) = 1 ⇒ (cid:0)a3, a − b(cid:1) = 1

Mặt khác (cid:0)a2 − a(cid:1)2 − a2 = a3 (a − 2) ∈ A. Vì (a, b) = 1 nên trong hai số a, b có ít nhất một số lẻ. Không mất tính tổng quát, giả sử a lẻ. Vì

1 = (a − 2, b − 2) = (a − 2, (a − 2) − (b − 2)) = (a − 2, a − b),

và

nên

(cid:0)a3 (a − 2) , 2 (a − b)(cid:1) = (cid:0)a3 (a − 2) , (a − b)(cid:1) = 1.

Suy ra 1 ∈ A. Nhận xét. Đây là bài toán số học - tập hợp khó. Sử dụng linh hoạt các tính chất về ước số chung lớn nhất, điều hay của bài toán là xây dựng tập hợp trung gian.

Bài toán 2.31. (IMO - 1981) a) Với giá trị nào của n (n > 2) thì sẽ tồn tại một tập hợp gồm n số nguyên dương liên tiếp thỏa mãn điều kiện: Số lớn nhất trong tập hợp này là một ước số của bội chung nhỏ nhất của n − 1 số còn lại?

b) Với giá trị nào của n (n > 2) thì sẽ tồn tại duy nhất một tập hợp có tính chất trên? Phân tích - Lời giải. Rõ ràng để giải bài toán này ta lần lượt xét các trường hợp của số tự nhiên n. Giả sử n = 3 thỏa mãn điều kiện đề bài. Khi đó, ta xét tập hợp gồm 3 số m, m − 1, m − 2. Vì m − 1, m − 2 không có ước chung nên bội chung nhỏ nhất của chúng (m − 1).(m − 2). Do đó, m chia hết (m − 1)(m − 2) = m2 + 3m − 2 suy ra m chia hết 2, điều này mâu thuẫn. Giả sử n = 4, xét tập hợp gồm 4 số m, m − 1, m − 2, m − 3; m và m − 1 không có ước chung, nên n chỉ có thể có ước chung là 2 với n − 2 và chỉ có thể ước chung là 3 với n − 3. Vì m là một ước số của bội chung nhỏ nhất của 3 số còn lại nên suy ra m có dạng 2α.3β. Nếu β = 0, lúc đó 2 không chia hết m − 1 và m − 3, chứng tỏ m chia hết m − 2, điều này mâu thuẫn. Tương tự, nếu α = 0 thì m chia hết m − 3, điều này mâu thuẫn. Giả sử α, β ≥ 1. Lúc đó, tương tự như trên, ta có 2α chia hết m − 2. Đặt m − 2 = 2αx, ta có

2αx + 2 = 2α3β ⇔ x + 21−α = 3β.

m, m − 1, .., m − (n − 2), m − (n − 1).

Từ đó α = 1. Lí luận tương tự như trên với m − 3 ta được β = 1. Suy ra m = 6. Vậy khi n = 4, tồn tại duy nhất tập hợp {3, 4, 5, 6} thỏa mãn điều kiện bài toán. Giả sử n > 4. Xét tập hợp gồm các số

Ta muốn rằng m chia hết bội chung nhỏ nhất của những số còn lại. Đặt m = (n − 1).(n − 2). Khi đó, n − 1 chia hết m − (n − 1) và n − 2 chia hết m − (n − 2), do đó m chia hết bội chung nhỏ nhất của hai số này, vì chúng nguyên tố cùng nhau. Từ đó, suy ra m chia hết bội chung nhỏ nhất của những số còn lại. Tương tự, nếu đặt m = (n − 2)(n − 3), thì ta cũng được kết quả như vậy. Tóm lại, câu trả lời cho a) là n ≥ 4 và câu trả lời cho b) là n = 4.

Bài toán 2.32. (Hồng Kông - 1998) Cho s, t là các số nguyên khác 0, gọi (x, y) là một cặp có thứ tự các số nguyên tùy ý. Ta gọi một nước đi là một phép biến đổi (x, y) thành cặp (x + t, y − s). Cặp (x, y) được gọi là cặp tốt

nếu sau một số (có thể bằng 0) nước đi nó sẽ biến thành một cặp số nguyên không nguyên tố cùng nhau.

1. (s, t) có phải là cặp tốt hay không?.

2. Chứng minh rằng với các số nguyên bất kì s và t, tồn tại cặp (x, y)

không tốt.

1. (s, t) là cặp tốt. Thật vậy:

Phân tích - Lời giải.

Nếu (s, t) (cid:54)= 1 thì bản thân (s, t) đã là cặp tốt. Do vậy, ta giả sử (s, t) = 1. Khi đó

1 = (s, t) = (s, t − s) = (t, t − s) =

st, (t − s)2(cid:17)

= (cid:0)st, t2 + s2(cid:1) .

(cid:16)

u (st) + v (cid:0)s2 + t2(cid:1) = 1 ⇒ −s2u (st) − s2v (cid:0)s2 + t2(cid:1) = −s2.

Suy ra tồn tại hai số nguyên u, v sao cho

(s + kt, t − ks) = (cid:0)s2 + kst, t2 − kst(cid:1) = (cid:0)s2 + kst, s2 + t2(cid:1) = s2 + t2 > 1.

Do đó tồn tại k = −s2u sao cho kst ≡ −s2 (cid:0)mods2 + t2(cid:1). Sau n bước đi (s, t) biến thành điểm (s + nt, t − ns). Do đó

2. Giả sử (s, t) = d. Khi đó tồn tại hai số nguyên x, y sao cho xs + yt = d,

Do đó s + kt, t − ks không nguyên tố cùng nhau. Suy ra (t, s) là cặp tốt.

+ y

= 1.

(cid:19) (cid:17) hay x (cid:16) s d (cid:18) t d

Chứng minh (x, y) là cặp tốt. Thật vậy, gọi n là số nguyên tùy ý. Giả sử k là ước chung của x + nt và y − ns. Ta có:

k| (x + nt)

+ (y − ns)

= 1.

(cid:19) (cid:17)

xs + yt d

(cid:16) s d (cid:18) t d

Suy ra k = 1. Từ đó, với mọi số nguyên n, hai số x + nt và y − ns nguyên tố cùng nhau, tức là với mọi s, t luôn tồn tại cặp (x, y) không tốt. Nhận xét. Bài toán này là bài toán tổ hợp, nhưng kĩ thuật giải hoàn toàn sử dụng kiến thức số học, cụ thể các tính chất tìm ước chung lớn nhất.

2.2 Bài toán chia kẹo Euler.

Có bao nhiêu cách chia k viên kẹo cho n người? Đó chính là cách phát biểu thực tế của bài toán chia kẹo Euler. Ở đây điều kiện duy nhất đối với số

2, ..., x(cid:48) n

1, x(cid:48)

2 + ... + x(cid:48)

1 + x(cid:48)

(cid:1) với x1 + x2 + ... + xn = k và x(cid:48)

kẹo xi mà người thứ i nhận được là xi là số nguyên không âm (ta không có ý định bẻ cây kẹo làm đôi, cũng như chia cho một người nào đó một số âm cây kẹo). Hai cách chia kẹo được gọi là khác nhau là hai bộ (x1, x2, ..., xn) và (cid:0)x(cid:48) n = k, trong đó hai bộ này khác nhau ít nhất một vị trí.

Như thế, bài toán chia kẹo Euler có thể phát biểu thành:

x1 + x2 + ... + xn = k.

Cho n số nguyên dương và k là một số nguyên không âm. Tìm số nghiệm nguyên không âm của phương trình

f (x1, x2, ..., xn) = 11...1 (cid:124) (cid:123)(cid:122) (cid:125)x1

0 11...1 (cid:124) (cid:123)(cid:122) (cid:125)x2

0...0 11...1 (cid:124) (cid:123)(cid:122) (cid:125)xn

k+n−1 = C n−1

Lời giải. Gọi A là tập hợp tất cả các nghiệm của phương trình đã cho. Gọi B là tập hợp các xâu nhị phân có độ dài k + n − 1 trong đó có k ký tự 0. Xét tương ứng f : A → B sao cho

Dễ dàng kiểm tra được f là một song ánh.Vậy |A| = |B| = C k k+n−1. Nhận xét. Ngoài cách chứng minh trên chúng ta có thể sử dụng phương pháp thiết lập hệ thức truy hồi hoặc khai triển nhị thức Newton. Dưới đây là một số bài tập áp dụng.

x1 + x2 + ... + xn = k.

Bài toán 2.33. Cho n số nguyên dương và k là một số nguyên lớn hơn n. Tìm số nghiệm nguyên dương của phương trình

y1 + y2 + ... + yn = k − n.

Phân tích - Lời giải. Đặt yi = xi − 1, (cid:0)i = 1, n(cid:1). Khi đó số nghiệm của phương trình đã cho bằng số nghiệm nguyên không âm của phương trình

Theo bài toán chia kẹo Euler, thì số nghiệm của phương trình là C n−1 k−1 .

x1 + x2 + x3 + x4 = 17,

Bài toán 2.34. Tìm số nghiệm nguyên không âm của phương trình

với x1 ≥ 1, x2 ≥ 2, x3 ≥ 3, x4 ≥ 4. Phân tích - Lời giải. Đặt y1 = x1 − 1, y2 = x2 − 2, y3 = x3 − 3, y4 = x4 − 4. Khi đó số nghiệm của phương trình đã cho bằng số nghiệm nguyên không âm của phương trình

y1 + y2 + y3 + y4 = 7.

Theo bài toán chia kẹo Euler thì số nghiệm của phương trình đã cho là C 3 10.

x1 + x2 + ... + xm ≤ n (m, n ∈ N) .

Bài toán 2.35. Tìm số nghiệm nguyên không âm của bất phương trình

(∗)

x1 + x2 + ... + xm + xm+1 = n,

Phân tích - Lời giải. Bất phương trình đã cho tương đương

m+n.

trong đó xm+1 là giá trị nguyên không âm. Như vậy, số nghiệm nguyên không âm của bất phương trình đã cho chính là số nghiệm nguyên không âm của phương trình (∗). Theo bài toán chia kẹo Euler thì số nghiệm phương trình (∗) bằng C m

px1 + x2 + ... + xn = k,

Bài toán 2.36. Tìm số nghiệm nguyên không âm của phương trình

x2 + ... + xn = k − px1.

trong đó n, p, k là các số nguyên dương cho trước. Phân tích - Lời giải. Phương trình đã cho viết lại dưới dạng:

Với mỗi x1, thì theo bài toán chia kẹo số nghiệm của phương trình là

C n−2 n−2+k−px1 (cid:20)k (cid:21) p

nên số nghiệm của phương trình đã Mặt khác, x1 nhận giá trị từ 0 đến









k p (cid:88)

C n−2

n−2+k−px.

x=0

cho là:

Một số ứng dụng khác của bài toán chia kẹo Euler.

Bài toán 2.37. (VMO - 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là G1, G2, G3, G4, G5 và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho ngồi vào các chiếc ghế đó sao cho các điều kiện sau được đồng thời thỏa mãn:

1. Mỗi ghế có đúng một người ngồi;

2. Thứ tự ngồi của các cô gái, xét từ trái qua phải là G1, G2, G3, G4, G5;

3. Giữa G1 và G2 có ít nhất 3 chàng trai;

4. Giữa G4 và G5 có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.

x1 + x2 + x3 + x4 + x5 + x6 = 12,

Hỏi có tất cả bao nhiêu cách xếp như vậy? Phân tích - Lời giải. Gọi x1 là số chàng trai được xếp bên trái G1, x2 là số chàng trai ở giữa G1 và G2, x3 là số chàng trai ở giữa G2 và G3, x4 là số chàng trai ở giữa G3 và G4, x5 là số chàng trai ở giữa G4 và G5, x6 là số chàng trai được xếp ở bên phải G5. Khi đó bộ số (x1, x2, ..., x6) hoàn toàn xác định vị trí các cô gái và ta có

x1 + y2 + x3 + x4 + y5 + x6 = 8,

trong đó x2 ≥ 3 và 1 ≤ x5 ≤ 4. Đổi biến y2 = x2 − 3 và y5 = x5 − 1 thì ta thu được phương trình

C 4

9 = 1161.

10 + C 4

11 + C 4

12 + C 4

với các ẩn không âm và có thêm điều kiện y5 ≤ 3. Cho y5 nhận giá trị 0, 1, 2, 3 và sử dụng bài toán chia kẹo Euler, thì số nghiệm của phương trình là:

C 4

9 = 1161.

10 + C 4

11 + C 4

12 + C 4

Vậy số cách phân ghế cho các cô gái là

Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp thỏa mãn yêu cầu bài toán là 12!.1161.

ABABA, ABABAB, BABA, BABAB;

Bài toán 2.38. (THTT) Một dãy a1, a2, ..., an với ai ∈ {0; 1} gọi là một xâu nhị phân có độ dài n. Hỏi có bao nhiêu xâu nhị phân độ dài n (n ≥ 4) chứa đúng hai lần xuất hiện của 01? Phân tích - Lời giải. Mỗi xâu nhị phân có đúng hai lần xuất hiện 01 có dạng

trong đó A là xâu nhị phân gồm toàn chữ số 1, B là xâu nhị phân gồm toàn chữ số 0, mỗi xâu có độ dài ít nhất là 1.

x1 + x2 + x3 + x4 + x5 = n;

n−1,

n−1.

n−1 và C 4

Xét xâu có dạng ABABA: Số xâu có dạng này chính là số nghiệm dương của phương trình

n−1

n = C 5

n + C 5

n+1.

n−1 + C 5 Bài toán 2.39. (Bài toán về vé hạnh phúc) Vé hạnh phúc là vé mang số a1a2a3a4a5a6 với a1 + a2 + a3 = a4 + a5 + a6, trong đó ai, i = 1, 2, ..., 6 là các chữ số trong hệ đếm thập phân. Có bao nhiêu vé hạnh phúc? Phân tích - Lời giải. Số vé hạnh phúc bằng số nghiệm nguyên của phương trình

(1)

a1 + a2 + a3 = a4 + a5 + a6,

(cid:0)C 3 (cid:1) + (cid:0)C 4 (cid:1) = C 4 nghiệm của phương trình này là C 4 n−1. Tương tự, số xâu dạng ABABAB, BABA, BABAB tương ứng là C 5 C 3 Do đó số xâu thỏa mãn bài toán là n−1 + C 4

(2)

a1 + a2 + a3 + b4 + b5 + b6 = 27,

trong đó 0 ≤ ai ≤ 9, i = 1, 2, ..., 6. Đổi biến bi = 9 − ai, i = 4, 5, 6. Thì số nghiệm của phương trình trên bằng số nghiệm của phương trình

trong đó 0 ≤ ai ≤ 9, 0 ≤ bj ≤ 9, i = 1, 2, 3; j = 4, 5, 6.

Theo bài toán chia kẹo Euler thì số nghiệm nguyên không âm của phương

b1 + a2 + a3 + b4 + b5 + b6 = 17

trình (2) bằng C 5 32. Nếu a1 > 9 thì đặt b1 = 10 − a1. Khi đó, số nghiệm không âm của phương trình

b1 + b2 + a3 + b4 + b5 + b6 = 7

là C 5 22. Nếu a1 > 9, a2 > 9 thì đặt b1 = 10 − a1, b2 = 10 − a2. Khi đó, số ngiệm không âm của phương trình

C 5

32 − 6C 5

22 + 15C 5

12 = 55252.

là C 5 12. Theo nguyên lý bù trừ, thì số nghiệm của phương trình (2) là:

Vậy số các vé thỏa mãn bài toán bằng 55252. Nhận xét.Với cách giải như trên chúng ta có thể giải bài toán vé hạnh phúc tổng quát, khi các số biểu diễn trong cơ số q bất kì.

a1 + a2 + ... + an = an+1 + an+2 + ... + a2n,

Bài toán 2.40. (Bài toán tổng quát) Tìm số nghiệm nguyên của phương trình

trong đó 0 ≤ ai ≤ q, i = 1, 2, ..., 2n và q là số nguyên dương tùy ý.

|Ak| ≤ |Ak+1|

|Ak| = |A3n−k|

(cid:21) Bài toán 2.41. (THTT) Cho tập hợp X = {0, 1, 2, ..., n} với n là số nguyên dương. Với (x1, x2, x3), (y1, y2, y3) thuộc X 3, ta nói xRy nếu xk ≤ yk với k = 1, 2, 3. Hãy xác định số nguyên dương nhỏ nhất p sao cho với bất kì tập con A có p phần tử nào của X 3 đều có tính chất: Nếu x, y thuộc A thì xRy hoặc yRx. Phân tích - Lời giải. Một cách tự nhiên, ta cần tìm tập hợp số phần tử lớn nhất k không có tính chất T , rồi sau đó chúng ta chứng minh k + 1 chính là số nhỏ nhất thỏa mãn yêu cầu bài toán. Cụ thể: Với mỗi x = (x1, x2, x3), đặt s (x) = x1 + x2 + x3. Ta nói tập Y ⊂ X 3 là tập loại T nếu với mọi x, y ∈ Y ta có xRy hoặc yRx. Ta nói Y ⊂ X 3 là tập loại F nếu không tồn tại x, y ∈ Y nào để xRy và yRx. Với mỗi k ∈ {0, 1, ..., 3n} đặt Ak = {a ∈ Y |s (a) = k}. Dễ thấy Ak là tập loại F . Ngoài ra   với k = 1, 2, ..., (cid:20)3n 2 

(cid:105) . (cid:104)n 2

x1 + x2 + x3 = n + r

n+r+2.

Khi đó, trong các tập Ak thì tập An+r có số phần tử lớn nhất với r = Kí hiệu q = |An+r| . Số nghiệm nguyên không âm của phương trình

x1 + x2 + x3 = n + r

r+1.

là C 2 Số nghiệm nguyên không âm của phương trình

Bk = {(k, a) |n − k ≥ a ∈ X} ∪ {(a, n − k) |k ≤ a ∈ X}.

với điều kiện n + r ≥ x1 ≥ n + 1 là C 2 n+r+2 − 3C 2 Do đó q = C 2 Với mỗi k = 0, 1, ..., n ta xét tập hợp

Bkj = {(a, b, j) | (a, b) ∈ Bk} ,

Với k = 0, 1, ..., r và j = 0, 1, ..., n ta xét tập hợp

Ak (a, b) = {(a, b, k) |k ∈ X} ,

i=1. Rõ ràng Xi có tính chất T và (Xi)q

i=1 là

có tất cả (n + 1)(r + 1) tập Bkj. Với k = r + 1, ..., n và (a, b) ∈ Bk, ta xét tập hợp

p = C 2

n+r+2 − 3C 2

r+1 + 1,

có tất cả (n − r)2 tập như vậy. Số các tập Bkj, Ak (a, b) là d = (n − k)2 + (n + 1) (r + 1) . Kiểm tra trực tiếp khi cho n là số chẵn hoặc n là số lẻ, ta dễ dàng chứng minh d = q. Kí hiệu các tập nêu trên là (Xi)q một phân hoạch của X 3. Với mỗi tập A ⊂ X 3 mà |A| ≥ q + 1 phần tử thì theo nguyên lý Dirichlet với mọi x, y ∈ A luôn tồn tại tập Xi sao cho x, y ∈ Xi. Do đó xRy hay yRx. Thành thử p = q + 1 chính là số cần tìm. Do đó

(cid:105) với r = (cid:104)n 2

2.3 Bất biến

Để giải các bài toán dạng:

α ∼ β ⇒ f (α) = f (β) .

Bài toán. Cho tập M (mà các phần tử của nó gọi là các trạng thái). Cho một quy tắc Q sao cho khi áp dụng quy tắc Q đó, từ một trạng thái thuộc M ta thu được một trạng thái khác thuộc M . Cho trước hai trạng thái α, β thuộc M . Hỏi sau một số hữu hạn bước áp dụng quy tắc Q, từ α có thể thu được β hay không? Trước hết ta xây dựng một số kí hiệu: - Ta kí hiệu β = Q (α) nếu theo quy tắc Q, từ trạng thái α có thể thu được trạng thái β. - Ta kí hiệu β ∼ α (đọc là α tương đương với β) nếu từ α có thể thu được β sau một số bước áp dụng Q. Chú ý. Ta sẽ chỉ xét các quy tắc Q có tính tương đương, tức là có tính phản xạ, đối xứng và bắt cầu. Định nhĩa. Hàm f xác định trên tập các trạng thái M được gọi là một bất biến của quy tắc Q (xác định trên M ) nếu thỏa mãn

• Nếu f (α) (cid:54)= f (β) thì β không thể thu được từ α sau hữu hạn bước áp

Vậy nếu ta xác định được một bất biến f thì với hai trạng thái α, β bất kì, ta có:

• Nếu f (α) = f (β) thì không thể kết luận gì về mối tương quan giữa

α, β.

dụng quy tắc Q.

Nhận xét. Các bài toán loại này yêu cầu chúng ta phải xây dựng được bất biến. Trong phạm vi luận văn này, chúng tôi chỉ xét các bài toán mà bất biến liên quan đến các tính chất số học như là chia hết, đồng dư,...

(a − 1) − (b − 1) ≡ (a − 1) − (b + 2) ≡ (a + 2) − (b − 1) ≡ a − b (mod3) .

Bài toán 2.42. Có 13 con tắc kè xanh, 15 con tắc kè đỏ và 17 con tắc kè vàng trên một hòn đảo. Khi hai con tắc kè khác màu gặp nhau, chúng đổi sang màu còn lại. Liệu có thể đến một lúc nào đó tất cả các con tắc kè có cùng màu hay không? Phân tích - Lời giải. Mỗi trạng thái trên đảo gồm a con tắc kè xanh, b con tắc kè đỏ và c con tắc kè vàng trên một hòn đảo với a + b + c = 45. Phép biến đổi màu sẽ chuyển từ trạng thái (a, b, c) sang một trong ba trạng thái (a − 1, b − 1, c + 2), (a − 1, b + 2, c − 1) hoặc (a + 2, b − 1, c − 1). Khi đó

Như vậy, hiệu giữa số tắc kè xanh và số tắc kè đỏ không đổi theo modulo 3. Lúc đầu hiệu này đồng dư 2 modulo 3. Vì vậy, tất cả các con tắc kè cùng màu không thể xảy ra.

Bài toán 2.43. Vào năm 3000, ở Việt Nam, một nhân dân tệ (RMB) đổi được 10 đồng Việt Nam (VNĐ). Trong khi đó, ở Trung Quốc, một VNĐ đổi được 10 RMB. Một khách người Nhật lúc đầu có 01 VNĐ. Ông này có thể đi lại tùy ý giữa hai nước Việt Nam và Trung Quốc. Hỏi ông ta có thể làm cho số VNĐ và RMB ông ta có là bằng nhau hay không? Phân tích - Lời giải. Xét X = số VNĐ − số RMB của du khách. Khi đó X mod 11 bất biến trong các bước đổi tiền. Nếu số VNĐ và số RMB bằng nhau thì X ≡ 0 (mod11). Lúc đầu X ≡ 1 (mod11), do đó không thể thu được X ≡ 0 (mod11). Như vậy không thể xảy ra.

Bài toán 2.44. Trên bảng ta viết ba số nguyên. Sau đó xóa đi một số và viết vào đó tổng của hai số còn lại trừ đi 1. Thao tác như vậy lặp lại một

số lần và cuối cùng ta nhận được ba số 29, 1876, 2011. Hỏi ba số đầu tiên có thể là 2, 2, 2 không? Phân tích - Lời giải. Sau bước đầu tiên từ ba số 2, 2, 2 ta nhận được 2, 2, 3 ba số này có hai số chẵn và một số lẻ. Từ bước thứ hai trở đi thì kết quả luôn luôn có hai số chẵn và một số lẻ dù ta thực hiện với bất kì số nào (vì số chẵn bằng tổng của một số chẵn và một số lẻ trừ đi 1, số lẻ là tổng của hai số chẵn trừ đi 1). Nhưng kết quả đã cho có hai số lẻ, một số chẵn nên với thao tác đã cho và xuất từ số 2, 2, 2 không thể cho kết quả.

Bài toán 2.45. Trên bảng viết các số 1, 2, 3, 4, 5. Mỗi bước cho phép chọn hai số a, b và thay bằng số a+b và ab. Hỏi có thể thu được các số 21, 27, 64, 180, 540 hay không? Phân tích - Lời giải. Bài toán này nhìn khá đơn giản nhưng để tìm được bất biến của bài toán này không phải là điều dễ dàng. Trước hết chúng ta thấy nếu chọn hai số mà trong đó có ít nhất một số chia hết cho 3 hoặc không chia hết cho 3 nhưng cùng số dư thì số lượng số chia hết cho 3 không thay đổi, và số lượng số chia hết cho 3 thay đổi khi và chỉ khi từ hai số chia 3 dư 2 và dư 1, chúng ta sẽ thu được một số chia hết cho 3 và một số chia 3 dư 2. Vì vậy, lần đầu tiên chuyển sang trang thái 4 số chia hết cho 3 thì số còn lại chia 3 dư 2, nhưng 64 chia 3 dư 1 nên câu trả lời không thể thu được.

(b + d + 2x) − (a + c − x) ≡ b + d − a − c (mod3).

Bài toán 2.46. (Hungary MO 1989) Mỗi đỉnh của một hình vuông đặt một hòn sỏi. Thực hiện thay đổi số sỏi theo quy luật sau: ta có thể lấy đi một số sỏi ở một đỉnh và thêm vào một trong hai đỉnh kề bên một số sỏi gấp đôi. Hỏi có thể nhận được 1989, 1988, 1990, 1989 viên sỏi tại các đỉnh liên tiếp của hình vuông được không? Phân tích - Lời giải. Gọi 4 đỉnh liên tiếp của hình vuông là A, B, C, D ứng với số sỏi là a, b, c, d. Khi đó ở bước tiếp theo gọi x là số sỏi lấy đi, giả sử ở đỉnh A, do đó số sỏi ở 4 đỉnh là: a − x, b + 2x, c, d hoặc a − x, b, c, d + 2x. Ta thấy

Mặt khác, vì ban đầu số sỏi ở mỗi đỉnh là 1, 1, 1, 1 nên từ đây ta có bất biến của bài toán này: hiệu giữa tổng số sỏi trên ở hai đỉnh A, C và B, D luôn là bội của 3. Như vậy với 1989, 1988, 1990, 1989 thì hiệu này có số dư 2 khi chia cho 3, nên không xảy ra.

Bài toán 2.47. Trên bàn cờ 8 × 8 có 32 quân trắng và 32 quân đen, mỗi quân chiếm một ô vuông. Tại mỗi bước đi người chơi thay tất cả các quân trắng thành quân đen và tất cả các quân đen thành quân trắng trên một hàng hay một cột nào đó. Hỏi sau một số hữu hạn bước có thể còn lại chính xác một quân trắng trên bàn cờ không? Phân tích - Lời giải. Nếu trước khi chuyển có chính xác k quân trắng trên hàng (cột) định chuyển thì số quân đen trên hàng (cột) đó là 8 − k. Sau khi chuyển, 8 − k quân đen này sẽ chuyển thành 8 − k quân trắng và k quân trắng sẽ chuyển thành k quân đen. Như vậy, số quân trắng trên bàn cờ sẽ thêm vào 8 − k và mất đi k quân, tức là số quan trắng thay đổi trên bàn cờ là (8 − k) − k = 8 − 2k. Số này là một số chẵn, mà số quân trắng trên bàn cờ lúc đầu là 32 quân do đó số quân trắng trên bàn cờ luôn là số chẵn. Vậy không thể còn lại duy nhất trên bàn cờ một quân trắng.

Bài toán 2.48. Mỗi ô vuông của bảng 2013 × 2013 điền các số (+1) hoặc (−1). Mỗi hàng i ta tính tích các số trong hàng đó, kí hiệu Ri . Mỗi cột i

(Ri + Ci)

2013 (cid:80) i=1

ta tính tích các số trong cột đó, kí hiệu Ci. Chứng minh rằng

luôn khác 0. Phân tích - Lời giải.

(Ri + Ci) theo modulo 4. Đại lượng

2013 (cid:80) i=1 này không đổi với bất kì sự thay đổi dấu nào của một trong những dấu được viết trên bảng. Thật vậy, giả sử có sự thay đổi phần tử ở hàng thứ i và cột thứ j cho ta − (Ri + Ci) thay vì (Ri + Ci). Vì (Ri + Ci) có giá trị 2, 0 hoặc −2 theo modulo 4 nên tổng ban đầu thay đổi một bội số của 4. Do đó, bất biến không phụ thuộc vào cách chọn các số (+1) hoặc (−1). Cho nên ta chỉ cần xét trường hợp tất cả các ô đều điền (+1). Khi đó

(Ri + Ci) ≡ 2 (mod4).

2013 (cid:80) i=1

Bất biến được sử dụng ở đây là số dư

(Ri + Ci)

2013 (cid:80) i=1

Vậy với mọi cách điền các số (+1) hoặc (−1) thì

luôn khác không.

Bài toán 2.49. Ba đóng sỏi có 51, 49 và 5 viên. Ta thực hiện một trong hai nước đi như sau. Một bước đi ta dồn hai đống tùy ý thành một đống, một

nước đi khác là chọn đống có số chẵn viên sỏi để chia thành hai đống bằng nhau. Hỏi có thể thực hiện một dãy nước đi như thế để chia 3 đống sỏi thành 36 đống sỏi không? Phân tích - Lời giải. Ban đầu số sỏi trong ba đống là 51, 49 và 5 viên đều là số lẻ nên bước đi đầu tiên là phải dồn hai đống lại.

Trường hợp 1. Trước tiên, dồn hai đống có 5 và 49 viên ta có hai đống là 51 và 54 viên, mỗi đống đều là bội của 3. Bước thứ hai là ta chia đống có 54 viên thành 2 đống mỗi đống có 27 viên. Bây giờ số sỏi ở ba đống là 51, 27 và 27 cùng chia hết cho 3. Vì cả ba đống có số lẻ viên nên bước thứ ba ta lại gộp hai đống 27 và 51 viên thành đống có 78 viên. Vì 27 và 51 đều chia hết cho 3 nên 78 chia hết cho 3. Tức là khi thực hiện các bước luân phiên thì số sỏi trong mỗi đống luôn là bội của 3. Đây chính là bất biến trong trường hợp này. Thật vậy, khi gộp hai đống sỏi có số sỏi chia hết cho 3 thì được một đống sỏi có số sỏi chia hết cho 3 và nếu chia một đống sỏi (là gộp của hai đống có số sỏi lẻ cùng chia hết cho 3) có số chẵn viên sỏi và chia hết cho 3 thành hai phần bằng nhau thì số sỏi trong mỗi phần vẫn chia hết cho 3. Do đó, số sỏi trong mỗi đống vẫn chia hết cho 3 và nhiều nhất có thể là 35 đống sỏi, mỗi đống 3 viên.

Trường hợp 2. Bước đầu tiên ta dồn hai đống có số sỏi là 5 và 51 viên, ta được hai đống có 49 và 56 viên, cả hai đều là bội của 7. Do đó, khi thực hiện luân phiên các bước đi số sỏi trong mỗi đống nhận được luôn là bội của 7. Do đó số đống sỏi nhiều nhất có thể là 15 đống mỗi đống có 7 viên sỏi.

Trường hợp 3. Bước đi đầu tiên ta dồn hai đống có 49 và 51 viên sỏi, ta được hai đống là 5 và 100 viên sỏi và số sỏi trong mỗi đống là bội của 5. Do đó, số đống sỏi nhiều nhất là 21 và mỗi đống có 5 viên sỏi. Như vậy, không thể chia đống sỏi thành 105 đống mỗi đống có 1 viên sỏi.

Bài toán 2.50. Cho dãy số 1, 0, 1, 0, 1, 0, ... Từ số hạng thứ 7 mỗi số bằng chữ số tận cùng của tổng 6 số hạng trước đó. Chứng minh rằng dãy số không chứa 6 số hạng liên tiếp 0, 1, 0, 1, 0, 1. Phân tích - Lời giải. Ta phát biểu lại bài toán như sau: Một bộ gồm 6 số (x1, x2, x3, x4, x5, x6) được biến đổi thành bộ (x2, x3, x4, x5, x6, x7), với x7 là chữ số tận cùng của (x1 + x2 + x3 + x4 + x5 + x6). Hỏi có thể nhận được bộ (0, 1, 0, 1, 0, 1) từ bộ (1, 0, 1, 0, 1, 0) bằng cách thực hiện phép biến đổi trên qua hữu hạn bước thực hiện được không? Bài toán trên nhìn thấy đơn giản, nhưng để tìm bất biến của bài toán trên

S (x1, x2, x3, x4, x5, x6) = 2 (x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6) ,

không phải là điều đơn giản tí nào. Nếu gọi

S (x2, x3, x4, x5, x6, x7) − S (x1, x2, x3, x4, x5, x6)

≡ 10 (x1 + x2 + x3 + x4 + x5 + x6) ≡ 0 (mod10) .

thì tổng này bất biến modulo 10. Thật vậy:

Vì S(1, 0, 1, 0, 1, 0) = 18 và S(0, 1, 0, 1, 0, 1) = 24 nên không thể xuất hiện bộ (0, 1, 0, 1, 0, 1). Vậy bài toán được giải quyết.

Bài toán 2.51. Ta bắt đầu với một số nguyên dương nào đó, các số còn lại thu được từ số này bằng cách thực hiện phép biến đổi như sau: tách chữ số hàng đơn vị của nó rồi nhân chữ số này cho 4, lấy tích đó cộng cho phần còn lại của số đã cho. (Ví dụ: 1997 biến thành 7.4 + 199 = 227). Thực hiện lặp đi lặp lại thao tác trên. Chứng minh rằng nếu trong dãy thu được có chứa số 1001 thì không có số nào trong dãy là một số nguyên tố. Phân tích - Lời giải. Nhận thấy 1001 = 13.77 nên có ước 13. Nếu n = 10a + b, với b là chữ số hàng đơn vị, thì phép biến đổi trên có thể biến n thành n(cid:48) = a + 4b. Vì n = 10n(cid:48) − 39b nên nếu một trong hai số chia hết cho 13 thì số kia cũng vậy. Bất biến ở đây là các số trong dãy phải là bội của 13, nên nếu có một số trong dãy là số nguyên tố thì chắc chắn đó là số 13. Ta nhận thấy 13 không thể đứng trước 1001, bởi vì phép biến đổi đưa số 13 thành số 4.3 + 1 = 13 và vẫn là số 13. Mặt khác, 13 không thể đứng sau số 1001 bởi vì, phép biến đổi sẽ đưa số 1001 thành số 4.1 + 100 = 104, 4.4 + 10 = 26, 4.6 + 2 = 26 vẫn còn lại số 26. Suy ra trong dãy không thể chứa số 13, do đó không chứa số nguyên tố nào trong dãy.

Bài toán 2.52. (German MO 1996) Từ điểm (1, 1) di chuyển một hòn sỏi trên mặt phẳng tọa độ thỏa mãn các điều kiện sau:

1. Từ điểm (a, b) có thể đến (2a, b) hoặc (b, 2a).

b > a.

2. Từ điểm (a, b) có thể đến điểm (a − b, b) nếu a > b hoặc (a, b − a) nếu

Với những số nguyên dương (x, y) như thế nào thì hòn sỏi có thể đến điểm (x, y). Phân tích - Lời giải. Ta sẽ chứng minh điều kiện cần và đủ của bài toán này là (x, y) = 2s, với s

là số nguyên không âm, (x, y) là ước chung lớn nhất của hai số tự nhiên x, y. Thật vậy:

Điều kiện cần: Vì (p, q) = (p, q − p); (a, b) = (2a, b) hoặc (2a, b) = 2 (a, b)

mà ban đầu (1, 1) = 1 nên (x, y) phải là lũy thừa của 2.

, q

q 2

(cid:17) (cid:16) (cid:17) hoặc

, q

(cid:19) , mâu thuẫn với tính Nếu p > q thì cũng có thể nhận được từ số Điều kiện đủ: Trong tất cả các cặp (p, q) có thể đến được (x, y) ta chọn một cặp sao cho p + q nhỏ nhất. Nếu p hoặc q chẵn thì một trong các điểm (cid:16)p cũng thỏa mãn, mâu thuẫn với tính nhỏ nhất của p + q. 2 (cid:18)p + q 2

nhỏ nhất của p + q. Tương tự với trường hợp p < q cũng mâu thuẫn. Do đó, p = q mà (p, q) là lũy thừa của 2. Từ đó, suy ra p = q = 1, nên (x, y) thỏa mãn. Điều kiện được chứng minh xong.

Bài toán 2.53. Một bảng hình vuông 100 × 100 có thể được lát bởi các viên gạch 3 × 1 hoặc 1 × 3 hay không? Trong các trường hợp sau đây:

1. Bỏ qua hình vuông 2 × 2 ở giữa sàn nhà.

2. Bỏ qua hình vuông 2 × 2 ở một góc sàn nhà.

1. Bỏ qua hình vuông 2 × 2 ở giữa sàn nhà, thì chúng ta có thể lát được nền nhà bởi các viên gạch 1 × 3. Cụ thể, chia phần còn lại của hình vuông thành hai khối hình chữ nhật 49 × 51 và hai khối hình chữ nhật51 × 49. Vì 51 chia hết cho 3 nên chia nhỏ mỗi khối hình chữ nhật thành các khối 3 × 49 và 49 × 3 và mỗi khối này luôn lát được bởi các viên gạch 1 × 3 hay 3 × 1. 2. Bỏ qua hình vuông 2 × 2 ở một góc sàn nhà, không thể lát được hình vuông. Do tính chất đối xứng của hình vuông nên chỉ cần xét bốn ô vuông ở góc thứ nhất. Tô màu bảng hình vuông như hình 2.5:

Hình 2.5:

Phân tích - Lời giải.

100 (1 + 2 + ... + 100) = 505000 ≡ 2 (mod3) .

Tổng tất cả các số trong bảng bằng

Mặt khác, với mỗi viên gạch 3 × 1 hoặc 1 × 3 luôn lát ba số có tổng chia hết cho 3, như vậy muốn lát phần còn lại thì 4 ô vuông bị bỏ có tổng các số chia 3 dư 2. Nhưng bốn ô vuông ở góc thứ nhất có tổng bằng 6 chia hết cho 3. Do đó không thể lát nền nhà được.

Bài toán 2.54. (VMO - 1992) Cho một bảng hình chữ nhật gồm 1991 hàng và 1992 cột. Kí hiệu (m, n) là ô vuông ở hàng thứ m và cột thứ n. Người ta tô màu các ô vuông của bảng theo nguyên tắc sau: Lần thứ nhất tô ba ô (r, s) , (r + 1, s + 1) , (r + 2, s + 1) với r, s là hai số tự nhiên thỏa 1 ≤ r ≤ 1989, 1 ≤ s ≤ 1991. Từ lần thứ hai trở đi tô ba ô chưa có màu nằm cạnh nhau trên cùng một hàng hay cùng một cột. Hỏi bằng cách tô màu đó có thể tô được tất cả các ô vuông trong bảng hay không ? Phân tích - Lời giải. Ta ghi vào mỗi ô vuông của bảng một số tự nhiên theo quy tắc sau: ở mỗi hàng, lần lượt từ trái sang phải, ghi các số tự nhiên từ 1 đến 1992. Như vậy ba số được ghi vào 3 ô vuông cạnh nhau trong cùng một hàng sẽ là 3 số tự nhiên liên tiếp, trong cùng một cột sẽ là 3 số tự nhiên bằng nhau. Suy ra, kể từ lần thứ hai, mỗi lần tô màu ta sẽ xóa đi ba số có tổng chia hết cho 3. Với cách điền số như trên thì ba số được ghi vào ba ô (r, s) , (r + 1, s + 1), (r + 2, s + 1) sẽ là s, s + 1 và s + 1 có tổng của chúng là một số chia 3 dư 2. Như vậy nếu tô tất cả các ô vuông của bảng đã cho thì tổng S của tất cả các số đã ghi vào bảng phải là số chia 3 dư 2. Mặt khác, S = 1991.(1 + 2 + ... + 1992) = 1991.1993.996 chia hết cho 3, mâu thuẫn. Do đó không thể tô tất cả các ô vuông của bảng đã cho.

Hình 2.6: móc câu

Bài toán 2.55. (IMO 2004) Ta định nghĩa viên gạch hình móc câu là hình gồm 6 ô vuông đơn vị như hình vẽ dưới đây, hoặc hình nhận được do lật hình đó (sang trái, sang phải, lên trên, xuống dưới) hoặc hình nhận được do xoay hình đó đi một góc:

Hãy xác định tất cả các hình chữ nhật m × n trong đó m, n là các số nguyên dương sao cho có thể lát hình chữ nhật đó bằng các viên gạch hình móc câu. Phân tích - Lời giải.

Hình 2.7:

Dễ thấy m, n /∈ {1, 2, 5}. Chia hình chữ nhật m × n thành m × n ô vuông và đánh số các hàng các cột từ trên xuống dưới, từ trái sang phải. Ta gọi (p, q) là ô vuông nằm ở hàng thứ p và cột thứ q. Hai viên gạch móc câu chỉ có thể ghép lại để được một trong hai hình 2.7.

Do đó, để lát được hình chữ nhật m × n thì m.n phải chia hết cho 12. Nếu ít nhất một trong hai số m hoặc n chia hết cho 4 thì có thể lát được hình chữ nhật m × n. Thật vậy, giả sử m chia hết cho 4. Nếu n chia hết cho 3 thì có thể chia hình chữ nhật 4 × 3, do đó có thể lát được. Nếu n không chia hết cho 3 thì có thể viết n dưới dạng n = 3a + 4b với a, b là hai số nguyên dương, với giả thiết m.n chia hết 12 nên có thể lát được. Bây giờ ta chứng minh một trong hai số m, n không chia hết cho 4 là kết quả bài toán. Giả sử ngược lại, khi đó cả hai m, n chia hết cho 2 nhưng không chia hết cho 4. Để chứng minh điều này không thể xảy ra, ta tạo ra bất biến sau: Xét ô vuông (p, q), nếu chỉ một trong hai số p hoặc q chia hết cho 4 thì ta điền số 1 vào ô đó, nếu cả hai số p, q cùng chia hết cho 4 điền số 2 vào ô đó. Với cách điền như vậy ta thu được bất biến là tổng các số trong mỗi hình (2.13) luôn là số lẻ. Do m, n là số chẵn nên tổng các số được ghi trong hình chữ nhật m × n là một số chẵn. Như vậy, muốn lát được hình chữ nhật thì tổng số hai loại hình (2.13) phải là số chẵn. Do đó, m.n chia hết cho 24. Điều này không xảy ra vì cả m, n đều không chia hết cho 4.

2.4 Cực trị trên tập hợp rời rạc

Các bài toán cực trị trên tập hợp rời rạc là một dạng toán khó, xuất hiện nhiều trong các kì thi học sinh giỏi. Các bài toán loại này thường được phát biểu dưới hình thức sau. Bài toán 1.

1. Tìm số nguyên dương n lớn nhất để tồn tại một tập hợp con gồm n

phần tử thỏa mãn điều kiện (T ).

2. Tìm số nguyên dương n bé nhất để tồn tại tập con gồm n phần tử thỏa

mãn điều kiện (T ).

Hướng giải chung.

1. Ta chứng minh mọi số nguyên n > n0 thì mọi tập con gồm n phần tử

đều không thỏa mãn tính chất (T ). Chỉ ra tồn tại một tập hợp con gồm n0 phần tử thỏa mãn tính chất (T ). Kết luận. n = n0 là giá trị cần tìm.

2. Ta chứng minh mọi số nguyên n < n0 thì mọi tập con gồm n phần tử

đều không thỏa mãn tính chất (T ). Chỉ ra tồn tại một tập hợp con gồm n0 phần tử thỏa mãn tính chất (T ). Kết luận. n = n0 là giá trị cần tìm.

Bài toán 2.

1. Tìm số nguyên dương n lớn nhất để mọi tập hợp con gồm n phần tử

thỏa mãn điều kiện (T ).

2. Tìm số nguyên dương n bé nhất để mọi tập con gồm n phần tử thỏa

mãn điều kiện (T ).

Hướng giải chung.

1. Ta chứng minh mọi số nguyên n > n0 thì tồn tại tập con gồm n phần

tử không thỏa mãn tính chất (T ). Ta chứng minh mọi tập hợp con gồm n0 phần tử thỏa mãn tính chất (T ). Kết luận. n = n0 là giá trị cần tìm.

2. Ta chứng minh mọi số nguyên n < n0 thì tồn tại tập con gồm n phần

tử đều không thỏa mãn tính chất (T ). Ta chứng minh mọi tập hợp con gồm n0 phần tử thỏa mãn tính chất (T ). Kết luận. n = n0 là giá trị cần tìm.

Nhận xét. Ta thường chọn n = n0 + 1 (đối với bài toán lớn nhất) và n = n0 − 1 (đối với bài toán nhỏ nhất).

a1 = 17, a2 = 34, a3 = 33, a4 = 32, a5 = 25, a6 = 18, a7 = 21, a8 = 16,

a9 = 18, a10 = 20, a11 = 22, a12 = 24, a13 = 26, a14 = 28, a15 = 30.

Bài toán 2.56. Tìm số tự nhiên n bé nhất sao cho ta có thể tìm được 15 phần tử khác nhau a1, a2, ..., a15 của tập hợp {16; 17; ...; n} mà các phần tử này thỏa mãn điều kiện ak là bội của k với k = 1, 2, ..., 15. Phân tích - Lời giải. Từ điều kiện bài toán ta thấy được n ≥ 30. Vì, nếu n = 30 thì trong tập {16; 17; ...; 30} có 4 số nguyên tố 17, 19, 23, 29 và các số này chỉ chia hết cho 1. Do đó n ≥ 33. Nếu n = 33 thì {16; 17; ...; 33} lại có thêm một số nguyên tố nữa là 31, điều này không thể thỏa mãn bài toán. Do đó n ≥ 34. Với n = 34 chứng minh bài toán thỏa mãn.Cụ thể ta có thể gán như sau:

Vậy n = 34 là số nhỏ nhất thỏa mãn.

(cid:12)A(cid:48)(cid:12)

Bài toán 2.57. Cho k ≥ 1 là một số tự nhiên. Tìm số tự nhiên n nhỏ nhất sao cho với mọi tập gồm n số nguyên luôn có hai số mà tổng hoặc hiệu của chúng chia hết cho 2k + 1. Phân tích - Lời giải. Tập {k + 1, k + 2, ..., 2k + 1} không thỏa mãn tính chất bài toán, vậy n > k + 1. Ta chứng tỏ n = k + 2. Với một tập A bất kỳ gồm k + 2 số, xét tập A(cid:48) các phần dư modulo 2k + 1 của tập A như là một tập con của tập {−k, −k + 1, ..., 0, 1, ..., k}. Nếu (cid:12) (cid:12) < k + 2 thì luôn có hai phần tử của tập A có cùng số dư nên hiệu chia hết cho 2k + 1, nếu (cid:12) (cid:12) = k + 2 thì trong A luôn có hai phần tử có tổng bằng 0 theo modulo 2k + 1. Như vậy bài toán được chứng minh.

Bài toán 2.58. Tìm số k nguyên dương lớn nhất có tính chất sau: Tập hợp các số nguyên dương phân hoạch thành k tập con A1, A2, ..., Ak sao cho với mọi n ≥ 15, với mọi i ∈ {1, 2, ..., k} tồn tại hai phần tử khác nhau của Ai có tổng bằng n. Phân tích - Lời giải. Ta bắt đầu với trường hợp k = 2. Rõ ràng có thể phân hoạch tập hợp các số nguyên dương thành hai tập con A1 = {2n, n ≥ 3} ∪ {1, 2} ; A2 = {2n − 1, n ≥ 3} ∪ {3, 4} có tính chất: mọi số nguyên dương n ≥ 7 biểu diễn được dưới dạng tổng của hai số thuộc A1 và tổng của hai số thuộc A2. Khi k = 3, dĩ nhiên việc phân hoặc thành "chẵn, lẻ" như trên được thay bởi phân hoạch theo modulo 3, và cũng như trước, cần thêm vào mỗi lớp đồng

A1 = {1, 2, 3} ∪ {3m; m ≥ 4} , A2 = {4, 5, 6} ∪ {3m − 1; m ≥ 4} , A3 = {7, 8, 9} ∪ {3m − 2; m ≥ 4} . Dễ thử lại rằng, phân hoạch trên thỏa mãn bài ra. Hơn nữa, có thể nhận thấy rằng, điều kiện biểu diễn được mọi số nguyên dương n ≥ 15 đối với phân hoạch trên đã rất chặt, chẳng hạn với số 14 không thể biểu diễn thành tổng của hai số thuộc A2 hoặc A3. Từ đó có thể dự đoán rằng, k = 3 là giá trị lớn nhất có thể phân hoạch thỏa mãn bài toán. Ta sẽ chứng minh dự đoán trên, nghĩa là với k ≥ 4 không thể phân hoạch các số tự nhiên thành k tập con thỏa mãn bài ra. Rõ ràng nếu với k ≥ 4 nào đó mà tồn tại phân hoạch thỏa mãn, thì phân hoạch như vậy cũng tồn tại với k = 4. Thật vậy chỉ cần lấy phân hoạch A1, A2, A3, A4 ∪ A5 ∪ ... ∪ Ak ta được phân hoạch thành 4 tập con thỏa mãn bài toán. Như vậy chỉ cần chứng minh không thể tồn tại phân hoạch gồm 4 tập con thỏa mãn bài ra. Giả sử tồn tại một phân hoạch như vậy: A1, A2, A3, A4. Như ta đã thấy trong ví dụ k = 2, 3 các tập hợp Ai phải chứa những số nào đó trong những số tự nhiên đầu tiên. Xét 10 số nhỏ nhất mà mỗi tập hợp Ai đều phải biểu diễn được các số 15, 16, ..., 24. Mỗi số trong 10 số này đều là tổng của hai số nào đó thuộc tập hợp B = {1, 2, ..., 23}. Như vậy, mỗi tập hợp phải chứa ít nhất 5 số thuộc B (vì 10 = C 2 5 ). Do bốn tập Ai rời nhau mà B chỉ chứa 23 phần tử nên tồn tại tập Ai nào đó chứa đúng 5 số thuộc B, giả sử đó là các số {x1, x2, x3, x4, x5}. Các số này biểu diễn được đúng 10 số trong các số từ 15 đến 24, tức là 10 số đó chính là 10 tổng có thể {xk + xl, k (cid:54)= l, 1 ≤ k, l ≤ 5}. Từ đó suy ra

15 + 16 + ... + 24 = 4 (x1 + x2 + x3 + x4 + x5) ,

dư modulo 3 một số số đầu tiên để đảm bảo mỗi tập được biểu diễn được mọi số nguyên dương n ≥ 15 dưới dạng tổng của hai số. Có thể phân hoạch như sau:

vì mỗi xi tham gia đúng 4 cặp số. Đẳng thức trên đây cho ta mâu thuẫn vì tổng ở vế trái là 195, trong khi vế phải chia hết cho 4.

x = a + b, y = b + c, z = c + a,

Bài toán 2.59. (Trung Quốc - 2012) Tìm số nguyên dương k nhỏ nhất thỏa mãn tính chất sau: Với mỗi tập con A của tập hợp S = {1, 2, ..., 2012} với |A| = k, luôn tồn tại ba phần tử của tập A là x, y, z sao cho

c =

, b =

, a =

y + z − x 2

x + y − z 2

x + z − y 2

trong đó a, b, c là các phần tử đôi một khác nhau của S. Phân tích - Lời giải. Từ điều kiện đã cho ta thấy rằng

(cid:12) = 1007 nên tập A muốn thỏa mãn điều kiện bài toán thì

Vì a, b, c đôi một khác nhau nên x, y, z cũng đôi một khác nhau. Dễ thấy điều kiện để có các số nguyên trên là x + y + z chẵn. Ta cần tìm điều kiện của bộ số (x, y, z) sao cho x < y < z, x + y > z và x + y + z là số chẵn. (∗) Ta nhận thấy tập hợp các số lẻ A(cid:48) = {1, 3, ..., 2009, 2011} không thỏa mãn điều kiện tồn tại ba số mà tổng của chúng là số chẵn. Tiếp theo, nếu thêm số 2 vào tập hợp đó thì được tập hợp A(cid:48)(cid:48) = {1, 2, 3, ..., 2009, 2011}. Khi đó, tổng ba số trong tập hợp này là số chẵn thì chắc chắn trong ba số đó phải chứa số 2. Tuy nhiên, điều kiện thứ hai nêu ở trên là tổng của hai số phải lớn hơn số còn lại không thỏa mãn, tức là tập hợp này vẫn không thỏa mãn điều kiện. (∗) (cid:12)A(cid:48)(cid:48)(cid:12) Hơn nữa, (cid:12) |A| = k > 1007 ⇒ k ≥ 1008. Ta chứng minh k ≥ 1008 đều thỏa mãn điều kiện (∗). Nhận xét. Tổng ba số là số chẵn thì ba số đó là ba số chẵn hoặc hai số lẻ và một số chẵn. Hơn nữa, tập A có ít nhất hai số chẵn nên phải có một số không bé hơn 4. Từ ý này xét các số chẵn và số lẻ trong tập A. Ta xét tập hợp A có 1008 phần tử trong đó có a số chẵn và 1008 − a số lẻ. Ta có hai trường hợp sau:

b908 − b1 ≤ 2011 − 1 = 2010.

Trường hợp 1. số phần tử chẵn trong A nhỏ hơn 100, tức là số phần tử lẻ trong A ít nhất là 908. Ta xét 908 phần tử trong đó là b1 < b2 < ... < b908. Dễ thấy rằng

(b2 − b1) + (b3 − b2) + ... + (b908 − b907) < 2010.

Đánh giá trên có thể viết lại là

Có tất cả 907 hiệu như thế nên có thể tìm được một hiệu không vượt quá

< 2.

(cid:21)

(cid:20)2010 907

Giả sử một hiệu thỏa mãn đó là bk+1 − bk ≤ 2. Loại hiệu đó ra, ta còn 906 hiệu và tổng của chúng không vượt quá 2008.

< 3 ⇔ z ≤ 711,

2010 − 2z 907 − z

Tiếp tục tập luận như trên, ta xét đánh giá

suy ra ta có thể chọn 711 hiệu có giá trị không vượt quá 2. Giả sử hiệu có chỉ số lớn nhất là bk+1 − bk thì bk+1 − bk ≤ 2 và bk ≥ 1420. Do trong A có ít nhất hai số chẵn nên có một số chẵn không nhỏ hơn 4 và gọi số đó là a0. Khi đó bộ ba a0, bk, bk+1 thõa mãn điều kiện (∗).

Trường hợp 2. Số phần tử chẵn trong a ít nhất là 100, tức là a ≥ 100.

a1 < a2 < ... < a100 thì a100 − a1 ≤ 2012 − 2 = 2010.

Giả sử 100 số chẵn trong đó là

(a2 − a1) + (a3 − a2) + ... + (a100 − a99) ≤ 2010.

Ta cũng thấy rằng đánh giá trên có thể viết lại là

< 21.

(cid:21) Có tất cả 99 hiệu trên nên tồn tại một số hiệu không vượt quá (cid:20)2010 99

< 21.

Tuy nhiên, do đây cũng là số chẵn nên các hiệu này sẽ không vượt quá 20. Giả sử một hiệu thỏa mãn điều đó là ak+1 − ak ≤ 20. Loại hiệu đó ra, ta còn 98 hiệu và tổng của chúng sẽ không vượt quá 2010 − 20 = 1990. (cid:21) Lập luận tương tự, ta sẽ tìm được một hiệu mới không vượt quá (cid:20)1990 98

< 21 được thỏa mãn

2010 − 20z 99 − z

Tiếp tục như thế ta thấy rằng nếu đánh giá

aj ≥ 120 > 20 ≥ ak+1 − ak ⇒ aj + ak > ak+1.

thì ta sẽ tìm được tất cả z hiệu mà giá trị của chúng không vượt quá 20. Dễ thấy bất phương trình trên tương đương z < 69, nên ta có thể chọn được 68 hiệu có giá trị không vượt quá 20. Ta gọi hiệu có chỉ số lớn nhất là ak+1 − ak thì ak+1 − ak ≤ 20 và dễ thấy ak ≥ 124. Tiếp tục ta gọi hiệu có chỉ số lớn thứ nhì là aj+1 − aj thì aj+1 − aj ≤ 20 và aj ≥ 120. Dễ dàng kểm tra bộ (aj, ak, ak+1) thỏa mãn aj < ak < ak+1 và

Rõ ràng bộ ba này thỏa mãn điều kiện (∗).

Từ đây, suy ra tất cả các tập A mà |A| = k ≥ 1008 đều thỏa mãn đề bài.

Vậy giá trị nhỏ nhất cần tìm là k = 1008.

Bài toán 2.60. Cho p là số nguyên tố lẻ và đặt S = {n1, n2, ..., nk} (các phần tử có thể trùng nhau) là tập hợp tất cả các số chính phương nguyên

tố cùng nhau với p. Tìm số k nhỏ nhất sao cho tồn tại một tập con A của S thỏa mãn tích các phần tử của A đồng dư với 1 theo modulo p. Phân tích - Lời giải. Để giải bài toán này, sử dụng khái niệm căn nguyên thủy và tính chất. Gọi g là căn nguyên thủy của số nguyên tố p.

p − 1 2

. Thật vậy:

Nếu k < thì xét tập S = (cid:8)g2, g2, ..., g2(cid:9) của k phần tử g2. Khi đó, tích Ta sẽ chứng minh k = p − 1 2

p − 1 2

. Do g

p − 1 2

. Thật vậy, ta xét các số

các phần tử của tập con bất kì của S đều có dạng g2a với a < là căn nguyên thủy của p nên g2a không đồng dư với 1 modulo p.

α1, α1 + α2, ..., α1 + α2 + ... + αp − 1

Như vậy k ≥ Xét tập hợp S = {n1, n2, ..., nk}. Vì (cid:8)1, g, ..., gp−1(cid:9) là hệ thặng dư đầy đủ theo modulo p nên giả sử ni = g2.αi với 0 ≤ αi ≤ p − 1 theo modulo p. Do đó, tích các phần tử của một tập con bất kì của S đều có dạng g2.a trong đó a chính là tổng các phần tử của tập J = {α1, ..., αk}. Bây giờ ta sẽ chứng minh trong tập J luôn tồn tại một tập con có tổng các phần tử chia hết cho p − 1 2

p − 1 2

có tất cả là số.

p − 1 2

Nếu trong các số trên tồn tại một số chia hết cho thì khẳng định được

chứng minh. Ngược lại, tồn tại i < j sao cho

mod

α1 + α2 + ... + αi ≡ α1 + α2 + ... + αj

p − 1 2

(cid:18) (cid:19)

mod

αi+1 + αi+2 + ... + αj ≡ 0

p − 1 2

Suy ra (cid:19) (cid:18)

Tóm lại, trong tập J luôn tồn tại một số phần tử sao cho tổng các phần tử

p − 1 2

, vì vậy luôn tồn tại một tập con của S sao cho tích

Vậy số nguyên k nhỏ nhất là này chia hết cho các phần tử của tập này bằng gm(p−1) đồng dư với 1 modulo p. p − 1 2 Nhận xét. Đây là bài toán cực trị trên tập hợp rời rạc, nhưng kiến thức sử

1 , nm

2 , ..., nm

dụng để giải trong bài này hoàn toàn là số học, với khái niệm căn nguyên thủy.

Bài toán 2.61. (Bài toán tổng quát) Cho p là số nguyên tố lẻ và đặt S = {nm k } là tập hợp tất cả các số chính phương nguyên tố cùng nhau với p. Tìm số k nhỏ nhất sao cho tồn tại một tập con A của S thỏa mãn tích các phần tử của tậpA đồng dư với 1 theo modulo p.

p − 1 m Nhận xét. Bài toán trên chúng ta có thể thay số nguyên tố p bằng số tự nhiên n có căn nguyên thủy.

Đáp số của bài toán là: kmin =

x ∈ S|x

S = {1, 2, ..., N } , A3 =

Bài toán 2.62. Tìm số nguyên dương lớn nhất N sao cho số tất cả các số nguyên dương trong tập {1, 2, ..., N } chia hết cho 3 bằng số tất cả các số nguyên trong tập đó chia hết cho 5 hoặc 7. Phân tích - Lời giải. Đặt (cid:110)

x ∈ S|x

A5 =

, A7 =

(cid:110) (cid:111) (cid:110) ...5 (cid:111) ...3 (cid:111) ...7

Khi đó

|A3| =

, |A5| =

, |A7| =

, |A5 ∩ A7| =

(cid:21) (cid:21) (cid:21) (cid:21)

(cid:20)N 3 (cid:20)N 5 (cid:20)N 7 (cid:20) N 35

|A3| = |A5| + |A7| − |A5 ∩ A7| ,

Theo yêu cầu bài toán |A3| = |A5 ∪ A7|. Áp dụng nguyên lý bù trừ, ta có

(1)

−

hay (cid:21) (cid:21) (cid:21) (cid:21)

(cid:20)N 3 (cid:20) N 35 (cid:20)N 7

−

(cid:21) (cid:21) (cid:21) (cid:21)

(cid:20)N 5 Ta có N = 35k + r (k ∈ N, 0 ≤ r ≤ 34), thay và (1) ta được (cid:20)35k + r (cid:20)35k + r 35 5 (cid:20)35k + r 7 (cid:20)35k + r 3

11k +

= 7k +

+ 5k +

− k −

Suy ra (cid:21) (cid:105) (cid:105) (cid:105)

(cid:104)r 5 (cid:104)r 7 (cid:104) r 35 (cid:20)2k + r 3

−

hay (cid:21) (cid:105) (cid:105) (cid:105)

(cid:20)2k + r 3 (cid:104)r 5 (cid:104)r 7 (cid:104) r 35

− 1 <

−

≤

− 0.

2k + r 3

Vì x − 1 < [x] ≤ x < [x] + 1 nên (cid:21) (cid:105) (cid:105) (cid:105)

r 5

r 7

(cid:20)2k + r 3 (cid:104)r 5 (cid:104)r 7 (cid:104) r 35

+ 3 ⇒ 2k <

+ 3 (cid:39) 3, 97.

2k <

r 35

34 35

Suy ra

⇒ k ≤ 1. Vì vậy N = 35k + r ≤ 35 + 34 = 69.

3 2

Do đó k ≤

Thay N = 69, 68, 67, 66, 65 vào (1), ta thấy N = 65 thỏa mãn. Nhận xét. Bài toán tổ hợp trên có cách giải khá tự nhiên, ta phải biết kiến thức nguyên lý bù trừ và biết kiến thức về hàm phần nguyên. Tương tự, sử dụng tính chất hàm phần nguyên trong bài toán sau:

(cid:105)

1 − s(cid:48) 2

1, s(cid:48)

Bài toán 2.63. (Chọn đội đội tuyển Việt Nam - 2008) Cho số nguyên dương n > 3. Kí hiệu T là tập hợp gồm n số nguyên dương đầu tiên. Một tập con S của T được gọi là tập khuyết trong T nếu S có tính chất: Tồn tại (cid:104)n số nguyên dương c không vược quá sao cho với s1, s2 là hai số bất kì 2

2 thì rõ ràng (cid:12) (cid:12) = c. Mâu thuẫn

(cid:105) .

(cid:1) − (cid:0)n − s(cid:48) 2

(cid:12)S (cid:48)(cid:12) (cid:12) nên khi S có số phần tử là lớn nhất thì tương ứng có

(cid:105)

(cid:104)n 2

không ít hơn số phần tử lớn hơn thuộc S ta luôn có |s1 − s2| (cid:54)= c. Hỏi tập khuyết trong T có tối đa bao nhiêu phần tử? Phân tích - Lời giải. Trước hết ta thấy rằng: Nếu S là một tập khuyết trong T thì S (cid:48) = {n − x|x ∈ S} cũng là tập khuyết trong T . Thật vậy: Giả sử ngược lại S (cid:48) không phải là tập khuyết trong T , khi đó tồn (cid:12) 2 ∈ S (cid:48) sao cho (cid:12) (cid:12)s(cid:48) tại hai số nguyên dương s(cid:48) (cid:12) = c với c là một số (cid:104)n nguyên dương nào đó không vượt quá 2 1, s2 = n − s(cid:48) Khi đó, xét tương ứng hai phần tử s1 = n − s(cid:48) (cid:12) = (cid:12) (cid:1)(cid:12) s1, s2 ∈ S và |s1 − s2| = (cid:12) (cid:0)n − s(cid:48) 1 − s(cid:48) (cid:12)s(cid:48) (cid:12) 2 1 với S là tập khuyết, nên nhận xét trên được chứng minh. Hơn nữa, do |S| = (cid:12) tập hợp S (cid:48) có số phần tử lớn nhất bằng với số phần tử của S. Từ đó, ta có thể xét các tập khuyết S có số phần tử không vượt quá (cid:104)n (cid:105) . Xét hai tập sau: 2

A =

x|x ∈ S, x ≤

x|x ∈ S, x >

, B =

n 2

(cid:110) (cid:111) (cid:110) (cid:111)

n 2 thì A ∩ B = ∅, A ∪ B = S và theo cách xác định trên thì |A| ≥ |B| . (cid:105) Khi đó, với c là một số nguyên dương nào đó không vượt quá

, ta xét (cid:104)n 2

|A ∪ B ∪ C| ≤ |T | ⇔ |A| + |B| + |C| ≤ n.

tập hợp C = {x + c|x ∈ A}. Ta có |A| = |C|, do A ⊂ S nên A cũng là tập khuyết và khi đó A ∩ C = ∅, B ∩ C = ∅ (vì nếu ngược lại thì tồn tại hai phần tử thuộc S mà hiệu của chúng bằng c, mâu thuẫn). Suy ra các phần tử của tập A hoặc B hoặc C đều là một số nguyên dương không vượt quá n, tức là A ∪ B ∪ C ⊂ S. Suy ra

|A| + |B| ≤

≤

4 |A| + 2 |B| 3

2n 3

Kết hợp các điều kiện lại ta được: 2 |A| + |B| ≤ n. Vì |A| ≥ |B| nên

(cid:21) Do đó, số phần tử của tập khuyết S không vượt quá (cid:20)2n 3 (cid:21) Bây giờ ta sẽ chỉ ra một tập khuyết có đúng phần tử. (cid:20)2n 3

1, 2, ...,

A =

+ 1, n −

+ 2, ..., n

, B =

n −

(cid:26) (cid:21)(cid:27) (cid:105) (cid:111) (cid:105) (cid:110)

Thật vậy, ta xét hai tập hợp A và B như sau: (cid:20)n + 1 3 (cid:104)n 3 (cid:104)n 3

. Khi đó, ta có

≤

• Hiệu của hai phần tử bất kì trong A không vượt quá

(cid:21) (cid:105) Và đặt S = A ∪ B. Chọn c = (cid:20)n + 1 3 (cid:104)n 2

− 1 <

(cid:21) (cid:21)

• Hiệu của hai phần tử bất kì trong B không vượt quá

(cid:20)n + 1 3 (cid:20)n + 1 3

+ 1

− 1 <

n −

(cid:21) (cid:17) (cid:105) (cid:105) (cid:16)

• Hiệu một phần tử bất kì trong A và một phần tử trong B không nhỏ

(cid:104)n 3 (cid:104)n 3 (cid:20)n + 1 3

hơn

n −

+ 1

−

≥ n −

−

+ 1 =

≥

(cid:21) (cid:21) (cid:16) (cid:105) (cid:17)

n 3

n + 1 3

n + 2 3

(cid:104)n 3 (cid:20)n + 1 3 (cid:20)n + 1 3

≤

c =

(cid:21) (cid:105) . Khi đó, rõ ràng S = A ∪ B là một tập khuyết trong T ứng với giá trị (cid:20)n + 1 3 (cid:104)n 2

. Từ cách

(cid:21) Để hoàn thành chứng minh thì ta phải chứng minh |S| = (cid:20)2n 3 (cid:21) (cid:105)

, |B| = (cid:21) (cid:20)2n , với mọi n ∈ N∗. (∗) 3

(cid:104)n 3 xây dựng A và B ta có, |A| = (cid:21) Ta cần chứng minh: (cid:20)n + 1 3 (cid:20)n + 1 3 (cid:104)n (cid:105) 3

• Nếu n chia hết cho 3 thì n = 3m với m ∈ N, suy ra:

Xét các trường hợp:

(cid:21) (cid:21) (cid:21) (cid:21) (cid:105)

6m 3

• Nếu n chia cho 3 dư 1 thì n = 3m + 1 với m ∈ N, suy ra: (cid:21)

(cid:20)n + 1 3 (cid:104)n 3 (cid:20)3m + 1 3 (cid:20)3m 3 (cid:20)2n 3

(cid:21) (cid:21) (cid:21) (cid:21) (cid:105)

6m 3

• Nếu n chia cho 3 dư 2 thì n = 3m + 2 với m ∈ N, suy ra: (cid:21)

(cid:20)n + 1 3 (cid:104)n 3 (cid:20)3m + 2 3 (cid:20)3m + 1 3 (cid:20)6m + 2 3 (cid:20)2n 3

(cid:21) (cid:21) (cid:21) (cid:21) (cid:105)

6m + 3 3

(cid:20)n + 1 3 (cid:104)n 3 (cid:20)3m + 3 3 (cid:20)3m + 2 3 (cid:20)6m + 4 3 (cid:20)2n 3

(cid:21) Từ đó, suy ra (∗) được chứng minh hay tập khuyết S đã cho có

. (cid:21) . Vậy giá trị lớn nhất của số phần tử của tập khuyết S trong T là (cid:20)2n 3 (cid:20)2n 3

x = m2 − n2, y = 2mn, z = m2 + n2.

Bài toán 2.64. Tìm số nguyên dương k nhỏ nhất sao cho mọi tập con gồm k phần tử của tập A = {1, 2, ..., 50} luôn chứa 3 số là độ dài 3 cạnh của một tam giác vuông. Phân tích - Lời giải. Để giải bài toán này, ta cần liệt kê tất cả các bộ Pitago (x, y, z), để làm điều này ta chỉ cần tìm được tất cả các bộ Pitago nguyên thủy (x, y, z). Như chúng ta đã biết, x, y, z lập thành bộ ba nguyên thủy, với y chẵn khi và chỉ khi tồn tại hai số nguyên dương nguyên tố cùng nhau m, n với m > n và m, n khác tính chẵn lẻ sao cho

(3, 4, 5), (15, 8, 17), (5, 12, 13), (21, 20, 29), (7, 24, 25), (9, 40, 41).

Từ nhận xét trên, ta có thể liệt kê được tất cả các cặp Pitago nguyên thủy là:

(3, 4, 5) , (6, 8, 10) , (9, 12, 15) , (12, 16, 20) , (15, 20, 25) ;

(15, 8, 17) , (30, 16, 34) ;

(5, 12, 13) , (10, 24, 26) , (15, 36, 39) ;

(21, 20, 29) ; (7, 24, 25) , (14, 48, 50) ; (9, 40, 41) .

Do đó, tất cả các cặp Pitago là:

(3, 4, 5) , (6, 8, 10) , (12, 35, 37) , (27, 36, 45) , (9, 40, 41) ;

(21, 20, 41) , (7, 24, 25) , (14, 48, 50) , (16, 30, 34) .

Xét tập hợp B = {5, 8, 9, 16, 20, 24, 35, 36, 50} . Dễ thấy mọi bộ ba Pitago đều có ít nhất một số thuộc tập B nên tập C = A\B không chứa bộ ba Pitago nào. Do đó k > |C| = 41. Bây giờ ta chứng minh k = 42 thỏa mãn yêu cầu bài toán. Xét 9 bộ Pitago rời nhau như sau:

Theo nguyên lý Dirichlet bất kì tập hợp gồm 42 phần tử nào đó của tập A cũng phải chứa ít nhất một bộ 3 số Pitago trong 9 bộ trên. Vậy kmin = 42. Nhận xét. Bài này chúng ta phải biết tìm nghiệm nguyên dương của phương trình x2 + y2 = z2.

(6, 3) , (12, 6) , (18, 9) , (24, 12) , (30, 15) , (36, 18) , (42, 21) , (48, 24) .

Bài toán 2.65. Tìm số nguyên dương k nhỏ nhất sao cho mọi tập hợp gồm k phần tử của tập {1; 2; ...; 50} đều chứa hai phần tử khác nhau a, b sao cho a + b chia hết ab. Phân tích - Lời giải. Để giải bài toán này, ta cần tìm tất cả các cặp (a, b) với a > b sao cho a + b chia hết ab. Đặt c = (a, b) suy ra a = ca1, b = cb1. Khi đó, theo giả thiết ta có c (a1 + b1) |c2a1b1 suy ra (a1 + b1) |c. Vì a, b ∈ {1, 2, ..., 50} nên a+b ≤ 99 hay c (a1 + b1) ≤ 99. Suy ra a1+b1 ≤ 9. Mặt khác a1 + b1 ≥ 3. Do đó ta có các khả năng xảy ra. Nếu a1 + b1 = 3 thì (a1, b1) = (2, 1) và c là bội của 3. Khi đó các cặp thỏa mãn trong trường hợp này

(12, 4) , (24, 8) , (36, 12) , (48, 16) .

Nếu a1 + b1 = 4 thì (a1, b1) = (3, 1) , c = 4k; k = 1, 2, ... Khi đó các cặp (a, b) là

(20, 5) , (40, 10) , (15, 10) , (30, 20) , (45, 30) .

Nếu a1 + b1 = 5 thì (a1, b1) = (4, 1) , (a1, b1) = (3, 2) , c = 5k; k = 1, 2, ... Khi đó các cặp (a, b) là

(42, 7) , (35, 14) , (28, 21) .

Nếu a1 + b1 = 7 thì (a1, b1) = (6, 1) , (a1, b1) = (4, 3) , c = 7k; k = 1, 2, ... Khi đó các cặp (a, b) là

M = {6, 12, 15, 18, 20, 21, 24, 35, 40, 42, 45, 48} .

Nếu a1 + b1 = 8 thì (a1, b1) = (7, 1) , (a1, b1) = (5, 3) , c = 8k; k = 1, 2, ... Khi đó (a, b) = (40; 24). Nếu a1 + b1 = 9 thì (a1, b1) = (8, 1) , (a1, b1) = (7, 2) , (a1, b1) = (5, 4) , c = 9k; k = 1, 2, ... Do đó (a, b) = (45; 36). Ta thấy mỗi cặp được liệt kê ở trên luôn chứa một phần tử của tập

(6, 3) , (12, 4) , (20, 5) , (42, 7) , (24, 8) , (18, 9) , (40, 10) ,

(35, 14) , (30, 15) , (48, 16) , (28, 21) , (45, 36) .

Như vậy T = {1, 2, ..., 50} − M không có tính chất đòi hỏi. Vì |T | = 50 − 12 = 38 nên k ≥ 39. Bây giờ ta phải chứng minh mọi tập con có 39 phần tử đều thỏa mãn bài toán. Từ 23 cặp đã liệt kê ở trên ta chọn ra 12 cặp mà không có phần tử nào trong mỗi cặp được lặp lại như sau :

Theo nguyên lý Drichlet, bất kỳ tập hợp gồm 39 phần tử nào cũng chứa ít nhất một cặp vừa liệt kê trên. Vậy bài toán được chứng minh. Bài này ta cần biết được các số nguyên tố bé hơn 1000, cũng dựa vào kết quả các số nguyên tố này giúp ta định hướng cách giải bài toán sau.

k ∈ S : k

(cid:110) (cid:110) (cid:111) (cid:110) ; (cid:111) ...5 (cid:111) ...3 ...2 ; A2 = ; A3 = Bài toán 2.66. Cho tập hợp S = {1; 2; ...; 280}. Tìm số tự nhiên n nhỏ nhất sao cho mọi tập con gồm n phần tử của S đều chứa 5 số đôi một nguyên tố cùng nhau. Phân tích - Lời giải. Để giải bài toán này trước hết, ta cần đếm xem trong tập S có bao nhiêu số là bội của 2, 3, 5, 7. Đặt A1 =

k ∈ S : k

A4 = Khi đó

|A1| = 140; |A2| = 93; |A3| = 56; |A4| = 40;

|A1 ∩ A2| = 46; |A1 ∩ A3| = 28; |A1 ∩ A4| = 28;

|A1 ∩ A2 ∩ A3| = 9; |A1 ∩ A2 ∩ A4| = 6; |A1 ∩ A3 ∩ A4| = 4;

|A2 ∩ A3 ∩ A4| = 2; |A1 ∩ A2 ∩ A3 ∩ A4| = 1.

(cid:110) (cid:111) . ...7

Đặt A = A1 ∪ A2 ∪ A3 ∪ A4, theo nguyên lý bù trừ, ta có:

4 (cid:88)

|A| =

|Ai ∩ Aj ∩ Ak|−|A1 ∩ A2 ∩ A3 ∩ A4|

|Ai|−

|Ai ∩ Aj|+

1≤i

i=1

1≤i

(cid:88) (cid:88)

B2 = {11.11; 11.13; 11.17; 11.19; 11.23; 13.13; 13.17; 13.19}.

Do đó |A| = 216. Theo nguyên lý Dirichlet, với 5 số đôi một khác nhau của A ta luôn tìm được 2 số thuộc cùng một tập hợp Ai và 2 số này không nguyên tố cùng nhau. Dẫn đến n ≥ 217. Ta chứng minh n = 217 là số nhỏ nhất thỏa mãn bài toán. Bây giờ đếm trong tập S có bao nhiêu số nguyên tố. Để làm điều này, ta đếm tất cả các hợp số của tập S. Đặt B1 = A\ {2, 3, 5, 7} và

|P | = |S| − (|B1| + |B2|) = 60.

Khi đó B1 ∪ B2 là tập hợp các hợp số của S. Vì vậy P = S\ (B1 ∪ B2) là tất cả các nguyên tố của tập S. Ta có

|T ∩ (S\P )| = |(T ∩ S) \ (T ∩ P )| = |T ∩ S| − |T ∩ P | ≥ 217 − 4 = 213.

Giả sử T là một tập hợp bất kì gồm 217 phần tử thuộc S thì chỉ ra T luôn tồn tại 5 số đôi một nguyên tố cùng nhau. Nếu |T ∩ P | ≥ 5 thì bài toán thỏa mãn. Nếu |T ∩ P | ≤ 4 thì

M1 = {2.23; 3.19; 5.17; 7.13; 11.11} , M2 = {2.29; 3.23; 5.19; 7.17; 11.13} ,

Chứng tỏ rằng trong 220 số không phải là số nguyên tố của S thì nhiều nhất là có 7 phần tử không thuộc T . Điều này gợi ý cho ta xây dựng 8 tập hợp con rời nhau mỗi tập hợp gồm 5 phần tử đôi một nguyên tố cùng nhau và các số đều là hợp số.

M3 = {2.31; 3.29; 5.23; 7.19; 11.17} , M4 = {2.37; 3.31; 5.29; 7.23; 11.19} ,

M5 = {2.41; 3.37; 5.31; 7.29; 11.23} , M6 = {2.43; 3.41; 5.37; 7.31; 13.17} , M7 = {2.47; 3.43; 5.41; 7.37; 13.19} , M8 = (cid:8)22; 32; 52; 72; 132(cid:9) . Rõ ràng Mi ⊂ S\P, i = 1, 2, .., 8 và mọi phần tử trong tập Mi đôi một nguyên tố cùng nhau. Do có không quá 7 phần tử của S\P không thuộc T nên theo nguyên lý Đirichlet tồn tại một Mi ⊂ T . Ta có điều phải chứng minh.

2.5 Số phức - Tổ hợp

Ý tưởng ở phần này là chuyển những bài toán đếm về bài toán xác định hệ số của đa thức. Hơn nữa, ở phần này, ta xác định các hệ số đặc biệt liên quan tính chất chia hết. Để làm tốt điều này, trước tiên ta chứng minh hai bổ đề sau:

a0 + a1ε + ... + ap−1εp−1 = 0,

Bổ đề 2.1. Nếu p là một số nguyên tố và a0, a1, .., ap−1 là những số nguyên sao cho

+ i sin

2π p

trong đó ε = cos thì a0 = a1 = ... = ap−1.

Chứng minh. Ta thấy 1+x+...+xp−1, a0 +a1x+...+ap−1xp−1 là hai đa thức hệ số nguyên nhận ε làm nghiệm. Vì p là số nguyên tố nên đa thức 1 + x + ... + xp−1 bất khả quy trên Q, do đó nó không thể phân tích thành tích của hai đa thức hệ số hữu tỉ có bậc dương. Vì vậy đa thức 1 + x + ... + xp−1 là ước của đa thức a0 + a1x + ... + ap−1xp−1 mà điều này chỉ xảy ra khi a0 = a1 = ... = ap−1.

akxk là đa thức với hệ số nguyên và m là số

n (cid:80) k=0

Bổ đề 2.2. Nếu f (x) =

f (cid:0)εj(cid:1),

ak =

1 m

m−1 (cid:80) j=0

nguyên dương thì

+ i sin

2π m

. trong đó ε = cos (cid:80) ...m 2π m Chứng minh.

n (cid:88)

m−1 (cid:88)

εjk

f (cid:0)εj(cid:1) =

akεjk

j=0

k=0

(cid:33) (cid:32) n (cid:88)  ak  .

m−1 (cid:88)

Nếu k chia hết cho m thì 1 + εk + ... + εk(p−1) = m, nếu k không chia hết cho m thì 1 + εk + ε2.k... + εk(m−1) = 0. Suy ra

f (cid:0)εj(cid:1).

ak =

1 m

j=0

(cid:88)

...m

Áp dụng giải một số bài toán "số học - tổ hợp " sau.

Bài toán 2.67. Tìm số các số gồm 2016 chữ số mà các chữ số nhận các giá trị thuộc tập hợp {1, 3, 4, 6, 7, 9} và có tổng các chữ số chia cho 7 dư i (i = 0, 1, 2, ..., 6) . Phân tích - Lời giải. Gọi X là tập hợp các số gồm n (n chia hết cho 7) chữ số mà các chữ số nhận các giá trị thuộc tập hợp {1, 3, 4, 6, 7, 9}. Khi đó |X| = 6n. Đặt Xi = {x ∈ X|S (x) ≡ i (mod7)} , i = 0, 1, ..., 7, với S(x) là tổng các chữ số của x. Xét đa thức

f (x) = (cid:0)x + x3 + x4 + x6 + x7 + x9(cid:1)n =

akxk,

(cid:88)

f (ε) = |X0| + |X1| ε + .... + |X6| ε6 ⇔ |X0| + |X1| ε + .... + |X6| ε6 = (cid:0)−ε5(cid:1)n = (−1)n,

trong đó ak là tổng tất cả các bộ có thứ tự gồm n chữ số mà có tổng bằng k. Khi đó

+ i sin

2π 7

trong đó ε = cos

|X0|−(−1)n = |X1| = ... = |X6| =

|X0| − (−1)n + |X1| + ... + |X6| 7

6n − (−1)n 7

Theo bổ đề 2.1, ta có

|X0| − (−1)n + |X1| + ... + |X6| 7

6n − (−1)n 7

+ (−1)n.

|X0| =

Do đó  

|X1| = ... = |X6| = 6n − (−1)n 7



f (x) = (cid:0)x3 + x4 + x5 + x6(cid:1)n =

akxk,

Bài toán 2.68. (PTNK TP Hồ Chí Minh) Tìm số các số gồm n mà số đó chia hết cho 3 đồng thời các chữ số nhận các giá trị thuộc tập hợp {3, 4, 5, 6}. Phân tích - Lời giải. Một số chia hết cho 3 khi và chỉ khi tổng các chữ số của nó chia hết cho 3. ...3. Như vậy, ta cần đếm tất cả các bộ (x1, x2, ..., xn) mà (x1 + x2 + ... + xn) Xét đa thức (cid:88)

ak là số các bộ mà có tổng chia hết cho 3.

...3.

trong đó ak là tổng tất cả các bộ (x1, x2, ..., xn) mà (x1 + x2 + ... + xn) Suy ra (cid:80) ...3 Theo bổ đề 2.2, ta có

+ i sin

ak =

1 3

2π 3

(cid:88) (cid:2)f (1) + f (ε) + f (cid:0)ε2(cid:1)(cid:3) , ε = cos

...3

f (1) = 4n, f (ε) = (cid:0)1 + ε + ε2 + 1(cid:1)n = 1, f (cid:0)ε2(cid:1) = (cid:0)1 + ε2 + ε + 1(cid:1)n = 1.

Ta có

ak =

4n + 2 3

Do đó (cid:88)

...3

(1) Lấy một số thuộc An rồi thêm 3 hoặc 6 vào phía sau (cả hai đều được). (2) Lấy một số thuộc Bn rồi thêm 4 hoặc 5 vào phía sau (chỉ có duy nhất

1 cách thêm). Do đó, ta có công thức

(1)

an+1 = 2an + bn.

Ngoài cách giải trên, chúng ta có thể giải bài toán này bằng phương pháp thiết lập hệ thức truy hồi. Gọi An là tập hợp các số có n chữ số lập được từ các chữ số thuộc tập {3, 4, 5, 6} và chia hết cho 3 và Bn là tập hợp các số có n chữ số lập được từ các chữ số thuộc tập {3, 4, 5, 6} và không chia hết cho 3. Ta cần tính an = |An| . Đặt bn = |Bn| . Ta thấy rằng mỗi số thuộc An+1 có thể thu được (và chỉ có thể thu được) bằng hai cách sau đây:

(2)

bn+1 = 2an + 3bn.

Lý luận hoàn toàn tương tự với Bn+1, ta được

an+2 − 2an+1 = 2an + 3 (an+1 − 2an) .

Rút bn = an+1 − 2an và bn+1 = an+2 − 2an+1 từ (1) rồi thế vào (2) ta được

(3)

an+2 − 5an+1 + 4an = 0.

Sau khi rút gọn ta được

Ta thấy a1 = 2 (với hai số 3 và 6), a2 = 6 (với sáu số 33, 66, 36, 63, 45, 54). Giải phương trình sai phân với điều kiện a1 = 2 và a2 = 6, ta được

an =

4n + 2 3

an = 4n−1+an−1 = 4n−1+4n−2+an−2 = ... = 4n−1+4n−2+...+1+a1 =

4n + 2 3

Ngoài cách trên, ta có thể lý luận tính bn như sau: Theo quy tắc nhân, số các số gồm n chữ số lập được từ các chữ số thuộc tập {3, 4, 5, 6} bằng 4n, nên bn = 4n − an. Như vậy, ta có thể thu được công thức truy hồi an+1 = 2an + 4n − an, từ đó

f (x) = (cid:0)x + x2 + .... + xn(cid:1)m =

akxk,

ak là số các các số gồm m chữ số mà có tổng chia hết cho p.

Bài toán 2.69. Cho 2 số nguyên dương m, n và p là số nguyên tố, trong đó n + 1 chia hết cho p. Tìm tất cả các số gồm m chữ số sao cho tổng chia hết cho p, các chữ số nhận giá trị của tập {1, 2, ..., n} . Phân tích - Lời giải. Xét đa thức (cid:88)

trong đó ak là tổng các bộ (x1, x2, ..., xm) thỏa mãn x1 + x2 + ... + xm = k. Suy ra (cid:80) ...p Theo bổ đề 2.2, ta có

+ i sin

ak =

2π p

1 p

(cid:88) (cid:2)f (1) + f (ε) + ... + f (cid:0)εp−1(cid:1)(cid:3) , ε = cos

...p

f (1) = nm,

Ta có

f (cid:0)εi(cid:1) = (cid:0)εi + ε2i + .... + εni(cid:1)m

− 1

= (−1)m.

ε(n+1)i − 1 εi − 1

(cid:32) (cid:33)m

Suy ra

ak =

nm + (p − 1) (−1)m p

(cid:88)

...p

f (x) = (cid:0)x + x2 + ... + xn(cid:1)3 =

akxk,

Bài toán 2.70. Cho số nguyên tố lẻ p và số nguyên dương n trong đó n + 2 chia hết cho p. Tìm số bộ số nguyên dương (x, y, z) sao cho x + y + z chia hết cho p, trong đó mỗi x, y, z đều không lớn hơn n. Phân tích - Lời giải. Xét đa thức (cid:88)

trong đó ak là số các bộ (x, y, z) với mỗi x, y, z ∈ {1, 2, ..., n} và x+y+z = k. Theo bổ đề 2.2, ta có

+ i sin

ak =

2π p

1 p

(cid:88) (cid:2)f (1) + f (ε) + ... + f (cid:0)εp−1(cid:1)(cid:3) , ε = cos

...p Ta có f (1) = n3 và

f (cid:0)εj(cid:1) =

− 1

= −

ε(n+1)j − 1 εj − 1

(cid:32) (cid:33)3 (cid:32) (cid:33)3 (cid:19)3

ε(n+2)j − εj ε2j − εj − 1 = − (cid:0)1 + 3ε−j + 3ε−2j + ε−3j(cid:1) .

(cid:18) 1 εj + 1

f (ε) + ... + f (cid:0)εp−1(cid:1) = − (p − 1 + 3δ (1) + 3δ (2) + δ (3)) ,

Do đó

trong đó

δ (k) =

ε−kj =

(cid:26)p − 1 nếu k chia hết cho p,

−1

p−1 (cid:80) j=1

nếu k không chia hết cho p.

Suy ra

ak =

n3 − [p − 1 + 3δ (1) + 3δ (2) + δ (3)] p

(cid:88)

ak =

n3 + 2 3

...p

ak =

n3 + 8 − p p

Nếu p = 3 thì δ (1) = δ (2) = −1, δ (3) = 2 ⇒ (cid:80) ...3

Nếu p > 3 thì (cid:80) ...p

Ngoài ra ta có thể sử dụng nguyên lý bù trừ.

∈ N∗, suy ra n = kp − 2. Xét tập hợp D = {kp − 1, kp} và

n + 2 p

E = {1, 2, ..., kp}. Xét các tập hợp

Đặt k =

A =

(x, y, z) |x, y, z ∈ E\D; x + y + z

;

(cid:110) (cid:111) ...p

;

B =

(x, y, z) |x, y, z ∈ E; x + y + z

(cid:110) (cid:111) ...p

C =

(x, y, z) |x ∈ D ∨ y ∈ D ∨ z ∈ D; x + y + z

(cid:110) (cid:111) ...p

...p.

Khi đó |A| = |B| − |C| . - Tính |B|. Có kp cách chọn x ∈ E và có kp cách chọn y ∈ E. Với cách chọn x, y có k cách chọn z để cho (x + y + z) Do đó |B| = km.km.k = k3p2. - Tính |C|. Đặt

X =

;

(cid:110) (cid:111)

Y =

(x, y, z) |y ∈ D, x ∈ E, z ∈ E, x + y + z

;

(cid:110)

Z =

(x, y, z) |z ∈ D, x ∈ E, y ∈ E, x + y + z

(cid:110) ...p (x, y, z) |x ∈ D, y ∈ E, z ∈ E, x + y + z (cid:111) ...p (cid:111) ...p

|C| = |X| + |Y | + |Z| − (|X ∩ Y | + |Y ∩ Z| + |Z ∩ X|) + |X ∩ Y ∩ Z| .

Khi đó C = X ∪ Y ∪ Z. Theo nguyên lý bù trừ, ta có

|X| = |Y | = |Z| = 2k2p.

Tính |X|. Có 2 cách chọn x, có kp cách chọn y, ứng với x, y đã chọn có k cách chọn z để cho (x + y + z) ...p. Do đó |X| = 2k2p. Suy ra

|X ∩ Y | = |Y ∩ Z| = |Z ∩ X| = 4k,

Tính |X ∩ Y | . Có 2 cách chọn phần tử x, 2 cách chọn phần tử y, ứng với x, y đã chọn có k cách chọn phần tử z. Do đó |X ∩ Y | = 4k. Suy ra

|X ∩ Y ∩ Z| =

và

(cid:26)1 nếu p > 3 2 nếu p = 3

n + 2 p

, ta được Thay k =

n3 + 2 3

|A| =

nếu p = 3

n3 + 8 − p p

nếu p > 3   

Bài toán 2.71. (Chọn đội tuyển Việt Nam - 2008) Kí hiệu M là tập hợp gồm 2008 số nguyên dương đầu tiên. Tô tất cả các số thuộc M bởi ba màu xanh, đỏ, vàng sao cho mỗi số được tô bởi một màu và mỗi màu dùng để tô ít nhất một số. Giả sử S1 là tập hợp tất các các bộ (x, y, z) ∈ M 3 trong đó x, y, z cùng màu và (x + y + z) ≡ 0 (mod2008); S2 là tập hợp tất các các bộ (x, y, z) ∈ M 3 trong đó x, y, z đôi một khác màu và (x + y + z) ≡ 0 (mod2008). Chứng minh rằng 2 |S1| > |S2|. (Kí hiệu M 3 là tích Đề - cac M × M × M ). Phân tích - Lời giải. Gọi A, B, C lần lượt là tập hợp tương ứng gồm các số được tô màu xanh, đỏ, vàng. Xét các đa thức

xc.

xa, G (x) =

xb, H (x) =

F (x) =

c∈C

a∈A

b∈B

(cid:88) (cid:88) (cid:88)

fnxn,

xc1+c2+c3 = (cid:80) n

I (x) = F 3 (x) + G3 (x) + H 3 (x) = xb1+b2+b3 + (cid:80) ci∈C

Khi đó

xa1+a2+a3 + (cid:80) bi∈B

(cid:80) ai∈A

2007 (cid:88)

I (cid:0)εk(cid:1) =

trong đó fn là tổng tất cả các bộ (x, y, z) được tô cùng một màu và x+y+z = n. Theo bổ đề 2.2, ta có

(1)

|S1| =

1 2008

k=0

+ i sin

(cid:0)F 3 (cid:0)εk(cid:1) + G3 (cid:0)εk(cid:1) + H 3 (cid:0)εk(cid:1)(cid:1),

2π 2008

trong đó ε = cos

Và đa thức

J (x) = F (x) .G (x) .H (x) =

xa+b+c =

gnxn,

a∈A b∈B c∈C

(cid:88) (cid:88)

trong đó gn là tổng tất cả các bộ (x, y, z) với x, y, z lần lượt được tô màu xanh, đỏ, vàng và x + y + z = n.

2007 (cid:88)

Theo bổ đề 2.2, ta có

F (cid:0)εk(cid:1) .G (cid:0)εk(cid:1) .H (cid:0)εk(cid:1).

gk =

1 2008

k=0

(cid:88)

...2008

2007 (cid:88)

F (cid:0)εk(cid:1) .G (cid:0)εk(cid:1) .H (cid:0)εk(cid:1) =

3F (cid:0)εk(cid:1) .G (cid:0)εk(cid:1) .H (cid:0)εk(cid:1).

(2)

|S2| =

6 2008

2 2008

k=0

εi = 0, nên suy ra

Do hoán vị, nên

2007 (cid:80) i=0

F 3 (cid:0)εk(cid:1) + G3 (cid:0)εk(cid:1) + H 3 (cid:0)εk(cid:1) = 3F (cid:0)εk(cid:1) G (cid:0)εk(cid:1) H (cid:0)εk(cid:1) .

(3)

Nếu k (cid:54)= 0 thì F (cid:0)εk(cid:1) + G (cid:0)εk(cid:1) + H (cid:0)εk(cid:1) =

F 3 (1) + G3 (1) + H 3 (1) ≥ 3F (1) .G (1) .H (1) .

Áp dụng bất đẳng thức Cauchy, ta có

F 3 (1) + G3 (1) + H 3 (1) > 3F (1) .G (1) .H (1) .

(4)

Dấu bằng xảy ra khi và chỉ khi F (1) = G (1) = H (1), suy ra 3F (1) = 2008 điều này không xảy ra do 2008 không chia hết 3. Vì vậy

Từ (1), (2), (3) và (4) suy ra 2 |S1| > |S2|. Nhận xét. Bài này giải thuần túy tổ hợp như đáp án thì quá phức tạp, sử dụng công cụ số phức lời giải rõ ràng và dễ hiểu. Tiếp theo ta xét bài toán. Bài toán 2.72. Cho p là số nguyên tố và m ∈ N∗. Giả sử

p−1 (cid:88)

E =

(k1, k2, ..., kp−1) , 0 ≤ ki ≤ m − 1 :

iki ≡ 0 (modp)

i=1

(cid:40) (cid:41)

p−1 (cid:89)

f (x) =

xki

akxk,

i=0

k=1

Tính số phần tử của tập E. Phân tích - Lời giải. Xét đa thức (cid:33) (cid:32)m−1 (cid:88) (cid:88)

trong đó ak là tổng tất cả các bộ (k1, k2, ..., kp−1) với 0 ≤ ki ≤ m − 1 và k1 + 2k2 + ... (p − 1) kp−1 = k. Theo bổ đề 2.2, ta có

ak =

1 p

(cid:88) (cid:2)f (1) + f (ε) + ... + f (cid:0)εp−1(cid:1)(cid:3) ,

...p

+ i sin

2π p

trong đó ε = cos

Ta có f (1) = mp−1.

1 − xmi 1 − xi . Khi đó

p−1 (cid:81) i=1

• Nếu m

Nếu x (cid:54)= 1 thì f (x) =

p−1 (cid:89)

f (cid:0)εj(cid:1) =

1 − εmij 1 − εij = 0, j = 1, ..., p − 1.

i=1

• Nếu (m, p) = 1 thì

p−1 (cid:89)

f (cid:0)εj(cid:1) =

1 − (cid:0)εji(cid:1)m 1 − εji = 1, j = 1, 2, ..., p − 1.

i=1

...p thì

Tóm lại

mp−1 + p − 1 p

|E|=

nếu m, p nguyên tố cùng nhau

mp−1 p

nếu m chia hết cho p   

Bài toán 2.73. (IMO - 1995) Cho p là số nguyên tố lẻ. Tìm số các tập con X của tập A = {1, 2, ..., 2p} biết rằng

1. X có đúng p phần tử.

2. Tổng số phần tử của X chia hết cho p.

+ i sin

Phân tích - Lời giải.

2π p

Giả sử ε = cos và xi là số tập con X của tập A sao cho |X| = p

p−1 (cid:88)

và m (X) ≡ i (modp), trong đó m(X) là tổng các số của tập X. Khi đó

εm(B) =

εc1+c2+...+cp.

xiεi =

i=0

1≤c1

B⊂A,|B|=p

(cid:88) (cid:88)

εc1+c2+...+cp chính là hệ số X p của đa thức

(X + ε) (cid:0)X + ε2(cid:1) ... (cid:0)X + ε2p(cid:1) .

Ta có (cid:80) 1≤c1

X p − 1 = (X − ε) (cid:0)X − ε2(cid:1) ... (X − εp) ,

Vì

X p + 1 = (X + ε) (cid:0)X + ε2(cid:1) ... (X + εp) .

nên

(X p + 1)2 = (X + ε) (cid:0)X + ε2(cid:1) ... (X + εp) (cid:0)X + εp+1(cid:1) ... (cid:0)X + ε2p(cid:1) .

Vì {1, 2, ..., p} và {p + 1, P + 2, ..., 2p} là hai hệ thặng dư đầy đủ modulo p, nên

Do đó hệ số X p trong khai triển (X + ε) (cid:0)X + ε2(cid:1) ... (cid:0)X + ε2p(cid:1) bằng 2.

xiεi = 2.

p−1 (cid:80) i=0

Suy ra

x0 − 2 = x1 = ... = xp.

Theo bổ đề 2.1, ta có

x0 + x1 + ... + xp = C p 2p.

Mặt khác

C p

+ 2 =

+ 2.

x0 =

x0 − 2 + x1 + ... + xp p

2p − 2 p

Suy ra

Bài toán 2.74. (Bài toán tổng quát) Cho p là số nguyên tố lẻ. Tìm số các tập con X của tập A = {1, 2, ..., n} (n ≥ p), biết rằng

1. X có đúng p phần tử.

2. Tổng số phần tử của X chia hết cho p.

Phân tích - Lời giải.

+ i sin

2π p

Giả sử ε = cos và xi là số tập con X của tập A sao cho |X| = p

p−1 (cid:88)

và m (X) ≡ i (modp), trong đó m(X) là tổng các số của tập X. Khi đó

εm(B) =

εc1+c2+...+cp.

xiεi =

i=0

1≤c1

B⊂A,|B|=p

(cid:88) (cid:88)

εc1+c2+...+cp chính là hệ số X n−p của đa thức

(X + ε) (cid:0)X + ε2(cid:1) ... (X + εn) .

Ta có (cid:80) 1≤c1

X p − 1 = (X − ε) (cid:0)X − ε2(cid:1) ... (X − εp) ,

Vì

X p + 1 = (X + ε) (cid:0)X + ε2(cid:1) ... (X + εp) .

nên

(X p + 1)k (X + ε) (cid:0)X + ε2(cid:1) ... (X + εr) = (X + ε) ... (X + εp) ... (X + εn) .

Giả sử n = kp + r, 0 ≤ r ≤ p − 1. Khi đó

k = k.

r (cid:81) i=1

Như vậy hệ số X n−p của đa thức (X p + 1)k (cid:0)X + εi(cid:1) bằng C 1

xiεi = k.

p−1 (cid:80) i=0

Suy ra

x0 − k = x1 = ... = xp.

Theo bổ đề 2.1, ta có

x0 + x1 + ... + xp = C p n,

Mặt khác

C p

+ 2 =

+ k.

x0 =

x0 − k + x1 + ... + xp p

n − k p

suy ra

Chương 3

Một số bài toán trò chơi

Ở phần này, ta xét các bài toán trò chơi bao gồm hai người chơi (hai đối thủ), và tập hợp các nước đi (hoặc chiến thuật) mà hai người chơi có thể chọn. Với chiến thuật đã biết, câu hỏi đối thủ nào có thể giành được chiến thắng sau khi kết thúc trò chơi. Trong các bài toán ở phần này, các chiến thuật đều liên quan đến tính chất số học và điều đặc biệt có sự xuất hiện của "tỉ số vàng" trong lời giải bài toán trò chơi.

Bài toán 3.1. Viết lên bảng các số 1, 2, ..., 2004. Có hai người chơi theo quy tắc sau. Đến lượt, mỗi người có quyền xóa đi hai số a, b trên bảng và thay vào số ab. Trò chơi sẽ kết thúc khi trên bảng chỉ còn lại một số. Nếu số đó tận cùng là 2, 3, 7, 8 thì người đi trước được xem là thắng cuộc. Hỏi ai là người có chiến thuật thắng trong trường hợp này? Phân tích - Lời giải. Ta gọi một số là số “tốt” nếu nó đồng dư với 0, 1, hoặc 4 môdulo 5, là “xấu” nếu nó đồng dư với 2, 3 môdulo 5. Dễ thấy rằng lũy thừa của một số tốt là một số tốt. Như vậy, người thứ hai sẽ có chiến thuật thắng, không phụ thuộc vào cách chơi của người thứ nhất. Thật vậy, mỗi lần đến lượt mình, người thứ hai luôn xóa số tốt a, số xấu b, và thay vào đó số ab (chừng nào còn có thể). Như vậy, mỗi lần số xấu sẽ giảm đi một đơn vị.Vì số xấu ít hơn một nửa các số nên đến một lúc nào đó, trên bảng chỉ còn toàn số tốt, tức là số đồng dư 0, 1, hoặc 4 môdulo 5. Số này có tận cùng là 0, 1, 6, hoặc 9. Vậy cách đó người thứ 2 sẽ thắng.

Bài toán 3.2. Có hai bạn An và Bình chơi một trò chơi như sau: Ban dầu, họ có một dãy các số nguyên dương a1 < a2 < ... < an (n là số nguyên dương). Ở mỗi lượt, họ sẽ chọn ra hai số x, y nào đó thuộc dãy và tính giá trị |x − y|, nếu như số này chưa xuất hiện trong dãy thì điền thêm vào. Đến lượt ai thực hiện mà không tìm được hai số nào thỏa mãn việc điền thêm

số thì coi như thua. Biết rằng An và Bình chơi tối ưu và An đi trước. Ai là người thắng cuộc? Phân tích - Lời giải. Để tìm được chiến lượt tổng quát, ta cần làm hai điều sau: Các số có thể được điền vào dãy có dạng như thế nào và số lượng số có thể điền vào là bao nhiêu?

x1a1 + x2a2 + ... + xnan.

Ta thấy rằng việc điền số |x − y| ở trên có thể coi như điền số x − y nếu x > y và điền số y − x nếu y > x. Ta có thể chọn các cặp số tùy ý để ghép lại với nhau nên các số điền vào được là một tổ hợp tuyến tính của n số đã cho

Hơn nữa, do là các tổ hợp tuyến tính nên thứ tự các số có thể chọn theo thứ tự tùy ý và không làm ảnh hưởng đến kết quả sau cùng.

an d

với 1 ≤ k ≤ Đặt d = ƯCLN(a1, a2, ..., an) thì các số có thể điền vào được có dạng kd . Rõ ràng các số a1, a2, ..., an đã cho đề có dạng này nên tổng

− n. Đến đây ta chỉ cần kiểm tra

an d

các số lượng có thể thêm vào dãy là

tính chẵn lẻ của số này. Nếu giá trị này chẵn thì Bình thắng, còn nếu giá trị này lẻ thì An thắng.

x2 + y2 = 4k(4s + 3),

Bài toán 3.3. Hai người A và B chơi một trò chơi như sau: A và B lần lượt viết các chữ số 0, 1 (từ trái sang phải) cho đến khi mỗi người viết được 2013 chữ số, khi đó sẽ nhận được biểu diễn nhị phân của một số nguyên dương N nào đó. A sẽ thắng nếu số N biểu diễn được thành tổng của hai số chính phương, và B thắng trong trường hợp ngược lại. A là người viết trước. Hỏi ai là người có chiến thuật giành chiến thắng? Phân tích - Lời giải. Trước tiên ta chứng minh rằng nếu biểu diễn nhị phân của một số nguyên dương có hai chữ số 1 đứng cạnh nhau và bên phải hai chữ số đó đều là chữ số 0 thì số này không thể viết được dưới dạng tổng của hai số chính phương. Thật vậy, số đó có dạng 4k(4s + 1). Nếu giả sử ngược lại, tồn tại x, y nguyên sao cho:

thì x2 + y2 chia hết cho 4s + 3 điều này không xảy ra.

• Nếu một trong các chữ số mà A viết xuống là 1 thì B sẽ lặp lại tất cả các chữ số mà A đã viết theo các bước tương ứng. Cuối cùng, số nhận

Chiến thuật để B thắng như sau:

• Nếu A viết toàn chữ số 0 thì B sẽ viết 3 chữ số đầu bằng 1 và sau đó chỉ toàn số 0. Số sau cùng có chính là 21.42010. Số này không có dạng x2 + y2.

được có dạng 4k(4s + 3), số này theo nhận xét trên không biểu diễn được dưới dạng x2 + y2.

Như vậy B luôn có chiến thuật thắng.

Bài toán 3.4. Trên bàn có n > 1 que diêm. Có hai người lần lượt lấy diêm. Mỗi người đến lượt mình được lấy một số que diêm tùy ý trong những que còn lại trên bàn, nhưng không vượt quá số que diêm mà người đi trước vừa lấy, và người đi đầu tiên lấy không quá n − 1 que. Người nào lấy được que diêm cuối cùng được xem là chiến thắng. Tìm các số n sao cho người đi trước có chiến thuật thắng. Phân tích - Lời giải. Dễ thấy rằng, nếu n lẻ thì người đi trước luôn thắng, bằng cách ở nước đi đầu tiên, người đó chỉ lấy một que diêm, do đó ở mỗi bước đi tiếp theo mỗi người chỉ được lấy một que diêm. Xét trường hợp n chẵn. Rõ ràng người nào lấy được số lẻ que diêm đầu tiên sẽ thua, vì để lại cho người đi tiếp theo một số lẻ que diêm, trở về trường hợp trên. Do đó, người chiến thắng luôn lấy một số chẵn que diêm. Như vậy, có thể hình dung các que diêm được gắn thành từng cặp, và mỗi người đến lượt sẽ lấy một số cặp nào đó.

1. Nếu chỉ có một cặp (n = 2), người đi trước thua, vì chỉ lấy một que.

2. Nếu số cặp lẻ và > 1 (n ≡ 2 mod 4)): Ta trở về trường hợp n lẻ (vì các

que diêm đã gắn thành từng cặp), và người đi trước thắng.

3. Nếu số cặp chẵn (n ≡ 0 mod 4): mỗi người muốn thắng thì phải lấy một số chẵn cặp (nếu ngược lại thì ta trở về trường hợp (2)). Khi đó có thể hình dung các que diêm được gắn thành từng nhóm 4 que. Tương tự trường hợp (1), (2) ta thấy nếu nhóm là một (n = 4) thì người đi trước thua; nếu n > 4 và số nhóm lẻ (n ≡ 4 mod 8) thì người đi trước thắng. Nếu số nhóm là chẵn (n ≡ 0 mod 8), ta lại gắn các que diêm thành nhóm 8 que,...

Như vậy, người đi trước có chiến thuật thắng khi và chỉ khi n là không phải một lũy thừa của 2 (cid:0)n (cid:54)= 2k(cid:1).

n1 n2

2k.

= pr

Bài toán 3.5. (IMO-1990) Cho trước một số n0 khởi đầu. Hai người A và B chơi một trò chơi, họ luân phiên chọn các số nguyên n1, n2, ... theo quy luật như sau: Trước tiên, A chọn n1 thỏa mãn điều kiện n0 ≤ n1 ≤ n2 0. Sau = pr, với p là số nguyên tố và r ≥ 1 là số nguyên. đó, B chọn n2 sao cho

n2k+1 n2k+2

Tổng quát, ta có trình tự tiếp theo: Nếu biết n2k là số nguyên mà B vừa chọn thì A chọn số nguyên dương tùy ý n2k+1 nào đó thỏa mãn điều kiện n2k ≤ n2k+1 ≤ n2 Nếu biết A chọn n2k+1 thì B sẽ chọn số tùy ý n2k+2 nào đó sao cho

với p là số nguyên tố và r ≥ 1 là số nguyên. A thắng cuộc nếu A chọn được số 1990, B thắng cuộc nếu B có thể chọn được số 1. Hỏi giá trị nào của n0 thì:

1. B có thể đảm bảo thắng lợi của mình.

2. A có thể đảm bảo thắng lợi của mình.

3. Không ai có thể thắng cuộc.

1. Nếu ban đầu A biết số 2 thì A chỉ có thể chọn số < 5 thì A thua ngay

Phân tích - Lời giải.

2. Ta chứng minh n0 ≥ 8 thì A thắng.

vì B chọn được số 1. Nếu ban đầu A biết số 3 thì A chỉ có thể chọn số < 10 thì B có thể chọn số 1 hoặc 2, nên A thua. Nếu ban đầu A biết số 4 thì A chỉ có thể chọn số < 17 thì B có thể chọn số 1 hoặc 2 hoặc 3, nên A thua. Nếu ban đầu A biết số 5 thì A chỉ có thể chọn số < 26 thì B có thể chọn số 1 hoặc 2 hoặc 3 hoặc 4, nên A thua. Vậy khi n0 ∈ {2, 3, 4, 5} thì A thua.

Nhận xét. Dễ thấy, A muốn thắng cuộc thì A không nên chọn số nguyên tố hoặc là lũy thừa của một số nguyên tố hoặc tích của một số nguyên bé hơn 6 với một số là lũy thừa của một số nguyên tố. Từ đây, ta xây dựng chiến thuật để A luôn thắng.

Trong trường hợp: 8 ≤ n0 ≤ 1990. Ta chỉ ra cách chọn mà A có thể thắng. Vì 442 < 1990 < 452 nên nếu n0 ∈ [45, 1990] thì A có thể chọn được số 1990, vì vậy nếu B chọn số thuộc [45, 1990] thì B thua ngay. Ta thấy số nguyên dương lớn nhất mà A có thể chọn để buộc B phải chọn số thuộc [45, 1990] là 504. Cụ thể: Vì 222 < 1990 < 232 nên nếu n0 ∈ [23, 44] thì A chọn số 504, thì B chỉ có

thể chọn các số 56, 63, 72, 168, nên A thắng. Lý luận tương tự: Nếu n0 ∈ [17, 22] thì A chọn số 280, khi đó B chỉ có thể chọn một trong các số 35, 40, 56, 70, 140 ∈ [23, 1990], nên A thắng. Nếu n0 ∈ [12, 16] thì A chọn số 140, khi đó B chỉ có thể chọn một trong các số 20, 28, 35, 70 ∈ [17, 1990], nên A thắng. Nếu n0 ∈ [8, 12] thì A chọn số 60, khi đó B chỉ có thể chọn một trong các số 12, 15, 20, 30 ∈ [12, 1990], nên A thắng.

Trong trường hợp: n0 ≥ 1991.

3. Bây giờ, xét trường hợp n0 ∈ {6, 7}, thì khi đó A chỉ có thể chọn n1 = 2.3.5 = 35 ∨ n1 = 2.3.7 = 42. (Nếu không thì B luôn chọn được một trong các số 1, 2, 3, 4, 5 thì B thắng).

• Nếu B đối diện với số 30 mà A đã chọn, B phải chọn một trong 3 số 6, 10, 15. Ta đã biết, nếu B chọn số 10 hoặc 15 thì A sẽ thắng nên B phải chọn số 6.

• Còn nếu B đối diện với số 42 thì B phải chọn một trong các số 6, 14, 21. Ta đã biết, nếu B chọn số 14 hoặc 21 thì A sẽ thắng nên B phải chọn số 6.

Nếu n0 = 1991 = 11.181 (∗) thì A chọn số 1991, khi đó B chỉ có thể chọn 11 hoặc 181, nên B thua. Nếu n0 ∈ (cid:2)11r.181 + 1, 11r+1.181(cid:3) , r > 0 (∗∗) thì A chọn số 11r+1.181, khi đó B chỉ có thể chọn một trong các số 181; 11.181; ...; 11r.181; 11r+1, tất cả các số này đều nhỏ hơn 11r+1.181. Vì vậy, nếu A biết số n như trong (∗), (∗∗) thì chiến thuật (∗), (∗∗) cho thấy A sẽ quay lại được số < n và (≥ 11), vì vậy A sẽ thắng cuộc sau một số hữu hạn bước quay lại.

Sau đó, cả hai người chơi A và B thay phiên nhau chọn số 30, 6, 30, 6, ... để tránh bị thua nên họ sẽ hòa.

Chúng ta đều biết "tỉ số vàng" sau đây thường xuất hiện trong khoa học,

√

1 + 2 Không những thế tỉ số vàng thường xuất hiện trong lời giải của những bài toán "số học - tổ hợp".

công nghệ và đời sống

= 1.

1 γ

1 δ

Bài toán 3.6. Giả sử γ, δ là những số vô tỷ dương, thỏa mãn

. Như vậy, các số

. Tương tự, các số m thỏa mãn [mδ] < N

n thỏa mãn là n = 1, 2, ...,

Chứng minh rằng nếu đặt an = [nγ] , bn = [nδ] thì mỗi số nguyên dương xuất hiện đúng một lần ở một trong hai dãy an, bn. Phân tích - Lời giải. Rõ ràng yêu cầu bài toán tương đương với việc chứng minh rằng, các số trong mỗi đoạn hữu hạn tùy ý [1, 2, ..., N ] có mặt ở một trong hai dãy, và xuất hiện đúng một lần. Như vậy, chỉ cần đếm xem trong N − 1 số nguyên dương nhỏ hơn N, có bao nhiêu số thuộc một trong hai dãy trên. N γ (cid:21)

Xét số nguyên dương n thỏa mãn [nγ] < N , tức là n < (cid:20)N γ (cid:21) là m = 1, 2, ..., (cid:20)N δ

N γ

N δ

(cid:21) (cid:21) hai dãy là Như vậy, trong các số nguyên dương nhỏ hơn N , số các số thuộc một trong /∈ Z. Từ đó ta có . Do γ, δ là các số vô tỷ nên (cid:20)N γ (cid:20)N δ

− 1 <

N γ

(cid:21)

− 1 <

N δ

(cid:21)

N δ

(cid:20)N γ (cid:20)N δ

suy ra

− 2 = N − 2 <

< N

= N.

(cid:19) (cid:21) (cid:21) (cid:19)

N δ

(cid:18)N γ (cid:20)N γ (cid:20)N δ (cid:18)N γ

= N − 1.

(1)

Do đó, (cid:21) (cid:21)

(cid:20)N γ (cid:20)N δ

Mặt khác: Nếu [nγ] = [mδ] = k với m, n là hai số nguyên dương thì γn = k + r, δm = k + s, 0 < r < 1, 0 < s < 1. Do đó

m + n = k

(cid:19)

1 δ

r γ

s δ

(cid:18) 1 γ

< 1,

0 <

r γ

s δ

Hơn nữa

[nγ] (cid:54)= [mδ] .

(2)

nên đẳng thức trên không xảy ra. Vậy với mọi số tự nhiên m, n thì

Từ (1) và (2), suy ra điều phải chứng minh.

{a1, a2, ..., an−1, b1, b2, ..., bn−1} .

Bài toán 3.7. Tìm các dãy tăng các số nguyên dương {an} , {bn} thỏa mãn những tính chất: 1/ a1 = 1, 2/ với mọi n ≥ 1, bn = an + n, 3/ an là số nguyên dương nhỏ nhất không thuộc tập hợp

= 1.

1 γ

1 δ

Phân tích - Lời giải. Rõ ràng ba điều kiện nói trên xác định duy nhất các dãy {an} , {bn}. Hơn nữa, đối với hai dãy tăng, việc thỏa mãn điều kiện 1/, 2/ và 3/ tương đương với việc thỏa mãn các điều kiện 1/, 2/ và 3(cid:48)/ như sau: 3(cid:48)/ Mỗi số nguyên dương đều thuộc một và chỉ một trong hai dãy đang xét. Do tính xác định duy nhất của các dãy thỏa mãn 1/, 2/ và 3(cid:48)/, ta chỉ cần chứng minh sự tồn tại. Bài toán trên cho ta cách tìm hai dãy số thỏa mãn điều kiện 3(cid:48)/ là các dãy an = [nγ] , bn = [δn] trong đó γ, δ là các số hữu tỷ dương thỏa mãn

n = n + [nγ] − [nγ] = [n + nγ] − [nγ] = [(1 + γ) n] − [nγ] .

Vấn đề ở đây chỉ cần tìm γ thỏa mãn điều kiện 1/, 2/. Để ý rằng

= 1.

1 γ

1 γ + 1

√

Như vậy chỉ cần tìm γ vô tỷ, thỏa mãn

1 + 2

Nghiệm của phương trình này là "tỉ số vàng"

√

Các dãy {an} , {bn} cần tìm là

an =

, bn =

1 + 2

3 + 2

(cid:34) (cid:35) (cid:35) (cid:34)

Hai bài toán trên có thể giúp ta giải quyết bài toán phức tạp sau đây.

Bài toán 3.8. Lập dãy số theo cách sau: Lấy x1 = 1, với i ≥ 2 số xi nhận được từ xi−1 bằng cách đổi (trong cách viết xi−1) số 1 thành số 01, số 0 thành số 1. Làm như vậy, ta nhận được dãy 1, 01, 101,01101,... Trong dãy này, gọi an là vị trí của số 1 thứ n, bn là vị trí của số 0 thứ n (như vậy a1 = 1, a2 = 3, a3 = 4, b1 = 2, b2 = 5, ...).

an = n + kn.

Tìm công thức của an và bn. Phân tích - Lời giải. Trước tiên, ta cần tìm công thức xác định mối liên hệ giữa an và bn. Gọi kn là số chữ số 0 đứng trước chữ số 1 thứ n. Theo định nghĩa hai dãy đang xét ta có

bn = 2n + kn.

Theo đề bài, chữ số 0 thứ n được sinh ra từ chữ số 1 thứ n. Mặt khác, chữ số 1 biến thành chữ số 01, chữ số 0 biến thành chữ số 1. Trước chữ số 1 có kn chữ số 0, và biến thành kn chữ số 1; còn n chữ số 1 biến thành 2n chữ số. Tù đó suy ra

bn = an + n.

√

Từ hai công thức trên, ta có

an =

, bn =

1 + 2

3 + 2

(cid:35) (cid:35) (cid:34) Vì an và bn đều là các "số thứ tự" nên hai dãy tăng, đồng thời mỗi một số nguyên dương xuất hiện đúng một lần trong một trong hai dãy. Áp dụng kết quả của hai bài toán trên cho ta đáp số: (cid:34)

Bài toán 3.9. Cho hai đống đá, một đống có a hòn đá, đống kia có b hòn đá. Hai người chơi, mỗi người đến lượt mình được lấy một số tùy ý hòn đá từ một trong hai đống, hoặc lấy từ hai đống số hòn đá như nhau. Người lấy được hòn cuối cùng là người chiến thắng. Tìm tất cả các cặp (a, b) sao cho người đi sau có chiến thuật thắng. (Ví dụ : (1, 2) là cặp có tính chất đó). Phân tích - Lời giải. Việc cho phép lấy hoặc một số đá tùy ý từ một trong hai đống hoặc lấy số đá như nhau từ mỗi đống gợi cho ta hình ảnh: Hoặc giảm theo chiều ngang, theo chiều dọc hoặc giảm theo đường chéo. Để mô tả hình ảnh đó, tốt nhất dùng đồ thị có hướng. Xét đồ thị mà các đỉnh là các điểm trên mặt phẳng tọa độ nguyên không âm, các cạnh là những đoạn thẳng nối hai điểm, nằm trên những đường thẳng song song với các trục tọa độ và trên những đường thẳng song song song với đường thẳng y = x. Các cạnh có hướng từ phải sang trái, từ trên xuống dưới −→ IO (với I(1, 1)). Với bài toán có hai đống đá với số đá hoặc cùng hướng với là a, b, ta có một đồ thị có hướng mà điểm xuất phát là điểm có tọa độ (a, b). Trong quá trình chơi, mỗi người đến lượt mình sẽ đi theo một trong 3 hướng

(phải - trái, trên -dưới hoặc giảm theo đường chéo) đến một đỉnh mới của đồ thị. Người chiến thắng là người đến điểm (0, 0) đầu tiên. Như vậy, một cặp (a, b) thỏa mãn bài toán ứng với một vị trí thắng theo định nghĩa sau: Định nghĩa. Ta gọi điểm (a, b) là một vị trí thắng nếu người nào đến lượt vị trí đó thì họ sẽ có chiến thuật thắng, không phụ thuộc vào bước đi tiếp theo của đối thủ. Rõ ràng bài toán này liên quan đến một khái niệm tập hợp ổn định của đồ thị. Định nghĩa. Giả sử R là tập hợp những vị trí nào đó. Khi đó ta nói R ổn định trong nếu mỗi bước (theo quy tắc trò chơi) xuất phát từ một điểm thuộc R sẽ có đích đến là một điểm không thuộc R. Tập hợp R gọi là ổn định ngoài nếu từ một vị trí tùy ý không thuộc R, tồn tại một bước đi mà đích đến thuộc R. Tập hợp R vừa ổn định trong, vừa ổn định ngoài là một lời giải. Rõ ràng (a, b) là một vị trí thắng nếu và chỉ nếu (a, b) thuộc tập hợp lời giải nào đó chứa điểm (0, 0). Bổ đề. Tồn tại không quá một lời giải chứa điểm (0, 0). Chứng minh. Giả sử R, S là hai lời giải khác nhau chứa điểm (0, 0). Lấy s1 ∈ S; s1 /∈ R. Từ s1 tồn tại một bước đi đến r1 và r1 /∈ S. Khi đó tồn tại một bước đi từ r1 đến s2 và s2 /∈ R. Lặp lại quá trình, ta được dãy s1, r1, s2, r2, ..., kết thúc tại điểm (0, 0) mà mỗi vị trí của dãy chỉ thuộc một trong hai tập hợp R, S. Suy ra điểm (0, 0) chỉ thuộc một trong hai tập hợp R, S, mâu thuẫn. Như vậy, ta đã chứng minh được tính duy nhất của tập hợp lời giải. Vấn đề còn lại là chỉ ra một tập hợp có tính chất đòi hỏi. Quan sát trên đồ thị dẫn đến bổ đề sau: Bổ đề. Giả sử R là tập hợp vị trí có tính chất sau:

1. (0, 0) ∈ R.

2. Nếu (a, b) ∈ R thì (b, a) ∈ R.

3. Với mọi a ∈ N∗ tồn tại duy nhất b ∈ N∗ sao cho (a, b) ∈ R.

4. d ∈ N∗ tồn tại duy nhất (a, b) ∈ R sao cho a − b = d.

5. Nếu (a, b), (k, l) ∈ R, a < b, k < l, b − a < l − k thì a < b, k < l.

Khi đó R là một lời giải. Chứng minh. Từ điều kiện (3) suy ra mọi số tự nhiên là tọa độ của một cặp

a) Tính ổn định trong. Giả sử (a, b) ∈ R. Theo tính chất (3) nếu giảm a hoặc b thì sẽ dẫn đến một vị trí không thuộc R. Nếu giảm a và b với cùng một đại lượng, thì theo tính chất (4) ta cũng đến một vị trí ngoài R.

b) Tính ổn định ngoài. Giả sử (a, b) /∈ R. Nếu a = b, ta có ngay một bước đi đến điểm (0, 0) ∈ R. Giả sử a (cid:54)= b. Theo tính chất (3), tồn tại c sao cho (a, c) ∈ R. Theo tính chất (4) tồn tại k, l sao cho l − k = b − a, (k, l) ∈ R. Khi đó nếu c < b thì tồn tại nước đi từ (a, b) đến (a, c) bằng cách giảm b. Nếu c > b thì c − a > b − a = l − k nên theo tính chất (5) thì c > l và a > k; khi đó ta giảm đồng thời a, b một đại lượng bằng a − k = b − l và đi đến vị trí (k, l) ∈ R. Như vậy, để giải bài toán ta chỉ cần tìm một tập hợp vị trí thỏa mãn tính chất từ (1) đến (5). Tập hợp như vậy ta đã gặp ở bài toán trên. Thật vậy, xuất phát từ điểm (0, 0) ta xây dựng dãy an, bn, n ≥ 1 bằng quy nạp như sau: Giả sử đã có (a1, b1) , (a2, b2) , ..., (an, bn). Khi đó ta lấy an+1 là số nguyên dương nhỏ nhất chưa xuất hiện trong dãy an, bn trước đó, đồng thời lấy bn+1 = an+1 + n + 1. Dễ dàng chứng minh rằng, tập R = {(0, 0) , (an, bn) , (bn, an) , n = 1, 2, ...} là tập hợp thỏa mãn điều kiện từ (1) đến (5), và do đó là tập hợp các vị trí thắng. Vậy tập hợp cần tìm là

√

đối xứng (tính chất (2)) các vị trí thuộc R. Ta chứng minh tính ổn định trong và ổn định ngoài của R.

(0, 0) ,

, n ∈ N

3 + 2

1 + 2

3 + 2

(cid:40) (cid:32)(cid:34) (cid:35) (cid:34) (cid:35)(cid:33) (cid:32)(cid:34) (cid:35) (cid:34) (cid:35)(cid:33) (cid:41)

Kết luận

• Tìm hiểu và trình bày lại một số kiến thức về số học và tổ hợp.

• Trình bày các bài toán tổ hợp mà lời giải yêu cầu việc sử dụng các tính chất số học. Hơn nữa, chúng tôi chia các bài toán thuộc loại này theo các chủ đề bao gồm: 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.

• Trình bày một số bài toán trò chơi và giới thiệu một số bài toán liên

Đóng góp chính của luận văn:

quan đến "tỉ số vàng".

Tài liệu tham khảo

[1] Hà Huy Khoái, 2005, Số học, NXB Giáo Dục Việt Nam.

[2] Hà Huy Khoái, 2012, Một số bài toán Số học - Tổ hợp, Bồi dưỡng giáo

viên.

[3] Nguyễn Văn Mậu (Chủ biên), Trần Nam Dũng, Vũ Đình Hòa, Đặng Huy Ruận, Đặng Hùng Thắng, 2008, Chuyên đề chọn lọc "TỔ HỢP và TOÁN RỜI RẠC", NXB Giáo Dục.

[4] ThS Nguyễn Văn Nho, 2002, Tuyển tập các bài toán từ những cuộc thi

tại Trung Quốc, NXB Giáo Dục.

[5] ThS Nguyễn Văn Nho, 2004, Olympic toán học châu Á Thái Bình Dương,

NXB Giáo Dục.

[6] PGS.TS.Vũ Dương Thụy - ThS Nguyễn Văn Nho, 2003, 40 năm Olympic

toán học quốc tế 1959-2000, NXB Giáo Dục.

[7] Tủ sách toán học tuổi trẻ, 2007, Các bài toán thi Olympic toán trung

học phổ thông Việt Nam 1990-2006, NXB Giáo Dục.

[8] Tạp chí toán học và tuổi trẻ.

[9] Tài liệu từ Internet.

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

MỘT SỐ BÀI TOÁN SỐ HỌC - TỔ HỢP

Mục lục

Lời mở đầu

Lời cảm ơn

Chương 1

Một số kiến thức chuẩn bị

1.1 Kiến thức tổ hợp

1.2 Kiến thức số học

Chương 2

Một số bài toán Số học - Tổ hợp

2.1 Tính chất số học

2.2 Bài toán chia kẹo Euler.

2.3 Bất biến

2.4 Cực trị trên tập hợp rời rạc

2.5 Số phức - Tổ hợp

Chương 3

Một số bài toán trò chơi

Kết luận

Tài liệu tham khảo

Có thể bạn quan tâm

Luận văn Thạc sĩ: Chế tạo và nghiên cứu tính chất điện, từ của vật liệu multiferroic Ba₀.₇Ca₀.₃TiO₃/ NiFe₂O₄

Luận văn Thạc sĩ: Nghiên cứu vật liệu biến hóa dạng chuỗi một chiều chế tạo từ kim loại đồng trên đế FR-4 hoạt động tại tần số MHz ứng dụng trong truyền năng lượng không dây

Luận văn Thạc sĩ: Đánh giá khả năng tác động tới môi trường biển của việc xả nước thải từ sự cố nhà máy điện hạt nhân Fukushima sử dụng công cụ ERICA

Luận văn Thạc sĩ: Xây dựng mô hình đầu dò nơtron và gamma sử dụng nhấp nháy EJ-276 ghép nối với mảng nhân quang silicon

Luận văn Thạc sĩ: Đánh giá khả năng ảnh hưởng của bức xạ ion hóa đến sức khỏe cư dân khu vực mỏ đất hiếm Đông Pao, xã Bản Hon, huyện Tam Đường, tỉnh Lai Châu

Luận văn Thạc sĩ: Sử dụng phương pháp nhiễu xạ neutron khảo sát cấu trúc tinh thể và pha trật tự từ trong vật liệu Pr2FeCrO6

Luận văn Thạc sĩ: Nghiên cứu phân lập, xác định cấu trúc và hoạt tính ức chế NO của các hợp chất thứ cấp từ chủng vi nấm biển Aspergillus sp. CL251

Luận văn Thạc sĩ: Phân tích một số hợp chất bisphenol thôi nhiễm từ bao bì nhựa lên một số mẫu thực phẩm nền tinh bột

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá hoạt tính kháng khuẩn, kháng nấm của loài hoa mộc (Osmanthus fragrans (Thunb.) Lour.) ở Việt Nam

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá tác dụng kháng viêm của loài côi Turpinia montana (Blume) Kurz

Luận văn Thạc sĩ: Tổng hợp và đặc trưng tính chất vật liệu composite có cấu trúc nano chitosan–cyclodextrin/TiO₂–Ag

Luận văn Thạc sĩ: Nghiên cứu chế tạo và khảo sát một số tính chất của màng phủ trên cơ sở nhựa epoxy gốc nước và khung cơ kim - ZIF

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất napthoquinone chứa nguyên tố flo bằng phản ứng đa thành phần

Luận văn Thạc sĩ: Nghiên cứu điều chế vật liệu Bioglass và tổ hợp lai với polymer ALG-F127 định hướng ứng dụng trong điều trị nội nha

Luận văn Thạc sĩ: Khảo sát thành phần hóa học và hoạt tính ức chế enzyme α-glucosidase trên một số hợp chất phân lập từ thịt quả bình bát nước (Annona glabra L.).

Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất của benzazole

Luận văn Thạc sĩ: Nghiên cứu chiết tách lignin từ vỏ sầu riêng Ri6 (Durio zibethinus Murr.) và tổng hợp vật liệu biocomposite định hướng ứng dụng trong bảo quản sau thu hoạch

Luận văn Thạc sĩ: Nghiên cứu tổng hợp hạt nano bạc phủ acid hyaluronic mang doxorubicin định hướng ứng dụng trong điều trị ung thư

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và hoạt tính kháng viêm của loài rau dừa nước (Ludwigia adscendens)

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook