Tài liệu bồi dưỡng học sinh giỏi - Chuyên đề 20 - TỔ HỢP VÀ RỜI RẠC - Lê Hoành Phò

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Chuyên đề 20: TỔ HỢP VÀ RỜI RẠC 1. KIẾN THỨC TRỌNG TÂM

N

Tổ hợp và xác suất CX

N Y H

Ư N

G

P ( A) P ( AB )

n

n

TR ẦN

− Nhị thức Newton: ( a + b ) = ∑ Cnk .a n - k .b k k =0

n

A1 ∪ ... ∪ An = ∑ Ai − n -1

3

1≤i < k ≤ n

A1 ∩ ... ∩ An

∑

Ai ∩ Ak ∩ Aj

1≤i < k ≤ n

ẤP

+... + ( −1)

Ai ∩ Ak +

2+

i =1

n

∑

10

n

00

B

− Cho n tập A1 ,..., An là n tập hợp hữu hạn ( n ≥ 2 ) thì số phần tử:

Cho ánh xạ f từ tập hữu hạn X có n phần tử vào tập hữu hạn Y có m phần tử.

C

−

A

Số ánh xạ f từ X và Y là m n .

Í-

H

Ó

Số đơn ánh f từ X vào Y là n(n − 1)( n − 2)...( n − m + 1) với n ≤ m

-L

Số toàn ánh f từ X vào Y là

m

∑ ( −1)

k

n

.Cmk ( m − k ) khi n ≥ m

k =0

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

ẠO

ωA ωB

− Xác suất có điều kiện: P ( A | B ) =

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

TP .Q

n! k !( n − k ) !

− Số tổ hợp n chập k: Cnk = − Xác suất: P ( A) =

n! ( n − k )!

U

− Số chỉnh hợp n chập k: Ank =

H Ơ

− Số hoán vị của tập A có n phần tử: Pn = n !

ÁN

Số song ánh f từ X và Y là n.(n − 1)( n − 2)...2.1 = n ! khi n = m

TO

Nguyên tắc Dirichlê

BỒ

ID Ư

Ỡ N

G

−

Nếu nhốt k + 1 con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa

ít nhất 2 con. Nếu nhốt 2k + 1 con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 3 con.

−

Nếu nhốt nk + 1 con thỏ vào k chuồng (k, n nguyên dương) thì tồn tại một chuồng chứa ít nhất n + 1 con.

Nguyên tắc cực hạn

Trang 1

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Tồn tại độ đo lớn nhất và độ đo nhỏ nhất hay đại lượng lớn nhất và đại lượng nhỏ nhất của tập hữu hạn khác rỗng các độ đo hay các đại lượng.

N

Bất biến và đơn biến

H Ơ

Đại lượng bất biến, tính chất bất biến là những đại lượng hay tính chất không

đó.

ẠO

Đồ thị

Đ

− Bổ đề bắt tay: Cho đồ thị G = (V , E ) thì tổng bậc các đỉnh củạ đồ thị là số chẵn và

G Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

∑ d (V ) = 2card ( E ) v∈V

TR ẦN

H

− Định lý Tocran: Nếu đồ thị G có n đỉnh và số tam giác của G là t ( G ) = 0 thì  n2  số cạnh: c ≤   4

00

B

2. CÁC BÀI TOÁN

10

Bài toán 20 .1 :

2+

3

Tính: A = Cn1 (cos x − sin x) + 0Cn2 + Cn3 3sin x cos x(sin x − cos x) + ... +

ẤP

+ Cnn .n sin x cos x(sin n -2 x − cos n -2 x )

C

Hướng dẫn giải

Ó

A

Xét hàm số y = (1 + cos x) n + (1 + sin x) n thì:

Í-

H

y = (Cn0 + Cn1 cos x + Cn2 cos 2 x + ... + Cnn cos n x) + ( Cn0 + Cn1 sin x + ... + Cnn sin n x )

-L

= 2Cn0 + Cn1 ( sin x + cos x ) + Cn2 ( sin 2 x + cos 2 x ) + ... + Cnn ( sin n x + cos n x )

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

TP .Q

U

chiều, hoặc tăng thêm hoặc giảm đi trong quá trình thực hiện các phép biến đổi nào

Y

Đại lượng đơn biến, tính chất đơn biến là những đại lượng hay tính chất thay đổi một

N

thay đổi trong quá trình thực hiện các phép biến đổi nào đó.

BỒ

ID Ư

Ỡ N

G

TO

ÁN

⇒ y ' = Cn1 (cos x − sin x) + 0.Cn2 + Cn3 3sin x cos x (sin x − cos x) + + ... + Cnn n sin x cos x ( sin n -2 x − cos n -2 x )

Do

đó:

A = y ' = [(1 + cos x) n + (1 + sin x) n ] = n(1 + cos x) n -1.( − sin x) + n(1 + sin x) n -1 cos x = n[cos x (1 + sin x) n -1 − sin x(1 + cos x) n -1 ]

Bài toán 20. 2: Tìm tất cả các cặp số tự nhiên dương n và k thoả: C3nn = (3n) k Hướng dẫn giải

Trang 2

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

⇔

( 3n − 2 )! = ( 3n ) 2n 2 ( n − 1)!( 2n − 1)! ( 3n − 1)

3k -1.2n.n k 3n − 1

N

⇔ C3nn-1-1 =

Y

k -1

TP .Q

U

Vì C3nn-1-1 ∈ Z ∀n ≥ 1 nên 3k -1.2n.n k ⋮ (3n − 1) (1) Mà (3, 3n − 1) = 1, (n, 3n − 1) = 1 nên (1) xả ra ⇔ 2n ⋮ ( 3n − 1)

ẠO

Do đó 2n ≥ 3n − 1 o ⇔ n ≤ 1 ⇔ n = 1

Đ

Thử lại Ck1 = 3k ⇔ k = 1 Tóm lại ( n, k ) = (1,1)

G m

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Bài toán 20. 3: Chứng minh rằng:

Hướng dẫn giải

TR ẦN

H

( −1) C m = 1 1 1 1 0 1 2 C1991 C1991 C1991 + − ... + 1991- m 1991 1991 1991 1991 − m 1991

Với n = 1, 2,..., ta đặt S ( n ) = ∑ ( −1) Cnm-m trong đó tổng được lấy từ m = 0

B

m

k m

= Cnm-1-+1m = 1 − S ( n )

3

∑C

2+

n

Ta có:

10

cho đến hết những số hạng khác 0.

00

m

k =m n -2

(1)

C

k =0

ẤP

Ta có S ( n ) = 1 − ∑ S ( k ) , suy ra S (n + 1) = S (n) − S (n − 1)

Ó

A

Ta có S (0) = S (1) = 1 , từ đó

Í-

H

S (2) = 0, S (3) = − 1, S (4) = − 1, S (5) = 0, S (6) = 1, S (7) = 1

-L

Từ (1) ta có S (m) = S (n) nếu m = n (mod 6) .Do

BỒ

ID Ư

Ỡ N

G

TO

ÁN

n Cnn-m = Cnm-m + Cnm-m-1-1 nên ta được: n-m

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

( 3n )! = 3n k ⇔ ( 3n − 2 )!( 3n − 1)( 3n ) = 3n k ( ) ( ) n !( 2n ) ! ( n − 1)!n ( 2n − 1)!( 2n )

H Ơ

⇔

N

Ta có: C3nn = (3n) k

m  1 −1) ( 1 1 1 995  0 1 2 m 1991.  + ... − C1991 − C1991 + C1991 − ... + C1991C996  = 1 m 1991 1991 1991 − m 996 1991 

Suy ra điều phải chứng minh.

Bài toán 20. 4: Cho các số nguyên dương m và n sao cho n ≤ m . Chứng minh rằng: 2n.n ! ≤

( m + n )! ≤ m2 + m n ( ) ( m − n )!

Trang 3

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com Hướng dẫn giải

( m + n )! = (m + n)(m + n − 1)...(m − n + 2)(m − n + 1) n = ∏ (m + 1 − i )(m + i ) ( m − n )! i =1

N H Ơ

n

Ngoài ra 2n. n ! n = 2 n.1.2.3.n =

( 2.1)( 2.2 ) ... ( 2n ) = ∏ 2i và

N

i =1

i =1

+ m)

Y

2

U

∏ (m

TP .Q

n

(m 2 + m)2 = (m 2 + m)(m 2 + m)...(m 2 + m) =

Do đó, các bất đẳng thức cần chứng minh tương đương với n

n

n

i =1

i =1

i =1

Đ

ẠO

∏ 2i ≤ ∏ (m + 1 − i)(m + i) ≤ ∏ ( m2 + m )

G

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Ta có:

Ư N

2i = i 2 + i − i 2 + i ≤ m 2 + m − i 2 + i = (m + 1 − i )(m + i ) ≤ m(m + 1) = m 2 + m

H

vì i là số nguyên nằm giữa 1 và n. Suy ra:

n

n

i =1

i =1

n

∏ 2i ≤ ∏ (m + 1 − i)(m + i) ≤ ∏ ( m

2

+ m)

B

i =1

00

do đó ta được:

TR ẦN

2i ≤ (m + 1 − i )(m + i ) ≤ m 2 + m

10

Vậy các bất đẳng thức đã cho là đúng.

n

2+

(a + b)

− an − bn ≥ 2n − 2

C

ẤP

Chứng minh:

3

Bài toán 20. 5: Cho n nguyên dương , n ≥ 2 và a, b > 0.

( ab )

n

Hướng dẫn giải

H

Ó

A

Ta có: Cn0 + Cn1 + Cn2 + ... + Cnn = 2n và khai triển nhị thức

Í-

(a + b)

n

n

∑ Cni a n-ibi − a n − bn

∑C a

i =0

i =0

2n − 2

i n

=

n -i i

b

2n − 2

BỒ

ID Ư

Ỡ N

G

TO

ÁN

-L

− an − bn = 2n − 2

n

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Ta có:

=

1 1  n -1 i  n -i i n -1 i n-i i   .  ∑ C n a b ∑ Cn b a   2n − 2 2  i =1   i =1

≥

1 n-1 i n n 1  2 n − 2  . a n .b n = .∑ Cn a .b = n n 2 − 2 i =1 2 −2

( ab )

n

Bài toán 20. 6: Hỏi từ các chữ số 1, 2, 3, 4, 5 ta có thể lập được tất cả bao nhiêu số có 15 chữ số mà trong mỗi số mỗi chữ số đều có mặt đúng 3 lần và không có chữ số nào chiếm 3 vị trí liên tiếp trong số?

Hướng dẫn giải

Trang 4

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Gọi X là tập gồm tất cả các số thoả mãn yêu cầu đề bài. A là tập gồm tất cả các số có 15 chữ số được lập nên bởi các chữ số 1, 2, 3, 4, 5 mà

N

mỗi chữ số đều có mặt đúng 3 lần trong số.

N

H Ơ

 5  Khi đó: X = A \  ∪ Ai  Với A i là tập gồm tất cả các số thuộc A mà chữ số i  i =1 

i

=

5- k

3

i =1

i =1

k =1

k

∑ ∩A

k -1

i

1≤i1 < i2 ...ix ≤ in i =1

G

15! 13! 11! 9! 7! 5! − C51 4 + C52 3 − C53 2 + C54 − C55 0 35 3 3 3 3! 3

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

⇒ X =

15! 35

ẠO

n

và A =

Đ

k

Áp dụng công thức: ∪ Ai = ∑ ( −1)

− 2k ) !

U

(15

TR ẦN

H

Bài toán 20. 7: Cho các số nguyên dương k và n với k ≤ n . Hỏi tất cả có bao nhiêu chỉnh hợp chập k ( a1 , a2 ..., ak ) của n số nguyên dương đầu tiên, mà mỗi chỉnh hợp

B

( a1 , a2 , ..., ak ) thoả mãn ít nhất một trong hai điều kiện sau:

10

00

1) Tồn tại s, t ∈ {1; 2;...; k } sao cho s < t và as > at

3

2) Tồn tại s ∈ {1; 2;...; k} sao cho ( as − s ) không chia hết cho 2.

2+

Hướng dẫn giải

ẤP

Gọi A là tập hợp tất cả chỉnh hợp chập k của n số nguyên dương đầu tiên và A1 là

C

tập hợp tất cả chỉnh hợp thoả mãn yêu cầu của bài ra.

Ó

A

Nếu kí hiệu A2 = { chỉnh hợp ( a1 ,.., ak ) ∈ A / ai < ai +1 , i = 1 , 2,..., k − 1 và rõ

ràng A2 ⊂ A và

A1 = A \ A2 .

Suy

ra:

Í-

H

ai , = i mod 2, i = 1, 2,..., k} thì

-L

A1 = A − A2

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

∪A

TP .Q

k

Xét 1 ≤ k ≤ 5 ta chứng minh được

Y

chiếm đúng 3 vị trí liên tiếp ( i = 1, 2, 3, 4, 5 )

TO

ÁN

Bây giờ ta xét A 2 . Với mỗi ( ai ,..., ak ) ∈ A2 ta đều có ai + i ≠ a j + j với mọi

BỒ

ID Ư

Ỡ N

G

i ≠ i ∈ {1,..., k} , ( ai + i )⋮ 2 và ai + i ∈ {1,..., n + k } với mọi

Ta chứng minh: A2 = Ckn + k  từ đó ta có: A1 =  2 

i = 1, 2,..., k .

n! − Ckn + k  ( n − k )!  2 

Bài toán 20. 8: Trong mặt phẳng cho 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng.Chứng minh rằng trong số các tam giác được tạo thành từ 100 điểm đó, có không quá 70% các tam giác nhọn.

