NGUYÊN Lí Cực TRỊ Rời Rạc - 123doc

Chứng minh rằng luôn tồn tại: - Một cách nối tất cả các điểm trắng với các điểm đen bởi n đoạn thẳng sao cho các đoạn thẳng không có điểm chung.. - Một cách nối tất cả các điểm trắng với

NGUYÊN LÍ CỰC TRỊ RỜI RẠC

Ví dụ minh họa

Ví dụ 1: Cho 2n điểm phân biệt trên một đường tròn, trong đó có n điểm trắng và n điểm đen(n ≥ 2) Chứng minh rằng luôn tồn tại:

- Một cách nối tất cả các điểm trắng với các điểm đen bởi n đoạn thẳng sao cho các đoạn thẳng không có điểm chung

- Một cách nối tất cả các điểm trắng với các điểm đen bởi n đoạn thẳng sao cho các đoạn thẳng từng đôi một cắt nhau

Chứng minh:

Gọi S là tập tất cả các cách nối các điểm trắng với các điểm đen bởi n đoạn thẳng Khi đó S hữu hạn và khác rỗng Theo nguyên lí cực trị sẽ tồn tại: Một cách nối N

có tổng độ dài các đoạn thẳng nối nhỏ nhất và một cách nối L có tổng độ dài các đoạn nối lớn nhất Ta sẽ chứng minh với cách nối N, thì các đoạn thẳng không có điểm chung Thật vậy, giả sử trái lại nếu có hai điểm trắng A; B và hai điểm X; Y được nối bởi hai đoạn AX và BY cắt nhau tại I

Khi đó, BI +IX > BX và IY + AI > AY , suy ra BX + AY < BI +IY + AI + IX

=AX + BY Vậy nếu ta thay đoạn BY bởi BX, AX bởi AY cùng với các đoạn còn lại của N ta được một cách nối N khác có tổng các đoạn nối nhỏ hơn tổng các đoạn nối của N (mâu thuẫn!) Vậy N thỏa mãn(i)

Bây giờ ta sẽ chứng minh tiếp rằng với cách nối L, thì các đoạn thẳng nối từng đôi một cắt nhau Thật vậy, giả sử có hai điểm trắng A; B và hai điểm đen X; Y được nối bởi hai đoạn AX và BY không cắt nhau Khi đó nếu ta thay tương ứng hai đoạn

AX và BY bởi AY và BX, thì AY sẽ cắt BX tại một điểm J nào đó.

Vì vậy AY + BX = (AJ + JY) + (BJ + JX) > AX + BY Từ đó ta tạo được một cách nối mới có tổng các đoạn nối lớn hơn tổng các đoạn nối L ( mâu thuẫn!) Do vậy L thỏa mãn (ii)

Ví dụ 2: Có n đội bóng đấu với nhau theo nguyên lí đấu vòng, tức là mỗi đội phải đấu với tất cả các đội còn lai.Biết rằng trong mỗi trận đấu không có hòa Chứng minh rằng luôn có thể sắp xếp thứ tự tên các đội theo cột dọc sao cho đội đứng

trước thắng đội đứng sau.

Chứng minh:

Gọi S là tập tất cả các cách xếp một số đội trong n đội trên theo cột dọc sao cho đội đứng trước thắng đội đứng sau Do S là hữu hạn và khác rỗng nên sẽ tồn tại cách xếp có tên nhiều đội nhất Ta sẽ chứng minh cách xếp này phải có đủ tên n

đội

Thật vậy, giả sử cách xếp chỉ có t < n đội, lần lượt là D1 ,D2 ,··· ,D t Khi đó phải có

sẽ có danh sách khác dài hơn D,D1,D2,··· ,D t Do đó D phải thua D1, nhưng D cũng

không thể thắng D2 vì nếu thế ta sẽ lại có cách xếp dài hơn:D1,D,D2,··· ,D t.Tiếp tục

lập luận như vậy ta có D thua D t , nhưng khi đó ta lại có danh sách dài hơn:D1,D2,···

Ví dụ 3: (Bài toán Sylvester,1814-1897) Trên mặt phẳng cho n − 3 điểm Biết

