Các phương pháp chứng minh bồi dưỡng học sinh giỏi Toán - Nguyễn Tất Thu

Trường THPT Chuyên Lương Thế Vinh

——————–o0o——————–

NGUYỄN TẤT THU

CHUYÊN ĐỀ LỚP 10 TOÁN

MỘT SỐ NGUYÊN LÝ TRONG GIẢI TOÁN

Biên Hòa - 2018

—————–

Mục lục

1 Các phương pháp giải toán 5

1. Phương pháp quy nạp toán học . . . 5

I. Mở đầu . . . 5

II. Nguyên lí quy nạp . . . 5

III. Một số ví dụ . . . 6

IV. Bài tập . . . 9

2. Nguyên lí Dirichlet . . . 15

I. Sử dụng nguyên lí Dirichlet . . . 15

II. Nguyên lí Dirichlet . . . 15

1. Nguyên lí Dirichlet . . . 15

2. Nguyên lí Dirichle mở rộng . . . 15

3. Nguyên lí Dirichle cho tập hợp . . . 15

4. Nguyên lí Dirichle trong hình học . . . 15

III. Ví dụ . . . 15

IV. Bài tập . . . 18

3. Nguyên lí cực hạn . . . 20

I. Ví dụ . . . 20

II. Bài tập . . . 21

4. Nguyên lí bất biến . . . 23

I. Ví dụ . . . 23

II. Bài tập . . . 24

3

Chương 1

Các phương pháp giải toán

§1. Phương pháp quy nạp toán học

I. Mở đầu

Quy nạp là phương pháp mạnh được sử dụng nhiều trong Toán học. Trong tổ hợp, phương pháp quy nạp được sử dụng để giải các bài toán đếm, bài toán chứng inh tồn tại, bài toán cực trị,. . . Trong bài viết này, tôi xin trao đổi một số áp dụng phương pháp quy nạp vào bài toán chứng minh tồn tại và cực trị trong tổ hơp.

II. Nguyên lí quy nạp

Quy nạp toán học là một phương pháp mạnh để chứng minh các phát biểu phụ thuộc vào một số tự nhiên.

Cho(P(n))_n≥0 là một dãy các mệnh đề. Phương pháp quy nạp toán học được sử dụng để chứng minhP (n) đúng với mọi n ≥n₀ với n₀ là một số tự nhiên.

Phương pháp quy nạp toán học (dạng yếu): Giả sử

• P (n₀) đúng.

• Với mọi k≥n₀ và P(k) đúng thì P (k+ 1) đúng.

Khi đó P (n) đúng với mọi n ≥n₀.

Phương pháp quy nạp toán học (bước nhảys): Cho s là số nguyên dương. Giả sử

• P (n0), P (n0+ 1), . . . , P(n0+s−1) đúng.

• Với mọi k≥n₀, P(k) đúng kéo theo P (k+s) đúng . Khi đó P (n) đúng với mọi n ≥n₀.

Phương pháp quy nạp toán học (Dạng mạnh): Giả sử

• P (n₀) đúng

• Với mọi k≥n₀, P(m) đúng với mọi m mà n₀ ≤m≤k kéo theo P(k+ 1) đúng.

Khi đó P (n) đúng với mọi n ≥n0.

5

III. Một số ví dụ

Ví dụ 1. Chứng minh rằng

1²+ 2²+ 3²+· · ·+n² = n(n+ 1)(2n+ 1)

6 . (1)

với mọi số tự nhiên n ≥1.

Lời giải.

Với n= 1, ta có (1) đúng, vì hai vế cùng bằng 1.

Giả sử (1) đúng với n =k, k≥1. Tức là

1²+ 2²+ 3²+· · ·+k² = k(k+ 1)(2k+ 1)

6 (1.1).

ta cần chứng minh (1) đúng với n=k+ 1, tức là

1² + 2²+ 3² +· · ·+k² + (k+ 1)² = (k+ 1)(k+ 2)(2k+ 3)

6 (2.1).

Thật vậy

V T(2.1) = k(k+ 1)(2k+ 1)

6 + (k+ 1)² = (k+ 1)

k(2k+ 1)

6 +k+ 1

= (k+ 1)2k²+ 7k+ 6

6 = (k+ 1)(k+ 2)(2k+ 3)

6 =V P(2.1).

Từ đó ta có đpcm.

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên n≥2 ta luôn có

3ⁿ>3n+ 1. (2)

Lời giải.

Với n= 2 ta có:V T(2) = 3² = 9 > V P(2) = 3.2 + 1 = 7nên (2) đúng với n= 1..

Giả sử (2) đúng với n =k ≥2, tức là: 3^k>3k+ 1. (1.2) Ta chứng minh (1) đúng vớin =k+ 1, tức là :

3^k+1 ≥3(k+ 1) + 1 = 3k+ 4. (2.2) Thật vậy:

3^k+1 = 3.3^k>3(3k+ 1) = 3k+ 4 + (6k−1)>3k+ 4 nên (2.2) đúng.

Vậy bài toán được chứng minh.

Ví dụ 3. Cho hàm số f :R→R, n≥2là số nguyên . Chứng minh rằng nếu f(x) +f(x)

2 ≥f

x+y 2

∀x, y ≥0(3.1) thì với ∀xi ≥0,i= 1, n ta có:

f(x₁) +f(x₂) +. . .+f(x_n)

n ≥f

x₁+x₂+. . .+x_n n

. (3.2)

Lời giải.

• Ta chứng minh (3.2) đúng với n= 2^k, k ≥1.

+) Vớik = 1 thì (3.2) đúng (do (3.1)).

+) Giả sử (3.2) đúng với n= 2^k, ta chứng minh (3.2) đúng với n= 2^k+1. Thật vậy:

f(x₁) +. . .+f(x₂^k)≥2^kf

x1+. . .+x₂^k 2^k

f(x₂^k₊₁) +. . .+f(x₂^k+1)

≥2^kf

x₂^k₊₁+. . .+x₂^k+1 2^k

.

Do đó:

f(x₁) +. . .+f(x₂^k+1)≥2^kf

x₁+. . .+x₂^k 2^k

+ 2^kf

x₂^k₊₁+. . .+x₂^k+1 2^k

≥2^k+1f

x₁+. . .+x₂^k +x₂^k₊₁+. . .+x₂^k+1 2^k+1

.

Do vậy (3.2) đúng với mọi n= 2^k.

•Giả sử (3.2) đúng với mọi n =k+ 1 ≥3, tức là f(x1) +f(x2) +. . .+f(xk+1)

k+ 1 ≥f

x1+x2 +. . .+xk+1

k+ 1

. (3.3)

Ta chứng minh (3.2) đúng với n=k, tức là f(x₁) +f(x₂) +. . .+f(x_k)

k ≥f

x₁+x₂ +. . .+x_k k

. (3.4)

Thật vậy:

Đặtx_k+1 = x₁+x₂+. . .+x_k

k = x

k, áp dụng (3.3) ta có f(x₁) +f(x₂) +. . .+f(x_k) +fx

k

k+ 1 ≥f





x₁+x₂+. . .+x k k+ 1



.

Hay

f(x₁) +f(x₂) +. . .+f(x_k)

k ≥f

x₁+x₂ +. . .+x_k k

.

Vậy bài toán được chứng minh.

Ví dụ 4. Chứng minh rằng với mỗi số tự nhiên n ≥2, luôn tồn tại một tập hợp S có n số nguyên dương phân biệt sao cho (a−b)² là ước củaa·b với mọia, b∈S.

Lời giải.

Với n= 2 ta chọn S₂ ={0, 1}.

Giả sử tồn tại tập S_n = {a₁, a₂,· · · , a_n} thỏa yêu cầu bài toán. Gọi x là bội chung nhỏ nhất của các số khác0 có dạng (a−b)² với a, b∈S_n. Đặt

Sn+1 ={x+a|a∈Sn} ∪ {0}. Khi đó|S_n+1|=n+ 1 và với a, b∈S_n+1 ta có :

• Nếu ab= 0 thì (a−b)²|ab.

• Nếuab6= 0,khi đó tồn tạii, j ∈ {1,2,· · · , n}; i6=j sao choa=x+a_i, b=x+a_j. Khi đó (x+a_i) (x+a_j) = x²+x(a_i+a_j) +a_ia_j ≡a_ia_j ≡0 mod(a_i−a_j)²