Trang 5

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com Hướng dẫn giải

Từ 4 điểm phân biệt không có 3 điểm nào thẳng hàng, nhiều lắm là có 3 tam giác

N

nhọn. Từ kết quả này, suy ra với 5 điểm phân biệt không có 3 điểm nào thẳng hàng,

H Ơ

ta nhận được 10 tam giác và có không quá 7 tam giác nhọn.

TP .Q

U

điểm chứa 3 điểm cho trước. Trong khi đó, số tất cả các tam giác tạo thành cũng có

Y

nhọn tạo thành là: số các tập con 4 điểm nhân cho 3 rồi chia cho số các tập con 4

N

Với 10 điểm phân biệt không có 3 điểm nào thẳng hàng, số cực đại các tam giác

biểu thức tương tự như í trên nhưng thay vì nhân 3 ta nhân cho 4. Do vậy số các tam

ẠO

giác nhọn chiếm không quá 3/4 số tất cả các tam giác (đối với 10 điểm).

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

cho số các tập con 5 điểm chứa 3 điểm cho trước.

G

số cực đại các tam giác nhọn tạo thành là: số các tập con 5 điểm nhân cho 7 rồi chia

H

Trong khi đó, số tất cả các tam giác tạo thành cũng có biểu thức tương tự như trên

TR ẦN

nhưng thay vì nhân 7 ta nhân cho 10. Do vậy số các tam giác nhọn chiếm không quá 7/10 số tất cả các tam giác tạo thành, điều phải chứng minh.

B

Bài toán 20. 9: Có một trò chơi xổ số như sau: Từ 90 số Ban tổ chức chọn ngẫu nhiên 5

00

số. Người chơi được quyền đặt tiền cho một số bất kì hay cho một nhóm số. Nếu tất

10

cả các số người chơi viết nằm trong 5 số của Ban tổ chức thì người chơi thắng số

2+

3

tiền bằng 15 lần số tiền đặt nếu người chơi viết một số; bằng 270 lần nếu người chơi

ẤP

viết hai số; bằng 5500 lần nếu người chơi viết ba số; bằng 75000 lần nếu người chơi

C

viết bốn số; bằng 1000000 lần nếu anh ta viết năm số. Tìm số lần thắng trung bình

A

của người chơi khi viết một số, hai số, .... năm số.Giả sử có 100000 người đặt tiền

Hướng dẫn giải

Í-

H

Ó

viết ba số. Tìm xác suất sao cho có hơn 10 người thắng trong số họ.

-L

Nếu người chơi viết k số, thì xác suất pk sao cho tất cả các số anh ta viết nằm trong

pk =

5- k C901 2 1 1 1 k ; p1 = ; p2 = ; p3 = ; p4 = ; p5 = 5 18 801 11748 511038 43949268 C90

Kí hiệu E k là số lần thắng trung bình của người chơi khi viết k số và đặt a đồng, ta có: E1 = 15a.

1 1 29 − a.1 = a; E2 = − a ≈ a,... 18 16 89

BỒ

ID Ư

Ỡ N

G

TO

ÁN

năm số của Ban tổ chức, bằng:

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

Lí luận tương tự, ta xét 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng,

Trang 6

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Vì tất cả Ek < 0 , nên rõ ràng là trò chơi xổ số này không có lợi cho người chơi dù viết mấy số. Xác suất sao cho có hơn 10 người thắng trong số những người viết 3 số

N

bằng ≈ 0.24

H Ơ

Bài toán 20. 10: Hai đấu thủ A và B thi đấu trong một giải cờ vua. Người thắng một ván

U

Y

β là p. Ai hơn đối thủ hai điểm thì thắng giải.

N

được một điểm và không có ván hoà. Xác suất thắng một ván của đấu thủ A là α và của

TP .Q

Tính xác suất thắng giải của mỗi đấu thủ.

Hướng dẫn giải

G Ư N

(*)

TR ẦN

H

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Pn ( A) = P ( A1 ) Pn-1 ( A / A1 ) + P ( B1 ) Pn -1 ( A / B1 ) = α Pn-1 ( A / A1 ) + β Pn -1 ( A / B1 )

Đ

các biến số tương ứng A và B thắng ván đầu tiên. Khi đó:

Trong đó Pn -1 ( A / A1 ) là xác suất A thắng giải sau n – 1 ván còn lại, khi A đã thắng

B

ván đầu tiên; Pn -1 ( A / B1 ) là xác suất A thắng giải sau n – 1 ván còn lại, khi B đã

00

thắng ván đầu tiên.

10

Xét n > 2 . Để A thắng giải sau n – 1 ván còn lại, khi A đã thắng ván đầu, thì B phải

2+

3

thắng ván thứ hai, nghĩa là: Pn -1 ( A / A1 ) = P ( B1 ) Pn -2 ( A) = β Pn -2 ( A)

ẤP

Tương tự: Pn -1 ( A / B1 ) = P ( A1 ) Pn -2 ( A) = α Pn -2 ( A)

C

Từ đó và (*) ta có Pn ( A) = 2α Pn -2 ( A) , và suy ra

Ó

A

P4 ( A) = 2αβα 2 ,..., P2 n ( A) = 2αβ n -1α 2

Í-

H

Khi n = 2 ta có P2 ( A ) = α 2 . Vì không có ván hoà nên α + β = 1 , do đó xác suất

-L

thắng giải của A là: ∞

2

2

TO

ÁN

α α 2 P( A) = ∑ P2 k ( A) = α 2 1 + 2αβ + ( 2αβ ) + ... = = 2   1 − 2αβ α + β 2 k =1

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Giả sử α > β . Kí hiệu Pn ( A ) là xác suất thắng giải của A sau n ván; A i và Bi là

ID Ư

Ỡ N

G

Bài toán 20. 11: Tìm tất cả các số nguyên dương n có tính chất sau: Có thể chia tập hợp 6 số {n, n + 1, n + 2, n + 3, n + 4, n + 5} thành hai tập hợp, sao cho tích tất cả các số c ủa

tập hợp này bằng tích tất cả các số của tập hợp kia.

BỒ

Hựớng dẫn giải Ta hãy để ý rằng trong 5 số nguyên liên tiếp phải có một số chia hết cho 5.

Trang 7

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Vì vậy nếu tập hợp 6 số {n, n + 1, ..., n + 5} có tính chất đã nêu trong đầu bài, thì trong tập hợp ấy phải có đúng hai số chia hết cho 5, dĩ nhiên đó phải là các số n và

N

n + 5 , còn các số n + 1, n + 2, n + 3, n + 4 không chia hết cho 5.

H Ơ

Mặt khác, nếu trong 6 số của tập hợp trên chia hết cho một số nguyên tố p ≥ 7 , thì 5

ẠO

n + 1 = 2k1 3I11 ; n + 2 = 2k2 3I 2 ; n + 3 = 2k k3 3I3 ; n + 4 = 2k4 3I 4 ,

Đ

Trong đó k1 I1 ,..., k4 , I 4 là những số nguyên không âm.

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

Nếu n + 1 (và do đó n + 4 ) chia hết cho 3, thì n + 2 và n + 3 không chia hết cho 3, vậy

H

nguyên liên tiếp mà lại là hai số chẵn, điều này vô lí.

Ư N

I 2 = I 3 = 0 và n + 2 = 2 k2 , n + 3 = 2 k3 nhưng như thế thì n + 2 và n + 3 là hai số

TR ẦN

Lập luận tương tự, ta thấy rằng nếu n + 2 chia hết cho 3, hoặc nếu n + 3 chia hết cho 3, thì ta vẫn gặp mâu thuẫn. Chứng tỏ không có số nguyên dương n nào thoả mãn

00

B

điều kiện bài toán.

10

Bài toán 20. 12: Tìm tất cả các số nguyên dương k sao cho có thể phân chia tập hợp

3

X = {1990, 1990 + 1, ..., 1990 + k } thành hai tập con A, B thoả mãn điều kiện:

2+

Tổng của tất cả các phần tử thuộc A bằng tổng của tất cả các phần tử thuộc B

ẤP

Hướng dẫn giải

C

Ta quy ước: tập số M được gọi là có tính chất T nếu M có thể được chia thành hai

Ó

A

tập con rời nhau sao cho tổng của tất cả các phần tử của tập con này bằng tổng của

H

tất cà các phần tử cùa tập con kia.

-L

Í-

Theo bài ra, ta cần tìm tất cả các số nguyên dương k để tập X có tính chất T. Dễ thấy

Y

ÁN

nếu X có tính chất T thì tổng của tất cả các phần tử của X sẽ là một số chẵn. Mà tổng

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

3, tức là:

TP .Q

U

biệt suy ra rằng các số n + 1, n + 2, n + 3 và n+4 chỉ chứa các thừa số nguyên tố 2 và

N

số còn lại sẽ không chia hết cho p, và tập hợp không có tính chất đòi hỏi. Từ đây đặc

TO

này bằng 1990 ( k + 1) + k ( k + 1) / 2 nên k ( k + 1)⋮ 4.

BỒ

ID Ư

Ỡ N

G

Suy ra, k cần có dạng k = 4t + 3 hoặc k = 4t với t ∈ N . Xét: Trường hợp 1 : k = 4t + 3 ∈ N . Khi đó, số phần tử cùa X sẽ là 4 ( t + 1) . Do đó, ta có thể chia tập X thành t + 1 tập con rời nhau sao cho mỗi tập con đều gồm 4 số tự nhiên liên tiếp. Dễ thấy, tập gồm 4 số tự nhiên liên tiếp là tập có tính chất T. Từ đó suy ra tập X có tính chất T.

Trang 8

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Trường hợp 2: k = 4t , t ∈ N . Khi đó, tập X sẽ có 4t + 1 phần tử. Do đó, nếu X

được chia thành hai tập con rời nhau A, B thì một trong hai tập con đó, không mất

N

tổng quát giả sử là A, phải có không ít hơn 2t + 1 phần tử. Như vậy, tập B sẽ có

H Ơ

không quá 2t phần tử. Suy ra, nếu kí hiệu a, b tương ứng là tổng của tất cả các phần

Ư N H

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

B = {1990 ; 1990 + 47, 1990 + 48,..., 1990 + 92}

G

Với t = 23 ta có X = {1990, 1990 + 1,..., 1990 + 92} = AUB,

Đ

⇔ 4t 2 ≥ 1990 nên t ≥ 23

TR ẦN

Hiển nhiên A, B rời nhau, và bằng tính toán trực tiếp dễ thấy a = b . Như vậy với

t = 23(⇔ k = 92) tập X có tính chất T. có:

X = X 1UX 2 với

B

ta

t >3

X 1 = {1990,1990 + 1,...,1990 + 92} và

00

Với

10

X 2 = {1990 + 93, 1990 + 94, ...,1990 + 4t}

2+

3

Theo phần trên, tập X1 có tính chất t. Hơn nữa, do tập X 2 có 4 ( t − 23) ,

ẤP

phần tử nên, vận dụng những lập luận đã trình bày khi xét trường hợp 1, ta sẽ được

C

tập X 2 có tính chất T. Từ đó suy ra tập X cũng có tính chất T.

A

Vậy, tóm lại, tất cả các số nguyên dương k cần tìm là tất cả các số có dạng

H

Ó

k = 4t + 3, t ∈ N và k = 4t , t ∈ N , t > 23

-L

Í-

Bài toán 20. 13: Cho tập hợp số M = {1, 2,..., n} . Hãy tìm số m nhỏ nhất sao cho mỗi

ÁN

tập con chứa m phần tử của tập M đều tồn tại ít nhất hai số a, b thoả số này là bội

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

1990 x 2t + t (6t + 1) > 1990(2t + 1) + t (2t + 1)

Với: A = {1990 + 1, 1990 + 2,..., 1990 + 46}.

U TP .Q

Với giả thiết a = b ta có:

Y

b ≤ (1990 + 2t + 1) + ... + (1990 + 4t ) = 1990 X 2t + t (6t + 1)

N

tử của A, B thì: a ≥ 1990 + (1900 + 1) + ... + (1900 + 2t ) = 1990 ( 2t + 1) + t ( 2t + 1)

BỒ

ID Ư

Ỡ N

G

TO

của số kia

Hướng dẫn giải

 n   n n Ta có C =    + 1;   + 2;...n  có n −   phần tử và không có phần tử nào là bội 2 2  2   của ít nhất 1 phần tử khác thuộc C.

 n + 1  n + 1 Suy ra: m ≥  + 1 phần tử. Ta chứng minh: m =  +1   2   2 

Trang 9

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

 n + 1 Xét 1 tập con P bất kì chứa  + 1 phần tử của M. Với mỗi p ∈ P đặt  2 

N

p = 2 s q; s ≥ 0; s ∈ N và q là số lẻ, vì 1 ≤ p ≤ n nên 1 ≤ q ≤ n mà từ 1 đến n

N Y

U

số q lẻ bằng nhau suy ra tồn tại ít nhất 2 số a, b ∈ P sao cho: a = 2 s1 l , b = 2 s2 l Tức là

H Ơ

 n + 1 có.  số lẻ khác nhau nên trong biểu diễn các phần tử p ∈ P , phải có ít nhất 2  2 

TP .Q

trong 2 số a, b phải có 1 số là bội của số kia.

Bài toán 20.14: Cho n là một số nguyên dương.

G

Đ

(n+1)3 - 1 điểm trong không gian 3 chiều. Hãy xác định số nhỏ nhất có thể các mặt

H

Hướng dẫn giải

TR ẦN

Ta thấy 3n mặt phẳng x = i, y = i và z = i chứa tất cả các điểm của S và không chứa điểm (0,0,0). Như vậy số mặt phẳng cần tìm không vượt quá 3n.