rằng mỗi đường thẳng đi qua 2 điểm bất kì đều đi qua một điểm thứ ba Chứng minh rằng n điểm đã cho thẳng hàng

Chứng minh:

điểm,luôn tồn tại đường thẳng đi qua hai điểm nào đó trông số các điểm còn lại nhưng không đi qua A

Xét tập tất cả các khoảng cách từ mỗi điểm A đến các đường thẳng đi qua 2 điểm trong số các điểm còn lại nhưng không đi qua A Vì số khoảng cách đó là hữu hạn nên tồn tại một khoảng cách ngắn nhất Gỉa sử khoảng cách ngắn nhất đó

là khoảng cách từ A tới đường thẳng BC Hạ AH ⊥ BC.

Gọi S là tập n điểm đã cho Nếu H ∈ S Ta có AH = d(A,BC) > d(H,AC)(mâu

thuẫn!)

Hình 3:

Do đó H 6∈ S Từ gỉa thiết mỗi đường thẳng qua 2 điểm bất kì trong S đều đi qua

điểm thứ ba thuộc S nên ∃D ∈ S nằm trên BC Gỉa sử C,D nằm cùng phía đối với H

Ta có

d(A,BC) = AH > d(H,AD) > d(C,AD)

(mâu thuẫn!)

Vậy n điểm đã cho thẳng hàng

Ví dụ 4: (Bài toán đối ngẫu của bài toán Sylvester) Trong mặt phẳng cho n đường

thẳng(n ≥ 3), trong đó hai đường thẳng bất kì đều cắt nhau và qua mỗi giao điểm có không ít hơn ba đường thẳng đi qua Chứng minh tất cả các đường thẳng đó đều đi qua 1 điểm

Chứng minh:

Giả sử n đường thẳng đã cho không đồng quy Xét tập tất cả các giao điểm trên

đến các đường thẳng đã cho Gọi S là tập các khoảng cách khác không từ các giao điểm trên đến các đường thẳng đã cho Do S hữu hạn và khác rỗng nên tồn tại

khoảng cách ngắn nhất Giả sử d(A,∆) là bé nhất(A 6∈ ∆) Theo giả thiết sẽ có các

đường thẳng ∆1,∆2,∆3 đi qua A

Hình 4:

Gọi B,C,D là giao điểm của ∆1,∆2,∆3 với ∆ Lại theo giả thiết thì qua C còn có

Vậy n đường thẳng đã cho đồng quy

Ví dụ 5: Trên mặt phẳng cho n − 3 điểm, trong đó không có 3 điểm nào thẳng hàng Chứng minh rằng tồn tại một hình tròn đi qua 3 điểm mà không chứa điểm còn lại nào bên trong

Chứng minh:

Chọn 2 điểm A,B cố định sao cho n − 5 điểm còn lại nằm về một phía đối với AB Với mỗi một điểm D bất kì trong n − 5 điểm còn lại ta xét góc ADB\ Do số các góc này là hữu hạn nên tồn tại diểm M sao cho số đo góc AMB\ là lớn nhất Ta sẽ chứng minh đường tròn đi qua 3 điểm A,M,B là đường tròn cần tìm.

Hình 5:

Thật vậy, giả sử tồn tại điểm D nằm trong đường tròn (AMB) Khi đó ta có

ADB >\ AMB\ (mâu thuẫn).

Vậy luôn tồn tại một hình tròn đi qua 3 điểm mà không chứa điểm còn lại nào bên trong

cho n

Chứng minh:

chia hết cho p, suy ra k ≤ p − 1 < p Ta sẽ chứng minh n Thật vậy, nếu n =

kq + r, với 0 < r < k thì

2n − 1 = (2k)q 2 r − 1 = (mp + 1) q 2 r − 1 = (m0p + 1).2 r − 1; với m,m’

∈ Z

Mà 2n − 1..p = 2 r − 1 .p(mâu thuẫn với việc chọn k)

Do đó n .k, nhưng k < p nên n có ước nguyên tố nhỏ hơn p (mâu thuẫn!).

Ví dụ 7: Chứng minh rằng có vô số số nguyên tố có dạng 6n + 5

Chứng minh:

Gọi A là tập tất cả các số nguyên tố có dạng 6n + 5 Nếu A hữu hạn và vì A khác

