Chuyên đề bồi dưỡng HSG Toán 11 Đại số tổ hợp (có lời giải)

Bài 1. Gọi f (n) là số cách chọn các dấu cộng,trừ đặt giữa biểu thức: E = 1   2 ... n = n sao cho E 0 n .Chứng minh rằng: a)
f (n) = 0 khi n 1, 2(m d 4 o ) ( n   2 ) 1 n +  n  
b) Khi n  0,3(m d 4 o ) ta có  2
 f (n)  2 − 2  2 Hướng dẫn giải
a) Giả sử tồn tại một cách đặt dấu +,- với n  1, 2(m d 4 o ) để E = 0 n . ( n n +1)
Khi đó 1+ 2 + ... + n là số chẵn,vì vậy  0( d
mo 2)  n  0,3(mod 4) ,trái với n 1, 2(mod 4) 2
.Vậy giả sử là sai,ta có điều cần chứng minh.   1 n +  n   b)Ta chứng minh :  2 f ( ) n  2 − 2  ,thật vậy: 1
Chia tất cả các biểu thức thành 2n− cặp theo dạng:
(1+ 2a + 3a + ...+ na ;-1+ 2a + 3a +...+ na ) với a bằng 1 hoặc 1 − 2 3 n 2 3 n i 1 − Nếu ( )  2n f n
thì theo nguyên lý Dirichlet tồn tại 2 biểu thức cùng nằm trong một cặp như trên,hiệu
của chúng bằng 2 .Do đó chúng không thể cùng bằng 0 được (mâu thuẫn !)   1 n +  − − Do đó n 1 n n 1 n  2 f ( ) n  2 = 2 − 2  2 − 2  (1) ( n 2 )
Ta chứng minh f (n)  2
Xét biểu thức E ,gọi A là tập hợp các số xuất hiện trong E với dấu + ở trước n n n n (n + ) 1
Nếu E = 0 thì tổng các phần tử của A là .Ta định nghĩa A n n + như sau: 4 n 4
Nếu 1 A thì A
= A \{1}{n + 2,n + 4} n + ; 4 n n
Nếu 1 A thì chọn A
= A {1,n +1,n +3} n + 4 n n
Nếu 2  A thì chọn A
= A \{2}{n +3,n + 4} n + 4 n n
Nếu 2  A ta chọn A
= A {2,n +1,n + 2} n + 4 n n
Như vậy với mỗi cách chọn A ta có thể xây dựng ít nhất 4 tập A n n+ 4
Giả sử cho trước tập A A
A và thêm đúng một cặp trong tập n+ .Ta thấy tập 4 n+
được xây dựng từ tập 4 n
n +1;n + 2;n +3;n + 
4 và A chứa đúng một cặp như thế. n
Do đó ta có thể chỉ ra 6 trường hợp khi xây dựng A
A là duy nhất.Do đó ánh xạ từ n+
từ đó xác định được 4 n A vào A n n+ là đơn ánh. 4
Mặt khác với mỗi A xác định được duy nhất một E ,với mỗi E cũng xác định được duy nhất A n n n n
Do đó f (n + 4)  4 f (n).Ta có f (3) = f (4) = 2 . + k ( )4k 3 2 2
Suy ra: f (4k + 3) = f (4k −1+ 4)  4 f (4k −1)  4 f (4k − 5)  ...  4 f (3) = 2 k− k− ( )4k 2 2 1 1
f (4k)  4 f (4k − 4)  4 f (4k −8)  ...  4 f (4) = 2.4 = 2 ( n 2 )
Vì vậy: f (n)  (2) 2
Bài 2. Giả sử a , a ,..., a là các số thực cho trước. Chứng minh luôn có một số thực x sao cho tất cả các số 1 2 n
a + x, a + x,..., a + x đều là số vô tỷ. 1 2 n Hướng dẫn giải
Giả sử t là số vô tỉ bất kì. Ta sẽ chứng minh trong các số t, 2t,..., (n + )
1 t sẽ có một số thỏa mãn.
Giả thiết phản chứng là không có số nào trong các số trên thỏa mãn. Lập bảng (n + ) 1 xn như sau: t + a t + a t + a 1 2 n 2t + a 2t + a 2t + a 1 2 n (n + ) 1 t + a
n +1 t + a
n +1 t + a 1 ( ) 2 ( ) n
Có n +1 hàng và n cột. Theo giả thiết phản chứng thì trong mỗi hàng có ít nhất một số hữu tỉ nên có ít nhất
n +1 số hữu tỉ trong bảng. Vì có n cột nên có một cột chứa hai số hữu tỉ. Khi đó hiệu của chúng là số hữu tỉ. Vô lí.
Bài 3. Trên mặt phẳng có 25 điểm, không có 3 điểm nào trong chúng thẳng hàng. Tìm số màu k nhỏ nhất
sao cho ta có thể tô màu tất cả các đoạn thẳng nối hai điểm trong mặt phẳng bởi k màu ( mỗi đoạn thẳng được
tô đúng một màu) và các cạnh của một tam giác bất kì tạo bởi 2 điểm trong chúng được tô bởi đúng hai màu. Hướng dẫn giải
Dùng định lí Ramsey chứng minh được: Tô màu các cạnh của đồ thị K ( đồ thị đầy đủ 17 đỉnh) 17
bằng 3 màu một cách tùy ý thì luôn có một K có ba cạnh cùng màu. ( trong các cuốn sách về đồ thị đều trình 3
bày chứng minh, học sinh phải chứng minh lại). Khi đó k  4.
Ta đi chứng minh: bằng 4 màu ta có thể tô được các cạnh của K thỏa mãn bài ra. 25
Thật vậy, chia 25 điểm thành 5 tập hợp 5 điểm A , A . Trong mỗi A lấy các đỉnh trên một ngũ giác đều. 1 5 i
Cạnh của ngũ giác con này tô màu 1 và các đường chéo của nó tô màu 2.
Sau đó mỗi tập hợp A coi là đỉnh một ngũ giác và thực hiện việc tô màu nối các đoạn thẳng của các nhóm i
A , A cũng theo cách tương tự với 2 màu còn lại. Ta đi chứng minh cách tô màu này thỏa mãn bài toán i j
Thật vậy : lấy 3 điểm A, B, C tùy ý. Ta xét các trường hợp sau:
TH1: A, B, C thuộc một tập 𝐴𝑖 nạo đó. Dễ dàng kiểm tra các cạnh được tô bởi 2 màu.
TH2: A, B, C thuộc hai tập hợp khác nhau. Giả sử A, B thuộc cùng một tập, C thuộc tập hợp khác. Khi đó
hai cạnh CA, CB được tô cùng màu và cạnh AB được tô khác màu.
TH3:A, B, C thuộc ba tập hợp khác nhau. Khi đó trường hợp này giống trượng hợp1.
Vậy k nhỏ nhất bằng 4.
Bài 4. Cho T là tập hợp gồm vô hạn các số nguyên dương. Trên mặt phẳng (P) cho B là một họ các hình i i T 
tròn không tính biên của mỗi hình tròn. Chứng minh rằng nếu hình vuông M trên mặt phẳng (P) được phủ kín m bởi họ B
thì tồn tại các số nguyên dương t , t ,..., t T sao cho M  B . i i T  1 2 m ti i 1 = Hướng dẫn giải
Giả sử hình vuông M không thể phủ bởi hữu hạn các hình B . Không mất tính tổng quát ta giả sử hình vuông i
M là hình vuông ABCD trong đó A(0;0), B (0 ) ;1 , C (1 )
;1 , D (1;0) . Chia hình vuông M thành 4 hình vuông bằng
nhau bởi hai đường thẳng đi qua tâm của M và vuông góc với các cạnh. Trong 4 hình vuông bằng nhau đó có
ít nhất một hình vuông M sao cho M không thể phủ bởi một số hữu hạn các hình B . Độ dài cạnh của hình 1 1 i 1 vuông M là
. Ta lại chia hình vuông M thành 4 hình vuông bằng nhau bởi hai đường thẳng đi qua tâm 1 2 1
của M và vuông góc với các cạnh. Trong 4 hình vuông bằng nhau đó có ít nhất một hình vuông M sao cho 1 2 1
M không thể phủ bởi một số hữu hạn các hình B . Độ dài cạnh của hình vuông M là . Tiếp tục như vậy 2 i 2 2 2
ta được một dãy các hình vuông M có các tính chất sau: n 
(i) M  M  M  ...  M  ... 1 2 n 1 (ii)
M là hình vuông có độ dài cạnh là n 2n
(iii) Không thể phủ mỗi hình vuông M bởi một số hữu hạn các hình B . n i
Từ tính chất (i) thì tồn tại điểm M  M với mọi số nguyên dương n. Do M  M  i  T sao cho 0 n 0 0 2
M  B . Do giả thiết của B và hình vuông M có đường chéo
→ 0 khi n → + nên M  B với n 0 n 0 i 0 i 2n n 0 i
đủ lớn, điều này mâu thuẫn với (iii). Vậy điều giả sử là sai và do đó tồn tại các số nguyên dương m
t , t ,..., t T sao cho M  B 1 2 m ti i 1 =
Bài 5. Cho 100 số tự nhiên không lớn hơn 100 có tổng bằng 200. Chứng minh rằng từ các số đó có thể chọn
được một số số có tổng bằng 100 Hướng dẫn giải
Nếu tất cả các số bằng nhau thì tất cả các số là 2. Khi đó ta lấy 50 số 2 sẽ có tổng là 100.
Giả sử a  a ta xét 100 số có dạng 1 2
0  a , a , a + a , a + a + a ,........, a + a + ... + a  200 1 2 1 2 1 2 3 1 2 99
Nếu có một số chia hết cho 100 thì số đó bằng 100 vì số đó bé hơn 200.
Nếu không có số nào chia hết cho 100 thì trong 100 số phải có hai số đồng dư trong phép chia cho 100 (vì
các số dư nhận giá trị từ 1 đến 99) suy ra hiệu của chúng chia hết cho 100 và hiệu hai số đó chính là tổng cần tìm
Bài 6. Cho các số nguyên a , a ,..., a
với 0  a  100, i = 1; 2015 . Với mỗi cặp (a ; a ta cộng thêm 1 i i 1 + ) 1 2 2015 i
vào cả hai số và mỗi cặp đó không được xuất hiện quá k lần. Tìm k nhỏ nhất sao cho hữu hạn lần thực hiện
thao tác trên ta được mọi số bằng nhau. Hướng dẫn giải a = a = = a =100
Ta xét trường hợp các số cạnh nhau cách nhau xa nhất 1 3 2015  a = a = = a = 0  2 4 2014
Đặt S = (a − a + a − a + + a − a
lúc đầu tiên chưa tác động thì S = −100 1007 2 3 ) ( 3 4 ) ( 2014 2015)
Sau hữu hạn lần tác động tất cả các số bằng nhau do đó khi đó S = 0 . Ta nhận xét rằng
Tác động lên các cặp (a ,a , a ,a ,..., a , a Thì S không đổi 2 3 ) ( 2 3 ) ( 2014 2015)