B

Để chứng tỏ số mặt phẳng cần tìm đúng bằng 3n, ta chứng minh bỗ đề sau:

00

Bổ đề: Xét đa thức k biến P ( x1 ; x2 , ..., xk ) . Nếu P triệt tiêu tại các điểm của tập hợp

3

10

S = {{a1 , a2 ,...,} : ai ∈ {0,1..., n} , a1 + a2 + ... + ak > 0} và không triệt tiêu tại điểm

2+

(0,0,...,0) thì p có bậc không nhỏ hơn kn.

ẤP

Chứng minh. Ta chứng minh kết quả bổ đề bằng quy nạp theo k. Dễ thấy kết luận

C

của bổ đề đúng với k = 0 . Giả sử kết luận bổ đề đúng cho k - 1 , ta chứng minh kết

Ó

A

luận của bổ đề cũng đúng cho k.

Í-

H

Thực vậy, nếu đa thức k biến P ( x1 , x2 ,..., xk -1 , X ) thoả mãn điều kiện của bỗ đề

-L

(trong đó X là biến thứ k), thì ta thực hiện phép chia P ( x1 , x2 ,..., xk -1 , X ) cho đa thức

ID Ư

Ỡ N

G

TO

ÁN

x ( x − 1) ... ( x − n ) để

BỒ

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

phẳng mà hợp của chúng chứa tất cả các điểm của s nhưng không chứa điểm (0,0,0).

được

thương

là

Q ( x1 , x2 ,..., xk -1 , X ) và

đa

thức

dư

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Xét S = {( x, y, z ) / x, y, z ∈ {0,1,..., n}, x + y + z > 0} như là một tập hợp gồm

R ( x1 , x2 ,..., xk -1 , X ) . Viết lại R ( x1 , x2 ,..., xk -1 , X ) dạng chính tắc theo luỹ thừa của x

ta có: R ( x1 , x2 ,..., xk -1 , X ) = Rn ( x1 , x2 ,..., xk -1 ) X n + ... + R0 ( x1 , x2 ,..., xk -1 ) (*) Ta sẽ chứng minh Rn ( x1 , x2 ,..., xk -1 ) là đa thức k-1 biến thoả mãn điều kiện của bổ

đề. a) T ( x ) = R ( 0, 0,...0, x ) là đa thức của x với bậc không vượt quá n và triệt tiêu tại các điểm X = 1, 2,...,n . Do

Trang 10

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

T ( 0 ) = R ( 0, 0,...,0, 0 ) ≠ 0 cho nên T(0) là đa thức bậc n của x, suy ra hệ số của bậc cao nhất x n trong khai triển (*) là Rn ( 0, 0,..., 0 ) ≠ 0

a1 ∈ {0,1,.., n} , a1 + a2 + ... + ak -1 > 0 X = 0, 1, 2......n .

N H Ơ

R ( a1 , a2 ,.., ak -1 , X ) triệt tiêu tại n+1 điểm

ta có

Vì bậc của

N

( a1 , a2 ,.., ak -1 ) thoả

U

R ( a1 , a2 ,.., ak -1 , X ) không vượt quá n, cho nên R ( a1 , a2 ,.., ak -1 , x ) là đa thức đồng

Y

b) Với một bộ

TP .Q

nhất 0, do đó tất cả hệ số của nó trong khai triển (*) bằng 0 và đặc biệt là

ẠO

R ( a1 , a2 ,.., ak -1 ) = 0

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

quy nạp, cho nên R ( x1 , x2 ,.., xk -1 , x ) là đa thức có bậc không nhỏ hơn kn.

H

Do đó deg P > deg R ( x1 , x2 ,.., xk -1 , x ) > kn . Bổ đề đựợc chứng minh.

nhưng không chứa điểm (0,0,...,0). Khi đó xét

00

i =1

B

N

P ( x, y, z ) = ∏ ( ai x + bi y + ci z + d j )

10

Đa thức này có bậc là N và P(x, y,z) thoả mãn các giả thiết của bổ đề, nên ta có

2+

3

N = deg P ≥ 3n là điều phải chứng minh.

ẤP

Bài toán 20. 15: Xét hoán vị S0 , S1 ,..., S n cua các số 0, 1, 2,...,n, ta tác động một phép

C

biến đổi lên hoán vị này nếu tìm được i, j sao cho si = 0 và s j = si -1 + 1 . Hoán vị mới

Ó

A

tạo thành nhận được bằng cách đổi chỗ hai phần tử Si và Sj.

Í-

H

Hỏi với số n nào thì xuất phát từ hoán vị (1, n, n − 1, n − 2,..., 3, 2, 0 ) ta có thể

-L

nhận được hoán vị (1, 2,..., n, 0 ) bằng cách lập lại nhiều lần phép biến đổi đó?

Hướng dẫn giải

ÁN TO G Ỡ N ID Ư

BỒ

TR ẦN

Bây giờ giả sử N mặt phẳng ai x + bi y + ci z + d i = 0 chứa tất cả các điểm của S

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

Như vậy, Rn ( x1 , x2 ,.., xk -1 ) là đa thức có bậc không nhỏ hơn (k – 1)n theo giả thiết

Thử trực tiếp, ta thấy rằng có thể thực hiện yêu cầu của bài toán trong trường hợp

n = 1, n = 2, 3, 7, 15 ,

nhưng

không

thực

hiện

được

khi

n = 4, 5, 6 ,8 ,9 , 10, 11, 12, 13,1 4 . Từ đó, ta dự đoán rằng các số dạng n = 2m − 1 và số n = 2 sẽ thoả mãn điều kiện bài toán. Ta

để

ý

n ếu

n = 2m ,

thì

sau

m-1 lần

biến

đỗi

ta

sẽ

có

1 n 0 n − 2 n − 1 n − 4 n − 3... 4 5 2 3 và không thể làm tiếp được. Vậy với n chẵn,

n > 2 ta không thực hiện được .

Trang 11

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

1 2 3 0 12 13 14 15 8 9 10 11 4 5 6 7

(sau; 8 lần biến đổi)

1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 15

(sau 8 lần biến đổi)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

(sau 8 lần biến đổi)

m

1 2 3...R − 1 0, n − R + 1, n − R + 1 n − R + 2 n − R + 3...

ẠO

n, n − 2 R + 1 n − 2 R + 2...n − R,..., R R + 1 ... 2 R − 1

G

Đ

ở đây R là kí hiệu cho số 2r và dấu phẩy ngăn cách biểu thị rằng, sau hoán vị ban

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

đầu 1, 2...R − 1 0 , tăng lên R số hạng. Nếu khởi đầu từ Pr , thì số 0 được chuyển đổi

H

thành công với R, 3R, 5 R,..., n − R + 1 , rồi với R + 1, 3R + 1..., n − R + 2 ,

TR ẦN

tiếp tục với 2 R − 1, 4 R − 1,..., n . Điều này sẽ cho ta Pr +1 . Dễ dàng kiểm tra được P0 dẫn đến P1 và sau đó đến pm là vị trí kết thúc. Như thế, có thể thực hiện được theo

00

B

yêu cầu đề bài cho trường hợp n = 2m − 1 .

+ 1) 2b − 1 (lấy 2b là luỹ thừa cao nhất của 2 sao cho nó chia hết n + 1 ).

3

( 2a

2+

n =

10

Tiếp theo, giả sử n lẻ nhưng không có dạng 2m − 1 . Lúc đó, ta có thể viết

ẤP

Ta có thể định nghĩa P0 , P1 ,..., Pb như trên. Ta có thể đạt đến Pb như trên:

C

1 2...B − 1 0, 2aB 2aB + 1 ... ( 2a + 1) B − 1, ( 2a − 1) B ... 2aB − 1,...,

Ó

A

3B, 3B + 1,... 4 B − 1, 2 B, 2 B + 1,..., 3B − 1, B, B + 1,..., 2 B − 1

Í-

H

với B = 2b − 1 . Khi đó, 0 được chuyển với B, 3B, 5 B..., ( 2a − 1) B , và đặt nó ngay

-L

bên phải của ( 2a + 1) B − 1 = n , nên không thể tiếp tục được xa hơn, điều này có

n = ( 2a + 1) 2b − 1

Bài toán 20.16: Cho S là tập hợp {1, 2,..., n} , n ≥ 1 . Ta gọi pn ( k ) là số các hoán n vị n

của S có đúng k điểm cố định. Chứng minh rằng:

BỒ

ID Ư

Ỡ N

G

TO

ÁN

nghĩa không thể thực hiện được để thoả mãn điều kiện bài toán cho

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

TP .Q

Tổng quát, ta giả sử n = 2 -1 . Gọi P0 là hoán vị đầu tiên và Pr là hoán vị có dạng:

H Ơ

(sau 7 lần biến đổi)

N

1 0 14 15 12 13 10 11 8 9 6 7 4 5 2 3

Y

(bắt đầu)

U

1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0

N

Nếu n = 15 ta có thể làm như sau:

∑ k. p ( k ) = n ! n

k =0

Hướng dẫn giải Ta có: nCnk-1-1 = kCnk ⇒

n k -1 Cn -1 = Cnk nếu k ≠ 0 k

Trang 12

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

n

Để ý: pn ( k ) = Cnk Pn -k (0), ∑ pn ( k ) = n ! k =0 n

∑ p (k ) = ∑ k .C n

pn- k (0)

i =1

n

n -1

n -1

k =0

k =0

k =0

H Ơ

k =0

k n

N

n

Từ đó suy ra:

TP .Q

U

Bài toán 20. 17: Chứng minh rằng tập hợp {1, 2, 3,...,1989} có thể được viết thành hợp

Y

N

= n∑ Cnk-1-1 pn -k (0) = ∑ Cnk-1 pn - k -1 (0) = n∑ pn -1 ( k ) = n ( n − 1) ! = n !

Đ

Hướng dẫn giải

ẠO

phần tử và tổng giá trị của các phần tử những Aị đều bằng nhau.

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

Trước hết, ta xây dựng 117 tập hợp gồm 3 số sao cho tổng của 3 số đó trong mỗi tập

{−994,

− 993,...,993, 994} , tập hợp này có được bằng cách lấy

từng số hạng của tập hợp đã cho trừ đi 995.

TR ẦN

tạo thành tập M =

H

đều bằng 0 và chúng rời nhau từng đôi một như sau: Từ tập {1, 2, 3,..., 1989} , ta

B

Khi đó, ta tạo 116 tập hợp gồm 3 số nói trên là:

10

00

N1 = {993, − 496, − 497}, N 2 = {−993, 496, 497},

3

N 2 k +1 = {993 − 4k , 2k − 496, 2k − 497},

2+

N 2 k + 2 = {−993 + 4k , − 2k + 496, − 2k + 497},

ẤP

…………………………………………

A

C

N115 = {665, − 382, − 383}, N116 = {−665, 382, 383}

H

Ó

Ngoài ra, ta đặt N117 = {−1 , 0, 1}

Í-

Tất cả 117 tập hợp trên đều rời nhau từng đôi một, Thật vậy, trong mỗi tập, do các

-L

phần tử thứ hai đều chẵn nên các phần tử thứ hai của các tập hợp N1 ,..., N116 không

ÁN

thể trùng với các phần tử thứ nhất hoặc thứ ba của những tập hợp này, tất cả các

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

của các tập rời nhau A1 , A2 ..., A117 sao cho mọi Ai , i = 1, 2,...,117 , đều có chứa 17

BỒ

ID Ư

Ỡ N

G

TO

phần tử thứ nhất của những tập hợp này có giá trị tuyệt đối lớn hơn tất cả phần tử thứ ba, thành thử các tập hợp N i rời nhau từng đôi một. Ngoài ra, nếu số x nào đó là phần tử của một trong các tập hợp N i thì số (-x) cũng là

phần tử của một trong các tập hợp N i . Để ý rằng 14.117 phần tử của tập hợp M, không thuộc về một trong các tập hợp N i , được chia thành 7.117 cặp số với dấu đối

Trang 13

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

nhau. Bằng cách tuỳ ý ta thêm 7 cặp số phân biệt vào tập hợp N i đã chọn ở trên, ta sẽ chia được tập hợp M thành 117 tập hợp con từng cặp không giao nhau.

N

Cuối cùng để thoả mãn yêu cầu của bài toán, ta chỉ cần xây dựng 117 tập Ai bằng

H Ơ

cách cộng 995 vào từng phần tử của các tập N i tương ứng.

Y

U

nhau. Quan hệ bạn bè là quan hệ hai chiều. Gọi một nhóm các thí sinh là nhóm bạn

N

Bài toán 20. 18: Trong một kì thi học sinh giỏi toán có một số thí sinh là bạn bè của

TP .Q

bè nếu như hai người bất kì trong nhóm này là bạn bè của nhau. (Mỗi nhóm tuỳ ý ít

ẠO

một nhóm bạn bè được gọi là cỡ của nó.

Đ

Cho biết rằng, trong kì thi này, cỡ của một nhóm bạn bè có nhiều người nhất là một

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

số chẵn. Chứng minh rằng có thể xếp tất cả các thí sinh vào hai phòng sao cho cỡ của nhóm bạn bè có nhiều người nhất trong phòng này cũng bằng cỡ của nhóm bạn

Hướng dẫn giải

TR ẦN

H

bè có nhiều người nhất trong phòng kia

Ta gọi cỡ của một tập hợp A, kí hiệu là c(A), là cỡ của nhóm bạn bè đông người

00

B

nhất trong A. Gọi M là nhóm bạn bè đông người nhất trong tập hợp G tất cả các thí

10

sinh, như vậy c ( M ) = c ( G ) = 2m là số chẵn. Ta chỉ ra một cách phân hoạch G

3

thành hai tập hợp có cùng cỡ như sau:

2+

Trước hết A là một tập hợp m thí sinh của M và B = G − A . Như vậy

C

ẤP

c ( B ) ≥ m ≥ c ( A ) . Chừng nào c ( B ) ≥ c ( A) + 2 ta chuyển một thí sinh của M

A

từ B sang A. Mỗi lần như vậy cỡ của B giảm không quá 1 và cỡ của A tăng đúng 1.

H

Ó

Do đó, ta có thể thực hiện được việc điều chỉnh này cho tới khi c ( B ) = c ( A ) hoặc

-L

Í-

c ( B ) = c ( A ) + 1 . Trong trường hợp c ( B ) = c ( A ) + 1 ta thực hiện tiếp việc điều

ÁN

chỉnh mới bằng cách xét tất cả nhóm bạn bè B1 , B2 ,..., Bs gồm c(B) người trong B.

TO

Nếu tồn tại Bi và m ∉ M − A sao cho m ∉ Bi thì tập hợp A ∪ {m} và B −

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

hơn hai thí sinh cũng vẫn được coi là một nhóm bạn bè), số lượng các thí sinh của

{m} là hai

BỒ

ID Ư

Ỡ N

G

tập hợp có cùng cỡ c ( A) + 1 . Nếu m ∈ Bi với mọi Bi và m ∈ M − A thì

Bi − ( M − A) luôn khác tập rỗng vì Bi có ít nhất m + 1 phần tử còn M − A chỉ có nhiều nhất m phần tử. Xuất phát từ

C = ∅ ta chọn một phần tử của

B − ( M − A ) vào C, với Bi là nhóm bạn bè nào đó có c(B) người trong tập hợp i

Trang 14

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

B − C . Quá trình kết thúc khi thu được một tập hợp c sao cho

c ( B − C ) = c ( B ) − 1 = c( A) .

H Ơ

N

Ta chứng minh c ( A ∪ C ) = c ( A) . Thật vậy, xét một nhóm bạn bè Q tuỳ ý trong

N

A ∪ C . Do mỗi phần tử của c là bạn bè của mọi phần tử M − A cho nên

= Q +

( 2m

− A) ⇒ A ≥ Q .

U

)