rỗng (vì 5 ∈ A) nên tồn tại số lớn nhất p thuộc A Ta xét số r=6p!-1 thì mọi phần

tử của A không là ước của r Mặt khác vì r có dạng 6n+5 nên r phải có ít nhất một

ước nguyên tố dạng 6n+5 Gọi ước nguyên tố đó là m thì m 6∈ A và m>p(mâu

thuẫn!)

Vậy có vô hạn số nguyên tố dạng 6n+5

Ví dụ 8: Có 64 người trong một hội thảo, biết rằng mỗi người đều quen với ít nhất

6 người khác Chứng minh rằng tồn tại 12 người để có thể xếp họ quanh một bàn tròn, sao cho mỗi người đều ngồi giữa 2 người mình quen

Chứng minh:

Nhận xét:Bài toán là không chính xác vì ta có phản ví dụ sau: Chia 64 người

thành 8 nhóm, mỗi nhóm 8 người sao cho trong mỗi nhóm tất cả đều biết nhau Giữa hai nhóm không ai quen ai cả Khi đó không có cách xếp 12 người nào để cho mỗi người đều ngồi giữa 2 người mình quen

Ví dụ 9: Có n điểm trên mặt phẳng sao cho diện tích của tam giác tạo bởi 3 điểm bất kì trong chúng lớn nhất bằng 1 Chứng minh rằng n điểm này nằm trên hoặc trong một tam giác có diện tích lớn nhất bằng 4

Chứng minh:

Vì số điểm đã cho là hữu hạn nên số tam giác tạo thành từ n điểm đã cho là hữu

hạn và khác rỗng Theo nguyên lí cực trị sẽ tồn tại tam giác có diện tích lớn nhất,

ta gọi tam giác đó là 4ABC Qua mỗi đỉnh của 4ABC ta kẻ các đường song song với các cạnh cảu tam giác, khi đó tam giác tạo bởi các giao điểm là 4A0B0C0 sẽ là tam giác cần tìm

Hình 6:

Thật vậy, vì 4ABC có diện tích không lớn hơn 1,mà 4A0B0C0 có diện tích bằng

4 lần diện tích 4ABC nên diện tích của 4A0B0C0 không vượt quá 4

Bây giờ ta sẽ chứng minh không có điểm nào trong n điểm không thuộc miền trong của 4A0B0C0 Phản chứng, giả sử điểm D nằm miền ngoài của 4A0B0C0 Khi

đó tồn tại một đỉnh của 4A0B0C0 nằm khác phía với D

Không mất tính tổng quát có thế giả thiết D,B0 nằm khác phía đối với A0C0 Khi

đó ta có d(D,AC) > d(B,AC) ⇒ S(4DAC) > S(4ABC)(mâu thuẫn!)

TÌM CỰC TRỊ RỜI RẠC

Ví dụ minh họa

Ví dụ 1: Cho m và d là các số nguyên với m ≥ d ≥ 2.Giả sử

x1,x2, ,xd là các biến nguyên dương sao cho x1 + x2 + ··· + xd = m Tìm giá trị nhỏ nhất và lớn nhất của biểu thức:

Chứng minh:

Gọi G là tập tất cả các giá trị của S Ta có G khác rỗng và hữu hạn nên theo

nguyên lí cực trị rời rạc thì luôn tồn tại N là số nhỏ nhất của G và L là số lớn nhất của G

Giả sử (a1,a2, ,a d) làm cho S nhận giá trị N Ta sẽ chứng minh rằng các số

a1,a2, ,a d chỉ hơn kém nhau tối đa là 1.

Thật vậy, giả sử a2 − a1 = a > 1.Khi đó lấy b = a1 − 1;c = a2 + 1,thì a1 + a2 = b + c

dãy a1 ≤ a2 ≤ ··· ≤ a d ta có a1 = a2 = ··· = a d −k = n;a d −k+1 = a d −k+2 = ··· = a d = n+1 Vậy giá trị nhỏ nhất N=(d − k)n2 + k(n + 1)2

Giả sử (b1,b2, ,b d ) làm cho S nhận giá trị lớn nhất L Ta sẽ chứng minh b1 = b2