, hay

(a−b)² = [(x+a_i)−(x+a_j)]² = (a_i−a_j)²|(x+a_i) (x+a_j) = ab.

Vậy bài toán được chứng minh.

Ví dụ 5. Trên đường tròn người ta điền n (n ≥ 3) số sao cho với mỗi số bất kì thì tổng của hai số kề bên chia hết cho số đó. Chứng minh rằng tổng các thương không vượt quá 3n.

Lời giải.

Ta chứng minh bài toán bằng phương pháp quy nạp.

• n= 3 . Gọi ba số đó a, b, c, khi đó ta có







a+b =xc b+c=ya c+a=zb .

Giả sửa = max{a, b, c}ta có

ya =b+c≤2a⇒y∈ {1, 2}. +) y= 2, ta cóa=b =c nên x+y+z = 6.

+) y= 1, ta cób+c=a. Giả sửb ≥c, khi đó ta có

zb =c+a= 2c+b ⇒2c= (z−1)b≥b nên c≤b ≤2c.

Suy ra

xc=a+b =c+ 2b≤5c⇒x≤5 zb =c+a= 2c+b≤3b⇒z ≤3.

Do đóx+y+z≤9. Do đó, bài toán đúng với n= 3.

• Giả sử bài toán đúng với n≥3, ta chứng minh bài toán cũng đúng với n+ 1.

+) Nếu n+ 1 số đã cho bằng nhau thì ta có đpcm.

+) Xét trường hợp ngược lại, tồn tạia, b, c sao chob, c xếp cạnh a và a >max{b, c} và b nằm giữa a và d, cnằm giữa a và e. Ta có







b+c=ma a+d=nb a+e =pc .

Do b+c <2a nên m= 1 hay b+c=a. Suy ra

c+d = (n−1)b b+e= (p−1)c.

Do vậy, khi ta bỏ a khỏi vòng tròn thìn số còn lại vẫn thỏa yêu cầu đề bài, theo giả thiết quy nạp thì tổng các thương của n số này không vượt quá 3n, do đó tổng các thương của n+ 1 số không vượt quá 3n+ 3 = 3 (n+ 1).

Vậy bài toán được chứng minh.

IV. Bài tập

Bài 1. Chứng minh các đẳng thức và bất đẳng thức sau a) 1.2²+ 2.3²+ 3.4²+. . .+ (n−1).n² = n(n²−1)(3n+ 2)

12 với ∀n ≥2.

b) 2²+ 4²+. . .+ (2n)² = 2n(n+ 1)(2n+ 1)

3 với ∀n ∈N∗.

c) 1 2.3

4.5

6. . . .2n+ 1

2n+ 2 < 1

√3n+ 4. d) √

n <1 + 1

√2+ 1

√3. . . .+ 1

√n ≤2√

n với ∀n ≥1.

e) 1 + 1 2+ 1

3+. . .+ 1

2ⁿ−1 < n; (∀n ∈N^∗, n≥2).

Bài 2. Chứng minh rằng với mọi số nguyên dương n, ta có a) n(2n²−3n+ 1) chia hết cho 6.

b) 11ⁿ⁺¹+ 12²ⁿ⁻¹chia hết cho133.

c) n⁵−n chia hết cho 5 d) 13ⁿ−1chia hết cho 6

e) 16ⁿ−15n−1chia hết cho 225 f) 4.3²ⁿ⁺¹+ 32n−36chia hết cho 64.

Bài 3. Trong mặt mặt phẳng cho n điểm rời nhau (n≥3) tất cả không nằm trên một đường thẳng. Chứng minh rằng tất cả các đường thẳng nối hai điểm trong các điểm đã cho tạo ra số đường thẳng khác nhau không nhỏ hơn n.

Bài 4. Tập A = {a₁, a₂, . . . , a_n} gồmn > 2 số nguyên dương phân biệt được gọi là tập “ tốt”

nếu a²⁰¹⁶_i luôn chia hết cho tícha₁a₂. . . ai−1a_i+1. . . a_n với mọi i= 1,2016. Tìm số nguyên dương n lớn nhất để tồn tại một tập “tốt” có đúng n phần tử.

Lời giải.

Giả sửA={a₁, a₂, . . . , a_n} là tập “tốt” với a₁ < a₂ < . . . < a_n. ĐặtP₁ =a₂a₃. . . a_n, theo đề bài ta cóP1|a²⁰¹⁶₁ nên P1 ≤a²⁰¹⁶₁ . Mặt khácP1 > aⁿ⁻¹₁ nên

n−1<2016 ⇒n < 2017⇒n≤2016.

Ta chứng min với mọi3≤n≤2016 luôn tồn tại một tập “tốt” có n phần tử.

Với n= 3 ta chọn A ={6,18,36}.

Giả sửA={a1, a2, . . . , ak} là tập “tốt” vớik <2016.

ĐặtP =a₁a₂. . . a_k và

b₀ =P, b₁ =a₁P, b₂ =a₂P, . . . , b_k =a_kP.

Khi đó

b₁b₂. . . b_k=P^ka₁a₂. . . a_k

P²⁰¹⁶ =b²⁰¹⁶₀ Và

b₀b₁. . . bi−1b_i+1. . . b_k =P^ka₁..ai−1a_i+1. . . a_k b²⁰¹⁶_i . Do đó tậpB ={b₀, b₁, . . . , b_k} là tập “tốt” có k+ 1 phần tử.

Theo nguyên lí quy nạp ta có đpcm.

Bài 5. Chứng minh rằng với∀n ≥1,∀x >0 ta có BĐT:

xⁿ(xⁿ⁺¹+ 1) xⁿ+ 1 ≤

x+ 1 2

2n+1

.

Đẳng thức xảy ra khi nào?

Lời giải.

Gọi (1) là BĐT cần chứng minh.

Với n= 1 ta cần chứng minh:

x(x²+ 1) x+ 1 ≤

x+ 1 2

3

⇔8x(x²+ 1) ≤(x+ 1)⁴.

Hay là:

x⁴−4x³+ 6x²−4x+ 1 ≥0⇔(x−1)⁴ ≥0(đúng).

Suy ra đúng với n= 1. Đẳng thức xảy ra khi x= 1.

Giả sử (1) đúng với n =k ≥1, tức là:

x^k(x^k+1+ 1) x^k+ 1 ≤

x+ 1 2

2k+1

. (1.1)

Ta cần chứng minh:

x^k+1(x^k+2+ 1) x^k+1+ 1 ≤

x+ 1 2

2k+3

. (1.2)

Thật vậy, ta có:

x+ 1 2

2k+3

=

x+ 1 2

2 x+ 1

2

2k+1

≥

x+ 1 2

2

x^k(x^k+1+ 1) x^k+ 1 Nên để chứng minh (1.2) ta chỉ cần chứng minh

x+ 1 2

2

x^k(x^k+1+ 1)

x^k+ 1 ≥ x^k+1(x^k+2+ 1) x^k+1+ 1 . Hay

x+ 1 2

2

(x^k+1+ 1)² ≥x(x^k+2+ 1)(x^k+ 1). (1.3)

Khai triển (1.3) , biến đổi và rút gọn ta thu được:

x^2k+2(x−1)²−2x^k+1(x−1)²+ (x−1)² ≥0⇔(x−1)²(x^k+1−1)² ≥0.

BĐT này hiển nhiên đúng. Đẳng thức có ⇔x= 1.

Vậy bài toán được chứng minh.

Bài 6. Một người thợ luôn phải lát những căn phòng có kích thước 2ⁿ×2ⁿ ô vuông bằng các mảnh đá lát hình đô-mi-nô kích thước 1×3 ô vuông và các mảnh đá lát hình thước thợ 3 ô vuông. Anh ta phải lát kín cả căn phòng chỉ trừ lại một ô vuông duy nhất để trống không lát đá để trang trí đặc biệt. Do giá thành của một viên đá lát hình thước thợ đắt hơn nhiều giá thành của một viên đá lát hình đô-mi-nô, cho nên anh ta muốn sử dụng càng ít viên đá lát hình thước thợ càng tốt. Anh ta nhận thấy rằng dù vị trí ô đặc biệt ở đâu đi chăng nữa, chưa lần nào anh ta phải dùng nhiều hơn n viên gạch lát hình thước thợ để hoàn thành công việc của mình. Hãy chứng minh rằng khẳng định của người thợ luôn đúng với mọi số nguyên dươngn.