TP .Q

c ( G ) = 2m ≥ Q ∪ ( M − A

Y

Q ∪ ( M − A ) là một nhóm bạn bè trong G và do đó:

Vậy B − C và A ∪ C là phân hoạch của G thành hai tập hợp có cùng cỡ (đpcm).

Đ

trong khoảng từ 1 đến 1000. Chứng tỏ rằng có thể chọn ra 9 học sinh thi Toán có

G Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

tổng các số ký danh được mang chia hết cho 9.

Hướng dẫn giải

TR ẦN

H

Xét 5 số tự nhiên tuỳ ý, khi chia cho 3 có thể xảy ra: Có 3 số dư giống nhau ⇒ Tổng 3 số tương ứng chia hết cho 3. Trái lại, sẽ có 3 số dư đôi một khác nhau ⇒ Tổng 3 số tương ứng chia hết cho 3.

00

B

Vậy trong 5 số tự nhiên bất kì, tồn tại 3 số có tổng chia hết cho 3.

10

Xét 17 số tự nhiên tuỳ ý: Chia chúng thành 3 tập, có lần lượt 5, 5, 7 phần tử. Trong

2+

3

mỗi tập, chọn được 3 số có tổng lần lượt là: 3a1 , 3a2 , 3a3 ( a1 , a2 , a3 ∈ N ) còn lại:

C

3 số có tổng là 3a 5 .

ẤP

17 − 9 = 8 số, trong 8 số này, chọn tiếp 3 số có tổng là 3a 4 , còn lại 5 số, chọn tiếp

Ó

A

Trong 5 số a1 , a2 , a3 , a4 , a5 có 3 số ai1 , ai 2 , ai 3 có tổng chia hết cho 3. ⇒ 9 học sinh

H

tương ứng có tổng các số kí danh là:

-L

Í-

3ai1 + 3ai 2 + 3ai 3 = 3 ( ai1 + ai 2 + ai 3 )⋮ 9

ÁN

Bài toán 20. 20: Cho 75 điểm trong hình lập phương có cạnh 1. Chứng minh rằng tồn tại

BỒ

ID Ư

Ỡ N

G

TO

một tam giác có 3 đỉnh trong số các điểm đó có diện tích không quá

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Bài toán 20. 19: Trong kỳ thi Olympic có 17 học sinh thi Toán được mang số ký danh

7 12

Hướng dẫn giải

Trước hết ta chứng minh bổ đề sau: Bổ đề: Trong hình lập phương cạnh a có 3 điểm, khi đó diện tích tam giác có 3

đỉnh tại các điểm đó không lớn hơn

a2 3 2

Trang 15

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Chứng minh: Dựa vào nhận xét đơn giản sau: trong không gian cho 5 điểm B, C, M, A, N trong đó M, A, N theo thứ tự nằm trên một đường thẳng, khi đó:

N

max {S ( MBC ) , S ( NBC )} ≥ S ( ABC )

H Ơ

Ta suy ra diện tích tam giác ABC không lớn hơn diện tích tam giác có đỉnh là đỉnh

U

2

3

2

=

TP .Q

(a 2 ) Diện tích đó bằng

Y

các đường chéo của các mặt bên có diện tích lớn nhất.

N

của hình lập phương. So sánh diện tích các tam giác này, ta thấy tam giác có cạnh là

a2 3 . Và như vậy bổ đề được chứng minh. 3

Đ

Vì 27 x 2 < 75 nên theo nguyên lý Dirichlet, tồn tại 3 điểm trong số 75 điểm đã

Ư N

1 3 7 . < (đpcm). 9 2 72

TR ẦN

này có diện tích không lớn hơn

H

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

cho nằm trong 1 hình lập phương nhỏ nào đó. Diện tích tam giác có đỉnh tại ba điểm

Bài toán 20. 21: Có 1991 học sinh đứng thành vòng tròn và quay mặt vào giữa để chơi trò đếm số như dưới đây. Mỗi học sinh đếm một số lần lượt theo chiều kim đồng hồ,

00

B

bắt đầu từ học sinh A nào đó. Các số đếm được là 1, 2, 3 và cứ lặp lại theo thứ tự

10

như thế. Nếu học sinh nào đến số 2 hoặc số 3 thì phải rời ngay khỏi vị trí ở vòng

3

tròn. Học sinh còn lại cuối cùng sẽ được thưởng. Hỏi học sinh muốn nhận phần

2+

thưởng thì lúc bắt đầu chơi phải chọn vị trí thứ bao nhiêu theo chiều kim đồng hồ kể

C

ẤP

từ học sinh A đếm số 1 lần đầu tiên?

Hướng dẫn giải

Ó

A

Xét 2 trường hợp:

Í-

H

1) Trường hợp có 3n học sinh đứng thành vòng tròn Nếu chia học sinh thành từng

-L

nhóm 3 người theo số đếm 1,2,3 thì có 3n : 3 = 3n -1 nhóm. Sau 1 vòng đếm thì số

ÁN

học sinh ra khỏi vòng là 2.3n-1 và còn lại 3n-1 học sinh. Chú ý rằng học sinh B đếm số

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Quay lại bài toán, ta chia hình lập phương thành 27 hình lập phương nhỏ cạnh 1/3.

TO

1 đầu tiên trong vòng đầu sẽ lại đếm số 1 đầu tiên ở mỗi vòng nên sẽ ở lại đến cuối

BỒ

ID Ư

Ỡ N

G

cùng và sẽ được nhận thưởng. 2) Trường hợp có 1991 học sinh Ta có: 36 = 729 < 1991 < 37 = 2187 . Ta đưa về trường hợp 1 bằng cách tính xem đến khi nào còn lại 729 = 36 học sinh thì học sinh B đếm số 1 đầu tiên trong 729 người sẽ được thưởng.

Trang 16

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Như vậy: cần có 1991 − 729 = 1262 học sinh rời khỏi vị trí có 1262 : 2 = 631 nhóm 3 người, do đó cần có 631 . 3 = 1893 học sinh đứng trước học sinh B đếm số

N

1 đầu tiên trong 729 người còn lại.

H Ơ

Vậy nếu chọn số 1 đầu tiên trong số 1991 người thì học sinh B đứng ở vị trí thứ

N

1894 sẽ là người đếm sổ 1 đầu tiên trong 729 người, do đó sẽ còn lại đến cuối cùng

U

Y

và được thưởng.

TP .Q

Bài toán 20. 22: Tại đỉnh A 0 của đa giác A0 A1 A2 ... An ( n ≥ 3) người ta đặt n viên bi.

Thực hiện việc chuyển chỗ các viên bi theo cách sau: mỗi lần lấy một viên bi ở A,

G

Đ

đỉnh kề A i với i, j e {0, 1, 2,..., n} (có thể i = j).

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Hãy tìm tất cả giá trị của n sao một số hữu hạn lần thực hiện việc chuyển bi nói trên

TR ẦN

Hướng dẫn giải

H

một cách thích hợp thì ở mỗi đỉnh A1 , A2 ,..., An đều có một viên bi. Ta thấy n = 2k (k là số tự nhiên > 2) thoả mãn bài ra.

00

B

Vậy ta xét n = 2k + 1 với k tự nhiên ≠ 0 . Ta tô các đỉnh A0 , A2 , ..., A2 k +1 với hai

10

màu xanh, đỏ sao cho đỉnh A 0 được tô màu đỏ; với mỗi i = 0,1, 2,..., 2k + 1 đỉnh

3

A i có màu khác với màu của đỉnh kề với nó.

2+

Ta nhận thấy rằng: trong mỗi lần chuyển bi, mỗi bi đều được chuyển từ đỉnh có màu

ẤP

này sang đỉnh có màu kia. Vì thế, sau mỗi lần chuyển bi, tổng số bi có tại tất cả các

A

C

đỉnh được tô màu xanh không thay đổi tính chẵn, lẻ. Suy ra có thể xếp được vào mỗi

H

Ó

đỉnh A1 A2 ,..., A2 k +1 một bi chỉ khi k + 1 = 0 ( mod 2 ) hay n = 3 ( mod 4 ) .

Í-

Ngược lại, với n = 4m + 3, m ∈ N , thực hiện việc chuyển bi theo cách sau đây

-L

chẳng hạn: Lần lượt, với mỗi k = 1, 2,..., 2m + 1 ở bước thứ 1 ta làm như sau: Lấy 2

ÁN

bi ở A 0 , chuyển chúng qua các đỉnh A1 , A2 ,..., tới đỉnh A2 k thì dừng lại. Sau bước

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

rồi đặt vào một đỉnh kề A i và đồng thời lấy một viên bi ở A i rồi đặt nó vào một

BỒ

ID Ư

Ỡ N

G

TO

thứ 2m + 1 , tại đỉnh A 0 sẽ có 1 bi, tại mỗi đỉnh A2 , A4 ,..., A4 m +1 đều có 2 bi, còn tại

các đỉnh

A1 , A3 ,..., A4 m +3 đều không có bi. Sau đó lần lượt với mỗi

k = 1, 2,..., 4m + 1 ở bước thứ k ta làm như sau: Lấy 1 bi ở A 4k chuyển sang

A4 k +1 , đồng thời lấy 1 bi ở A4 k + 2 chuyển sang A 4k+3 (quy ước coi A 0 là A4 m + 4 )- Sau bước thứ m + 1 , tại mỗi điểm A1 , A3 ,..., A4 m +3 sẽ có 1 bi. Vậy tất cả giá trị n ≠ 3 phải tìm là n = 1 ( mod 4 ) .

Trang 17

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

BỒ

ID Ư

Ỡ N

G

TO

ÁN

-L

Í-

H

Ó

A

C

ẤP

2+

3

10

00

B

TR ẦN

H

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

Đ

ẠO

TP .Q

U

Y

N

H Ơ

N

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

Trang 18

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

2 số nào nằm trong cùng một cột của bảng. Tính tổng n sổ đã chọn.

ẠO

Hướng dẫn giải

Đ

Kí hiệu a ij là số ở hàng thứ i, cọt thứ j và để ý đến cấu tạo của bảng thì ta có:

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

aij = ( i − 1) n + j Muốn có n số thoả mãn đầu bài, ta chỉ việc lấy n số sau:

H

a1α1 , a2α 2 ,..., anαn trong đó α i là số thứ tự chỉ cột và αi ≠ α j nếu i ≠ j .

TR ẦN

Như vậy nếu hoán vị các α i cho nhau, ta được tất cả n! cách chọn Muốn có cách chọn khác ta chỉ việc hoán vị α i và α j cho nhau mà phép hoán vị không làm thay

B

đổi tổng của hai số đã cho, nên mọi cách chọn đều có chung một tổng. Gọi tổng của

10

00

n chữ số đó là S ta có:

3

S = (1 − 1)n + α1 + ( 2 − 1) n + α 2 + ... + ( n − 1) n + α n

ẤP

2+

S = 0n + n + 2n + ... + ( n − 1) n + α1 + α 2 + ... + α n n ( n + 1) 2

A

C

Mà α1 + α 2 + ... + α n = 1 + 2 + ... + n =

Í-

H

Ó

2 n ( n + 1) n ( n + 1) Nên S = 1 + 2 + ... + ( n − 1)  n + = 2 2

24: Tồn tại hay không một cách xếp 100 số nguyên:

-L

Bài toán 20.

ÁN