= ··· = b d−1 = 1;b d = m + 1 − d.

Thât vậy, giả sử tồn tại i < d sao cho b i > 1 Đặt c i = b i − 1;c d = b d + 1, ta có

b2

i +

b2

d Như vậy ta tìm được các số nguyên b1, ,b i−1,c i ,b i+1 , ,b d−1,c d thỏa mãn

b1+···+b i−1+c i +b i+1 +···+c d = m và làm cho giá trị của S lớn hơn L(mâu thuẫn!)

nhất của biểu thức:

.

Ví dụ 2: Cho m > d là một số nguyên dương Giả sử x1,x2, ,xd là các biến nguyên dương sao cho x1x2 xd = m Tìm giá trị lớn nhất của

Chứng minh:

Gọi A là tập tất cả các giá trị của S Ta có A hữu hạn và khác rỗng.

Theo nguyên lí cực trị rời rạc, tồn tại U là số lớn nhất của A Gỉa sử (a1,a2, ,a d)

làm cho S nhận giá trị U Ta sẽ chứng minh rằng các số a1,a2, ,a d có một số là m, còn tất cả các số khác là 1

Không mất tính tổng quát ta giả sử a1 ≥ a2 ≥ ··· ≥ a d Ta chỉ cần chứng minh a1 =

m,a2 = a3 = ··· = a d = 1 Thật vậy, nếu a1 < m thì a2 > 1 Đặt b = a1a2,c = 1, thì ta có

Như vậy ta tìm được các số nguyên

dương b,c,a3, ,a d thỏa mãn bca3 a d = m làm cho giá trị của S lớn hơn U(mâu

thuẫn)

Vậy a1 = m,a2 = = a d = 1 và U=m3 + (d − 1).

Ví dụ 3: Cho m và d là các số nguyên với m ≥ d ≥ 2 Giả sử

x1,x2, ,xd là các biến nguyên dương sao cho x1 +x2 +···+xd = m Tìm giá trị nhỏ nhất và giá trị lớn

d nhất của S = P kxk

k=1

Chứng minh:

Gọi A là tập tất cả các giá trị của S Ta có A hữu hạn và khác rỗng nên theo

nguyên lí cực trị rời rạc luôn tồn tại phần tử lớn nhất L và phần tử nhỏ nhất N của A

• Giả sử (a1,a2, ,a d ) làm cho S nhận giá trị L Ta sẽ chứng minh a1 = a2 = ··· =

a d−1 = 1;a d = m − d + 1.

Thật vậy giả sử a d < m + 1 − d, khi đó phải tồn tại a i > 1,i 6= d Đặt b d = a d

+ 1;b i = a i − 1 thì a1 + ··· + a i−1 + b i + a i+1 + ··· + b d = m và ib i + db d = i(a i −

1) + d(a d + 1) = ia i + da d + d − 1 > ia i + da d

Như vậy ta tìm được các số nguyên dương a1, ,a i−1,b i ,a i+1 , ,b d thỏa mãn a1 +

··· + a i−1 + b i + a i+1 + ··· + b d = m và làm cho giá trị của S lớn hơn L(mâu

thuẫn!)

Vậy a1 = a2 = ··· = a d−1 = 1;a d = m − d + 1 và L=

• Giả sử (b1,b2, ,b d ) làm cho S nhận giá trị N Ta sẽ chứng minh b1 = m + 1

− d;b2 = b3 = ··· = b d = 1

Thật vậy giả sử b1 < m + 1 − d, khi đó phải tồn tại b i > 1,i 6= 1 Đặt c1 = b1

+ 1;c i = b i − 1 thì c1 + b2 + ··· + b i−1 + c i + b i+1 + ··· + b d = m và c1 + ic i = (b1 +

1) + i(b i − 1) = (b1 + ib i ) − (i − 1) < b1 + ib i

Như vậy ta tìm được các số nguyên dương c1,b2, ,b i−1,c i ,b i+1 , ,b d thỏa mãn

c1 + b2 + ··· + b i−1 + c i + b i+1 + ··· + b d = m và làm cho giá trị của S nhỏ hơn

N(mâu thuẫn!)

Vây

