Một số bài toán về tập [2n]

Tống Hữu Nhân

(Sinh viên Đại học Y Dược, thành phố Hồ Chí Minh)

Tóm Tắt

Bài viết tổng hợp và giới thiệu một số bài toán từ các đề thi Olympic có liên quan đến tập gồm2n số nguyên dương đầu tiên, kí hiệu là [2n] ={1,2, . . . ,2n}.

1. Hoán vị của [2n]

Có khá nhiều bài toán khai thác các tính chất hoán vị của [2n]. Ta bắt đầu bằng bài toán số 6 trong kỳ thi IMO 1989 tại Braunschweig, Đức.

Bài toán 1. Xét (x₁, x₂, . . . , x_2n) là một hoán vị các phần tử của [2n]. Hoán vị này gọi là có tính chất P nếu tồn tại ít nhất một chỉ số i ∈ {1,2, . . . ,2n−1} sao cho

|x_i+1−x_i|=n. Chứng minh rằng số hoán vị có tính chất P nhiều hơn số hoán vị không có tính chấtP.

(IMO 1989)

Lời giải. Đặt X là tập các hoán vị có tính chất P và X_i, i= 1, n là tập các hoán vị mà hai phần tử i, i+n kề nhau. Khi đó X = ^Sn

i=1Xi. Với i= 1, n, ta tạo một hoán vị thuộc X_i như sau.

◦ Chọn một hoán vị của (1,2, . . . , i+n−1, i+n+ 1, . . . ,2n) : có (2n−1)! cách.

◦ Xếp phần tử i+n trước hoặc sau phần tử i: có 2cách.

Suy ra |X_i|= 2·(2n−1)!,∀i= 1,2, . . . , n.

Với 1≤i < j ≤n, ta tạo một hoán vị thuộc X_i∩X_j như sau.

◦ Chọn một hoán vị của(1,2, . . . , i+n−1, i+n+ 1, . . . , j+n−1, j+n+ 1, . . . ,2n) có(2n−2)! cách.

◦ Xếp phần tử i+n trước hoặc sau phần tử i, xếp phần tử j+n trước hoặc sau phần tửj : có 4cách.

Suy ra |Xi∩Xj|= 4·(2n−2)!, ∀1≤i < j ≤n.

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

|X| ≥

n

X

i=1

|X_i| − ^X

1≤i<j≤n

|X_i∩X_j|

=n·2·(2n−1)!−C_n²·4·(2n−2)! = 2n²·(2n−2)!>(2n)!/2.

Từ đây suy ra số hoán vị có tính chất P nhiều hơn số hoán vị không có tính chất P. Tiếp theo, xin giới thiệu bài 6 của kỳ thi Việt Nam TST 2017.

Bài toán 2. Xét (x₁, x₂, . . . , x_2n) là một hoán vị các phần tử của [2n]. Hoán vị này gọi là “đẹp” nếu thỏa đồng thời

(i) x_i+x_n+i = 2n+ 1, với mọi i= 1,2, . . . , n.

(ii) x_i−x_i+1 6≡x_j −x_j+1 (mod 2n+ 1), với mọi 1≤i < j ≤2n.

Trong đó, ta quy ước x_2n+1 =x₁.

(a) Với n = 6, hãy chỉ ra một hoán vị đẹp.

(b) Chứng minh rằng với mỗi số nguyên dương n luôn tồn tại một hoán vị đẹp.

(Vietnam TST 2017)

Lời giải. (a) Xét hoán vị (1,2, 4, 8, 3, 6, 12, 11,9, 5, 10, 7). Dễ thấy 1 + 12 = 2 + 11 = 4 + 9 = 8 + 5 = 3 + 10 = 6 + 7 = 13

i 1 2 3 4 5 6 7 8 9 10 11 12

xi−xi+1 (mod 13) 12 11 9 5 10 7 1 2 4 8 3 6 Do đó, hoán vị này là một hoán vị đẹp.

(b) (Dựa trên ý tưởng của Nguyễn Huy Tùng, cựu học sinh chuyên Trần Phú, Hải Phòng, HCĐ IMO 2014)

Gọi X là tập hợp các hoán vị đẹp. Yêu cầu bài toán tương đương chứng minh |X|>0.

Gọi Y là tập hợp các hoán vị (y₁, y₂, . . . , y_2n) của [2n] thỏa đồng thời (iii) y_i +y_n+i = 2n+ 1, ∀i= 1,2, . . . , n.

(iv) Không có bất cứ một dãy liên tiếp các số nào (ít hơn 2n số) có tổng chia hết cho 2n+ 1.

Ta chuyển yêu cầu bài toán về việc chứng minh tồn tại song ánh từ X sang Y và|Y|>0.

. Giả sử(x₁, x₂, . . . , x_2n)∈X. Đặt y_i ∈[2n] và

y_i ≡x_i−x_i+1 (mod 2n+ 1), i= 1,2n

Do các số xi phân biệt và điều kiện (ii), rõ ràng (y1, y2, . . . , y2n) cũng là một hoán vị của [2n]. Hơn nữa, theo điều kiện (i), ta có

yi+yi+n ≡xi −xi+1+xi+n−xi+n+1 ≡0 (mod 2n+ 1), mà 0< y_i+y_i+n<2(2n+ 1) nên y_i+y_i+n= 2n+ 1,∀i= 1,2, . . . ,2n. (1) Mặt khác, với 1≤i < j ≤2n−1, ta có

j

X

t=i

yt ≡

j

X

t=i

(xt−xt+1)≡xi−xj+1 (mod 2n+ 1),

mà các số x_i đôi một phân biệt theo modulo 2n+ 1, nên không có bất cứ một dãy liên tiếp các số yi nào (ít hơn 2n số) có tổng chia hết cho 2n+ 1. (2)

Từ (1) và (2), suy ra (y₁, y₂, . . . , y_2n)∈Y.

. Giả sử(y₁, y₂, . . . , y_2n)∈Y. Đặt x_i ∈[2n]















x₁ ≡

2n

X

t=1

ty_t (mod 2n+ 1), x_i ≡x₁−

i−1

X

t=1

y_t (mod 2n+ 1), i= 2,2n

Từ cách đặt và theo điều kiện (iv), rõ ràng (x₁, x₂, . . . , x_2n) cũng là một hoán vị của [2n].

Hơn nữa, thực hiện biến đổi ta được

x_i−x_i+1 ≡y_i (mod 2n+ 1), ∀i= 1,2, . . . ,2n,

mà các số y_i phân biệt nên các sốx_i −x_i+1 cũng phân biệt modulo2n+ 1. (3) Mặt khác, cũng từ biến đổi trên, kết hợp điều kiện (iii), ta có

x_i−x_i+1+x_n+i−x_n+i+1 ≡y_i+y_n+i ≡0 (mod 2n+ 1), ∀i= 1,2, . . . , n, tương đương

x_i+x_n+i ≡x_i+i+x_n+i+1 (mod 2n+ 1), ∀i= 1,2, . . . , n, hay n số x_i+x_n+i đều có cùng số dư r theo modulo 2n+ 1. Suy ra

nr ≡

n

X

i=1

(x_i+x_n+i)≡

2n

X

i=1

i≡0 (mod 2n+ 1),