51, 52, ..., 149, 150 vào trong một lưới vuông gồm 10 hàng 10 cột (mỗi ô vuông

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

TP .Q

U

Hãy chọn n số sao cho không có hai số nào đứng trong cùng một dòng và không có

Y

N

H Ơ

N

Bài toán 20. 23: Từ bảng

TO

một số) sao cho nếu a và b là hai số đứng kề nhau trên một hàng hoặc trên một cột

G

thì ít nhất một trong hai phương trình x 2 − ax + b = 0, x 2 − bx + a = 0 có

BỒ

ID Ư

Ỡ N

nghiệm nguyên?

Hướng dẫn giải Đặt S =

−

{51;

52 : ...; 150} . Giả sử a, p ∈ S; p nguyên tố. Khi đó:

Nếu phương trình x 2 − a x + p = 0 có nghiệm nguyên, thì theo định lý Vi-ét, cả hai nghiệm x1 ,x 2 của nó đều nguyên và dương; hơn nữa, do p là số nguyên tố,

Trang 19

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

x1 x2 = p ⇒ { x1 ; x2 } = {1; p} ⇒ a = x1 + x2 = p + 1 Nếu phương trình x 2 − a x + p = 0 có nghiệm nguyên. Cả hai nghiệm x1 ,x 2 của

H Ơ

N

phương trình này cũng nguyên dương và x1 + x2 = p , nên

Y

[ p / 2]}

Suy ra: a = p − 1 ∨ a = 2 ( p − 2 ) ∨ ... ∨ a = [ p / 2 ]( p − [ p / 2 ]) .

[ p / 2])

ẠO

Nhưng do p − 1 ≤ 2 ( p − 2 ) ≤ ... ≤ [ p / 2] ( p −

U

−

TP .Q

{[ p / 2]; p

N

{x1 ; x2 } = {1; p − l} ∨ {x1 ; x 2 } = {2; p − 2} ∨ . . . ∨ {x1 ; x 2 } =

Đ

nếu p thỏa: 2(p − 2) > 150 ⇔ p > 77 thì chỉ còn khả năng a = p − 1

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

Từ hai trường hợp trên, ta thấy: nếu tồn tại một cách xếp 100 số của S vào trong một

Ư N

lưới vuông gồm 10 hàng 10 cột sao cho yêu cầu của bài toán được thỏa mãn, thì mỗi

H

số nguyên tố p thỏa (1) của s có tối đa 2 số đứng kề với nó, là p ± 1 ; vậy, chỉ có thể

TR ẦN

xếp p vào một trong 4 ô vuông ở góc của lưới vuông đó.

Nhưng S có nhiều hơn 4 số nguyên tổ thỏa p > 77, là 79, 83, 89, 97, 101, ...; nên

00

B

ta không thể xếp hết chúng vào lưới vuông.

10

Mâu thuẫn đó chứng tỏ rằng: không thể tồn tại một cách xếp thỏa yêu cầu bài toán.

3

Bài toán 20. 26: Một bảng vuông gồm 1999 x 1999 ô với mỗi ô có chứa một hoặc

2+

không hòn đá. Tìm số bé nhất các hòn đá để cho khi chọn một ô trống bất kì, tổng số

ẤP

các hòn đá trong hàng và cột tương ứng với ô trống này ít nhất là 1999.

C

Hướng dẫn giải

Ó

A

Ta hãy xếp các hòn đá len bảng vuông sao cho ở bốn góc đều

H

có bốn hòn đá, và sắp xếp toàn bảng như hình bàn cờ(ô đen

-L

Í-

có một hòn, ô trắng không có – có dạng như hình 5x5 bên

ÁN

cạnh).

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

−

Dễ thấy cách sắp xếp này thoả mãn điều kiện đề bài.

BỒ

ID Ư

Ỡ N

G

TO

Tổng số các hòn đá được dùng trong cách sắp xếp này là:

1000 x 1000 + 999 x 999 = 1998001 (hòn đá) Ta sẽ chứng minh rằng 1998001 là

số bé nhất cần tìm. Giả sử các điều kiện của bài toán được thoả mãn, trong đó, k là số bé nhất các hòn đá trong một hàng hay cột bất kì.

Không mất tính tổng quát, có thể giả sử rằng có một cột nào đó chứa k hòn đá. Trong cột này, tương ứng với mỗi một trong k hòn đá, hàng có chứa hòn đá đó phải

Trang 20

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

chứa ít nhất k hòn đá, do giả thiết k là số bé nhất các hòn đá trong một hàng hay cột bất kì. Với 1999 - k ô trống của cột này, tương ứng với một ô trống, để thoả mãn

N

điều kiện đã nêu, hàng chứa ô trống phải chứa ít nhất 1999 - k hòn đá. Vậy tổng số

2

H Ơ

các hòn đá ít nhất phải là: 2

U

Y

N

1999  1999 2  k 2 + (1999 − k ) = 2  k − ≥ 1998000,5  + 2  2  Bài toán 20. 26: Một khối bằng gạch có dạng hình của một tam

ẠO

cấp gồm ba bậc có bề rộng là 2 được làm từ 12 khối hình

G

Ư N

(dạng tam cấp) ấy.

H

Hưởng dẫn giải

TR ẦN

Thể tích trọn viên gạch (dạng tam cấp) bằng 12, nên điều kiện ắt có là cạnh của hình lập phương phải là bội của 6. Hai viên gạch có thể gắn với nhau dễ dàng để tạo

B

thành một hình hộp chữ nhật kích thước 2 x 3 x 4 , và hình hộp chữ nhật này có thể

10

00

xếp thành hàng để tạo thành một hình lập phương cạnh 1 hay thành một hình lập phương bất kì có cạnh là bội của 12.

2+

3

Đảo lại, ta sẽ chứng minh rằng: Một hình lập phương cạnh n = 6ℓ chỉ có thể tạo

ẤP

thành theo điều kiện bài toán nếu ℓ chẵn.

C

Thật vậy, giả sử một hình lập phương như thế được tạo xong, thế thì ta đã sử dụng

Ó

A

m = n 3 /12 = 18ℓ 3 viên gạch (dạng tam cấp). Ta chuyển hình lập phương này vào

H

trong góc phần tám x, y, z ≥ 0 của hệ trục toạ độ trong không gian với một đỉnh của

Í-

hình lập phương nằm tại gốc O ( 0, 0, 0 ) . Tô màu mỗi cạnh của hình lập phương đơn

ÁN

vị

-L

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

thể dựng một khối lập phương cạnh n từ các khối bằng gạch

Đ

lập phương đơn vị. Hãy xác định số nguyên n sao cho ta có

+ 1] x [ j , i + 1] x [ k , k + 1]

TO

[i, i

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

TP .Q

Tóm lại, số cần tìm là 1998001.

BỒ

ID Ư

Ỡ N

G

bằng một trong tám màu, tuỳ theo tính chẵn lẻ của bộ ba ( i, j, k ) . Trong mỗi viên

gạch, tất cả tám màu đều có sáu trong tám mày ấy xuất hiện chỉ trong một hình lập phương đơn vị, và mỗi một trong hai màu còn lại có mặt trong ba hình lập phương đơn vị. Ta chọn một trong tám màu và gọi p là số viên gạch mà trong đó màu này xuất hiện ba lần. Trong hình lập phương có m viên gạch, màu này xuất hiện cả thảy

Trang 21

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn 3p +

(m

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

− p ) = m + 2 p lần.

Mặt khác, tám màu được phân phối đều trong hình lập phương cạnh 6ℓ , cho nên

N

mỗi màu xuất hiện đúng 12m/8 lần. Suy ra rằng m + 2 p = 12m / 8 và thế là

H Ơ

m = 4p . Như vậy m là bội của 4 và ℓ phải là số chẵn.

Y

U

vòng tròn lớn. Mỗi học sinh sẽ vỗ vào tay một trong hai học sinh kề hai bên một số

N

Bài toán 20. 27: Tại một cuộc khiêu vũ, một nhóm S gồm 1994 học sinh đứng thành một

TP .Q

lần. Với mọi học sinh x, ta gọi f(x) là tổng tất cả các số lần mà X vỗ vào tay những

người bạn đứng kề. Chẳng hạn, ta giả sử có 3 học sinh A, B và C, A vỗ vào tay B hai

G

Đ

f ( A ) = 7, f ( B ) = 5 và f ( C ) = 8

n ≠ 3, 2 ≤ n ≤ 1996}

Hướng dẫn giải

Ư N

{ f ( x)

/ x ∈ S } = {n / n là số nguyên,

H

b) Tìm một số ví dụ chứng tỏ:

TR ẦN

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

a) Chứng minh { f ( x ) / x ∈ S } ≠ {n / n là số nguyên , 2 < n < 1995}

∑ f ( x) không thể bằng số lẻ: 2

+ 3 + 4 + ... + 1995

10

và bằng

00

B

a) Để ý rằng hai lần tổng số các lần vỗ vào tay là một số chẵn, và bằng f(x) số này

3

x∈S

2+

b) Cho n ≥ 2 . Với một nhóm sn gồm 4n − 2 học sinh, biểu đồ sau đây cho ta ví

/ x∈S

} = {n / n

ẤP

{ f ( x)

là số nguyên, n ≠ 3, 2 ≤ n ≤ 1996}

BỒ

ID Ư

Ỡ N

G

TO

ÁN

-L

Í-

H

Ó

A

C

dụ chứng tỏ.

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

lần, B vỗ vào tay C ba lần và C vỗ vào tay A năm lần. Như thế, ta có:

Trang 22

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

N

Mỗi vòng tròn trên biểu đồ biểu diễn một học sinh x và con số trong vòng tròn biểu

H Ơ

diễn f(x). số nằm trên các cung tròn thì biểu diễn số lần 2 học sinh kề nhau vỗ vào

Y

U

Bài toán 20. 28: Cho n > 1 là một số nguyên. Một con đường từ ( 0, 0 ) tới ( n,n ) trong

N

tay nhau. Chọn n = 499 , ta có được ví dụ thoả mãn bài toán.

TP .Q

mặt phẳng xOy được định nghĩa là một chuỗi các di chuyển liên tiếp của đơn vị sang

phải (di chuyển này được kí hiệu bởi E) hay lên trên (di chuyển này được kí hiệu bởi

Đ

con đường là sự kết hợp của hai di chuyển liên tiếp có dạng EN. Chứng minh rằng

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

số các con đường từ ( 0, 0 ) đến ( n,n ) mà chứa đúng s bước nhảy ( n ≥ s ≥ 1) là bằng

Hướng dẫn giải

TR ẦN

H

1 s -1 s -1 Cn -1Cn s

B

Một con đường với s bước nhảy từ ( 0, 0 ) đến ( n,n ) được gọi là một con đường

10

00

1 kiểu ( n, s ) . Cho f ( n, s ) là số con đường kiểu ( n, s ) và đặt g ( n, s ) = Cns-1-1Cns -1 s

2+

3

Ta sẽ chứng minh bằng quy nạp theo n rằng (n, s) = g (n, s ) với s = 1, 2,..., n . Dễ dàng thấy rằng:

C

ẤP

f (1 , 1) = 1 = g ( 1, 1 ), f ( 2 , 1 ) = 1 = g ( 2 , 1 ), f ( 2 , 2 ) = 1 = g ( 2 , 2 ).

A

Cho n ≥ 2 và giả sử rằng (m, s) = g (m, s) với 1 ≤ s ≤ m ≤ n . Rõ ràng là Ta

sẽ

chứng

minh

rằng

H

Ó

f (n + 1, 1) = g (n + 1, 1) .

Í-

f (n + 1, s + 1) = g (n + 1, s + 1) với1 ≤ s ≤ n

ÁN

-L

Ta nói một con đường kiểu ( n, s ) và một con đường kiểu ( n + 1, s + 1) là liên đới

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

N), mọi di chuyển được thực hiện trong nửa mặt phẳng x ≥ y . Một bước nhảy trên

với nhau nếu con đường sau thu được từ con đường trước bằng cách hoặc nhét thêm N) hay (N, E), hoặc thêm vào một cặp EN ở cuối con đường. Ta cũng nói rằng con

đường kiểu ( n, s + 1) và con đường kiểu ( n + 1, s + 1) là liên đới nếu con đường

dài hơn có được từ con đường ngắn hơn bằng cách thêm một cặp EN vào giữa (E, N).

BỒ

ID Ư

Ỡ N

G

TO

vào con đường thứ nhất một cặp EN giữa hai di chuyển liên tiếp có dạng (E, E), (N,

Trang 23

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn Mỗi

đường

( n, s ) liên

kiểu

đới

với

2n + 1 − s con

đường

kiểu

+ 1, s + 1) khác; mỗi con đường kiểu ( n, s + 1) liên đới với s + 1 con đường

H Ơ

N

kiểu ( n + 1, s + 1) khác; mỗi con đường kiểu ( n + 1, s + 1) liên đới với đúng

( 2n

+ 1 − s ) f ( n, s ) +

(s

+ 1) f ( n, s + 1)

+ 1 − s ) g ( n, s ) +

(s

+ 1) g ( n, s + 1) và khi

( 2n

ẠO

+ 1) g ( n + 1, s + 1) =

TP .Q

Dễ dàng kiểm chứng được rằng:

(s

Đ

đó

( 0, 0 ) đến ( n, n ) có s bước nhảy sẽ

Ư N

Chú ý: Nếu m ≥ n ≥ s ≥ 1 , số các con đường từ

G

f ( n + 1, s + 1) = g ( n + 1, s + 1) .

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Y

+ 1) f ( n + 1, s + 1) =

U

(s

N

s + 1 con đường kiểu ( n, s ) hay ( n, s + 1) . Vì thế số các cặp liên đới là:

nạ p

theo

+ 1) f ( m + 1, n + 1, s + 1) =