Thước thợ Đô-mi-nô Lời giải.

Trước hết ta chứng minh các bổ đề sau:

Bổ đề 1. Mọi hình chữ nhật có kích thước một cạnh chia hết cho3 thì lát được bởi các viên đá hình đô-mi-nô 1×3.

Bổ đề này là hiển nhiên.

Bổ đề 2. Mọi hình thước thợ tạo bởi ba hình vuông kích thức 2ⁿ×2ⁿ đều lát được bởi một số viên đá hình đô-mi-nô và1 viên đá hình thước thợ.

Chứng minh:

Kết luận hiển nhiên đúng khin = 1.

Giả sử kết luận đúng cho n = k−1 thì ta chia một hình thước thợ tạo bởi 3 hình vuông kích thước 2^k×2^k thành các hình chữ nhật có một cạnh chia hết cho 3 và một thước thợ tạo bởi 3 hình vuông kích thước2^k−1×2^k−1 (như trong hình 1).

Hình 1 Hình 2

Dễ thấy các hình chữ nhật thu được đều có đồ dài một cạnh chia hết cho3 nên chúng được lát bởi các viên đá đô-mi-nô theo Bổ đề 1.

Hình thước thợ gồm 3 ô vuông 2^k−1 ×2^k−1 theo giả thiết quy nạp lạt được bởi các viên đá đo-mi-nô và một viên đá hình thức thợ.

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

Với n= 1 thì bài toán hiển nhiên đúng.

Giả sử kết luận của bài toán đúng vớin =k−1≥ 1. Xét một căn phòng kích thước 2^k×2^k ô vuông. Chia hình vuông này thành 4 hình vuông bằng nhau thì ô trống sẽ rời vào một trong 4 hình vuông này, chẳng hạn rời vào góc phần tư thứ nhất (hình 2). Theo giả thiết quy nạp thì cần không quá k−1 viên đá lát hình thước thợ để lát hình vuông ở góc phần tư thứ nhất. Để lát hình thước thợ gồm 3 hình vuông kích thức 2^k−1×2^k−1, thi theo Bổ đề 2 ta cần một viên đá hình thước thợ. Do đó, ta cần không qua (k−1) + 1 =k viên đá hình thước thợ để lát căn phòng kích thước 2^k×2^k.

Vậy bài toán được chứng minh.

Bài 7. Một tập hợp con A có ít nhất ba phần tử của tập các số nguyên dương được gọi là tập

“thô” nếu với 3 phần tử phân biệt a, b, c của A thì a không là bội của (b, c), với (x, y) là kí hiệu ước chung lớn nhất của hai số nguyên x và y. Chứng minh rằng nếu A là tập “thô” có n phần tử và n≥4 thì maxA≥4 (n²−n−1) .

Lời giải.

Bổ đề 1. Từ 2n−2số tự nhiên đầu tiên ta chọn ra n số, khi đó luôn có hai trongn số đã chọn là bội của nhau.

Thật vậy:

Xétn số2^kim_i với k_i là các số tự nhiên vàm_i là các số nguyên dương lẻ.

Vì trong tập {1,2, . . . ,2n−2} có đúngn−1số lẻ, suy ra trongn số{m1, m2, . . . , mn} có hai số bằng nhau, chẳng hạn m_t=m_l (t > l). Khi đó 2^ktm_t...2^klm_l (đpcm).

Nhận xét: Từ bổ đề trên ta thấy:

Nếu lấy n số mà trong đó không có hai số nào là bội của nhau thì max của n số đó không nhỏ hơn 2n−1.

Bổ đề 2. NếuA={a, b, c} là tập “thô” thìmax{a, b, c} ≥15.

Thật vậy:

Vì {a, b, c} là tập thô nên (a, b), (b, c), (c, a) là ba số mà không có hai số nào là bội của nhau.

Theo bổ đề 1, ta có

max{(a, b), (b, c), (c, a)} ≥5.

Hơn nữa1< a

(a, b) 6= b

(a, b) nên

max a

(a, b), b (a, b)

≥3.

Từ đó, suy ra

max{a, b, c} ≥3 max{(a, b), (b, c), (c, a)} ≥15.

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

Xétn = 4, đặt A ={a, b, c, d}. Gọi x₁, x₂,· · · , x₆ là UCLN của hai trong 4 số thuộc tậpA và x= max{x₁, x₂,· · · , x₆}. Ta có x≥11.

Dễ thấy x /∈A.

+) Nếu kx∈A với k ≥4thì maxA ≥4.11 = 44.

+) Nếu 2x ∈ A, 3x ∈ A. Xét y ∈ A\ {2x,3x}. Nếu (y,3) = 1 thì (y,3x) = (y, x)|2x (vô lí).

Do đó 3|y, hay A = {2x,3x,3y,3z}. Do A là tập thô nên B = {x, y, z} cũng là tập thô, suy ra

maxA≥3 max{x, y, z} ≥3.15 = 45>44.

Suy ra bài toán đúng vớin = 4.

Giả sử bài toán đúng đến n−1. Ta chứng minh bài toán đúng đến n.

XétA là tập thô có n phần tử, khi đó có C_n² UCLN của hai phần tử bất kì thuộcA.

Đặt X ={x₁, x₂,· · · , x_k}, k =C_n² là tập các UCLN và x= maxX.

Theo chứng minh tương tự như trường hợp n= 4 ta chỉ xét 2x,3x∈A. Khi đó A={2x,3x,3a₁,3a₂,· · · ,3an−2}

Và tậpY ={x, a₁, a₂,· · · , an−2} là tập thô, nên

maxY ≥4 (n−1)²−(n−1)−1 . Suy ra

maxA≥12 n² −3n+ 1

≥4 n²−n+ 1

∀n≥4.

Vậy bài toán được chứng minh.

Bài 8. Chon (n ≥2) số thực bất kì có tổng bằng 0. Hỏi trongn số đó có ít nhất bao nhiêu cặp có tổng không âm.

Lời giải.

Ta gọi một cặp số thực có tổng không âm là một cặp "đẹp" và f(n) là số cặp đẹp ít nhất trong n số thưc có tổng bằng 0. Ta có các nhận xét sau:

Nhận xét 1. Nếu có n số thực có tổng bằng k > 0thì số cặp đẹp không nhỏ hơn f(n).

Nhận xét 2. Xét n số gồm n−1 số −1 và số n−1, khi đó ta thấy có n−1 cặp đẹp, do đó f(n)≤n−1.

Ta thấyf(2) = 1, f(3) = 1, f(4) = 3, f(5) = 3, f(6) = 5.Ta chứng minhf(n) = n−1, ∀n≥6 bằng cách chứng minh

f(n+ 1)≥f(n) + 1 ∀n≥6 .(1)

Thật vậy, ta xét n+ 1 số thực có tổng bằng 0.

• Nếu trong n+ 1 số có một số bằng0thì ta loại số đó ra, khi đón số còn lại có tổng bằng0 nên số cặp đẹp trong n số này là f(n). Vì trong n số này có ít nhất một số không a không âm nên 0và a tạo thêm một cặp đẹp, dẫn đến (1) đúng.

• Xét n+ 1 số khác 0. Gọi A, B lần lượt là tập các số âm và tập các số dương trong n+ 1 số đã cho. Ta có|A|+|B|=n+ 1. Xét a= minA, a <0, ta loạia thì n số còn lại có tổng dương nên số cặp đẹp trong n số này không nhỏ hơn f(n).

+) Nếu maxB ≥minA thì tồn tạib ∈B đểa+b≥0, khi đó số cặp đẹp sẽ thêm1, nên (1) đúng.

+) Nếu maxB <minA thì |A|<|B| và f(n+ 1) =C_|B|² . Khi đó, nếun+ 1 = 2k+ 1 thì

|B| ≥k+ 1 nên

f(n+ 1)≥C_k+1² = k(k+ 1)