mà (n,2n+ 1) = 1 nên r= 0. Từ đó x_i+x_n+i ... 2n+ 1, mà 0< x_i+x_i+n<2(2n+ 1) nên x_i+x_i+n= 2n+ 1,∀i= 1,2, . . . ,2n. (4)

Từ (3) và (4), suy ra (x₁, x₂, . . . , x_2n)∈X.

Như vậy, ta đã chứng minh được tồn tại song ánh giữa X vàY. Việc chứng minh |Y|>0 xin dành cho bạn đọc (có thể tham khảo thêm ở[4]).

Chủ đề này cũng đã từng xuất hiện trong đề thi Học sinh giỏi Quốc gia của Việt Nam.

Bài toán 3. Xét (x1, x2, . . . , x2n) là một hoán vị các phần tử của [2n] sao cho các số

|x_i+1−x_i|, i= 1,2n−1 đôi một phân biệt. Chứng minh rằng x₁ −x_2n=n khi và chỉ khi 1≤x_2i ≤n, với mọi i= 1,2, . . . , n.

(Vietnam MO 2001, France TST 2002)

Lời giải. Điều kiện đủ. Do 1 ≤ x_2i ≤ n nên n + 1 ≤ x2i−1 ≤ 2n, suy ra x_2i < x2i−1,

∀i= 1,2, . . . , n. Hơn nữa,(x₂, x₄, . . . , x_2n), (x₁, x₃, . . . , x2n−1) lần lượt là các hoán vị của (1, . . . , n), (n+ 1, . . . ,2n). Khi đó

T =

2n−1

X

i=1

|xi+1−xi|

= (x₁−x₂) + (x₃−x₂) + (x₃−x₄) +· · ·+ (x2n−1−x_2n)

= 2

n

X

i=1

x_2i−1−2

n

X

i=1

x_2i+x_2n−x₁

= 2

2n

X

i=n+1

i−2

n

X

i=1

i+x_2n−x₁ = 2n²+x_2n−x₁.

(1)

Mặt khác, do1≤ |x_i+1−x_i| ≤2n−1và|x_i+1−x_i|đôi một phân biệt,∀i= 1,2, . . . ,2n−1, do đó

T =

2n−1

X

i=1

|x_i+1−x_i|=

2n−1

X

i=1

i= 2n²−n. (2)

Từ (1) và (2) suy ra x₁−x_2n=n.

Điều kiện cần. Do 1 ≤ |x_i+1−x_i| ≤ 2n − 1 và |x_i+1−x_i| đôi một phân biệt, ∀i = 1,2, . . . ,2n−1; kết hợp x₁−x_2n =n, nên

T⁰ =

2n−1

X

i=1

|x_i+1−x_i|+x₁−x_2n =

2n−1

X

i=1

i+n = 2n².

Mặt khác, sau khi khai triển dấu giá trị tuyệt đối ở các số hạng củaT⁰, ta có thể biễu diễn T⁰ dưới dạng ^P2n

i=1

e_ix_i, trong đóe_i ∈ {−2,0,2},∀i= 1,2, . . . ,2n. Ta có các nhận xét sau.

(i) ^P2n

i=1

e_i = 0.

(ii) Nếu trong dãy e1, e2, . . . , e2n, ta bỏ đi các số 0thì ta nhận được một dãy các số2 và

−2nằm xen kẽ nhau.

Đặt a_i, b_i, i= 1, n lần lượt, theo thứ tự xuất hiện trong dãyx₁, x₂, . . . , x_2n, là các số vượt quá n và không vượt quá n. Từ (i)ta được

T⁰ =

2n

X

i=1

e_i(x_i−n)≤2

n

X

i=1

(a_i−n)−2

n

X

i=1

(b_i−n) = 2

n

X

i=1

a_i−2

n

X

i=1

b_i

= 2

2n

X

i=n+1

i−2

n

X

i=1

i= 2n² =T⁰.

Suy ra ei = 2 với mọii mà xi > n và ei =−2với mọi i mà xi ≤n.

Do x1−x2n= n nên x2n ≤n, suy ra e2n =−2. Theo (ii), ta có e2i =−2,∀i= 1,2, . . . , n, hay 1≤x_2i ≤n,∀i= 1, ,2, . . . , n.

Điều đặc biệt trong ba bài toán trên là việc khai thác tính chất hoán vị của [2n] đều đi kèm với việc xét các hiệu xi+1−xi. Một sự trùng hợp thú vị !

2. Phân hoạch tập [2n]

Bài toán 4. Chứng minh tập con bất kỳ của [2n] gồm n+ 1 phần tử luôn có (a) Hai số liên tiếp (hai số nguyên tố cùng nhau).

(b) Hai số có hiệu bằng n.

(c) Hai số có tổng bằng 2n+ 1.

Lời giải. Bản chất của bài toán là việc phân hoạch [2n] thành n tập S_i, i= 1, n, mỗi tập có2 phần tử. Do S ⊂[2n] thoả |S| ≥n+ 1 nên theo nguyên lý Dirichlet, tồn tạiS_i ⊂S.

Tuỳ theo cách xây dựng các tập S_i mà ta thu được tính chất củaS.

◦ Si ={2i−1,2i}, i= 1, n, suy ra trong S luôn có hai số liên tiếp (hai số nguyên tố cùng nhau).

◦ S_i ={i, i+n}, i= 1, n, suy ra trong S luôn có hai số có hiệu bằng n.

◦ S_i ={i,2n+ 1−i}, i= 1, n, suy ra trong S luôn có hai số có tổng bằng2n+ 1.

Bài toán được giải quyết.

Bài toán 5. Tìm số nguyên dương k nhỏ nhất sao cho trong tập con bất kỳ có k phần tử của [2n], luôn tìm được bốn số phân biệt có tổng bằng 4n+ 1.

(China South-Eastern MO 2005)

Lời giải. (seshadri)XétS ={n−1, n, n+ 1, n+ 2, . . . , 2n} ⊂[2n]. Nhận thấy|S|=n+ 2 và tổng bốn phần tử bất kỳ củaS đạt giá trị nhỏ nhất là

(n−1) +n+ (n+ 1) + (n+ 2) = 4n+ 2>4n+ 1.

Do đó k ≥n+ 3. Ta sẽ chứng minh n+ 3 là giá trị cần tìm, hay trong tập con bất kỳ có n+ 3 phần tử luôn tìm được bốn số phân biệt có tổng bằng4n+ 1.

Gọi A là tập con bất kì của [2n]sao cho |A|=n+ 3. Ta phân hoạch [2n]\ {n,2n} thành n−1 tập S_i ={i, 2n−i}, i= 1, n−1. Rõ ràng

(A\ {n,2n})⊆([2n]\ {n,2n}), |A\ {n,2n}| ≥n+ 1,

nên theo nguyên lý Dirichlet, tồn tại S_i ⊂ (A\ {n,2n}), hay có hai phần tử phân biệt x, y ∈A mà x+y= 2n. Khi đó

(A\ {x, y})⊆[2n], |A\ {x, y}| ≥n+ 1.

Do đó, theo bài toán , có hai phần tử phân biệt z, t∈(A\ {x, y}) mà z+t = 2n+ 1. Từ đó suy ra, ta luôn tìm được bốn phần tử phân biệt x, y, z, t∈A sao cho

x+y+z+t = 2n+ (2n+ 1) = 4n+ 1.