(m

+ n + 1 − s ) f ( m, n, s ) +

m:

(s

+ 1)( m, n, s + 1)

00

B

(s

TR ẦN

H

được cho bởi f (m, n , s) = Cms Cns-1-1 − Cms -1Cns-1 . Điều này được chứng minh bằng quy

10

Bài toán 20. 29: Có 18 người tham gia một cuộc thi đấu gồm 17 vòng đấu.

3

Mỗi vòng có 9 trận thi đấu và trong mỗi vòng, mỗi đấu thủ tham gia một trận. Mỗi

2+

người đều thi đấu với người khác đúng một trận trong suốt cuộc thi đấu. Tìm số n

ẤP

lớn nhất sao cho nếu có xếp lại cuộc thi đấu (theo nguyên tắc trên) ta vẫn có thể tìm

C

được 4 người trong số 18 người tham gia, mà họ chỉ chơi đúng một trận vào lúc kết

H

Ó

A

thúc vòng đấu thứ n.

Hướng dẫn giải

-L

Í-

Câu trả lời là n = 7 Đầu tiên, ta chứng minh n = 8 không thoả mãn Thật vậy, khi

ÁN

n = 8 ta chỉ ra một sự sắp xếp để không thoả mãn như sau: Gọi A là tập con của một

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

(n

con

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

tập gồm 9 cầu thủ và B phần bù của A trong tập 9 cầu thủ đó. Lúc đó, ở 8 vòng thi khác của B. Ta chỉ cần chỉ ra rằng có một cuộc đấu gồm 2N - 1 vòng trong số 2N

đấu thủ sao cho có N trận đấu ở mỗi vòng và mỗi người đều thi đấu với người khác đúng một trận trong suốt cuộc thi đấu đó. Ta đánh số các đấu thủ là

0, 1,..., 2 N −, X . Đánh số các vòng đấu là 0, 1, 2, ..., 2 N − 2 . Giả sử hai đấu thủ

BỒ

ID Ư

Ỡ N

G

TO

đấu đầu tiên, ta có thể sắp xếp sao cho mỗi phần tử của B thi đấu với mọi phần tử

Trang 24

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

khác nhau i, j (không phải X) thi đấu ở vòng i + j (mod 2 N − 1) . Cho i và X đấu nhau ở vòng

N

2i ( mod 2 N − 1) . Dễ dàng kiểm tra rằng cách sắp xếp như vậy thoả mãn yêu cầu.

H Ơ

Bây giờ ta xét trường hợp n = 7 . Gọi S là tập hợp lớn nhất gồm các cầu thủ mà

S'

Y

TP .Q

U

Chọn A trong S' là một người đã chơi với vài đấu thủ trong S. Giả sử S =m , ta có

N

không có hai người nào trong đó đấu với nhau, gọi S' là tập hợp các đấu thủ còn lại.

= 18 − m . Ta sẽ chứng minh rằng A đã chơi nhiều nhất là với m − 2 phần

Đ

tử của s đều có chơi với các phần tử của S' nên đã có 7m trận diễn ra giữa các phần

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

tử của S và các phần tử của S'. Nếu mọi phần tử của S' đã chơi với m − 1 hay nhiều

và

các

phần

tử

của

S',

suy

ra

(18

H

S

− m )( m − 1) ≥ 7 m ,

TR ẦN

của

Ư N

hơn các phần tử của S thì có ít nhất (18 − m )( m − 1) trận diễn ra giữa các phần tử

m 2 − 12m + 18 ≤ 0 , do đó

B

m < 2 hoặc m > 10 . Rõ ràng không thể có m < 2 (vì chắc chắn có hai đấu thủ

10

ít hơn m - 2 phần tử của S'.

00

không chơi với nhau). Còn nếu m > 10 thì do A chỉ chơi có 7 trận nên anh ta đã chơi

2+

3

Vì vậy, ta có thề tìm được B và C thuộc S sao cho A không chơi với B hay C. Vì A không thuộc S và S lớn nhất như đã nói trên nên phải có D thuộc S là người đã chơi

ẤP

với A. Như thế A, B, C, D là 4 người cần tìm mà trong số họ chỉ chơi có một trận (A

A

C

với D).

Ó

Bài toán 20. 30: một cuộc họp có 12k người, mỗi người trao đổi lời chào với đúng

Í-

H

3k + 6 người khác. Với hai người bất kì nào đó, số người trao đổi lời chào với cả

-L

hai người này là giống nhau.

Hướng dẫn giải

TO

ÁN

Hỏi có bao nhiêu người tham dự cuộc họp?

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

tử của S. Giả sử điều ngược lại xảy ra. Mỗi đấu thủ đã chơi 7 trận, do tất cả các phần

BỒ

ID Ư

Ỡ N

G

Với hai người bất kì, ta gọi n là số cố định những người khác có trao đỗi lời chào với

cả hai. Xét một người đặc biệt a. Gọi B là tập hợp những người có trao đồi lời chào với a, và C là tập hợp những người không trao đổi lời chào với a. Thế thì có 3k + 6 người trong B và 9k − 7 người trong C. Với một người b bất kì trong B, thì người có trao đổi lời chào với a và b phải thuộc B. Như thế b đã trao đổi lời chào với n người trong B, và như thế với 3k + 5 − n người trong C.

Trang 25

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Với một người c bất kì trong C, người trao đồi lời chào với a và c cũng phải thuộc B. Do đó c đã trao đổi lời chào với n người trong B. Tổng số lời chào được trao đổi

N

giữa B và C được cho bởi:

Y

N

9k + 43 12k − 1

36 người tại cuộc họp.

G

Đ

Bài toán 20. 31: Trong mặt phẳng cho n đường thẳng đôi một cắt nhau nhưng không

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

cùng đi qua một điểm. Chứng minh rằng tồn tại ít nhất một điểm là giao của hai và

TR ẦN

A

C

ẤP

2+

3

10

00

B

Hướng dẫn giải

H

chỉ hai trong số n đường thẳng đó

H

Ó

Gọi a1 , a2 ,..., an là n đường thẳng đã cho. Kí hiệu giao của hai đường thẳng

Í-

ai , a j là aij . Xét các khoảng cách từ điểm a ij tới đường thẳng ak không đi qua nó. Vì

-L

số các khoảng cách đó là hữu hạn nên phải tìm được 3 đường thẳng (chẳng hạn

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

9k + 43 nhận giá trị nguyên. Vậy có tất cả 12k − 1

ẠO

Với 1 ≤ k ≤ 4 , chỉ có k = 3 làm cho số

TP .Q

Nếu k ≥ 15 thì 12k − 1 > 9k + 43 và 4m sẽ không phải là một số nguyên.

U

Suy ra n = 3m với m nguyên dương và 4m = k + 6

H Ơ

(3k + 6)(3k + 5 − n) = (9k − 7)n, hay 9k 2 − 12n + 33k + n + 30 = 0

ÁN

a1 , a2 , a3 ) sao cho khoảng cách từ điểm A1,2 tới đường thẳng a3 là ngắn nhất (hoặc

BỒ

ID Ư

Ỡ N

G

TO

một trong những khoảng cách ngắn nhất).

Ta chứng minh rằng không còn một đường thẳng thứ ba nào (khác a1 , a2 ) lại đi qua điểm A1,2 . Trước hết ta nhận thấy rằng nếu qọi H là chân đường vuông góc hạ từ

A1,2 tới a 3 thì H phải thuộc đoạn thẳng nối A1,3 và A2,3 . Thật vậy nếu H nằm ngoài đoạn thẳng đó và A2,3 gần H hơn A1,3 thì rõ ràng khoảng cách từ A2,3 tới A1 còn nhỏ hơn A1,2 H .

Trang 26

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Bây giờ giả sử rằng qua A1,2 còn có đường thẳng a 4 . Khi đó a 4 phải cắt a, tại một điểm A3,4 , điểm này phải nằm trên một trong hai tia có gốc H của đường thẳng a 3 .

H Ơ

N

Giả sử nó nằm trên tia chứa điểm A2,3 thì rõ ràng khoảng cách từ A2,3 tới a 2 nhỏ

ẠO

Hướng dẫn giải

Đ

Gọi các đỉnh của đa giác đều đã cho là A 1 A 2 , ..., A2007

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

Chú ý rằng tứ giác (tạo nên từ 4 trong số các đỉnh của đa giác) có 3 cạnh là 3 cạnh

Ư N

của đa giác khi và chỉ khi 4 đỉnh của tứ giác đó là 4 đỉnh liên tiếp của đa giác.

TR ẦN

H

Gọi A là tập các đỉnh: [ A1 , A2 , A3 , A5 , A6 , A7 ,..., A2003 , A2006 ]

(bỏ đi các đỉnh A4i , i = 1,...501 và A2007 ). Hiển nhiên A = 1505 và trong A không chứa 4 đỉnh liên tiếp nào của đa giác. Dễ thấy, mọi tập con của A đều không chứa 4

00

B

đỉnh liên tiếp của đa giác. Vậy k ≥ 1506 . Ta sẽ chứng minh mọi cách chọn 1506

10

đỉnh tuỳ ý của đa giác thì sẽ tồn tại 4 đỉnh liên tiếp của đa giác trong 1506 đỉnh đó.

2+

3

Thật vậy, giả sử T là một tập gồm 1506 đỉnh tuỳ ý của đa giác. Phân hoạch tập các đỉnh của đa giác thành các tập hợp.

{ A5 , A6 , A7 , A8 } ;....

ẤP

{ A1 , A2 , A3 , A4 } ; B2

=

C

B1 =

Ó

A

B501 = { A2001 , A2002 , A2003 , A2004 } ; B502 = { A2005 , A2006 , A2007 }

H

Giả sử T không chứa 4 đỉnh liên tiếp của đa giác. Lúc đó với mỗi i = 1,..., 501 , tập

-L

Í-

Bi không thuộc T, tức là mỗi tập Bi đó sẽ có ít nhất một đỉnh không thuộc T. Khi

ÁN

đó T ≤ 3 x 502 = 1506 . Do T = 1506 nên B502 ⊂ T và mỗi tập Bi ( i=1,501) ó đúng

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

một tứ giác lồi mà 3 trong số 4 cạnh của nó là 3 cạnh của đa giác đã cho.

TP .Q

U

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

Y

Bài toán 20. 32: Cho một đa giác đều 2007 đỉnh. Tìm số nguyên dương k nhỏ nhất thoả

N

hơn A1,2 H . Vô lý!.

TO

3 phần tử thuộc T.

⇒ A2 , A3 , A4 ∈ T ⇒ A5 ∉ T ⇒ A6 , A7 , A ∈ T ⇒ A2002 , A2003 , A2004 ∈ T

Khi đó 4 đỉnh liên tiếp A2002 , A2003 , A2004 , A2005 thuộc T, mâu thuẫn Vậy k = 1506

BỒ

ID Ư

Ỡ N

G

Ta có A2005 , A2006 , A2007 ∈ T suy ra Ai ∉ T

Trang 27

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Có thể giải ngắn gọn hơn bằng cách xét 2007 − 1506 = 501 điểm còn lại chia đường tròn ngoại tiếp đa giác đều đã cho không quá 501 cung, và phải có một cung

N

1506 > 3 đỉnh liên tiếp. 501

H Ơ

trong chúng chứa không ít hơn

N

Bài toán 20. 33: Có bao nhiêu cách tô màu đỏ cho 16 khối lập phương đơn vị của khối

Y

lập phương 4 x 4 x 4 , sao cho mỗi khối 1 x 1 x 4 (và mỗi khối 1 x 4 x 1 hay

TP .Q

U

4 x 1 x 1 ) có chứa đúng một khối lập phương đơn vị màu đỏ? Hướng dẫn giải

ẠO

Mấu chốt của vấn đề là chứng tỏ tồn tại một song ánh giữa tập các sắp xếp chấp

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

và mỗi hàng hoặc mỗi cột đều có chứa đựng n phần tử này).

G

hình vuông n x n ô được gọi là một hình vuông Latin nếu nó chứa n phần tử a1 ,...,a n

H

Ở mặt đỉnh của khối lập phương, ta viết các sổ 1, 2, 3 hoặc 4 lên mỗi hình vuông

TR ẦN

(của mặt đỉnh này) tuỳ theo khoảng cách đến khối đơn vị có màu đỏ tính từ trên xuống. Chú ý rằng dưới mỗi hình vuông (trên mặt đỉnh) chắc chắn có ít nhất một

B

khối đơn vị màu đỏ. Có 16 hình vuông, và chỉ có 16 khối đơn vị đó, do đó chắc chắn

00

trong mỗi cột có đúng một khối đơn vị đỏ. Bây giờ, phải có một số 1 trong mỗi hàng

10

của mỗi hình vuông, vì nếu không thì sẽ không có khối đơn vị đỏ nào trong khối cột

2+

3

1 x 1 x 4 tương ứng. Tương tự như thế, phải có các số 2, 3 và 4. Như vậy, mỗi hàng

ẤP

phải là một hoán vị của 1, 2, 3, 4. Lí luận tương tự cho mỗi cột. Do đó, hình vuông

C

(trên mặt đỉnh) phải là hình vuông Latin. Đảo lại, một hình vuông Latin cũng tương

A

ứng với một sắp xếp chấp thuận được.

H

Ó

Như thế, việc còn lại là tính xem có bao nhiêu hình vuông Latin 4 x 4 như thế. Dễ

BỒ

ID Ư

Ỡ N

G

TO

ÁN

-L

Í-

thấy có đúng 4 hình vuông theo mẫu như hình bên trái, đó là:

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

nhận được (tức là thoả mãn yêu cầu đề bài) và tập các hình vuông Latin 4 x 4 (Một

Đến đây, có thể tiếp tục lí luận dựa trên các hoán vị để chứng tỏ có tất cả

4 x 24 x 6 = 576 khả năng sắp xếp một hình vuông Latin.

Bài toán 20. 34: Cho tam giác ABC. Nếu ta sơn các điểm của mặt phẳng bằng hai màu xanh và đỏ, hãy chứng minh rằng hoặc là tồn tại hai điểm màu đỏ có khoảng cách

Trang 28

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

bằng một đơn vị, hoặc là tồn tại ba điểm màu xanh tạo thành một tam giác bằng tam giác ABC.

N

Hướng dẫn giải

H Ơ

Ta sẽ gọi một đa giác là đa giác xanh (tương ứng, đỏ) nếu nó có tất cả các đỉnh

TP .Q

U

ứng, đỏ).

Y

(tương ứng, đỏ) nếu đoạn thẳng đó có hai điểm đầu mút cùng màu xanh (tương

N

cùng màu xanh (tương ứng, đỏ) ta cũng gọi một đoạn thẳng là đoạn thẳng xanh

Giả sử ngược lại rằng không tồn tại hai điểm màu đỏ có khoảng cách bằng một đơn

ẠO

vị và cũng không tồn tại ba điểm màu xanh tạo thành một tam giác bằng tam giác

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

giả sử rằng: a ≤ b, c. .

Ư N

Đầu tiên ta sẽ chứng minh rằng không có đoạn thẳng đỏ nào có độ dài a cả.

H

Thật vậy, giả sử XY là một đoạn thẳng đỏ có độ dài a, khi đó, các đường tròn đơn vị

TR ẦN

nhận X, Y làm tâm sẽ hoàn toàn màu xanh. Gọi Z là điểm sao cho ∆XYZ = ∆ABC (viết theo các đỉnh tương ứng). Khi đó, đường tròn đơn vị tâm z phải có toàn màu

B

đỏ, vì nếu không thì z màu xanh và tam giác XYZ là tam giác xanh bằng ∆ABC ,

00

mâu thuẫn với giả thiết (*). Trên đường tròn đơn vị này chắc chắn có hai điểm màu

10

đỏ có khoảng cách bằng một đơn vị, vô lí.

2+

3

Bây giờ, toàn mặt phẳng không thể màu xanh, nên có một điểm nào đó màu đỏ mà ta

ẤP

gọi là R. Đường tròn (T) có tâm R và bán kính a phải toàn màu xanh. Khi đó, lấy hai

C

điểm D và E trên (T) sao cho DE = a . Vì a ≤ b, c nên ta có thể dựng điểm F nằm

Ó

A

ngoài (T) sao cho ∆DEF = ∆ABC (viết theo các đỉnh tương ứng), điểm F phải có

H

màu đỏ. Như vậy, nếu ta quay DE quanh R, thì điểm F sẽ vạch nên một đường tròn

Í-

bán kính lớn hơn a và có toàn màu đỏ, trên đường tròn này ta có thể tìm được hai

-L

điểm màu đỏ có khoảng cách a, mâu thuẫn với chứng minh trên. Như vậy, giả thiết

ÁN

(*) là sai và ta có điều phải chứng minh.

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

ABC (*) Kí hiệu a, b, c là ba cạnh của tam giác ABC, không mất tính tổng quát, ta

BỒ

ID Ư

Ỡ N

G

TO

Bài toán 20. 35: Tìm số nguyên dương n bé nhất ( n > 3) thoả mãn tính chất sau: Với n điểm đôi một phân biệt, thẳng hàng và A1 A2 = A2 A3 = ... = An -1 An thì mọi cách tô

màu n điểm đó bằng đúng 2 màu khác nhau đều tồn tại 3 điểm Ai , Aj , A2 j -1 (với

1 ≤ i < 2 j − 1 ≤ n ) được tô cùng một màu.

Hướng dẫn giải Giả sử ta dùng 2 màu là xanh kí hiệu là (X) và đỏ kí hiệu là (Đ)

Trang 29

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Bổ đề: Với n điểm đã cho cùa đề bài, nếu ta đặt chúng trên một trục toạ độ x'Ox sao cho điểm Ak có toạ độ bằng k. Vậy: 3 điểm Ai , Aj , A2 j -1 được tô cùng một màu

N

khi và chỉ khi toạ độ của 3 điểm trên theo thứ tự lập thành một cấp số cộng.

H Ơ

a) Ta chứng minh: Với n = 8 (và từ đó ∀n ≤ 8 ) thì tồn tại cách tô màu 8 điểm

Y U

TP .Q

Thật vậy: Ta chỉ việc tô các điểm A1 , A1 , A5 , A6 cùng màu (X) và tô các điểm

N

A1 , A2 , ..., A8 sao cho không có 3 điểm Ai , Aj , A2 j -1 nào được tô cùng màu.

A3 , A4 , A7 , A8 cùng màu (Đ) ⇒ đpcm.

Đ

đúng 2 màu khác nhau đều tồn tại 3 điểm Ai , Aj , A2 j -i (với 1 ≤ i < 2 j - 1 ≤ 9 )

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

được tô cùng một màu. Thật vậy, Giả sử trái lại rằng: tồn tại cách tô màu 9 điểm

H

trên sao cho mọi bộ 3 điểm Ai , Aj , A2 j -i (với 1 ≤ i < 2 j - i ≤ n ) đều bị tô khác

TR ẦN

nhau. Khi đó, vận dụng Bồ đề trên, ta suy ra rằng: với mỗi chỉ số k ∈ {3, 4, 5} thì các điểm Ak và Ak + 2 phải được tô khác màu (vì: nếu điểm Ak và Ak + 2 được tô

00

B

cùng màu chẳng hạn là màu (X) thì ta cổ thể tô cậc điểm Ak + 2 , Ak +1 , Ak + 4 cùng màu

10

(Đ), điều này lại trái với điều giả sử trên). Không mất tính tổng quát ta có thể giả

3

sử tô A3 màu (Đ) ⇒ A5 màu (Đ) và do đó A7 cùng màu (Đ). Vì 3, 4, 5 là cấp số

2+

cộng ⇒ A4 màu (X) và do đó A6 cũng màu (X). Vì 4, 6, 8 là cấp số cộng

C

ẤP

⇒ A8 màu (Đ). Vì 7, 8, 9 là cấp số cộng => A9 màu (X). Vì 1, 3, 5 là cấp số cộng

A

⇒ A1 màu (X). Vì 2, 5, 8 là cấp số cộng ⇒ A2 màu (X). Vậy 3 điểm

H

Ó

A 2 , A 4 , A 6 lại cùng màu (X), trái với điều giả sử trên.

Í-

Vậy số n phải tìm là n = 9.

-L

Bài toán 20. 36: Cho G tà một đồ thị liên thông gồm k cạnh. Chứng minh rằng có thể

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

b) Ta phải chứng minh: Với n = 9 thì mọi cách tô màu 9 điểm: A1 , A2 , ..., A9 bằng