2 ≥2k ≥f(n) + 1 ∀k ≥3 (n ≥6).

Nếu n= 2k thì |B| ≥k+ 1 và chứng minh tương tự như trên.

Bài 9. Cho n ≥ 2 con chim đậu trên đường tròn (O), mỗi điểm có nhiều nhất một con chim đậu. Hai con chim đậu tại điểmP_i, P_j được gọi là trông thấy nhau nếuP^◊_iOP_j ≤120⁰. Tìm theo n số nhỏ nhất các cặp con chim trông thấy nhau.

Lời giải.

Gọi f(n)là số nhỏ nhất các cặp con chim trông thấy nhau.

Ta chứng minhf(n) =

"

(n−1)² 4

# .

Ta có f(2) = 0, f(3) = 1 nên bài toán đúng với n= 2, n= 3.

Giả sửf(n) =

"

(n−1)² 4

#

, n≥2. Ta chứng minh f(n+ 1) = n²

4

.

Theo nguyên tắc cực hạn thì trong n+ 1con chim có một con chim trông thấy nhiều con chim nhất, giả sử đó là con chim đậu ở điểmA (ta gọi tắt làA) và mlà số con chim mà Anhìn thấy . Trên đường tròn lấy hai điểmX, Y sao cho

AOX÷ =XOY^÷ =Y OA^÷ = 120⁰. Vì A trông thấy m con chim nên M con chim này nằm trên cung

_

XAY tính cả hai điểm mút.

Do đó, trên cung nhỏ

_

XY cón+ 1−(m+ 1) =n−m con chim, và mỗi con chim này trông thấy n−m−1 con chim còn lại.

Suy ra số cặp chim trông thấy, trong đó có A làm và do tính chất của A nên ta có m≥n−m−1⇒m≥ n−1

2 ≥hn 2 i

.

Số nhỏ nhất các cặp chim thấy nhau của n con chim còn lại (trừ A) là f(n) và rõ ràng các cặp chim trông thấy nhau này khác với m cặp chim trông thấy nhau ở trên. Do đó, ta có

f(n+ 1) =f(n) +m≥

"

(n−1)² 4

# +hn

2 i

.

Ta chứng minh

"

(n−1)² 4

# +

hn 2 i

= n²

4

. (1)

+) n = 2k thì

V T (1) =

k(k−1) + 1 4

+ [k] =k(k−1) +k=k² = n²

4

=V P(1).

+) n = 2k+ 1 thì

V T (1) =k²+

k+ 1 2

=k²+k = n²

4

=V P(1).

Do đó, ta chứng minh được f(n)≥

"

(n−1)² 4

#

. Ta chỉ ra trường hợp có dấu “=”.

Trên đường tròn lấy hai điểmX, Y sao cho cung sđXY^_ = 30⁰. Chohn 2 i

con chim đậu trên cung nhỏ

_

XY vàn−hn 2 i

=

n+ 1 2

con chim còn lại đầu trên cung nhỏ

_

X⁰Y⁰ đối xứng với cung

_

XY

qua tâm O. Khi đó, các con chim nằm trên hai cung

_

XY và

_

X⁰Y⁰ trông thấy nhau , đồng thời hai con chim bất kì nằm trên hai cung XY^_ và

_

X⁰Y⁰ đều không trông thấy nhau. Do đó, số cặp chim trông thấy nhau là

hn 2

i hn 2 i

−1

2 +

n+ 1 2

n+ 1 2

−1

2 =

"

(n−1)² 4

# .

§2. Nguyên lí Dirichlet

I. Sử dụng nguyên lí Dirichlet

Nguyên lí Dirichle (hay là nguyên lí chuồng thỏ) được phát biểu hết sức đơn giản nhưng lại có nhiều ứng dụng trong toán học và đặc biệt nguyên lí Dirichle là một công cụ mạnh để chứng minh bài toán tồn tại. Sau đây, chúng ta đi xét một số ứng dụng của nguyên lí Dirichle cho bài toán tồn tại.

II. Nguyên lí Dirichlet

1. Nguyên lí Dirichlet

Nếu nhốtn+ 1 con thỏ vào n chuồng thì có một chuồng chứa ít nhất 2 con thỏ.

2. Nguyên lí Dirichle mở rộng

Nếu nhốtn con thỏ vào m chuồng (m≤n) thì có một chuồng chứa ít nhất

n+m−1 m

con.

3. Nguyên lí Dirichle cho tập hợp

Cho S là tập hợp hữu hạn. S₁, S₂, . . . , S_m là các tập con của S sao cho

m

P

i=1

|S_i|> k.|S|. Khi đó tồn tại một phần tửx∈S sao cho x chứa ít nhất trong k+ 1 tập của họ{S₁, S₂, . . . , S_m}.

4. Nguyên lí Dirichle trong hình học

Cho một hình phẳng (H) và (H_i), i= 1, n là các hình phẳng nằm trong (H). Kí hiệu S, S_i là diện tích của các hình phẳng (H) và (H_i). Khi đó, nếu S <

n

P

i=1

S_i thì tồn tại hai hình phẳng (H_i), (H_j) có giao khác rỗng với i, j ∈ {1,2, . . . , n}.

Để sử dụng nguyên lí Dirichle, ta cần tạo ra số chuồng và số thỏ.

III. Ví dụ

Ví dụ 1. Chứng minh rằng trongn+ 1số bất kì thuộc tập hợp{1,2,3, . . . ,2n}luôn chọn được hai số mà số này là bội của số kia.

Lời giải.

Viếtn+ 1 số đã cho dưới dạng:

a₁ = 2^k1b₁, a₂ = 2^k2b₂, . . . , a_n+1 = 2^kn+1b_n+1.

Trong đób₁, b₂, . . . , b_n+1 là các số lẻ. Ta có: 1≤b₁, b₂, . . . , b_n+1 ≤2n−1. Mặt khác trong khoảng từ1 đến 2n−1 có đúng n số lẻ nên tồn tại hai số m < n sao cho b_n=b_m. Khi đó, trong hai số a_n và a_m có một số là bội của số kia.

Ví dụ 2. Chọn bất kì n+ 1 số trong 2n số tự nhiên từ 1 đến 2n (n ≥ 2). Chứng minh rằng trong các số được chọn có ít nhất1số bằng tổng của2số được chọn (kể cả các trường hợp 2 số hạng của tổng bằng nhau ).

Lời giải.

Giả sử a₁ < a₂ < . . . < a_n< a_n+1 làn+ 1 số được chọn.

Xétn số:a_n+1−a₁ =b₁,a_n+1−a₂ =b₂,. . ., a_n+1−a_n=b_n.

Trong tập 2n+ 1 số đó là a1, a2, . . . , an+1, b1, b2, . . . , bn tồn tại 2 số bằng nhau, hai số ấy không thể cùng thuộc dãy a₁, a₂, . . . , a_n+1 cũng không thể cùng thuộc dãy b₁, b₂, . . . , b_n . Ta có:

a_n+1−a₁ =a_i, suy ra a_n+1 =a₁+a_i.

Ví dụ 3. Trong mặt phẳng cho 2n+ 1 điểm sao cho với 3 điểm bất kì luôn có 2 điểm mà khoảng cách giữa chúng nhỏ hơn 1. Chứng minh rằng tồn tại một đường tròn có bán kính bằng 1 chứa ít nhất n+ 1 điểm trong 2n+ 1 điểm đã cho.

Lời giải.

Xét A là một trong 2n+ 1 điểm. Xét đường tròn (S) = (A,1).

Nếu(S) chứa2n điểm còn lại thì ta có điều phải chứng minh.

NếuB /∈(S), ta xét đường tròn (S⁰) = (B,1).

Khi đó với điểmC bất kì khác A và B, ta có:

"

AC <1 BC <1 ⇒

"

C ∈(S) C ∈(S⁰).

Do đó trong 2n−1 điểm còn lại ( khác A và B) hoặc thuộc (S) hoặc thuộc (S⁰) nên trong hai đường tròn đó chứa ít nhất n điểm. Hay đường tròn đó chứa ít nhất n+ 1 điểm trong 2n+ 1 điểm đã cho.