Ta thu được điều phải chứng minh.

Bài toán 6. Cho n ≥ k³ +k. Phân hoạch tập [2n] thành k tập S₁, S₂, . . . , S_k. Chứng minh rằng tồn tại k+ 1 số n1, n2, . . . , nk+1 sao cho

(i) 2n₁,2n₂, . . . ,2n_k+1 thuộc tập S_i nào đó, với 1≤i≤k.

(ii) 2n₁−1,2n₂−1, . . . ,2n_k+1−1 thuộc tập S_j nào đó, với 1≤j ≤k.

(IMO Shortlist 1978)

Lời giải. (mavropnevma) Do n ≥ k³ +k nên theo nguyên lý Dirichlet, trong k tập S₁, S₂, . . . , S_k, tồn tại tập S_i chứa ít nhất 2n/k ≥2k²+ 2 phần tử. Do đó S_i chứa ít nhất k²+ 1 số chẵn, giả sử là

2i₁, 2i₂, . . . , 2i_k²₊₁. Ta cho tương ứng k²+ 1 số lẻ

2i1−1, 2i2−1, . . . , 2i_k²₊₁−1.

Lại theo nguyên lý Dirichlet, tồn tại tập S_j chứa ít nhất b^k2_k⁺¹c+ 1 =k+ 1 số lẻ trên. Từ đây, ta chọn được k+ 1 sốn₁, n₂, . . . , n_k+1 thỏa yêu cầu bài toán.

Bài toán 7. Phân hoạch tập [2n] thànhn tập S_i, i= 1, n, mỗi tập có 2phần tử và s_i là tích hai phần tử của tập S_i. Chứng minh rằng với mọi cách phân hoạch, ta đều có

S =

n

X

i=1

1 s_i = 1

s₁ + 1

s₂ +. . .+ 1 s_n <1.

(Baltic Way 2007)

Lời giải. (djuro) Trước tiên, ta chứng minh max^Pn

i=1 1

si đạt được khi và chỉ khi s_i = (2i−1)·2i.

Thật vậy, gọi 2k−1∈[2n]là phần tử nhỏ nhất mà 2k−1và 2k không cùng thuộc một tập S_i, khi đó sẽ tồn tại các tập {2k−1, a} và {2k, b}. Do các số nhỏ hơn 2k−1sẽ bắt thành từng cặp hai số liên tiếp nên a, b >2k.

Ta chứng minh khi thay {2k−1, a}, {2k, b} bởi {2k−1,2k}, {a, b}thì S sẽ tăng lên, hay 1

(2k−1)·a + 1

2k·b < 1

(2k−1)·2k + 1 ab

⇔4k²−2(1 +a+b)k+ab+a >0⇔(2k−a)(2k−b−1)>0, luôn đúng do a, b >2k.

Suy ra

2·S ≤

n

X

i=1

2

(2i−1)·2i = 1 +

n

X

i=2

2 (2i−1)·2i

<1 +

n

X

i=2

Ç 1

(2i−2)(2i−1)+ 1 (2i−1)·2i

å

= 1 +

2n−1

X

i=2

1 i(i+ 1)

= 1 +

2n−1

X

i=2

Ç1 i − 1

i+ 1

å

= 3 2− 1

2n <2, hay S < 1. Ta thu được điều phải chứng minh.

Bài toán 8. Phân hoạch tập [2n] thành n tập S_i, i= 1, n, mỗi tập có 2 phần tử. Có tối thiểu bao nhiêu tập S_i mà hai phần tử của nó nguyên tố cùng nhau ?

(Switzerland TST 2016)

Lời giải. (tastymath75025) Trước tiên, ta thấy cặp {1, s} luôn nguyên tố cùng nhau, với mọi s∈[2n].

Gọi π(n) là số các số nguyên tố không vượt quá n. Rõ ràng, nếu plà một số nguyên tố nằm giữa n+ 1 và2n thì bất kỳ số nào bắt cặp với nó cũng tạo thành một cặp nguyên tố cùng nhau. Thật vậy, giả sử có cặp{p, q} mà (p, q)>1thì q...p, suy ra q≥2p >2n, vô lý.

Như vậy, ta đã có π(2n)−π(n) + 1 số mà bất kỳ số nào bắt cặp với chúng sẽ tạo thành một cặp nguyên tố cùng nhau. Do yêu cầu tìm tối thiểu các cặp Si, nên ta cho các số này bắt cặp với nhau, khi đó có tổi thiểu

¢π(2n)−π(n) + 1 2

•

cặp nguyên tố cùng nhau.

Ta sẽ xây dựng một cách phân hoạch để đạt được giá trị tối thiểu này. Đặt T₀ ⊆[2n] gồm các số còn lại sau khi bỏ đi {1} và các số nguyên tố nằm giữa n+ 1 và 2n. Ta cần chứng minh có thể chia T₀ thành từng cặp không nguyên tố cùng nhau (có thể thừa ra một phần tử tùy vào tính chẵn lẻ của |T₀|).

Gọi p1 < p2 < . . . < pk là các số nguyên tố không vượt quá n. Để chia T0 thành từng cặp không nguyên tố cùng nhau, ta thực hiện k bước. Ở bước thứ0≤i≤k−1, ta lần lượt

◦ Xét M_i ={m ∈T_i|m...pk−i}. Do2pk−i <2n nên 2pk−i ∈M_i.

◦ Nếu M_i chẵn, ta bắt cặp các phần tử. Do chúng đều là bội số của pk−i nên sẽ tạo thành các cặp không nguyên tố cùng nhau.

◦ Nếu M_i lẻ, ta loại2pk−i và bắt cặp các phần tử còn lại. Do chúng đều là bội số của pk−i nên sẽ tạo thành các cặp không nguyên tố cùng nhau.

◦ Đặt T_i+1 =S_i\T_i và thêm vào phần tử 2pk−i nếu nó không được bắt cặp.

Rõ ràng sau khi thực hiện k bước, ta đã chia được T₀ thành từng cặp không nguyên tố cùng nhau và thừa lại tậpT_k gồm các số không được bắt cặp. Nhưng các số này đều có dạng 2p_i nên có ước chung là 2. Do đó, ta có thể bắt cặp chúng (có thể thừa một phần tử tùy vào tính chẵn lẻ của |T_k|) tạo thành các cặp không nguyên tố cùng nhau. Bài toán được giải quyết.

Bài toán 9. Chứng minh rằng với mọi cách phân hoạch tập [2n] thành hai tập A = {a1 < a2 <· · ·< an}, B ={b1 > b2 >· · ·> bn} rời nhau, ta đều có

n

X

i=1

|ai−bi|=|a1−b1|+|a2−b2|+· · ·+|an−bn|=n².

(All-Soviet Union MO 1985)

Lời giải. (trumcongcong) Do a_n > an−1 >· · ·> a₁ nên a_n≥n.

◦ Nếua_n=n thì a_i =i, b_i = 2n−i+ 1, ∀i= 1,2, . . . , n. Khi đó

n

X

i=1

|a_i−b_i|=

n

X

i=1

(2n−2i+ 1) =n².

◦ Nếuan> n thì tồn tại k ∈ {1,2, . . . , n−1} sao cho

a₁ < a₂ <· · ·< a_k ≤n≤a_k+1 <· · ·< a_n. Khi đó, ta có