BỒ

ID Ư

Ỡ N

G

TO

ÁN

đánh số các cạnh bằng tất cả các số 1, 2, 3,..., k sao cho tại mỗi đỉnh thuộc về ít

nhất hai cạnh của đồ thị, ta đều có ước số chung lớn nhất của các số nguyên viết trên các cạnh của đỉnh này bằng 1.

Hướng dẫn giải Ta bắt đầu tại một đỉnh v0 nào đó. Hãy tưởng tượng rằng ta đang đi dọc theo các cạnh phân biệt của đồ thị, vừa đi vừa đánh số chúng như ta đang đếm: 1, 2, 3,..., cho đến khi ta không thể đi xa hơn được nữa vì nếu muốn đi thêm phải dừng lại một cạnh đã đi qua.

Trang 30

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Nếu có những cạnh không được đánh số thì một trong những cạnh này phải có một đỉnh ta đã đi qua, vì G liên thông. Hãy khởi đầu từ đỉnh này, ta tiếp tục đi dọc theo

N

các cạnh chưa dùng tới, đánh số lại nơi ta đi qua, và tiếp tục như thế cho đến khi

H Ơ

một lần nữa ta không thể đi xa hơn. Quá trình này được lặp lại cho đến lúc tất cả

TP .Q

U

tại mỗi đỉnh thuộc về ít nhất hai cạnh của đồ thị, ta đều có ước số chung lớn nhất

Y

Bây giờ, ta sẽ chứng minh rằng việc đánh số như trên thoả mãn điều kiện ở đề bài:

N

các cạnh đều được đánh số.

của các số nguyên viết trên các cạnh của đỉnh này bằng 1.

Đ

Nếu v = v0 , tức V là đỉnh xuất phát, thì một trong các cạnh chứa đỉnh V đã được

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

đánh số 1, do đó hiển nhiên ta có ước số chung lớn nhất của các số nguyên viết trên

H

TR ẦN

đường đi là vào lúc cuối của cạnh được đánh số r.

Ư N

các cạnh của đỉnh V này bằng 1. Nếu v ≠ v0 , giả sử lần đầu tiên ta đánh số V trên Vào lúc đó, có nhiều hơn 1 cạnh chưa sử dụng tại đỉnh V, một trong những cạnh này được đánh số r + 1 . Do đó, ước số chung lớn nhất của các số nguyên viết trên

00

B

các cạnh của đỉnh V này bằng 1, vì các cạnh này có chứa r và r + 1 . Suy ra điều

10

phải chứng minh.

3

Bài toán 20. 37: Cho G là một đồ thị đơn (G không chứa khuyên và không có hai cạnh

2+

khác nhau nào nối cùng một cặp đỉnh), có hữu hạn đỉnh. Mỗi đỉnh của G sẽ được tô

ẤP

chỉ một trong hai màu đen hoặc trắng. Giả sử ban đầu tấu cả các đỉnh của G đều có

C

màu đen. Ta được phép thực hiện nhiều lần thao tác: chọn một đỉnh P tùy ý của G

Ó

A

rồi đổi màu của P và của mọi đỉnh kề với P (hai đỉnh được gọi là kề nhau nếu

H

chúng được nối với nhau bởi một cạnh).

-L

Í-

Hỏi: sau một số hữu hạn lần thực hiện các thao tác như vậy, ta có thể đổi màu của

Hướng dẫn giải

Giả sử G = (V , E ) . Ta sẽ chứng minh bằng quy nạp theo n = V rằng: sau một

số hữu hạn lần thực hiện (các) thao tác như đề toán cho phép, ta có thể đỗi màu của tất cả các đỉnh của đồ thị đã cho sang trắng. Đpcm rõ ràng là đúng khi n = 1 .

Giả sử n ≥ 2 và đpcm đã đủng cho mọi đồ thị với số đỉnh là n -1

BỒ

ID Ư

Ỡ N

G

TO

ÁN

tất cả các đỉnh của G sang trắng hết được hay không?

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Thật vậy, gọi V là một đỉnh như thế (v thuộc về ít nhất hai cạnh của đồ thị).

Trang 31

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Xét một đồ thị G = (V , E ) với

{P1 , P2 ,..., Pn } ;

V = n, V =

mỗi đỉnh