Ví dụ 4: Cho a1,a2, ,ad,a,b1,b2, ,bd là các hằng số thưc dương, còn x1,x2, ,xd

d

là các biến không âm sao cho P akxk = a Hãy tìm giá trị nhỏ nhất và lớn nhất của

k=1 d

biểu thức: S = P bkxk

k=1

Chứng minh:

d

giả thiết ta có Do đó

Vậy S đạt giá trị lớn nhất bằng khi và S đạt

giá trị nhỏ nhất bằng

Ví dụ 5: Giả sử x1,x2, ,xd là các biến nguyên dương có tích là d! Tìm giá trị nhỏ

Chứng minh:

Gọi A là tập các giá trị của S Dễ thấy A là khác rỗng và hữu hạn Do vậy theo

nguyên lí cực trị rời rạc thì A luôn có phần tử lớn nhất L Giả sử bộ các số nguyên

a1 ≥ a2 ≥ ··· ≥ a d Ta chỉ cần chứng minh a1 = d!,a i = 1 với i ∈ {2,3, ,d} Thật vậy, giả sử a1 < d! thì a2 > 1, đặt b=1 và c = a1a2 Ta có bca3 a d = d!, hơn nữa

(mâu thuẫn với tính lớn nhất của L)

Vậy L = (d − 1) + (d!)5 khi a1 = d!,a i = 1,∀i = 2,d.

Ví dụ 6: Cho các số dương a1,a2,a3,a4,a5 thỏa mãn các điều kiện:

(i) 2ai là số nguyên dương với i = 1,5

(ii) a1 + a2 + a3 + a4 + a5 = 99

Tìm giá trị lớn nhất của P = a1a2a3a4a5

Chứng minh:

Gọi G là tập tất cả các giá trị của P Dễ thấy G hữu hạn và khác rỗng.

Do đó theo nguyên lí cực trị rời rạc thì luôn tồn tại N là số bé nhất của G Ta sẽ

chứng minh các số x1,x2,x3,x4,x5 hơn kém nhau tối đa là 0.5

Thật vậy, Giả sử chẳng hạn x1−x2 = x > 0.5 KHi đó lấy b = 0,5 và c = x2+0.5 thì 2b,2c là các số nguyên và x1+x2 = b+c và bc = (x1−0.5)(x2+0.5) = x1x2+0.5x−0.25

> x1x2 (do x1 −x2 = x > 0.5) Vậy ta tìm được bộ số (b,c,x3,x4,x5) thỏa mãn (i) và (ii)

và làm cho giá trị của P bé hơn N (Mâu thuẫn!) Vậy các số x1,x2,x3,x4,x5 hơn kém nhau tối đa là 0.5

Bây giờ giả sử x1 ≤ x2 ≤ x3 ≤ x4 ≤ x5 mà do a1+a2+a3+a4+a5 = 99 ta suy ra ngay a1

= a2 = 19.5 và a3 = a4 = a5 = 20.Vậy giá trị lớn nhất cần tìm là:N = 19.52203.

Ví dụ 7: Tèo dùng n≥2n≥2 que diêm để xếp thành các con số như hình bên dưới Hỏi số lớn nhất và nhỏ nhất mà Tèo có thể nhận được là bao nhiêu?

Chứng minh:

Ở bài này, ta chỉ cần dùng một ý tưởng tham lam (greedy paradigm) đơn giản sau:

số càng có nhiều chữ số thì càng lớn và có càng ít chữ số thì càng nhỏ Nhờ đó mà trường hợp số lớn nhất, Tèo có thể dễ dàng thực hiện được như sau:

- Nếu nn chẵn thì xếp n/2n/2 số 1

- Nếu nn lẻ thì xếp 1 số 7 ở đầu tiên và (n−3)/2(n−3)/2 số 1

Rõ ràng cách xếp này cho nhiều chữ số nhất và hiển nhiên số tương ứng sẽ lớn nhất

Tuy nhiên, trường hợp nhỏ nhất lại không đơn giản như vậy Mình đã phải viết đến nn gần 30 mới dự đoán được quy luật Còn lí do tại sao có sự khác nhau này giữa lớn nhất và nhỏ nhất thì dễ thôi, vì đặc điểm của số lượng các que diêm để xếp các số