b₁ > b₂ >· · ·> b_k ≥n≥b_k+1 >· · ·> b_n. Suy ra a_i ≤b_i, ∀i= 1, . . . , k và a_i ≥b_i,∀i=k+ 1, . . . , n.

Hơn nữa, (a1, . . . , ak, bk+1, . . . , bn),(b1, . . . , bk, ak+1, . . . , an) lần lượt là các hoán vị của (1, . . . , n), (n+ 1, . . . ,2n). Do đó

n

X

i=1

|a_i−b_i|=

k

X

i=1

(b_i−a_i) +

n

X

i=k+1

(a_i −b_i)

=

Ñ k

X

i=1

b_i+

n

X

i=k+1

a_i

é

−

Ñ k

X

i=1

a_i+

n

X

i=k+1

b_i

é

=

2n

X

i=n+1

i−

n

X

i=1

i=n². Ta thu được điều phải chứng minh.

Bài toán 10. Tìm hằng số C_n lớn nhất sao cho : với mọi cách phân hoạch tập [2n]

thành hai tập hợp, mỗi tập có n phần tử là A và B, sẽ luôn tồn tại cách đánh số mỗi phần tử của các tập A, B lần lượt là a1, a2, . . . , an và b1, b2, . . . , bn thỏa mãn

(a₁−b₁)²+ (a₂−b₂)²+. . .+ (a_n−b_n)² ≥C_n. (∗) (RMM Shortlist 2019, A2)

Lời giải. (Võ Quốc Bá Cẩn, giáo viên THCS Archimedes Academy, Hà Nội) Ta có (∗) tương đương với

2·(a₁b₁+a₂b₂+. . .+a_nb_n)≤(a²₁+b²₁) + (a²₂+b²₂) +. . .+ (a²_n+b²_n)−C_n

=

2n

X

i=1

i²−C_n= n(2n+ 1)(4n+ 1)

3 −C_n

Do đó, bài toán quy về việc tìm giá trị lớn nhất của Pn=a1b1+a2b2+. . .+anbn. Bằng quy nạp theo n, ta sẽ chứng minh

maxP_n= 1·2 + 3·4 +. . .+ (2n−1)·2n, trong đó (a₁, a₂, . . . , a_n, b₁, b₂, . . . , b_n)là một hoán vị của [2n].

. Với n= 1, hiển nhiên đúng.

.Giả sử mệnh đề quy nạp đúng tớin ≥1. Khi đó, với mọi hoán vị(a₁, a₂, . . . , a_n, b₁, b₂, . . . , b_n) của [2n], ta luôn có

P_n=a₁b₁+a₂b₂+. . .+a_nb_n ≤1·2 + 3·4 +. . .+ (2n−1)·2n.

. Ta sẽ chứng mệnh đề quy nạp đúng với n+ 1. Thật vậy, không mất tính tổng quát, giả sử a_i = 2n+ 1, b_j = 2n+ 2, với 1≤i, j ≤n. Ta có hai trường hợp.

◦ Nếu i =j thì (a1, a2, . . . , ai−1, ai+1, . . . , an+1, b1, b2, . . . , bi−1, bi+1, . . . , bn+1) chính là một hoán vị của [2n], nên theo giả thiết quy nạp, ta có

P_n+1 =a₁b₁+a₂b₂+. . .+a_n+1b_n+1

= (a₁b₁+a₂b₂+. . .+ai−1bi−1+a_i+1b_i+1+. . . a_n+1b_n+1) + (2n+ 1)(2n+ 2)

≤(1·2 + 3·4 +. . .+ (2n−1)·2n) + (2n+ 1)(2n+ 2)

◦ Nếui6=j thì ta có các cặp (a_i = 2n+ 1, b_i)và (a_j, b_j = 2n+ 2). Ta sẽ chứng minh a_ib_i+a_jb_j < a_ib_j +a_jb_i.

Thật vậy, bất đẳng thức trên tương đương với

(2n+ 1)b_i+ (2n+ 2)a_j <(2n+ 1)(2n+ 2) +a_jb_i ⇔(2n+ 1−a_j)(2n+ 2−b_i)>0, luôn đúng do a_i, b_j <2n+ 1.

Mặt khác, rõ ràng(a₁, a₂, . . . , a_i−1, a_i+1, . . . , a_n+1, b₁, b₂, . . . , b_j−1, b_j+1, . . . , b_n+1)chính là một hoán vị của [2n]. Do đó, kết hợp giả thiết quy nạp, ta được

P_n+1 <(1·2 + 3·4 +. . .+ (2n−1)·2n) + (2n+ 1)(2n+ 2).

Như vậy, mệnh đề quy nạp đúng với n+ 1.

Cuối cùng, ta tính được Cn.

C_n = n(2n+ 1)(4n+ 1)

3 −2

n

X

i=1

(2i−1)·2i=n.

Bài toán được giải quyết.

Bài toán 11. Với S là một tập con của [2n], gọi R_S là đa tập (một giá trị có thể xuất hiện nhiều lần trong tập R) gồm thặng dư không âm bé nhất của các tổng (có thứ tự) dạng s_i+s_j modulo 2n+ 1, trong đó các số s_i, s_j ∈ S không nhất thiết phân biệt. Chứng minh rằng với mọi cách phân hoạch [2n] thành hai tập A= {a₁, a₂, . . . , a_n}, B ={b₁, b₂, . . . , b_n} rời nhau, ta luôn có R_A=R_B.

(St. Petersburg MO 1995)

Lời giải. Xét hai đa thức

P(x) = ^X

i∈A

xⁱ, Q(x) = ^X

i∈B

xⁱ. Yêu cầu bài toán tương đương với việc chứng minh

P²(x)≡Q²(x) (mod x²ⁿ−1).

Điều này dễ dàng suy ra từ hai nhận định sau

◦ (x−1)|(P(x)−Q(x)) doP(x), Q(x) đều cón hạng tử.

◦ (x²ⁿ⁻¹+· · ·+x+ 1)|(P(x) +Q(x))do các số xⁱ, i= 1,2n xuất hiện đúng một lần.

Ta thu được điều phải chứng minh.

3. Tập con của tập [2n]

Trước tiên, xin giới thiệu một bài toán quen thuộc về tập con của tập [2n].

Bài toán 12. Một tập hợp các số nguyên gọi là cân nếu có số các phần tử chẵn bằng số các phần tử lẻ. Tính số tập con cân của tập [2n].

Lời giải. Gọi S₁ ={1,3, . . . ,2n−1}, S₂ ={2,4, . . . ,2n} thì |S₁|=|S₂|=n.

Cách 1. Ta xây dựng một tập cân bằng cách chọn k phần tử từ mỗi tập S₁ và S₂, suy ra số tập cân là

n

X

k=0

(C_n^k)² = (C_n⁰)²+ (C_n¹)²+. . .+ (C_nⁿ)² =C_2nⁿ. Việc chứng minh đẳng thức trên khá quen thuộc, xin dành cho bạn đọc.

Cách 2. GọiC là họ các tập cân và N là họ các tập con của [2n]có n phần tử. Với X ⊂ C, đặt X₁, X₂ là tập các số chẵn và số lẻ trong X thì |X₁|=|X₂|. Từ đó

|X1 ∪(S2\X2)|=|X1|+|S2| − |X2|=|S2|=n, hay X₁∪(Y \X₂)⊂ N. Từ đó, xét ánh xạ