Pi ( (1 ≤ i ≤ n ) đang được tô đen. Gọi f i (1 ≤ i ≤ n ) là thao tác “cơ sở”: đổi màu

H Ơ

N

của Pi và của mọi đỉnh kề với Pi trong G.

N

Ta sẽ chứng minh rằng tồn tại một dãy g gồm một số hữu hạn các thao tác cơ sở fi

U

Y

mà “hợp thành” của chúng đổi được màu pủa mọi đỉnh của G. (1)

TP .Q

Xét các đồ thị Gi = (Vi , Ei ) với tập đỉnh Vi = V \ { Pi } tập cạnh Ei của G i thu được từ tập cạnh E của G bằng cách bỏ đi các cạnh có một trong hai đầu mút là

G

Đ

thao tác cơ sở trong Gị mà hợp thành của chúng đổi được màu của mọi đỉnh của

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G i suy ra: tồn tại một dãy gi (1 ≤ i ≤ n ) gồm một số hữu hạn các thao tác cơ sở

H

f j ( j ≠ i ) trong chính G (như đã vừa được giới thiệu ở trên) mà hợp thành của

TR ẦN

chúng đổi được màu của tất cả các đỉnh của G, “không kể” đỉnh Pi . Nếu một trong n dãy g i có hợp thành (của các thao tác “thành phần” trong nó) đỗi được màu của

00

B

cả đỉnh Pi ( thì chỉ cần lấy g = g i đó ta có ngay (1).

10

Giả sử: mọi dãy gi (1 ≤ i ≤ n ) đều có hợp thành không đổi được màu của đỉnh Pi

2+

3

(2)

Với n chẵn: lấy g =

( g1 , g 2

C

−

ẤP

Xét hai trường hợp :

,..., g n ) : nghĩa là, g là dãy gồm tất cả các thao tác

Ó

A

thành phần liên tiếp trong gr ròi các thao tác thành phần liên tiếp trong g 2 , .... cuối

Í-

H

cùng là các thao tác thảnh phần liên tiếp trong g n . Do (2) và do n − 1 lẻ, dễ thấy g Với n lẻ: trong trường hợp này, từ Bổ đề Bắt tay suy ra G có ít nhất một đỉnh bậc

BỒ

ID Ư

Ỡ N

G

TO

ÁN

−

-L

thỏa (1).

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Pi (1 ≤ i ≤ n ) . Theo giả thiết quy nạp, với mỗi1 ≤ i ≤ n , tồn tại một dãy hữu hạn các

chẵn; không mất tính tổng quát, giả sử đó là đỉnh P1 và tất cả các đỉnh kề với đỉnh

P1 gồm các đỉnh P2 , P3 , ..., P2 k +1 . Lấy g = ( f1, g1 , g 2 ,..., g 2 k +1 ) ; do (2), dễ thấy g thỏa (1). Vậy (1) luôn đúng. Theo nguyên lý quy nạp đpcm đúng cho mọi n.

Bài toán 20. 38: Cho 21 điểm nằm trên đường tròn. Chứng minh rằng có ít nhất 100 cung được xác định bởi các cặp điểm trong các điểm đã cho được nhìn từ tầm dưới một góc không vượt quá 120°.

Trang 32

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com Hướng dẫn giải

Bổ đề: Cho graph G và A, B, c là 3 đỉnh của G sao cho 2 trong số 3 đỉnh đều được nối

N

với nhau bởi 1 cạnh thì tập hợp gồm 3 đỉnh A, B, c và 3 cạnh AB, AC, BC là một

H Ơ

tam giác của G. số tam giác của graph G được kí hiệu là t(G).

TP .Q

U

Y

 n2  của graph G ≤   4

N

Khi đó ta có Định lí Turan : Nếu graph G có n đỉnh và t ( G ) = 0 thì số cạnh

Chứng minh: Gọi A là đỉnh của G có bậc lớn nhất, là k. Gọi B1 , B2 ,...,Bk là các

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Rõ ràng rằng không có cạnh nào nối Bi và Bk , bởi vì ngược lại ta có tam giác tạo

H

thành, trong G' chỉ đếm được tất cả các cạnh nối từ n − k − 1 các đỉnh của G

G ' ≤ ( n − k − 1) k .

TR ẦN

(trừ AB1 , B2 ,...,Bk ) vì bậc cao nhất của các đỉnh là k nên số cạnh của số

cạnh

của

n2 (đpcm). 4

00

(n − k ) k ≤

10

G ≤ ( n − k − 1) k + k =

đó

B

Do

3

Áp dụng vào bài : Từ 21 điểm ta có tất cả C221 = 210 cung. Đếm tất cả các cung

2+

không vượt quá 180° và đầu mút là 2 trong số 21 điểm đã cho. Nối 2 điểm nào đó

ẤP

bởi 1 cạnh, xác định cung có số đo > 120°. Xét tất cả các cạnh trên tạo thành 1

C

graph G (có các đỉnh từ 21 điểm đã cho). Không có tam giác nào trong G (nếu

Ó

A

ngược lại sẽ có 1 tam giác có tổng lớn hơn 180°) theo định lý Turan có không

-L

Í-

H

 212  nhiều hơn   cạnh nên phải có ít hơn 210 − 110 = 100 cung không vượt quá  4 

ÁN

120°.

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ G

phát từ A. Khi đó số cạnh của G = k + số cạnh của G'.

ẠO

đỉnh được nối với A. G' là graph nhận được từ G bằng cách bỏ A và các cạnh xuất

BỒ

ID Ư

Ỡ N

G

TO

Bài toán 20. 39: Cho trước một số số tự nhiên được viết trên một đường thẳng. Ta thực hiện các bước điền số trên đường thẳng như sau: tại mỗi bước, xác định tất cả các cặp số kề nhau hiện có trên đường thẳng theo thứ tự từ trái qua phải, sau đó điền vào giữa mỗi cặp một số bằng tổng của hai số thuộc cặp đó. Hỏi sau 2013 bước, số 2013 xuất hiện bao nhiêu lần trên đường thẳng trong các trường hợp sau: a) Các số cho trước là 1 và 1000? b) Các số cho trước là 1, 2, ..., 1000 và xếp theo thứ tự tăng dần từ trái qua phải?

Trang 33

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com Hướng dẫn giải

a) Ta chứng minh có đúng hai số 2013 trong dãy nhận được sau 2013 lần thực

N

hiện. Chú ý ta chỉ quan tâm đến số lần xuất hiện của 2013 nên khi có 2 số đứng kề

H Ơ

nhau mà tổng các số đều lớn hơn 2013 hoặc các số đã xuất hiện từ trước đó rồi thì

N

1,1000

Sau bước 1

1,1001,1000

Sau bước 2

1,1002,1001,2001,1000

Sau bước 3

1,1003,1002,2003,1001,3002,2001,3001,1000

Ta chỉ giữ lại 4 số đầu

1,1003,1002,2003

Sau bước 4

1,1004,1003,2005,...

Sau bước 5

1.1005, 1004,2007,...

Sau bước 6

1.1006, 1005,2009,...

Sau bước 7

1.1007, 1006,2011,...

Sau bước 8

1 1008 1007 2013 ...

B

Sau bước 8 số 2013 xuất hiện lần đầu. Sau đó trừ tổng của cặp đầu bé hơn 2013

00

còn tổng các cặp còn lại đều lớn hơn 2013. Hơn nữa, sau mỗi lần thực hiện thì số

3

2+

đó sẽ không có số 2013 nữa.

10

thứ 2 trong dãy tăng đúng 1 đơn vị nên sau 1013 bước thì số thứ 2 đó là 2013 và từ

ẤP

b) Ta chứng minh có đúng 1198 số 2013 trong dãy nhận được sau 2013 lần thực

H

Ó

A

3. BÀI LUYỆN TẬP

C

hiện bằng cách chuyển thao tác trên đường thẳng về trên đường tròn.

Í-

Bài tập 20.1: Cho số nguyên dương n, tính tổng an =

 n +1   2   

∑C

i n -i +1

-L

i=0

ÁN

Hướng dẫn

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

H

Ư N

G

Đ

ẠO

TP .Q

U

Y

Dãy ban đầu

TR ẦN

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

ta không cần liệt kê nữa.

BỒ

ID Ư

Ỡ N

G

TO

Chứng minh an = an-1 + an + 2 n

5 + 3 5  1+ 5  5 − 3 5 1 − 5  Kết quả   +   10  2  10 2  

n

Bài tập 20. 2: Cho S = {1, 2, 3..., 280} . Tìm số tự nhiên n nhỏ nhất sao cho mọi tập hợp con gồm n phần tử của s đều chứa 5 số đôi một nguyên tố cùng nhau.

Hướng dẫn Đếm số các bội của 2, 3, 5, 7 . Kết quả n = 217.

Trang 34

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Bài tập 20. 3: Một hoán vị { x1 , x2 , ..., x2 n } của tập hợp

{1, 2,...,2n} được gọi là có tính

chất p, trong đó n là một số nguyên dương, nếu xi − xi +1 = n với ít nhất một i

H Ơ

N

thuộc {1, 2,..., 2n − 1} . Chứng minh rằng với mỗi n, số các hoán vị có tính chất p

Hướng dẫn

1 ( 2n ) ! 2

ẠO

không toàn ánh. Hoặc chứng minh: A >

TP .Q

U

Lập ánh xạ f từ tập không có tính chất P vào tập có tính chất P, chứng minh f

Y

N

lớn hơn số các hoán vị không có tính chất đó.

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

G

của tập {1, 2,...,1998} . Với mọi k thuộc S (tức là k là một n-bộ như trên), ta gọi

Ư N

f(k) là số tất cả các phần tử trong hội của n tập hợp của k. Tìm tồng tất cả các f(k)

Hướng dẫn

TR ẦN

H

khi k chạy trong khắp S.

X i là một tập con của tập {1, 2, 3 , m} thì tổng cần tính là

2 n +1

10

 1 Bài tập 20. 5: Chứng minh 7 < 1 +   n

00

B

s(n, m) = m(2nm − 2n ( m-1) ).

2+

3

≤ 8 ,n là nguyên dương.

2 n +1

C

Chứng minh: ak < ak -1 thì được an ≤ 8

A

 1 Đặt an = 1 +   n

ẤP

Hướng dẫn

2

m

H

Ó

Và chứng minh: (1 + a ) ≥ 1 + ma + ( m − 1) a 2

Í-

Bài tập 20. 6: Có 9 em học sinh cùng đi một chuyến tàu. Mỗi em chọn tuỳ ý và ngẫu

-L

nhiên một trong 3 toa tàu đã định.

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

Bài tập 20. 4: Gọi s là tập hợp tất cả các n-bộ ( X 1 , X 2 ,..., X n ) với mỗi X i là một tập con

BỒ

ID Ư

Ỡ N

G

TO

ÁN

a) Tìm xác suất để toa đầu có 3 em;

b) Tìm xác suất để một trong 3 toa có 4 em, một toa nữa có 3 em và toa còn lại có

2 em

Hướng dẫn a) Không gian mẫu có số phần tử 93 . Kết quả P1 = b) Kết quả F2 =

5376 1792 = 19683 6561

280 729

Trang 35

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Bài tập 20. 7: Ba kì thủ dự giải cờ đấu vòng tròn theo cách thức như sau: đầu tiên A đấu với B, người thắng sẽ đấu với c, tiếp theo người thắng mới sẽ đấu với người đã

N

thua.v.v. Giải sẽ kết thúc nếu có ai đó thắng liên tiếp hai ván. Tính xác suất thắng

H Ơ

cuộc của mỗi kì thủ nếu tất cả đều ngang tài và tính xác suất thắng cuộc của mỗi kì

N

thủ nếu ván đầu tiên A thắng.

U

5 5 4 4 2 1 . . và . . 14 14 14 7 7 7

TP .Q

Kết quả

Y

Hướng dẫn

mãn các điều kiện:

G

Đ

(i) Không có 3 điểm nào trong S thẳng hàng.

Ư N

1 + 2n 2

H

Chứng minh rằng k <

Hướng dẫn

TR ẦN

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

(ii) Với mọi điểm P thuộc S, tồn tại ít nhất k điểm trong S cách đều P.

B

Dùng phản chứng và nguyên tắc Dirichlê. Để ý: nCk2 > 2.Cn2

00

Bài tập 20. 9: Trên một bảng vuông 5 x 5 ô, hai người chơi trò chơi thay nhau đánh số

10

lên các ô vuông. Người thứ nhất luôn đánh số 1, còn người thứ hai luôn đánh số 0.

2+

3

Mỗi lượt, mỗi người đánh một số, cho đến khi không còn ô để đánh nữa. Sau đó,

ẤP

họ tính tổng các số trên các hình vuông 3 x 3 (trong bảng vuông 5 x 5 ô đó). Gọi A

C

là số lớn nhất trong các tổng này. Hỏi người thứ nhất có thể làm cho A lớn đến bao

Hướng dẫn

H

Ó

A

nhiêu, bất chấp người thứ hai đánh như thế nào?

Í-

Sử dụng tính đối xứng của bảng vuông. Kết quả A = 6

-L

Bài tập 20. 10: Các tấm thẻ có ghi số từ 1 đến 9 được sắp xếp ngẫu nhiên thành hàng.

ÁN

Trong mỗi nước đi, ta có thể chọn một khối tuỳ ý các tấm thẻ liên tiếp sao cho số

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

ẠO

Bài tập 20. 8: Cho n và k là các số nguyên dương, s là tập n điểm trong mặt phẳng thoả

BỒ

ID Ư

Ỡ N

G

TO

ghi trên chúng là theo thứ tự tăng dần hay giảm dần rồi xáo lộn vòng chúng. Chẳng

hạn 916532748 có thể xáo đổi thành 913562748. Chứng minh rằng trong không quá 12 nước đi, ta có thể sắp xếp 9 tấm thẻ này sao cho số của chúng được sắp theo thứ tự tăng dần hay giảm dần.

Hướng dẫn Gọi f(n) là giá trị lớn nhất của số nước đi bé nhất cần đến để sắp thứ tự các hoán vị. Chứng minh f ( n ) ≤ f ( n − 1) + 2

Trang 36

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial

www.twitter.com/daykemquynhon https://plus.google.com/+DạyKèmQuyNhơn

www.facebook.com/daykem.quynhon www.daykemquynhon.blogspot.com

Bài tập 20. 11: Trên một bàn người ta dán 2015 hình tròn có bán kính bằng nhau sao cho không có hai hình nào giao nhau. Chứng minh rằng với 4 màu khác nhau ta có thể

N

tô các hình tròn (mỗi hình tròn được tô bởi một màu) sao cho các hình tròn tiếp xúc

H Ơ

nhau được tô bởi các màu khác nhau Chứng minh qui nạp theo số các hình tròn.

TP .Q

U

Bài tập 20. 12: Ta gọi một hội −S là một tập hợp S người sao cho mỗi cặp hai người nào

Y

N

Hướng dẫn

trong họ cũng có quen nhau. Trong một buổi tiệc, cứ hai hội − 3 thì có chung một

ẠO

người, và không có hội − 5 nào trong buổi tiệc này. Chứng minh rằng trong buổi

G

nào cả.

Ư N

www.daykemquynhon.ucoz.com MailBox : nguyenthanhtuteacher@hotmail.com

Hướng dẫn

H

Sử dụng đồ thị với đỉnh là người dự và cạnh nối 2 đỉnh nếu 2 người tương ứng

BỒ

ID Ư

Ỡ N

G

TO

ÁN

-L

Í-

H

Ó

A

C

ẤP

2+

3

10

00

B

TR ẦN

quen nhau.

Tài liệu bồi dưỡng học sinh giỏi - Tác giả : Lê Hoành Phò

Đ

tiệc đó có hai người (hoặc ít hơn) mà khi họ rời đi thì sẽ không còn lại một hội − 3

Trang 37

Đóng góp PDF bởi GV. Nguyễn Thanh Tú

www.facebook.com/daykemquynhonofficial www.facebook.com/boiduonghoahocquynhonofficial