Ví dụ 4. Cho đa giác lồi2018cạnh có các tọa độ nguyên. Chứng minh rằng trong đa giác có ít nhất 403 điểm có tọa độ nguyên.

Lời giải.

Xét 5 đỉnh liên tiếp của đa giác A, B, C, D, E. Vì

(A+B) + (B+C) + (C+D) + (D+E) + (E+A) = 2(A+B+C+D+E) = 6·180^◦. Suy ra trong 5 đỉnh A, B, C, D, E luôn tồn tại hai đỉnh chung cạnh và tổng của hai góc đó lớn hơn180^◦. Giả sử hai góc đó làA+B >180^◦. Mặt khác:

A+B+C₁+D₁ = 360^◦ ⇒

"

A+E₁ >180^◦ B+C₁ >180^◦ .

Giả sử B+C₁ >180^◦. Dựng hình bình hành ABCF, suy ra F nằm trong tứ giác ABCE. VìABCF là hình bình hành vàA, B, C có tọa độ nguyên nên dẫn tớiF cũng có tọa độ nguyên.

Từ đó ta có đpcm.

Ví dụ 5. Trên bàn cờ 10×10người ta viết các số từ 1đến 100. Mỗi hàng chọn ra số lớn thứ ba. Chứng minh rằng tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các chữ số lớn thứ ba được chọn.

Lời giải.

Kí hiệu các số lớn thứ ba là a₉ < a₈ < . . . < a₀. Khi đó số phần tử lớn hơn a₀ nhiều nhất là 20 (nhiều nhất là 2 phần tử ở mỗi hàng). Suy raa0 ≥80 (1).

Tương tự a₁ ≥78(2).

Mặt khác a₈ ≥a₉+ 1, a₇ ≥a₉+ 1, . . . , a₂ ≥a₉+ 7. Kết hợp với (1) và (2) suy ra:

a0+a1+. . .+a9 ≥80 + 78 + (a9+ 1) +. . .+ (a9+ 7) = 8a9+ 180.

Xét hàng chứa a₉. Tổng các số của dòng chứaa₉ là

S(a₉)≤100 + 99 +a₉+a₉−1 +. . .+a₉−7

= 8a₉+ 171<8a₉+ 180≤a₀ +a₁ +. . .+a₉ (đpcm).

Ví dụ 6. Trong một cuộc thi Toán có 65 học sinh tham gia đến từ hai trường. Mỗi học sinh thi một trong 4 môn Toán, Lí, Hoá, Anh Văn. Biết rằng trong 5 học sinh thi cùng một môn thì có hai học sinh cùng tuổi. Chứng minh rằng trong 65 học sinh có ít nhất 3 học sinh đến từ một trường, thi cùng một môn và bằng tuổi nhau.

Lời giải.

Giả sử không có3 học sinh nào thoả yêu cầu bài toán.

Vì có 65 học sinh đến từ hai trường nên có ít nhất 33 học sinh đến từ một trường. Xét33 học này thì có ít nhất9 học sinh thi cùng một môn.

Ta xét9 học sinh này:

Lấy5học sinh bất kì trong 9 học sinh trên. Khi đó sẽ có hai học sinh cùng tuổi, ta giả sử đó là hai học sinhA₁, B₁. Ta loại hai học sinh này còn lại7 trong học sinh và trong7học sinh nay ta tìm được hai học sinh cùng tuổi A2, B2. Sau khi loại hai học sinh này ta còn lại 5 học sinh và tiếp tục chọn được 2học sinh A₃, B₃.

Xét3 học sinh A₁, A₂, A₃ ta có tuổi của ba học sinh này đôi một khác nhau.

Xét 5 học sinh gồm ba học sinh A1, A2, A3 với 2 trong ba học sinh còn lại, khi đó hai học sinh còn lại ta kí hiệu A₄, B₄ cùng tuổi nhau.

Xét5học sinh gồm 4học sinhA₁, A₂, A₃, A₄ và học sinh còn lại (ta kí hiệu là A₅). Khi đóA₅ sẽ cùng tuổi với 1 trong 4 học sinh A1, A2, A3, A4. Chẳng hạn A5, A1 cùng tuổi. Khi đóA1, B1, A5

thoả yêu cầu bài toán . Điều này mâu thuẫn với điều giả sử ở trên.

Vậy bài toán được chứng minh.

Ví dụ 7. Mỗi đỉnh của một cửu giác đều (đa giác đều9cạnh) được tô một trong hai màu xanh hoặc đỏ. Chứng minh rằng tồn tại hai tam giác có đỉnh là đỉnh của cửu giác, đồng dạng với nhau và các đỉnh được tô cùng một màu.

Lời giải.

A₃

A₄ A₈

A₉ A₇ A₆

A₅

A₁ A₂

O

Chúng ta gọi một tam giác đỏ (xanh) nếu tất cả các đỉnh của tam giác được tô màu đỏ (xanh).

Vì 9 đỉnh của cửu giác được tô bởi hai màu nên theo nguyên lí Drichle, có ít nhất 5 đỉnh được

tô một màu. Ta giả sử 5 đỉnh được tô màu đỏ. Suy ra có ít nhấtC₅³ = 10 tam giác đỏ, kí hiệu T là tập gồm 10 tam giác đỏ này. Ta chứng minh trong 10 tam giác đỏ này, có hai tam giác đồng dạng với nhau.

Đặt cửu giác đó là A₁A₂...A₉ và đường tròn (O) là đường tròn ngoại tiếp cửu giác. Khi đó cửu giác sẽ chia đường trong (O) thàng 9 cung nhỏ bằng nhau. Ta gọi mỗi cung nhỏ là một “lá”.

Xét tam giác A_iA_jA_k với A_iA_j ≤A_jA_k≤A_kA_i. Gọi a_ij là số “lá” nằm trên cung

_

A_iA_j không chứaA_k;a_jk, a_ki được định nghĩa tương tự. Ta thấy mỗi tam giác A_iA_jA_k tương ứng với một bộ (a_ij, a_jk, a_ki) thỏa 1≤a_ij ≤a_jk ≤a_ki ≤7 và a_ij +a_jk +a_ki = 9. Ví dụ tam giác A₃A₅A₉ tương ứng với bộ(2; 3; 4). ChiaT thành các tập con T_i mà mỗi tập conT_i chứa các tam giác đồng dạng thuộc T. Như vậy mỗi T_i tương ứng với một bộ nghiệm của phương trình