f :C → N

X 7→X₁∪(S₂\X₂)

Dễ thấyf là đơn ánh. Ta sẽ chứng minh f toàn ánh. Thật vậy, gọiN ⊂ N và N₁, N₂ là tập các số chẵn và số lẻ trong N. Đặt X1 =N1, X2 =S2\N2, X =X1∪X2. Khi đó

|X₂|=|S₂\N₂|=|S₂| − |N₂|=n− |N₂|=|N₁|=|X₁|, hay X ⊂ C. Từ đóf song ánh, suy ra |C|=|N |=C_2nⁿ.

Tiếp theo là một bài toán với ý tưởng tương tự.

Bài toán 13. Gọi E_n vàO_n là họ các tập con n-phần tử của tập [2n] và lần lượt có tổng các phần tử chẵn và lẻ. Tính |En| − |On|.

(Polish MO 2001)

Lời giải. Gọi S₁ ={1,3, . . . ,2n−1}, S₂ ={2,4, . . . ,2n} thì |S₁|=|S₂|=n.

Cách 1. Ta xây dựng một tập thuộc En bằng cách chọn 2k phần tử từ S1 và n−2k phần tử từ S₂. Tương tự, ta xây dựng một tập thuộc O_n bằng cách chọn 2k+ 1 phần tử từ S₁ vàn−2k−1 phần tử từ S₂. Do đó

|E_n|=

bⁿ

2c

X

k=0

C_n^2kC_n^n−2k =

bⁿ

2c

X

k=0

(C_n^2k)², |O_n|=

bⁿ

2c

X

k=0

C_n^2k+1C_n^n−2k−1 =

bⁿ

2c

X

k=0

(C_n^2k+1)².

Suy ra

|E_n| − |O_n|=

bⁿ

2c

X

k=0

(C_n^2k)²−

bⁿ

2c

X

k=0

(C_n^2k+1)² =











0, khin = 2t+ 1, C_n^n/2, khi n= 4t,

−C_n^n/2, khin = 4t+ 2, Việc chứng minh đẳng thức trên không khó, xin dành cho bạn đọc.

Cách 2. (mathexplorer) Phân hoạch [2n] thành n cặpS_i ={2i−1,2i}, i= 1, n. Xét các tập con n-phần tử S của [2n]sao cho tồn tại ít nhất một cặp S_i mà |S∩S_i|= 1. Ta gọiS là tập ‘độc thân’ và phần tử giao của chúng gọi là phần tử ‘độc thân’.

Gọi E⁰_n và O⁰_n là họ các tập ‘độc thân’ thuộc E_n và O_n. Ta dễ dàng xây dựng song ánh giữa chúng bằng cách chọn phần tử ‘độc thân’ lớn nhất và thay bởi phần tử còn lại trong cặp của nó, suy ra |E⁰_n|=|O⁰_n|.

Do đó, ta chỉ cần tính phần còn lại của các tập con n-phần tử của [2n], tức là các tập mà phần tử của nó phải bắt thành từng cặp (2i−1,2i).

. Khi n lẻ thì mọi tập conn-phần tử đều ‘độc thân’ nên

|E_n| − |O_n|=|E⁰_n| − |O⁰_n|= 0.

. Khi n chẵn thì phần còn lại của các tập con n-phần tử của [2n] gồm C_n/2ⁿ tập, mỗi tập chứa đúng n

2 cặp. Nhận thấy tổng hai số trong một cặp luôn lẻ.

◦ Nếu n= 4k thì tổng các phần tử của tập này chẵn nên phần còn lại của các tập con n-phần tử của [2n] đều thuộc En, suy ra

|E_n| − |O_n|=C_n^n/2.

◦ Nếu n = 4k+ 2 thì tổng các phần tử của tập này lẻ nên phần còn lại của các tập con n-phần tử của[2n] đều thuộc O_n, suy ra

|E_n| − |O_n|=−C_n^n/2. Sử dụng số phức, ta có thể biểu diễn kết quả trên dưới dạng

|E_n| − |O_n|= i³ⁿ+iⁿ

2 ·C_n^bn/2c. Bài toán được giải quyết.

Bài toán tiếp theo là một tính chất kinh điển của tập con (n+ 1)-phần tử của tập[2n].

Về mặt phát biểu, nó khá tương đồng với bài toán 4, nhưng việc giải quyết lại liên quan đến một số khái niệm của Số học.

Bài toán 14. Chứng minh tập con bất kỳ của [2n] gồmn+ 1 phần tử luôn có hai số a, b sao cho a|b.

Lời giải. Trước tiên, ta cần một số định nghĩa sau.

◦ Số mũ đúng của số nguyên tố ptrongn, kí hiệuv_p(n), là số mũ lớn nhất củaptrong phân tích thừa số nguyên tố củan. Nói cách khác,vp(n)là số tự nhiên thỏap^vp(n) |n nhưng p^vp(n)+1 6 |n.

◦ Ước lẻ lớn nhất của n, kí hiệugod(n), là số lẻ lớn nhất chia hết n.

Từ định nghĩa, ta dễ dàng chứng minh được các nhận xét sau.

(i) n= 2^v2(n)·god(n), ∀n ∈N. (ii) Nếua |b thì god(a)|god(b).

(iii) Nếugod(a) = god(b) thì a |b hoặc b|a.

Do trong [2n] có n số lẻ nên theo nguyên lý Dirichlet, trong tập con bất kỳ có n+ 1 phần tử luôn có hai số a, bsao cho god(a) =god(b). Khi đó, theo nhận xét (iii) thì a|b hoặc b|a. Ta thu được điều phải chứng minh.

Tiếp theo là hai bài toán sử dụng khái niệm god trên.

Bài toán 15. Gọi S là tập con gồm n phần tử của tập [2n] sao cho không chứa hai số a, b mà a|b. Chứng minh rằng phần tử c có thể thuộc một tập S như vậy khi và chỉ khi

c > n·

Ç2 3

å_v2(c)+1

.

(Romania TST 2007)

Lời giải. (edriv) GọiD là họ các tập con gồm n phần tử của [2n]sao cho không chứa a, b mà a|b. Trước tiên, ta chứng minh các nhận xét sau :

(i)Với mọi số nguyên lẻ t ∈[2n]

◦ Tồn tại duy nhất i∈N sao cho n < 2ⁱ·t≤2n. Thật vậy, chọn ilớn nhất sao cho 2ⁱ·t ≤2n, tức là

2ⁱ·t≤2n <2ⁱ⁺¹·t ⇒ 2ⁱ⁻¹·t≤n <2ⁱ·t.

Từ đó, tính duy nhất của iđược xác định.

◦ Tồn tại duy nhất j ∈Nsao cho 2^j·t ∈S. Thật vậy, theo nhận xét (iii)của bài toán 14, thì godcủa các phần tử trong S đôi một phân biệt. Từ đó, do |S|=n và trong [2n] có đúng n số lẻ nên tính duy nhất của j được xác định.

(ii)Với mọi n < a < b≤2n thì a6 |b. Thật vậy, nếu a|b thì b≥2a >2n, vô lý.

Trở lại bài toán, ta sẽ chứng minh mệnh đề yêu cầu bằng quy nạp theo v₂(c).