Gọi f(n)f(n) là số nhỏ nhất thu được Ta thử liệt kê các kết quả xếp được bằng tay như sau:

f(2)=1,f(3)=7,f(4)=4,f(5)=2,f(6)=0,f(7)=8,f(8)=10,f(9)=18,f(10)=22,f(2)=1,f(3)=7,f (4)=4,f(5)=2,f(6)=0,f(7)=8,f(8)=10,f(9)=18,f(10)=22,

f(11)=20,f(12)=28,f(13)=80,f(14)=88,f(15)=108,f(16)=188,f(17)=200,f(11)=20,f(1 2)=28,f(13)=80,f(14)=88,f(15)=108,f(16)=188,f(17)=200,

f(18)=208,f(19)=288,f(20)=688,f(21)=888,f(22)=1088,f(23)=1888,f(24)=2008f(18 )=208,f(19)=288,f(20)=688,f(21)=888,f(22)=1088,f(23)=1888,f(24)=2008

Đến đây ta mới thấy được có một quy luật bắt đầu rõ ràng từ 14 và nó có chu kỳ 7

Việc chứng minh hầu như chỉ mang tính hình thức vì kết quả trên đã quá cụ thể.

Ví dụ 8: Có một con thỏ ăn nn củ cà rốt trong một số ngày theo quy luật sau:

(1) Ngày đầu tiên và ngày cuối cùng, nó phải ăn 1 củ cải

(2) Hai ngày liên tiếp nhau, con thỏ phải ăn số củ cải chênh lệch không quá 1 Hỏi số ngày ít nhất mà con thỏ ăn hết số củ cải là bao nhiêu?

Chứng minh:

Mô tả của bài toán khá rõ ràng và việc xây dựng tương đối đơn giản, thậm chí là trong trường hợp nn khá lớn Gọi f(n)f(n) là số ngày ít nhất cần tìm, ta có dãy sau:

f(1)=1,f(2)=2,f(3)=3,f(4)=3,f(5)=4,f(6)=4,f(7)=5,f(8)=5,f(9)=5,f(10)=6,f(1)=1,f(2)

=2,f(3)=3,f(4)=3,f(5)=4,f(6)=4,f(7)=5,f(8)=5,f(9)=5,f(10)=6,

f(11)=6,f(12)=6,f(13)=7,f(14)=7,f(15)=7,f(16)=7,f(17)=8,f(18)=8f(11)=6,f(12)=6,f (13)=7,f(14)=7,f(15)=7,f(16)=7,f(17)=8,f(18)=8

Quan sát quy luật của dãy số, ta thấy rằng:

- Giá trị của ff thay đổi tại các số có dạng k2+1k2+1

- Trong khoảng từ (k−1)2+1(k−1)2+1 đến k2k2, giá trị của ff thay đổi một lần nữa tại điểm giữa

Từ đó suy ra:

- Với k2−k+1≤n≤k2k2−k+1≤n≤k2 thì giá trị f(n)=2k−1f(n)=2k−1

- Với k2+1≤n≤k2+kk2+1≤n≤k2+k thì giá trị f(n)=2kf(n)=2k

Cách xây dựng thì cũng dễ thấy do ta có thể dựa theo mô hình tam giác Pascal và lựa chọn khi nào cần phải có tam giác đỉnh nhọn, đỉnh bằng phù hợp

Nếu tìm công thức trên một cách tổng quát thì ta có [4n−3−−−−−√][4n−3] Rõ ràng bằng một lập luận thú vị nào đó, ta có thể tìm ra được công thức này nhưng ở đây, mọi việc hoàn toàn có thể làm một cách thủ công và trong thời gian không quá lâu

Rõ ràng công việc này đáng được xem xét và áp dụng!

Ví dụ 9: Cho số nguyên dương nn Xét dãy số nguyên dương hữu hạn (ak)(ak) gồm kk số hạng sao cho với mọi 1≤i<j≤n1≤i<j≤n thì tồn tại tt với 1≤t≤k1≤t≤k sao

cho at=i,at+1=jat=i,at+1=j hoặc at=j,at+1=iat=j,at+1=i Hỏi giá