Bài tập có đáp án chi tiết về cực trị tổ hợp của giáo viên nguyễn tất thu

CỰC TRỊ TỔ HỢP

GV: Nguyễn Tất Thu 1

MỘT SỐ DẠNG TOÁN CỰC TRỊ TỔ HỢP, RỜI

RẠC VÀ ĐỊNH HƯỚNG CÁCH GIẢI

Bài toán cực trị trong tổ hợp và rời rạc thường xuất hiện trong các kì thi

học sinh giỏi và đây thường là bài khó dùng để phân loại học sinh. Các bài

toán này thường không có một thuật giải cụ thể. Lời giải có được chủ yếu

dựa vào năng lực tư duy sáng tạo của học sinh. Nhằm giúp học sinh có

được cơ sở để giải các bài toán về cực trị trong tổ hợp và rời rạc, chúng tôi

hệ thống một số bài toán và một số định hướng cách giải quyết các bài toán

về cực trị trong tổ hợp và rời rạc. Trong bài viết này, chúng tôi đưa ra một

số bài toán thường gặp và định hướng giải các bài toán đó.

Bài toán 1. Tìm số nguyên dương k nhỏ nhất (lớn nhất) sao cho mọi tập A

mà A k = đều có tính chất T nào đó.

Với bài toán này, chúng ta thường xét một tập A có tính chất đặc biệt nào

đó sao cho A m = và A không thỏa tính chất T, từ đó suy ra được

min k m 1 ≥ + . Tiếp theo ta chứng minh mọi tập A mà A m 1 = + đều có

tính chất T, từ đó ta tìm được min k m 1 = + .

Để chứng minh mọi tập A mà A m 1 = + đều có tính chất T thì ta có thể sử

dụng nguyên lí Dirichlet hoặc xây dựng

Ví dụ 1. Gọi A là tập tất cả các số tự nhiên lẻ không chia hết cho 5 và nhỏ hơn 30.

Tìm số k nhỏ nhất sao cho mỗi tập con của A gồm k phần tử đều tồn tại hai số chia

hết cho nhau?

Lời giải.

Ta có: { } A 1,3,7,9,11,13,17,19,21,23,27,29 , A 12 = =

CỰC TRỊ TỔ HỢP

GV: Nguyễn Tất Thu 2

Xét tập { } 0 A 9,11,13,17,19,21,23,29 =

Dễ thấy hai phần tử bất kì thuộc 0 A thì không chia hết cho nhau. Từ đó ta

suy ra được k 9 ≥ .

Ta chứng minh k 9 = thỏa đề bài.

Xét S là một tập con bất kì của A và S 9 = .

Xét ba cặp { } { } { } 21,7 , 27,9 , 1,11 , ta thấy mỗi cặp là bội của nhau.

Nếu trong 3 cặp trên có ít nhất một cặp thuộc S thì bài toán được giải quyết

Giả sử trong ba cặp trên không có cặp nào cùng thuộc S, do S 9 = nên S

phải chữa một số trong mỗi cặp và chứa 6 số còn lại. Từ đó suy ra trong S

phải có cặp { } 3;9 hoặc { } 3;27 và mỗi cặp này là bội của nhau. Hay nói cách

khác trong S luôn tồn tại hai số chia hết cho nhau.

Vậy min k 9 = .

Nhận xét:

Mẫu chốt trong bài toán trên là chúng ta phát hiện ra tập 0 A để từ đó ta

khẳng định được k 9 ≥ và dự đoán min k 9 = . Để tìm tập 0 A , ta liệt kê hết

các số trong A mà không có hai số nào là bội của nhau. Với bài toán này,

việc tìm ra tập 0 A khá đơn giản.

Ví dụ 2. Cho tập A gồm 16 số nguyên dương đầu tiên. Hãy tìm số nguyên dương

k nhỏ nhất có tính chất: Trong mỗi tập con có k phần tử của A đều tồn tại hai số

phân biệt a,b sao cho 2 2 a b + là số nguyên tố (VMO 2004).

Lời giải.

Giả sử k là số nguyên dương sao cho trong mỗi tập con có k phân tử của

tập A đều tồn tại hai số phân biệt a,b sao cho 2 2 a b + là số nguyên tố

CỰC TRỊ TỔ HỢP

GV: Nguyễn Tất Thu 3

Ta xét tập T gồm các số chẵn thuộc tập A. Khi đó T 8 = và với mọi a,b T ∈

ta có 2 2 a b + là hợp số, do đó suy ra k 9 ≥ .

Xét các cặp số sau:

{ } { } { } { } { } { } { } { } = ∪ ∪ ∪ ∪ ∪ ∪ ∪ A 1;4 3;2 5;16 6;15 7;12 8;13 9;10 11;14

Ta thấy tổng bình phương của mỗi cặp trên là một số nguyên tố.

Xét T là một tập con của A và T 9 = , khi đó theo nguyên lí Dirichlet T sẽ

chứa ít nhất một cặp nói trên, hay nói cách khác trong T luôn tồn tại hai số

phân biệt a,b sao cho 2 2 a b + là số nguyên tố.

Vậy min k 9 = .

Chú ý:

1) Vì giả thiết 2 2 a b + là số nguyên tố nên 2 2 a b + không thể là số chẵn hay

a,b phải khác tính chẵn, lẻ. Dựa vào đó ta xây dựng được tập T.

2) Để tìm được sự phân hoạch tập A thành hợp của 8 cặp rời nhau như trên

ta làm như sau:

• Ta liệt kê tất cả các số 1 2 16 a A,a A,...,a A ∈ ∈ ∈ sao cho 2 2 i i a + ( i 1,16 = ) là

số nguyên tố . Từ đó ta có được sự phân hoạch trên, sự phân hoạch trên

không phải là duy nhất.

Ví dụ 3. Cho một đa giác đều 2007 đỉnh . Tìm số nguyên dương k nhỏ nhất thảo

mãn tính chất: Trong mỗi cách chọn k đỉnh của đa giác, luôn tồn tại 4 đỉnh tạo

thành một tứ giác lồi mà 3 trong số 4 cạnh của tứ giác là …