. Khi v₂(c) = 0 thì c=god(c) là số lẻ.

◦ c≤ 2

3n, khi đó số nguyên lẻ 3c≤2n. Do đó, theo nhận xét (i) thì tồn tại duy nhất j sao cho 2^j·3c∈S, mà c|2^j·3cnên c6∈S.

◦ c > 2

3n, ta cần xây dựng S ∈ D chứa c. Theo nhận xét (i), với các số lẻ t ∈ [2n]

khác c, tồn tại duy nhất i sao cho n <2ⁱ ·t≤2n. Lấy S gồm các số dạng 2ⁱ·t này và c thì |S|=n. Ta sẽ chứng minh S ∈ D.

Thật vậy, vì n <2ⁱ·t≤2n nên theo nhận xét (ii), các số dạng 2ⁱ·t sẽ không chia hết nhau.

· Nếu 2

3n < c≤n <2ⁱ·t thì c= minS. Do đó nếu tồn tại a, b∈S màa|b thì a=c, hayc|b. Khi đó, theo nhận xét (ii)của bài toán 14, thì god(c)|god(b), mà god(c)6=god(b) nên god(b)≥3·god(c) = 3c >2n, vô lý.

· Nếu n < c ≤ 2n thì S = {n+ 1, n+ 2, . . . ,2n}, theo nhận xét (ii), ta được S∈ D.

. Giả sử mệnh đề đúng với mọi v2(c)≤ k−1. Ta chứng minh mệnh đề cũng đúng với v₂(c) =k, khi đó c= 2^k·god(c).

◦ c ≤ n ·

Ç2 3

å_k+1

, khi đó số nguyên lẻ 3^k+1

2^k ·c = 3^k+1 ·god(c) ≤ 2n. Do đó, theo nhận xét (i) thì tồn tại duy nhất j sao cho 2^j ·3^k+1·god(c) ∈ S. Nếu j ≥ k thì c= 2^k·god(c)| 2^j ·3^k+1·god(c) nên c6∈S. Ngược lại, nếu j ≤ k−1 thì theo giả thiết quy nạp

2^j·3^k+1·god(c)> n·

Ç2 3

å_j+1

⇒ 2^k·god(c) = c > n·

Ç2 3

å_k+1

, mâu thuẫn.

◦ c > n·

Ç2 3

å_k+1

, ta cần xây dựngS ∈ Dchứa c. Ta chia các số lẻt ∈[2n] khácgod(c) thành hai lớp

· Lớp I :god(c)6 |t, theo nhận xét (i), tồn tại duy nhất isao cho n <2ⁱ·t ≤2n.

· Lớp II : god(c) | t, khi đó chọn i lớn nhất sao cho 3ⁱ ·god(c) ≤ t. Tức là 3ⁱ·god(c)≤t <3ⁱ⁺¹·god(c), và ta xét các số dạng 2^k−i·t. Dễ thấy, nếu trong các số này cóa, bmà god(a)< god(b)thì v₂(a)> v₂(b).

Lấy S gồm các số dạng 2ⁱ·t ở lớp I, các số dạng 2^k−i·t ở lớp II và cthì |S|= n. Ta sẽ chứng minh S∈ D. Thật vậy, giả sử có a, b∈S mà a|b.

· Nếua thuộc lớp I, khi đó n < a < b ≤2n, mâu thuẫn với nhận xét (ii).

· Nếu a thuộc lớp II hay a =c thì god(c) |god(a). Theo nhận xét (ii) của bài toán 14, thìgod(a)|god(b), suy ra god(c)|god(b) hay b cũng thuộc lớp II. Từ đó, dogod(a)|god(b) nên god(a)< god(b), suy rav₂(a)> v₂(b), vô lý vì a|b.

Như vậy, ta đã chứng minh được S ∈ D.

Theo nguyên lý quy nạp, ta thu được điều phải chứng minh.

Bài toán 16. Cho số nguyên dương n >1. Gọi N là họ các tập con gồm n phần tử của tập [2n]. Xác định

maxS∈N

Ç

x,y∈S, x6=ymin [x, y]

å

.

(Romania TST 2013)

Lời giải. (numbertheorist17) Trước tiên, ta chứng minh nhận xét sau.

[a, b] =^î2^v2(a)·god(a), 2^v2(b)·god(b)^ó= 2^{max{v2(a), v2(b)}}·[god(a), god(b)]. (∗)

◦ Nếugod(a)|god(b)thì

[a, b] = 2^{max{v2(a), v2(b)}}·god(b)≥max{a, b}.

Nói riêng trường hợp god(a) =god(b) thì [a, b] = max{a, b}.

◦ Nếugod(a)6 |god(b)và god(b)6 |god(a)thì

[a, b]≥2^{max{v2(a), v2(b)}}·3·max{god(a), god(b)} ≥3·max{a, b}.

Nhận xét được chứng minh.

Trở lại bài toán, gọi mS = min

x,y∈S, x6=y[x, y]. Ta chia S ∈ N thành hai loại.

. Loại I : tồn tạia, b∈S mà god(a) = god(b). Khi đó theo nhận xét(∗), ta có m_S ≤[a, b] = max{a, b} ≤2n,

nên maxm_S ≤2n, với S∈ N thuộc loại I.

. Loại II : godcủa các phần tử của S đôi một phân biệt. Trước tiên, ta chứng minh S^∗ ={n+ 1, n+ 2, . . . ,2n} ∈ N

là một tập thuộc loại II. Thật vậy, giả sử a, b∈S^∗ mà god(a) = god(b), thì theo nhận xét (iii)của bài toán 14, sẽ có a|b hoặc b|a, mâu thuẫn với nhận xét (ii) của bài toán 15.

Nếu tồn tại a ∈ S mà a ≤ n thì khi thay a bởi 2a ≤ 2n ta sẽ thu được tập S⁰ ∈ N, mà god(2a) = god(a) nên S⁰ cũng thuộc loại II. Dễ thấy m_S⁰ ≥ m_S. Từ đây suy ra maxmS =mS^∗, với S ∈ N thuộc loại II.

Xét a, b∈S^∗ mà god(a)< god(b).

◦ Nếugod(a)|god(b)thì god(b)≥3·god(a) nên theo nhận xét(∗)

[a, b] = 2^{max{v2(a), v2(b)}}·god(b)≥2^v2(a)·3·god(a) = 3a≥3·(n+ 1).

◦ Nếugod(a)6 |god(b)thì god(b)≤3·god(a) nên theo nhận xét(∗) [a, b]≥3·max{a, b} ≥3a≥3·(n+ 1).

Suy ra maxm_S =m_S^∗ ≥3·(n+ 1), với S ∈ N thuộc loại II.

Như vậy, tổng hợp loại I và II, ta thấy max

S∈N m_S = m_S^∗ ≥ 3·(n+ 1). Bây giờ, ta sẽ xác định chính xác giá trị mS^∗ theo n.

. Nếun lẻ thìv₂(n+ 1)>0 nên

god(n+ 1) = n+ 1

2^v2(n+1) ≤ n+ 1 2 ≤ 2n

3 .

hay 3·god(n+ 1)≤2n. Do đó, theo nhận xét (i)của bài toán 15, tồn tại duy nhất t sao cho 2^t·3·god(n+ 1) ∈S^∗. Nếu t > v₂(n+ 1) thì