(a+b+c= 9 1≤a≤b≤c≤7 (*) và ngược lại. Phương trình (*) có 7 bộ nghiệm:(1; 1; 7), (1; 2; 6), (1; 3; 5), (1; 4; 4), (2; 2; 5), (2; 3; 4), (3; 3; 3) Do đó ta có 7 tập Ti, mà trong T có 10 tam giác nên theo nguyên lí Dirchle, trong các tập T_i có ít nhất một tập chứa ít nhất hai tam giác. Bài toán được giải quyết.

IV. Bài tập

Bài 1. Trong hình vuông có cạnh bằng 1đặt 51điểm bất kì phân biệt. Chứng minh rằng có ít nhất ba trong số51 điểm đó nằm trong một hình tròn bán kính 1

7.

Bài 2. Trên tờ giấy kẻ caro lấy101 ô vuông bất kì. Chứng minh rằng trong 101 ô vuông đó có 26ô vuông không chung cạnh hoặc chung đỉnh.

Lời giải.

Tô màu xen kẽ các ô bởi4màu. Hàng thứ nhất tô Xanh, Đỏ xen kẽ, hàng thứ hai tô Trắng, Đen xen kẽ. Khi đó có một màu tô ít nhất 26ô.

Bài 3. Xét100 số nguyên dươnga₁, a₂, . . . , a₁₀₀; a_i ≤100 với i= 1, 2, . . . ,100 và a₁+a₂+. . .+a₁₀₀ = 200.

Chứng minh rằng trong 100 số đó luôn tồn tại một vài số có tổng bằng 100.

Lời giải.

• Nếua_i =a_j với mọii, j thì ta có điều phải chứng minh.

• Nếu tồn tại hai số khác nhau, chẳng hạn a₁ 6= a₂. Xét các số a₁, a₂, a₁ +a₂, a₁ +a₂ + a₃, . . . , a₁+a₂+. . .+a₉₉.

Nếu trong các số trên, có một số chia hết cho100 thì ta có đpcm.

Nếu trong các số trên, không có số nào chia hết cho 100 thì trong các số trên có hai số có cùng số dư khi chia cho 100. Hiệu hai số đó là tổng cần tìm.

Bài 4. Cho 69 số nguyên dương phân biệt không vượt quá 100. Chứng minh rằng có thể chọn được4 sốa, b, c, d sao cho a < b < c và a+b+c=d.

Lời giải.

Giả sử các số là 1≤a₁ < a₂ < . . . < a₆₉≤100. Khi đó a₁ ≤32. Xét hai dãy sau:

1< a₁+a₃ < a₁ +a₄ < ... < a₁+a₆₉ ≤132 (1) 1< a₃−a₂ < a₄−a₂ < ... < a₆₉−a₂ ≤132 (2).

(1) và (2) có 134 số hạng trong đoạn[1; 132] suy ra có 2 số bằng nhau thuộc về hai dãy . Ta có đpcm.

Bài 5. Xét tập hợp S ={(x;y)|x, y ∈Z, 0≤x, y ≤3}. Chọn ra 9 phần tử thuộc S. Chứng minh rằng trong 9 phần tử được chọn, tìm được4 phần tử (x₁;y₁), (x₂;y₂), (x₃;y₃), (x₄;y₄) sao cho x1+x2+x3+x4 chia hết cho 4 và y1+y2+y3+y4 chia hết cho 4.

Lời giải.

Ta chia các phần tử củaSvào 4 nhóm theo tính chẵn lẻ của các tọa độ:(C; C), (C; L), (L; C) và(L, L). Giả sử trong một nhóm có k phần tử là (x1, y1), ..., (xk, yk) thì ta lập các phần tử mới là

x₁+x₂

2 ,y₁+y₂ 2

, ...,

x₁+x_k

2 ,y₁+y_k 2

. Ta được k−1 phần tử khác nhau thuộc S.

Từ 4 nhóm ta sẽ có được 9−4 = 5 phần tử. Trong 5 phần tử này, có 2 phần tử có tọa độ có cùng tính chẵn lẻ. Từ đẳng thức

x₁+x₂+x₃+x₄

4 =

x₁+x₂

2 +x₃+x₄ 2 2 ta suy ra điều phải chứng minh.

Bài 6. Cho tập S = {1,2,3, . . . ,99} và A là một tập con bất kì của S mà |A|= 835. Chứng minh rằng luôn tồn tại4 phần tử a, b, c, d thuộcA sao cho: a+ 2b+ 3c=d.

Lời giải.

ĐặtA ={a₁, a₂, . . . , a₈₃₅} với a₁ < a₂ < . . . < a₈₃₅. Xét hiệu

d=a₈₃₅−3a₁ = 3(a₈₃₅−a₁)−2a₈₃₅ ≥3·834−2·999 = 504.

Do đó 166 cặp số sau là phân biệt (d−2; 1), (d−4; 2), . . . , (d−2.165; 165), (d−2.166; 166).

Vì có 164 phần tử S không thuộc tập A, nên trong các cặp trên tồn tại ít nhất một cặp (x;y) với y6=a₁ mà x, y ∈A, giả sử cặp đó là (d−2k;k) với k∈ {1,2, . . . ,166} . Khi đó ta có ngay:

x+ 2y+ 3a₁ =a₈₃₅, suy ra đpcm.

Bài 7. Trong mặt phẳng Oxy, cho 19 điểm có toạ độ nguyên, trong đó không có 3 điểm nào thẳng hàng. Chứng minh rằng có ít nhất 3 điểm trong 19 điểm đã cho tạo thành một tam giác có trọng tâm là các điểm có toạ độ là số nguyên.

Bài 8. Cho ngũ giác lồi ABCDE có độ dài mỗi cạnh và độ dài các đường chéo không vượt quá

√3 . Lấy 2011 điểm phân biệt tùy ý nằm trong ngũ giác đó. Chứng minh rằng tồn tại một hình tròn đơn vị có tâm nằm trên cạnh của ngũ giác đã cho chứa ít nhất403 điểm trong số các điểm đã lấy.

§3. Nguyên lí cực hạn

Một tập hợp hữu hạn các số thực luôn có phần tử lớn nhất và phần tử nhỏ nhất. Một tập con bất kỳ của N luôn có phần tử nhỏ nhất. Nguyên lý đơn giản này trong nhiều trường hợp rất có ích cho việc chứng minh. Hãy xét trường hợp biên! Đó là khẩu quyết của nguyên lý này.

I. Ví dụ

Ví dụ 1. Có 3 nhóm học sinh, mỗi nhóm có 100 em. Biết mỗi học sinh ở nhóm này quen với ít nhất 101 em học sinh ở hai nhóm còn lại. Chứng minh rằng ta có thể chọn ra mỗi nhóm một học sinh sao cho ba học sinh đó đôi một quan nhau.

Lời giải.

Gọi A là học sinh có nhiều bạn nhất ở một trường khác. Gọi số bạn nhiều nhất này làk. Giả sử A ở trường thứ nhất và tập những bạn quen A làM ={B₁, B₂, . . . , B_k} ở trường thứ 2. Cũng theo giả thiết, có ít nhất 1 học sinh C ở trường thứ 3 quen với A. Vì C quen không quá k học sinh ở trường thứ nhất nên theo giả thiếtC quen với ít nhất n+ 1−k học sinh của trường thứ hai, đặt N = {D₁, D₂, . . . , D_m} là những người quen C ở trường thứ hai thì m ≥ n+ 1−k.

Vì M, N đều thuộc tập hợp gồm n học sinh và |M|+|N| ≥ k+n+ 1−k =n+ 1 nên ta có M ∪N 6=∅. Chọn B nào đó thuộc M ∪N thì ta có A, B, C đôi một quen nhau.

Ví dụ 2. Chứng minh rằng không tồn tại n > 1lẻ để 15ⁿ+ 1 chia hết cho n.

Lời giải.

Giả sử tồn tại một số nguyên lẻn >1 sao cho15ⁿ+ 1 chia hết cho n. Gọi plà ước số nguyên tố nhỏ nhất của n, khi đó plẻ. Giả sử k là số nguyên dương nhỏ nhất sao cho 15^k−1 chia hết cho p(số k được gọi là bậc của 15theo modulo p).

Vì15²ⁿ−1 = (15ⁿ−1)(15ⁿ+ 1)chia hết chop. Mặt khác, theo định lý nhỏ Fermat thì15^p−1−1 chia hết cho p. Theo định nghĩa của k, suy ra k là ước số của các số p− 1 và 2n. Suy ra k|(p−1,2n). Do plà ước số nguyên tố nhỏ nhất củan nên(n, p−1) = 1. Suy ra(p−1,2n) = 2.

Vậy k| 2. Từ đó k = 1 hoặc k = 2. Cả hai trường hợp này đều dẫn tới p = 7. Nhưng điều này mâu thuẫn vì 15ⁿ+ 1 luôn đồng dư 2mod 7.

Ví dụ 3. Cho hai số nguyên dương a, b nguyên tố cùng nhau. Chứng minh rằng tồn tại hai số nguyên x, y sao cho ax+by = 1.

Lời giải.

ĐặtA ={ax+by >0|x, y ∈Z}. Vìa= 1.a+ 0.b, b = 0.a+ 1.b nên a, b∈A, do đó A6=∅. Suy ra trong tập A luôn tồn tại phần tử nhỏ nhất. Gọi d là phần tử nhỏ nhất của tập A, ta chứng minh d= 1. Đặt a=dq+r, 0≤r < d. Vìd∈A và d≤a nên q >0tồn tại x, y ∈Z sao cho

d=xa+yb.

Suy ra

qd=axq+byq ⇔a−r=axq+byq ⇔r= (1−xq)a−yqb=x⁰a+y⁰b,

với x⁰, y⁰ ∈ Z. Do tính nhỏ nhất củad nên ta có r= 0 hay a...d. Chứng minh tương tự, ta cũng cób...d. Mà(a, b) = 1 nên ta có d= 1. Bài toán được chứng minh.

Ví dụ 4. Trong mặt phẳng cho 2015 đường thẳng phân biệt sao cho ba đường thẳng bất kì luôn đồng quy tại một điểm. Chứng minh rằng 2015đường thẳng trên cùng đi qua một điểm.

Lời giải.

Giả sử2015đường thẳng đã cho không đồng quy tại một điểm. Xét tất cả các khoảng cách khác0từ các giao điểm của2015đường thẳng đã cho đến các đường thẳng đó. Vì các khoảng cách này là hữu hạn nên tồn tại một khoảng cáchhnhỏ nhất. Giả sử h=d(A,∆) =AH vớiAlà một trong các giao điểm, ∆ là một trong 2015 đường thẳng đã cho vàH là chân đường vuông góc hạ từ A xuống ∆.

A K

E

B H C D

Vì qua Acó ít nhất ba đường thẳng đi qua. Giả sử ba đường thẳng đó lần lượt cắt đường thẳng

∆tại các điểmB, C, D. Trong ba điểm B, C, D có ít nhất 2điểm nằm cùng phía so với điểmH, ta giả sử đó là C, D và HC < HD. Gọi E, K là hình chiếu vuông góc của C và H lên đường thẳngAD. Ta có CE < HK < AH , suy ra vô lí vì AH là khoảng cách nhỏ nhất. Vậy bài toán được chứng.

II. Bài tập

Bài 1. Cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh rằng ta có thể nối2n điểm này bằngn đoạn thẳng có đầu mút khác màu sao cho chúng đôi một không giao nhau.

Bài 2. Trên mặt phẳng cho 2×2011 điểm, trong đó không có bất kỳ 3 điểm nào thẳng hàng.

Người ta tô2011 điểm bẳng màu đỏ và tô2011 điểm còn lại bằng màu xanh. Chứng minh rằng:

bao giờ cũng tồn tại một cách nối tất cả các điểm màu đỏ với tất cả các điểm màu xanh bởi2011 đoạn thẳng không có điểm nào chung.

Lời giải.

Ta nhận thấy rằng luôn tồn tại cách nối2011 cặp điểm với nhau bằng2011 đoạn thẳng và vì có 2011 cặp điểm nên số cách nối là hữu hạn và nếu dùng tổ hợp thì ta có thể tính được con số chính xác các cách nối. Và hiển nhiên là trong hữu hạn cách nối đó ta luôn tìm ra được một cách nối có tổng độ dài các đoạn thẳng là ngắn nhất. Ta chứng minh cách nối đó là cách mà chúng ta cần tìm.

Thật vậy: Giả sử ngược lại ta có hai đoạn thẳngAX và BY mà cắt nhau tại điểm O ( giả sử A vàB tô màu đỏ, cònX và Y tô màu xanh).

Khi đó, nếu ta thay đoạn thẳng AX và BY bằng hai đoạn AY và BX, các đoạn còn lại giữ nguyên thì ta có cách nối này có tính chất:

AY +BX <(AO+OY) + (BO+OX)

= (AO+OX) + (BO+OY)

⇒AY +BX < AX+BY.

Như vậy, việc thay hai đoạn thẳng AX và BY bằng hai đoạn thẳng AY và BX , ta nhận được một cách nối mới có tổng độ dài đoạn thẳng là nhỏ hơn. Vô lý, vì trái với giả thiết là đã chọn cahcs nối có tổng các độ dài là bé nhất.

Điều vô lí đó chứng tỏ cách nối có tổng độ dài các đoạn thẳng là ngắn nhất là không có điểm chung.

Bài 3. Một nước có 80sân bay, mà khoảng cách giữa hai sân bay nào cũng khác nhau. Mỗi máy bay cất cánh từ một sân bay và bay đến sân bay nào gần nhất. Chứng minh rằng: trên bất kỳ sân bay nào cũng không thể có quá 5máy bay đến.

Lời giải.

Từ giả thiết suy ra nếu các máy bay tư các sân bay M và N đến sân bay O thì khoảng cách M N là lớn nhất trong các cạnh của tam giác M ON, do đóM ON >^◊ 60^◦.

Giả sử rằng các máy bay bay từ các sân bay M1, M2, M3, M4, . . . ,Mn đến sân bay O thì một

trong các góc M^Ÿ_iOM_j không lớn hơn 360^◦

n (i, j, n = 1,2,3,4,5, . . . ,80 ) vì tổng các góc đã cho bằng 360^◦.

Do đó, ta có 360^◦

n >60^◦ ⇒n <6. Suy ra điều phải chứng minh.

Bài 4. Chứng minh rằng: Bốn hình tròn có đường kính là bốn cạnh của một tự giác lồi thì phủ kín miền tứ giác ABCD.

Lời giải.

LấyM là một điểm tùy ý của tứ giác lồiABCD. Có hai khả năng xảy ra:

•Nếu M nằm trên biên của đa giác (tứcM nằm trên một cạnh của tứ giác ABCD). Khi đó M nằm trong hình tròn có đường kính là cạnh ấy. Trong trường hợp này kết luận của bài toán hiển nhiên đúng.

•NếuM nằm bên trong tứ giác lồiABCD. Khi đó ta cóAM B^◊+BM C^◊+CM D^◊ +DM A^◊ = 360^◦. Theo nguyên lí cực hạn, tồn tại

max{AM B,^◊ BM C,^◊ CM D,^◊ DM A}^◊ =BM C.^◊

Khi đó : BM C^◊ ≥90^◦. (1)

Từ (1) suy ra M nằm trong ( hoặc cùng lắm là nằm trên) đường tròn đường kính BC. Vậy dĩ nhiên M bị phủ bởi đường tròn này.

Như thế do M là điểm tùy ý của tứ giác ABCD, ta suy ra bốn hình tròn nói trên phủ kín tứ giác lồi đã cho.

Bài 5. Có 3 nhóm học sinh, mỗi nhóm có n(n ≥2) học sinh. Biết rằng mỗi học sinh quen với n+ 1 học sinh ở hai nhóm còn lại. Chứng minh rằng từ mỗi nhóm ta có thể chọn ra một học sinh sao cho ba học sinh được chọn đôi một quen nhau.

Lời giải.

Trong các học sinh ta gọi A là học sinh mà có số người quen nhiều nhất với các học sinh trong một nhóm khác.Giả sử A ở nhóm 1 và quen với k (k ≤ n) học sinh B₁, B₂, . . . , B_k ở nhóm 2.

Khi đó A sẽ quen với ít nhất một học sinh ở nhóm thứ 3. Ta giả sử A quen với C ở nhóm thứ 3. Vì C quen với không quá k học sinh ở nhóm thứ nhất nên C sẽ quen với ít nhất n+ 1−k học sinh ở nhóm thứ hai. Giả sử C quen với m học sinh B₁⁰, B₂⁰, . . . , B⁰_m ở nhóm thứ 2 với m ≥ n+ 1−k. Nếu hai tập {B₁, B₂, . . . , B_k} và

B₁⁰, B₂⁰, . . . , B_m⁰ không có phần tử chung thì ta có m+k ≤n điều này vô lí vìm+k ≥n+ 1> n. Vậy tồn tại một học sinh B nằm ở hai nhóm trên. Khi đó ba học sinh A, B, C ở ba nhóm và đôi một quen nhau. Bài toán được chứng minh.

§4. Nguyên lí bất biến

Bất biến là đại lượng hay tính chất không thay đổi khi các trạng thái khác thay đổi. Bất biến có nhiều ứng dụng trong toán học, nhất là trong các bài toán chứng minh tồn tại một trạng thái hay tính chất nào đó qua một số lần thực hiện các thuật toán.

I. Ví dụ

Ví dụ 1. Lúc đầu ta ghi lên bảng cặp (1; 2). Từ lần thứ hai trở đi, nếu trên bảng có cặp (a;b) thì ta được phép ghi cặp

√3a−b

2 ;a+√ 3b 2

!

. Chứng minh rằng không tồn tại cặp

√3; 1 +√ 3

được ghi lên bảng?

Lời giải.

ĐặtSn =a²_n+b²_n. Ở bước thứ n+ 1 ta có:

S_n+1 =

√3a_n−b_n 2

!2

+ a_n+√ 3b_n 2

!2

=a²_n+b²_n=S_n.

Do đó, Sn là một đại lượng bất biến.

Mà

S₁ = 56=√ 32

+ 1 +√

32

, nên không thể ghi được cặp √

3; 1 +√ 3

.

Ví dụ 2. Trên bảng ghi hai số 1 và 2. Thực hiện cách ghi số theo quy tắc sau: Nếu trên bảng có hai số a, b thì được ghi thêm số a+b+ab. Hỏi có thể ghi được số 2012 và 2013 lên bảng hay không?

Lời giải.

Ta ghi được các số 1,2,5,11,17, . . ..

Đặtc=a+b+ab⇒c+ 1 = (a+ 1)(b+ 1) nên dãy số thu được công thêm 1 sẽ được các số có dạng2^m3ⁿ. Tuy nhiên 2013 và 2014 không có dạng đó nên ta không thể ghi được các số đó.

Ví dụ 3. Hình tròn được chia thành 2014 hình quạt. Mỗi hình quạt ta đặt một viên bị.

Ta thực hiện chuyển bị như sau: Mỗi lần lấy hai ô, mỗi ô một viên và chuyện qua ô bên cạnh ngược chiều nhau. Hỏi với cách làm như vậy ta có thể chuyển tất cả các viên bi về cũng một ô hay không?

Lời giải.

Tô màu các hình quạt bởi hai màu đen và trắng sao cho hai hình quạt kề nhau thì khác màu.

Khi đó mỗi lần chuyển thì số viên bi trong các ô màu đen hoặc không đổi hoặc tăng 2 hoặc giảm 2. Hay nói cách khác số viên bi trong ô đen luôn cùng tính chẵn lẻ với số bi ban đầu ở trong ô đen. Mà lúc đầu có 1007 viên bi nằm trong các ô đen nên số bi ở các ô đen không thể là 0 và 2014 được. Do đó không thể thực hiên được yêu cầu của bài toán.

Ví dụ 4. (IMO Shorlist C1, 2012) Một số số nguyên dương được viết trên một hàng.

Lựa chọn hai số kề nhaux, y sao chox > y vàx nằm bên trái của yvà thay cặp (x;y) bởi cặp (y+ 1;x)hoặc(x−1;x). Chứng minh rằng quá trình trên chỉ thực hiện được hữu hạn lần.

Lời giải.

Giả sử ta viết n số nguyên dương a₁, a₂, . . . , a_n và M = max{a₁, a₂, ..., a_n}. Đặt S =a₁+ 2a₂+. . .+na_n.

Mỗi lần đổi ta đổi cặp (a_i;a_i+1) với a_i > a_i+1 thành cặp (c;a_i) với c=a_i+1+ 1 hoặc c=a_i−1.

Mỗi lần thay đổi như vậy thì tổng S thay đổi một lượng

d=ic+ (i+ 1)a_i−(ia_i+ (i+ 1)a_i+1) = (a_i−a_i+1) +i(c−a_i+1)>0

Do đó, sau mỗi lần thay thì tổng S tăng thêm ít nhất1 đơn vị. MàS ≤(1 + 2 +. . .+n)M nên đến một lúc nào đó quá trình trên sẽ dừng lại. Vậy bài toán được chứng minh.

II. Bài tập

Bài 1. Giả sử rằng n là một số lẻ. Đầu tiên ta viết các số từ 1 tới 2n trên một bảng đen. Sau đó ta chọn ra hai số bất kì xoá chúng và thay thế chúng bởi|a−b|. Chứng minh rằng số còn lại cuối cùng là một số lẻ.

Lời giải.

Gọi S là tổng của tất cả các số trên bảng . lúc đầu ta có S = 1 + 2 + 3 +· · ·+ 2n=n(2n+ 1)là một số lẻ vì n là một số lẻ .

Ta cần tìm đại lượng bất biến .

Nhận thấy rằng sau mỗi lần thực hiện thuật toán như trong đầu bàI đã nói thì S sẽ bị mất đi một đại lượng có giá trị bằng 2·min(a;b). Vì thế tính chẵn lẻ của S được giữ nguyên sau mỗi lần thực hiện thuật toán. Trong trường hợp của chúng ta thì S luôn là một số lẻ và vì thế khi trên bảng còn lại một số thì số đó là số lẻ .

Bài 2. Một hình tròn được chia làm6 cung. Viết các số1, 0,1, 0,0, 0nên các cung tròn (theo chiều ngược chiều quay của kim đồng hồ ). Bạn có thể cộng hai số ở cạnh nhau với 1. Có thể xảy ra trường hợp tới một lúc nào đó tất cả các số trên các cung tròn bằng nhau hay không ? Lời giải.

Giả sử rằng sau một lúc nào đó trên hình tròn còn lại các sốa₁,a₂, a₃, a₄,a₅,a₆ theo chiều kim đồng hồ.

Với giả thuyết của bài toán, ta dễ dàng nhận thấy rằng đại lượngL=a₁−a₂+a₃−a₄+a₅−a₆ luôn không đổi (vì hiệu của2 sốa_i và a_i+1 luôn không đổi) và ban đầuL= 2. Vậy Lluôn bằng 2. Trường hợpL= 0 không thể xảy ra.

Vậy dễ dàng nhận thấy các số trên các cung tròn không thể bằng nhau .

Bài 3. Xét dãy1,2,3,4, . . . ,2014. Mỗi lần ta xóa hai số a, bvà viết thêm vào dãy số |a−b|. Sau mỗi bước giảm một số. Hỏi số còn lại cuối cùng có thể là số 10 hay không?

Bài 4. Cho các số 1,2,3, . . . ,2012 được xếp theo một thứ tự nào đó. Mỗi phép biến đổi cho phép đổi thứ tự hai số kề nhau. Chứng minh rằng sau 2013 lần đổi chỗ không thể nhận được hoán vị ban đầu.

Bài 5. Cho bộ ba số nguyên (a;b;c), ta xây dựng bộ mới (|a−b|;|b−c|;|c−a|). Chứng minh rằng sau hữu hạn bước biến đổi ta được bộ gồm 3số 0.

Bài 6. Giả sử n số thực n ≥4 được viết xung quanh một đường tròn. Nếu 4 số kề nhau a, b, c, d thỏa (a−d)(b−c)<0 thì ta đổi vị trí củab và c. Chứng minh rằng các phép biến đổi như trên sẽ kết thúc sau hữu hạn bước.

Bài 7. Cho một bảng1991×1992. Kí hiệu (m, n)là ô vuông nằm ở giao của hàng thứ m và cột thứ n. Tô màu các ô vuông của bảng theo quy tắc sau: lần thứ nhất tô ba ô (r;s),(r+ 1;s+ 1), (r+ 2;s+ 2) với 1≤r≤1989, 1≤s≤1990, từ lần thứ hai trở đi, mỗi lần tô đúng ba ô chưa có màu nằm cạnh nhau trong cùng một hàng hoặc cùng một cột. Hỏi có thể tổ màu được tất cả các ô hay không ?

Bài 8. Với bộ các số thực dương (a;b;c;d)ta thực hiện phép biến đổi T như sau (a;b;c;d)→^T (ab;bc;cd;da).

Tìm bộ(a;b;c;d) ban đâu sao cho sau hữu hạn bước ta thu được bộ (a;b;c;d).

Lời giải.

Đặt P =abcd sau phép biến đổi thứ k ta thu được tích của bộ số P^2k Vì sau hữu hạn bước ta thu được bộ ban đầu nênP = 1 hay abcd= 1 Ta có phép biến đổi

(a;b;c;d)→(ab;bc;cd;da)→ ab²c;bc²d;cd²a;da²b

→ b²c²;c²d²;d²a²;a²b² .

Đặtt_k= max{a_k;b_k;c_k;d_k} là giá trị lớn nhất của bộ tại bước thứ k.

Suy ra t_2k =t²_k =t²₂^k. Vì sau hữu hạn bước ta thi được bộ ban đầu nên t₂ = 1.

Suy ra

1 =ab.bc.cd.da ≤t⁴₂ = 1⇒ab=bc=cd=da= 1⇒a=b =c=d= 1.

Rõ ràng với bộ bạn đầu là(1; 1; 1; 1) thì sau hữu hạn lần ta sẽ thu được bộ đó.