sea_snow_angel
New Member
Download miễn phí Đề tài 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
Vídụ 15. Cho 2006 điểm phânbiệt trong không gian, không cóbốn điểm nào
thẳng hàng. Số kgọi làsốtốtnếu ta có thể điền lênmỗi đoạn thẳngnối hai điểm
trong 2006 điểm đã chomộtsốtự nhiên khôngvượtquá k sao chovớimọi tam giác
cóba đỉnh trong 2006 điểm đa cho thì có haicạnh được điền haisốbằng nhau và
cạnh cònlại thì được điềnsốlớnhơn. Tìmsốtốt có giá trị nhỏ nhất(TST Việt
Nam 2006).
Lời giải.
Tasẽ chứngminhsốtốt nhỏ nhất là 10 .
Trướchết ta định nghĩamộtsố khái niệm như sau:
Một cách điền cácsốtự nhiên khôngvượt quá k lên các đoạn thẳngnối n
điểm trong không gian, không cóbốn điểm nào đồngphẳng, làmột cách
điềntốtnếuvớimọi tam giác có ba đỉnh trong n đỉnh đã cho thì có hai
cạnh được điền haisốbằng nhau vàcạnh cònlại được điềnsốlớnhơn, và
khi đó tagọi k làsố n-tốt.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
t nhất 2007 1 4501
é ù
+ =ê ú
ë û
đỉnh liên tiếp của đa giác. Dĩ nhiên 4 đỉnh này thuộc T và là 4 đỉnh liên tiếp
của đa giác đã cho.
Vậy mink 1506= .
Chú ý:
1) Để chứng minh mink 1506= ta có thể làm theo cách sau
Đặt { } { }1 1 2 3 4 2 5 6 7 8T A ,A ,A ,A , T A ,A ,A ,A= = ….
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 5
{ } { }501 2001 2002 2003 2004 502 2005 2006 2007T A ,A ,A ,A ,T A ,A ,A= =
Nếu có iT T,i 1,501Ì = thì bài toán được chứng minh
Giả sử iT T,i 1,501Ë = , vì T 1006= nên iT T 3, i 1,501Ç = " = và 502T TÌ
Vì 2005 2006 2007A ,A ,A TÎ nên 1 2 3 4 5A T A ,A ,A T A TÏ Þ Î Þ Ï … ta suy
ra được 2001 2002 2003 2004A T A ,A ,A TÏ Þ Î .
Do đó 2002 2003 2004 2005A ,A ,A ,A TÎ . Bài toán được chứng minh.
2) Mẫu chốt bài toán trên là chúng ta đưa ra được nhận xét: Đa giác thỏa
yêu cầu bài toán khi và chỉ khi 4 đỉnh của tứ giác là 4 đỉnh liên tiếp của đa
giác . Từ đó chúng ta xây dựng tập X không thỏa yêu cầu bài toán. Khi xây
dựng tập X ta chú ý, cần xây dựng X sao cho trong X không chứa 4 đỉnh
liên tiếp và X có số phần tử lớn nhất.
Ví dụ 4. Trong một cuộc hội thảo cứ 10 người thì có đúng một người quen chung.
Tìm số người quen lớn nhất của một người.
Lời giải. Từ giả thiết bài toán, ta suy ra được:
Mỗi người có ít nhất một người quen.
Giả sử có k (2 k 10£ £ ) người 1 2 kn ,n ,...,n đôi một quen nhau. Khi đó sẽ có
người thứ k 1+ là k 1n + quen với k người 1 2 kn ,n ,...,n , suy ra
k 1
i i 1(n )
+
= đôi
một quen nhau.
Bằng cách xây dựng như vậy ta có được ít nhất 11 người 11i i 1(n ) = đôi một
quen nhau.
Giả sử có người k 1i i 1n (n )
+
=Ï và n quen với ít nhất 1 trong 11 người
11
i i 1(n ) = ,
ta xét các trường hợp sau:
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 6
TH 1: Số người quen của n không nhỏ hơn 2.
Giả sử n quen với 1 2n ,n trong
11
i i 1(n ) = . Khi đó nhóm gồm 10 người
3 11n,n ,...,n có 2 người quen chung là 1 2n ,n , suy ra vô lý.
TH 2: n quen đúng 1 người trong 11 người 11i i 1(n ) = .
Giả sử n không quen 2 3 11n ,n ,...,n . Khi đó
4 11 1n,n ,...,n ,n có một người quen chung là p và ( )
11
i i 1p n =Ï
Suy ra p có không ít hơn 2 người quen trong 1 2 3 11n ,n ,n ,...,n . Ta đưa về
trường hợp trên và dẫn đến điều vô lí.
Vậy số người quen nhiều nhất của một người là 10 .
Bài toán 2: Tìm số phần tử lớn nhất (nhỏ nhất ) của tập A gồm các phần
tử có tính chất T.
Để giải bài toán này, chúng ta thường thực hiện theo cách sau
Đặt A k= , bằng các lập luận ta chứng minh k m£ ( k m³ ). Sau đó ta xây
dựng một tập A' thỏa tính chất T và A' m= .
Chú ý: Nếu trong một bài toán liên quan đến một phần tử a thuộc giao
1 2 kA A ... AÇ Ç Ç , ta có thể đi đếm bộ 1 k(a,A ,...,A ) bằng hai cách. Từ đó
ta thiết lập được các bất đẳng thức.
Ví dụ 5. Cho A là tập hợp gồm 8 phần tử. Tìm số lớn nhất các tập con gồm 3 phần
tử của A sao cho giao của hai tập bất kì trong các tập con này không phải là tập
gồm hai phần tử.
Lời giải.
Gọi 1 2 nB ,B ,...,B là số tập con của A thỏa :
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 7
i i jB 3, B B 2 (i, j 1,2,...,n)= Ç ¹ =
Giả sử có phần tử a thuộc vào 4 tập trong các tập 1 2 nB ,B ,...,B (chẳng hạn
a thuộc 4 tập 1 2 3 4B ,B ,B ,B ). Khi đó: i jB B 1 i, j 1,2,3,4Ç ³ " =
Mặt khác với i j¹ thì i jB B¹ nên i jB B 3Ç ¹
Suy ra i jB B 1 i, j 1,2,3,4;i jÇ = " = ¹
Do đó: A 1 4.2 9³ + = vô lí.
Như vậy mỗi phần tử thuộc tập A thì sẽ thuộc nhiều nhất ba tập trong số
các tập 1 2 nB ,B ,...,B . Khi đó, suy ra 3n 3.8 n 8£ Þ £ .
Xét { }A 1,2,3,4,5,6,7,8= và các tập
{ } { } { } { }1 2 3 4B 1,2,3 , B 1,4,5 , B 1,6,7 , B 3,4,8= = = =
{ } { } { } { }5 6 7 8B 6,2,8 , B 8,7,5 , B 3,5,6 , B 2,4,7= = = =
Là các tập con gồm ba phần tử của A và i jB B 2Ç ¹ .
Vậy số tập con lớn nhất là 8.
Ví dụ 6. Trong một cuộc thi có 11 thí sinh tham gia giải 9 bài toán. Hai thí sinh
bất kì giải chung với nhau không quá 1 bài. Tìm k lớn nhất để mọi bài toán có ít
nhất k thí sinh giải được.
Lời giải.
Gọi iH là thí sinh thứ i và tập các bài toán là { }1 2 9b ,b ,...,b
Theo đề bài ta có: i jH H 1, i jÇ £ " ¹ . Đặt in là số thí sinh giải được bài ib .
Ta đi đếm bộ i j l(b ,H ,H ) , trong đó i j lb H HÎ Ç .
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 8
Ta có số bộ này chính bằng: i j
i j
H H
<
Çå
Mặt khác: số bộ này lại bằng
i
9 2
n
i 1
C
=
å . Do đó ta có:
i
9 2
i j n
i j i 1
H H C
< =
Ç =å å
Suy ra
9 2 2 2
i i i j 11
i 1 i j
(n n ) 2 H H 2.C 110 9(k k) 110 k 4
= <
- £ Ç £ = Þ - £ Þ £å å
Với k 4= . Giả sử tồn tại in 5³ , suy ra
9 2
i i
i 1
(d d ) 8.12 20 116
=
- ³ + =å vô lí.
Suy ra in 4, i 1,9= " =
2
i j 11
i j
H H 54 C 1
<
Þ Ç = = -å
Do đó, tồn tại (i; j) sao cho i jH HÇ = Æ
Giả sử 1 2H HÇ = Æ và i jH H 1, i j,(i; j) (1;2)Ç = " < ¹
Nếu tồn tại i để iH 3, i 1,2£ " ¹ { } { }i tH H 1, t 1,2,...,11 \ iÞ Ç = " Î
Nên tồn tại một phần tử của iH thuộc ít nhất
10 1 4
3
é ù
+ =ê ú
ë û
tập tH ,t i¹ .
Suy ra tồn tại một phần tử thuộc nhiều hơn 5 tập jH , vô lí.
Suy ra
11
i i 1 2
i 1
H 4 H 36 H H 36
=
³ Þ ³ + + >å vô lí.
Do đó k 3£ . Với k 3= ta chỉ ra như sau:
Quy ước : số 1 là thí sinh giải được bài đó
số 0 là thí sinh không giải được bài đó.
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 9
1b 2b 3b 4b 5b 6b 7b 8b 9b
1H 1 0 0 1 0 0 1 0 0
2H 1 0 0 0 1 0 0 0 1
3H 0 1 1 0 0 1 0 1 0
4H 0 1 0 1 1 0 0 0 0
5H 0 0 0 1 0 0 0 1 1
6H 0 0 1 0 0 0 1 0 1
7H 0 0 0 0 1 1 0 0 0
8H 1 1 0 0 0 0 0 0 0
9H 0 0 1 0 0 0 0 0 0
10H 0 0 0 0 0 1 1 0 0
11H 0 0 0 0 0 0 0 1 0
Ví dụ 7. Trong một kì thi, 8 giám khảo đánh giá từng thí sinh chỉ bằng hai từ
đúng hay sai. Biết rằng với bất kì hai thí sinh nào cũng nhận được kết quả như
sau: có hai giám khảo cùng cho đúng; có hai giám khảo với người thứ nhất cho
đúng và người thứ hai cho sai; có hai giam khảo với người thứ nhất cho sai, người
thứ hai cho đúng; cuối cùng có hai giám khảo cùng cho sai. Hỏi số thí sinh lớn
nhất có thể bằng bao nhiêu?
Lời giải.
Gọi n là số thí sinh. Ta xét hình chữ nhật 8xn gồm 8 hàng và n cột sao cho
ô vuông ở hàng thứ I và cột thứ j cho số 0 (số 1) nếu vị giám khảo thứ i
đánh giá thí sinh thứ j sai (đúng).
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 10
Từ giả thiết đề bài ta suy ra bất cứ hai cột nào của bảng cũng có tính chất:
8 hàng của hai cột này chứa các cặp số 00,01,10,11 va mỗi cặp số xuất hiện
hai lần.
Ta chứng minh, không tồn tại bảng gồm 8 cột có tính chất trên.
Giả sử tồn tại một bẳng như thế.
Do trong một cột bất kí, ta đổi số 0 thành số 1 và ngược lại thì tính chất trên
vẫn được bảo toàn. Vì vậy ta có thể giả sử hàng đầu tiên gồm các số 0. Gọi
ia là số các số 0 nằm ở hàng thứ i . Ta có tổng các số 0 là 8.4 32= , hơn nữa
số lần xuất hiện củacặp 00 là 282.C 56= .
Mặt khác số này cũng bằng
i
8 2
a
i 1
C
=
å
Vì 1a 8= nên ta có
8
i
i 2
a 24
=
=å . Từ đó ta có:
i
8 82 2
i ia
i 2 i 2
1C (a a ) 30
2= =
= - ³å å
Do vậy:
i i
8 82 2 2
8a a
i 1 i 2
56 C C C 58
= =
= = + ³å å vô lí.
Từ đó suy ra số thí sinh nhiều nhất chỉ có thể là 7.
Bảng sau chứng tỏ có thể có 7 thí sinh.
0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 1 1 0 0 1 1
0 0 0 1 1 1 1
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 0 1 0 0 1
1 1 0 1 0 0 1
CỰC TRỊ TỔ HỢP
GV: Nguyễn Tất Thu 11
Ví dụ 8. Cho bảng ô vuông kíc...