n <2^v2(n+1)·god(n+ 1)<2^v2(n+1)+1·god(n+ 1)≤2^t·god(n+ 1)<2^t·3·god(n+ 1)<2n, mâu thuẫn với nhận xét(i) của bài toán 15 về tính duy nhất của t. Do đó t≤v₂(n+ 1) nên theo nhận xét (∗)

î2^v2(n+1)·god(n+ 1),2^t·3·god(n+ 1)^ó= 2^v2(n+1)·3·god(n+ 1).

Như vậy, m_S^∗ có thể đạt được giá trị 3·(n+ 1).

. Nếun ≥6chẵn thì v₂(n+ 2)>0nên god(n+ 2) = n+ 2

2^v2(n+2) ≤ n+ 2 2 ≤ 2n

3 .

hay 3·god(n+ 2)≤2n. Do đó, theo nhận xét (i)của bài toán 15, tồn tại duy nhất t sao cho 2^t·3·god(n+ 2) ∈S^∗. Tương tự trường hợpn lẻ, ta cũng chứng minh được

î2^v2(n+2)·god(n+ 2),2^t·3·god(n+ 2)^ó= 2^v2(n+2)·3·god(n+ 2).

Như vậy, m_S^∗ có thể đạt được giá trị 3·(n+ 2).

Ta sẽ chứng minh đây là giá trị cần tìm, hay ta cần chứng minh [n+ 1, a]>3·(n+ 2),

∀a > n+ 1 ∈S^∗. Thật vậy, do n≥6 chẵn nênn+ 1 =god(n+ 1) lẻ.

◦ Nếugod(a)≤n thì do a > n nên v₂(a)>0. Từ đó, theo nhận xét (∗)

[god(n+ 1), 2^v2(a)·god(a)]≥2^v2(a)·3·god(n+ 1)≥6·(n+ 1)>3·(n+ 2).

◦ Nếugod(a)> n thì theo nhận xét (∗)

[god(n+ 1), 2^v2(a)·god(a)]≥2^v2(a)·3·god(a)≥3·(n+ 2).

. Trường hợp n= 2 thì S^∗ ={3,4} vàmS^∗ = 12.

. Trường hợp n= 4 thì S^∗ ={5,6,7,8} và m_S^∗ = 24.

Tóm lại, max

S∈N m_S là 3·(n+ 1) khin lẻ; 3·(n+ 2) khi n 6= 4chẵn và 24 khi n= 4.

Tiếp theo, mời bạn đọc cùng xem chuỗi hai bài toán sau đây.

Bài toán 17. Tính số tập con của [2n] thoả mãn không chứa hai phần tử a, b mà a+b= 2n+ 1.

(Polish MO 1995, Swedish MO 2006)

Lời giải. Xét bảng sau

1 2 3 . . . n

2n 2n−1 2n−2 . . . n+ 1

Rõ ràng, nếu hai phần tử a, bcủa [2n] thuộc cùng một cột thìa+b = 2n+ 1. Do đó ở mỗi cột, ta có 3lựa chọn : chọn một số ở hàng trên, hoặc chọn một số ở hàng dưới, hoặc không chọn cả hai. Suy ra số tập con của[2n]thoả yêu cầu bài toán là 3ⁿ.

Bài toán 18. Tính số tập con của [2n] thoả mãn không chứa hai phần tử a, b mà

|a−b| ∈ {1, n}.

(Vietnam MO 2009)

Lời giải. Xét bảng sau

1 2 3 . . . n−1 n

n+ 1 n+ 2 n+ 3 . . . 2n−1 2n

Yêu cầu bài toán tương đương với việc tính số cách chọn một số ô (có thể là không có ô nào) thoả

(i) Hai ô kề nhau trong bảng không đồng thời được chọn.

(ii) n và n+ 1 không đồng thời được chọn.

Ta đặt S_n là số cách chọn này. GọiA_n, B_n, C_n là số cách chọn thoả (i) từ các bảng sau.

1 2 3 . . . n−1 n n+ 1 n+ 2 n+ 3 . . . 2n−1 2n

A_n - Bảng bình thường.

1 2 3 . . . n−1 n

n+ 2 n+ 3 . . . 2n−1 2n B_n - Bảng bị mất một ô ở góc.

1 2 3 . . . n−1

n+ 2 n+ 3 . . . 2n−1 2n C_n - Bảng bị mất hai ô ở hai góc đối nhau.

. XétA_n, ta có các trường hợp sau

◦ Chọn ô{1}, khi đó không chọn hai ô{2} và {n+ 1} : có Bn−1 cách.

◦ Chọn ô{n+ 1}, khi đó không chọn hai ô {1} và {n+ 2} : có Bn−1 cách.

◦ Không chọn cả hai ô {1} và {n+ 1}: có An−1 cách.

Suy ra

A_n=An−1 + 2·Bn−1. (1)

. XétB_n, ta có các trường hợp sau

◦ Chọn ô{1}, khi đó không chọn ô {2} : có Bn−1 cách.

◦ Không chọn ô {1} : có An−1 cách.

Suy ra

B_n=An−1 +Bn−1. (2)

. XétC_n, ta có các trường hợp sau

◦ Chọn cả hai ô {1} và {n+ 2}, khi đó không chọn hai ô {2} và {n+ 3} : có Cn−2

cách.

◦ Chọn ô{1} và không chọn ô {n+ 2}, khi đó không chọn ô {2} : có B_n−2 cách.

◦ Không chọn ô {1} : có Bn−1 cách.

Suy ra

C_n=Bn−1+Bn−2+Cn−1. (3)

. XétA_n lần nữa, ta có các trường hợp sau

◦ Chọn cả hai ô{n}và{n+ 1}, khi đó không chọn bốn ô{2},{n+ 2},{n−1},{2n} : cóCn−2 cách.

◦ Không chọn đồng thời hai ô {n} và {n+ 1} : có Sn cách.

Suy ra

A_n =Cn−2 +S_n. (4)

Từ (1),(2),(3) và (4), ta thiết lập được hệ thức truy hồi riêng của Sn

(S_n =Sn−1+ 3·Sn−2+Sn−3

S₁ = 3, S₂ = 6, S₃ = 10 hay S_n= (3 +√

2)(1 +√

2)ⁿ+ (3−√

2)(1−√

2)ⁿ−2·(−1)ⁿ

4 , ∀n ∈N.

Tiếp theo cũng là một bài toán dùng ý tưởng truy hồi.

Bài toán 19. Cho số nguyên không âm n. Tính số cách chọn (n+ 1)² tập con Si,j của tập [2n], với 0≤i, j ≤n thỏa mãn đồng thời các điều kiện sau.

(i) Tập S_i,j có i+j phần tử.

(ii) Nếu 0≤i≤k ≤n và 0≤j ≤l≤n thì S_i,j ⊆S_k,l.

(USA MO 2019, Ricky Liu)

Lời giải. (TheUltimate123) Ta sẽ sử dụng phương pháp truy hồi. GọiT_n là số cách chọn (n+ 1)² tập S_i,j thỏa yêu cầu bài toán. Ta lần lượt chọn S_i,j theo thứ tự sau.

(1) Chọn S_n,n. Theo (i) thì |S_n,n|=n+n = 2n nên rõ ràngS_n,n = [2n]. Do đó chỉ có 1 cách chọn.

(2) Chọn Sn−1,n−1. Theo (i) thì |Sn−1,n−1| = (n−1) + (n −1) = 2n−2 và hiển nhiên S_n−1,n−1 ⊂ [2n] = S_n,n nên ta cần chọn 2n −2 phần tử bất kỳ từ [2n]. Do đó ta có C_2n²ⁿ⁻² =C_2n² cách chọn.

(3) Rõ ràng nếu thay tập [2n] trong đề bài bằng tập có 2n phần tử bất kỳ thì bài toán không thay đổi, tức là T_n cũng không thay đổi.

Do đó, khi đã chọn xong Sn−1,n−1 (nói cách khác ta đã cố định Sn−1,n−1) thì số cách chọn n² tập S_i,j ⊆Sn−1,n−1, với 0≤i, j ≤n−1, đồng thời thỏa (i) và (ii) chính là Tn−1. (4) Như vậy, việc cuối cùng là chọn các tập có dạng Si,n và Sn,j, với 0≤i, j ≤n−1.

Từ tập S_n,n, ta sẽ lần lượt chọn ngược về từ Sn−1,n, Sn−2,n, . . . đếnS_0,n. Giả sử ta đã chọn xongSi,n (cố định Si,n), ta sẽ tính số cách chọn Si−1,n. Theo (i) và (ii) thì Si−1,n chỉ cần thỏa mãn hai điều kiện sau là được

Si−1,n−1 ⊂Si−1,n ⊂S_i,n, |Si−1,n|+ 2 =|Si−1,n|+ 1 =|S_i,n|=i+n.

Từ trên suy ra Si,n\Si−1,n−1 ={a, b}, do ta cũng đã chọn xong Si−1,n−1 (cố địnhSi−1,n−1) nên a, bcố định. Và như vậy, Si−1,n chính làSi−1,n−1 cộng thêm một trong hai phần tử a vàb. Do đó ta có 2 cách chọn Si−1,n.

Từ đây suy ra có 2ⁿ cách chọn các tập dạng Si,n, với0≤i≤n−1. Tương tự, có2ⁿ cách chọn các tập dạng S_n,j, với 0≤j ≤n−1.

Tổng hợp lại, ta thiết lập được hệ thức truy hồi của T_n.

(T₀ = 1

T_n =C_2n² ·2²ⁿ·T_n Suy ra T_n = (2n)!·2ⁿ², ∀n ∈N.

Bài toán 20. Cho số nguyên n ≥ 2, gọi X là một tập con của [2n]. Xét các tổng có dạng e1x1+e2x2+e3x3, trong đó các phần tử x1, x2, x3 thuộc tập X (không nhất thiết phân biệt) và e₁, e₂, e₃ ∈ {−1,0,1} thoả

◦ e²₁+e²₂+e²₃ 6= 0.

◦ Nếu xi =xj thì eiej 6=−1.

Tập X được gọi là tự do nếu tất cả các tổng đều không chia hết cho 2n. Tìm giá trị lớn nhất của số phần tử của một tập tự do.

(Bulgaria MO 1997)

Lời giải. Gọi X là một tập tự do, ta sẽ chứng minh |X| ≤ bn/2c. Trước tiên, ta có các nhận xét sau.

◦ 1·2n+ 0·x₂+ 0·x₃ = 2n...2n, do đó2n6∈X.

◦ 1·n+ 1·n+ 0·x₃ = 2n...2n, do đó n6∈X.

◦ 1·k+ 1·(2n−k) + 0·x3 = 2n...2n, do đó k và 2n−k không thể cùng thuộcX.

Hơn nữa, khi ta đổik ∈X thành2n−k và ở các tổng chứa k, nếu hệ số củak khác 0, ta đổi1 thành −1và ngược lại. Theo đó, tập các số dư của các tổng modulo 2n sẽ không đổi, và tập X mới nhận được cũng tự do.

Từ đây, ta có thể giả sử X là một tập con của S⁰ ={1,2, . . . , n−1}.

Gọi d là phần tử nhỏ nhất của X. Ta chia các phần tử của S⁰ lớn hơn d thành các nhóm sau.

(n−1, n−2, . . . , n−2d), (n−2d−1, n−2d−2, . . . , n−4d), . . .

Như vậy, trừ nhóm cuối có r phần tử, ta được q nhóm, mỗi nhóm có 2d phần tử. Suy ra

|S⁰|= 2dq+r+d=n−1.

Chú ý là không tồn tạix_i, x_j ∈X màx_i−x_j = d, vì nếu không thì1·x_i−1·x_j−1·d= 0...2n.

Do đó trongq nhóm đầu, ở mỗi nhóm chỉ có thể tối đa d phần tử thuộc X. Ta xét nhóm cuối.

◦ Nếur > d thì ở nhóm cuối có thể tối đa d phần tử thuộc X. Suy ra

|X| ≤dq+d+ 1≤(2dq+d+r+ 1)/2 = n/2.

◦ Nếur < d thì ở nhóm cuối có thể tối đa r phần tử thuộc X. Suy ra

|X| ≤dq+r+ 1≤(2dq+d+r+ 1)/2 =n/2.

◦ Nếu r =d thì nhóm cuối là (2d,2d−1, . . . , d+ 1). Do1·d+ 1·d−1·2d= 0...2n nên 2d6∈X, ở nhóm cuối chỉ có thể tối đa d−1 phần tử thuộc X. Suy ra

|X| ≤dq+ (d−1) + 1<(2dq+d+r+ 1)/2 = n/2.

Từ đây ta thu được |X| ≤ bn/2c. Ta sẽ chỉ ra một tập tự do có số phần tử là bn/2c.

Xét X ={1,3,5, . . . ,2bn/2c −1}, rõ ràng |X|= bn/2c. Ta sẽ chứng minhX tự do. Thật vậy,

◦ Nếu không có số nào hoặc hai trong ba sốe1, e2, e3 bằng0thì tổnge1x1+e2x2+e3x3

lẻ, do đó không chia hết cho 2n.

◦ Nếu có một trong ba số e₁, e₂, e₃ bằng 0, giả sử là e₁, thì

|e₁x₁ +e₂x₂+e₃x₃|=

"

2≤ |x2−x3|<2bn/2c −2< n 2≤ |x₂+x₃|<4bn/2c −2<2n do đó không chia hết cho2n.

Từ đây suy ra tập X như đã chỉ ra là tự do. Vậy nếu X tự do thì max|X|=bn/2c.

Bài toán 21. Tập con S khác rỗng của tập [2n] gọi là tốt nếu tập {a±b | a, b∈ S}

không chứa tập {1,2, . . . , n}. Tìm hằng số c nhỏ nhất sao cho với mọi tập con S tốt của tập [2n], ta luôn có |S| ≤cn.

(China TST 2015)

Lời giải. (Wolstenholme) Xét n = 5t, với t ∈ N^∗ và S = {1,2, . . . ,2t −1,6t + 1,6t + 2, . . . ,10t} ⊂[2n]. Rõ ràng 4t6∈(S+S)∪(S−S) nên S là tập tốt. Do đó

c≥ |S|

n = 6t−1 5t .

Khi cho t= ⁿ₅ → ∞, ta được c≥ ⁶₅. Ta sẽ chứng minh c= ⁶₅ là giá trị cần tìm.