Đa thức và dãy số trong các kỳ thi HSG các nước năm 2017 - Lê Phúc Lữ

(1)

ĐA THỨC, DÃY SỐ TRONG KỲ THI CÁC NƯỚC 2017

Bài 1. (USA Preselection) Cho các đa thức P Q, hệ số thực thỏa mãn



^{P x}^{( )}

 

^ ^{Q x}^{( )}



^{với mọi}^x^.

Chứng minh rằng P x( )Q x( ).

Gợi ý. Đặt R x( )P x( )Q x( ) thì dễ thấy 1 R x( ) 1

   với mọi x. Nếu degR1 thì điều trên không thể xảy ra nên degR0.

Đặt R x( )c và giả sử c0. Không mất tính tổng quát, ta có thể xét c0, thì

( ) ( ) P x Q x c.

Ta thấy, tồn tại x₀ đủ lớn thì P Q, đều đơn điệu và song ánh trên ( ;x₀ ). Xét mx₀ sao cho

( )

P m  k ^, khi đó Q m( )k nên ta sẽ có



^{Q m}^{( )}

 

^ ^{P m}^{( )}



, mâu thuẫn.

Vậy c0 hay P x( )Q x( ).

Bài 2. (Bosnita) Cho 0;

2

_^  ^_

  thỏa mãn tan 2. Xét dãy số ( )u_n xác định bởi

n tan

u  n với n1, 2,3,

Chứng minh rằng với mọi n thì u_n có thể viết thành phân số nguyên tối giản có mẫu là số lẻ.

Gợi ý. Sử dụng công thức cộng của tan rồi quy nạp, đặt tan( 1) p

n   q với ( , ) 1p q  và q lẻ;

thay vào là có đpcm.

Bài 3. (Indonesia) Cho đa thức P x( ) có hệ số nguyên và có ít nhất 9 nghiệm nguyên phân biệt.

Giả sử tồn tại x₀ sao cho P x( )₀ 2017.

Chứng minh rằng P x( ) 0.₀ 

Gợi ý. Đặt P x( ) ( x x x x ₁)(  ₂)(x x Q x ₉) ( ) với Q x( )[ ]x , trong đó x x₁, , ,₂  x₉ là các nghiệm phân biệt của P x( ). Giả sử tồn tại x₀ sao cho P x( ) 0₀  thì Q x( ) 0₀  , suy ra Q x( ) 1.₀  Ta có

( )0 4!5! 2880 2017

P x    , mâu thuẫn.

Bài 4. (Belarus) Cho số (0;1], chứng minh rằng không tồn tại dãy số ( )x_n gồm vô hạn số hạng sao cho x_n_₂  x_n_₁x_n,n.

Gợi ý. Ta có x_n_₁x_n nên x_n_₁x_n. Suy ra

1 1

n n n

x x x

 _   _ hay x_n x_n_₁x_n²_₁. Bài 5. (Moldova) Cho

0

( ) ⁿ _i ⁱ

i

P x a x





^với^aⁿ ^⁰

và a₀ a a₁, , ,₂  a_n 0^{. Gọi}b là hệ số của xⁿ^¹ trong P x²( ), chứng minh rằng P²(1) 4 b. Gợi ý. Dùng BĐT AM-GM, ta có

2 2

1 0

1 1 0

1 (1)

4 4

n n n

i n i i i

i i i

b a a _{ } a a a P

  

 

     

 

  

^.

Bài 6. (Ấn Độ) Cho đa thức bậc ba

( ) 3 4 2 2016ⁿ

P x x x   với n.^Biết rằng P có ba nghiệm nguyên (không nhất thiết phân biệt), chứng minh rằng   3.

Gợi ý. Xét theo mod 7 để chứng tỏ n0.

Từ đó suy ra nghiệm là



^{ }^{1, 1, 2}



^.

Bài 7. (ELMO) Cho 1 0;2 k  

 

 ^và a b, (0;1).

Xét dãy số ¹

1

1 2

n n

a a



  



 

và ¹

1

( )^k

n n

b b

  

 

 .

Chứng minh rằng tồn tại n để a_n b_n.

(2)

Gợi ý. Tìm công thức tổng quát của hai dãy rồi dùng BĐT ln(1  x) x với mọi x(0;1).

Bài 8. (Benelux) Cho số nguyên dương k2 và đặt 65^k a a_{n n}_₁a a a_{2 1 0}. Xét đa thức

1

1 1 0

( ) _n ⁿ _n ⁿ

P x a x a x_ ^   a x a ^. Chứng minh rằng đa thức này không có nghiệm hữu tỷ.

Gợi ý. Nghiệm hữu tỷ của đa thức có dạng p

q thì ^p^

 

^1;5 ^và^q^



^{1, 2, ,9}



. Xét phép chia đa thức q P xⁿ ( ) ( qx p f x ) ( ) với ^{f x}^{( )}^

 

^x

(cần nhân qⁿ để đảm bảo f hệ số nguyên) rồi thay x10, ta có qⁿ65^k (10q p f ) (10). Nếu p1 thì dễ thấy vô lý vì 65^k không có ước dạng 10q1.

Nếu p5 thì xét chữ số tận cùng ở hai vế để suy ra điều vô lý.

Bài 9. (Iran MO) a) Chứng minh rằng không tồn tại dãy vô hạn các số nguyên dương a a a₁, , ,₂ ₃  sao cho gcd(a_i  j a, _j  i) 1 với mọi i j. b) Chứng minh rằng tồn tại dãy số ( )a_n gồm vô hạn các số nguyên dương sao cho

gcd(a_i j a, _ji) không chia hết cho 2017.

Gợi ý. a) Xét các trường hợp a_2n chẵn, lẻ rồi xét tương ứng a₂_n_₁,a₂_n_₁ để suy ra điều vô lý.

b) Chọn dãy số a_n   n 1 (mod 2017).

Bài 10. (China MO) Với n^, xét đa thức

0

( ) ⁿ _i ⁱ

i

P x a x





^với^aⁱ^

 

^0;1 ^và^aⁱ ^^Cⁿⁱ^{(mod 2).}

Tính số các số n2017 để P x( ) phân tích được thành tích 5 đa thức hệ số nguyên bất khả quy?

Gợi ý. Ta có các bổ đề:

(1) (Định lý Lucas) Với m n, ^, giả sử 2 ,^a 2^b

a A b B

m n

 









^với^{A B}^, là tập hợp các số tự nhiên. Khi đó, C_mⁿ lẻ khi và chỉ khi B A. (2) Với số nguyên dương n thì P x( )x²ⁿ 1 bất khả quy.

Từ đó suy ra nếu 2ⁱ

i A

n







thì đa thức P x_n( ) có thể phân tích thành _i( )

i A

P x



 ^.

Từ đó đếm được C₁₁⁵ số n thỏa mãn.

Bài 11. (USA TST) Cho các đa thức f g, có hệ số không âm thỏa mãn ² ( )

1 ( ) x cx f x

   g x với mọi x, trong đó c 2 2 2 . Chứng minh rằng deg f 16.

Gợi ý. Ta có 2cos c_ 16

. Đặt

0

( ) ⁿ _i ⁱ

i

g x a x





^với

i 0

a  rồi khai triển, tìm điều kiện cần của n để có tất cả hệ số f x( ) đều không âm. Có thể nhân

sin16 k

vào các BĐT rồi biến đổi tích thành tổng.

Bài 12. (China TST) Cho đa thức P x( ) có bậc ba và ba nghiệm vô tỷ a b c, , có tổng là 0. Giả sử tồn tại p q, ^{sao cho}^{a b}^ ²^ ^{pb q}^ ^{. (*)} Chứng minh rằng T  p²2p8q7 là số chính phương.

Gợi ý. Đặt f x( )x² px q rồi xét phép chia ( ( )) ( ) ( ) ( )

P Q x P x f x r x , thay x b vào suy ra 0r b( ) nên dễ có r x( ) 0 hay (*) cũng đúng với b c ² pc q c a ,  ² pa q .

Từ a b c  0 ta có (p a p b p c )(  )(  ) 1.

(3)

Bài giảng Tổ hợp 1 trường Đông 2017

MỘT SỐ BÀI TOÁN TỔ HỢP TRÊN DÃY SỐ

I) Giới thiệu.

- Các khía cạnh thường gặp của dãy số: giới hạn, dãy số nguyên và tính chất số học, các bài toán đếm – tính chất của dãy số dạng tổ hợp.

- Các phương pháp thường gặp: truy hồi, xuống thang, cực hạn, …

- Bổ sung định lý Beatty và bài toán áp dụng.

II) Các bài tập áp dụng.

Bài 1. Tìm tất cả các bộ số nguyên dương

1, , , ,2 3 2017

x x x  x sao cho có thể đặt chúng lên vòng tròn theo thứ tự đó mà 6 số liên tiếp bất kỳ đều có thể chia thành hai nhóm 3 có tổng bằng nhau.

Phân tích. Dùng phương pháp xuống thang.

Ta có x_ix_i_₁x_i_₂x_i_₃x_i_₄x_i_₅ 0(mod 2) với mọi i1, 2,3, , 2017 ^nên

6

i i

x x_ với mọi .i

Vì (6, 2017) 1 nên suy ra tất cả các số có cùng tính chẵn lẻ. Ta xét phép biến đổi dãy số sau:

Nếu tất cả các số cùng chẵn thì thay bằng 2

i i

y  x . Nếu tất cả các số cùng lẻ thì thay bằng 1

2

i i

y  x  .

Dễ thấy dãy mới cũng thỏa và tổng ²⁰¹⁷

1 i i

S a





^sẽ

giảm ngặt nếu có một số nào đó trong dãy khác 1;

suy ra quá trình biến đổi sẽ dừng lại khi tất cả đều là 1. Vì ta thu được một dãy toàn là 1 nên dãy ban đầu có tất cả các số hạng bằng nhau.

Nhận xét. Bài toán trên có thể thay việc chia 2 nhóm thành 3, 4,5, nhóm và vẫn giải được bằng cách tương tự. Ta xét các bài tương tự sau:

(APMO 2017) Bộ 5 số nguyên là tốt nếu có thể đặt chúng là a b c d e, , , , để a b c d e    29. Tìm tất cả các bộ 2017 số sao cho 5 số liên tiếp bất kỳ trong chúng đều tốt.

Ở bài toán này, điểm khó là không biết các số đã cho có dương hay không; vì thể, đại lượng tổng ở trên không xét tiếp tục được.

Tuy nhiên, cách áp dụng vẫn tương tự như sau:

- Trừ tất cả các số của bộ cho 29, ta thu được điều kiện tốt trở thành a b c d e    0.

- Tất cả các số đã cho cùng tính chẵn lẻ, và chính xác là cùng chẵn.

- Xét đại lượng ²⁰¹⁷

1 2

i i

S a





thì thông qua phép chia 2, tổng này giảm ngặt. Từ đó suy ra tất cả các số này phải là 0 và tất cả ban đầu phải là 29.

(VMO 2014) Tìm tất cả các bộ số 2014 số hữu tỷ không âm sao cho nếu bỏ đi bất kỳ số nào trong chúng thì các số còn lại có thể được chia thành 3 nhóm rời nhau, mỗi nhóm có 671 số sao cho tích các số trong mỗi nhóm là bằng nhau.

Bài này khó hơn vì: số hữu tỷ chứ không nguyên, tích chứ không phải tổng, ... Ta lần lượt giải quyết điều đó như sau:

- Quy đồng mẫu để đưa về số nguyên.

- Xét số mũ của 1 ước nguyên tố để đưa về tổng.

- Chú ý thêm trường hợp số 0 (nếu có 1 số thì phải có ít nhất 4 số).

Bài 2. Cho dãy số nguyên dương ( )a_n thỏa mãn:

i) Gồm các số phân biệt nhau.

ii) Với mọi n thì a_n n. iii) a₁5,a₂ 4,a₃ 3.

a) Chứng minh rằng tồn tại n2017 sao cho

n 1

a  n ?

(4)

b) Giả sử a_n  n 2 với mọi n2017, hỏi có tất cả bao nhiêu dãy số như thế?

Phân tích.

a) Bài toán có thể giải quyết dễ dàng bằng phản chứng và Dirichlet. Thật vậy, nếu a_n  n 1 với mọi n2017 thì các số hạng a₄ a₂₀₁₇ sẽ nhận các giá trị trong tập hợp 62018. Khi đó, sẽ có hai số hạng bằng nhau, không thỏa.

b) Nếu đã có a_n  n 2 với mọi n2017 thì các số hạng a₄ a₂₀₁₇ sẽ nhận các giá trị trong tập hợp 62019. Nhận xét:

 

2017 2017, 2018, 2019

a  nên có 3 cách chọn.

 

2016 2016, 2017, 2018, 2019

a  nhưng vì a₂₀₁₇ đã

lấy một số nên cũng còn 3 cách chọn.

Tương tự, đến a₆ vẫn có 3 cách chọn. Còn lại a₅ có 2 cách chọn và a₄ có 1 cách chọn.

Theo nguyên lý nhân, ta có 2 3 ²⁰¹² dãy thỏa mãn.

Bài 3. Xét lục giác ABCDEF có độ dài cạnh là 1 được điền các số như hình vẽ

Một con ếch xuất phát từ A và nhảy đến các đỉnh sao cho mỗi bước nhảy đều có độ dài nguyên. Hành trình của ếch là dãy các tên đỉnh mà ếch đã nhảy qua; và hai hành trình được coi là khác nhau nếu ở một lần thứ k nào đó, đỉnh mà ếch nhảy đến ở hai hành trình là khác nhau.

Gọi m là số hành trình ếch nhảy sao cho tổng các số mà nó nhảy qua là 2017. Chứng minh rằng m không phải là số chính phương.

Phân tích.

Ta thấy ACE và BDF là hai tam giác đều có cạnh là 3 nên mỗi lần, ếch sẽ nhảy từ tam giác đều này đến tam giác đều kia.

Chia nhóm: I ( , , )A C E tương ứng với các số (0,0,1) và II ( , , )B D F tương ứng với (1,1, 2). Ta thấy



x y x I y II ^|  ^, 

 

 1,1,1,1, 2, 2, 2, 2,3



chứng tỏ tổng các số trên hai bước nhảy liên tiếp của ếch sẽ nhận giá trị là 4 số 1, 4 số 2 và 1 số 3. Nếu gọi s_n là số hành trình của ếch có tổng là n thông qua chẵn bước thì

1 2 3

4 4

n n n n

s  s _  s _ s _ .

Một cách tương tự, gọi t_n là số hành trình của ếch có tổng là n thông qua lẻ bước thì công thức truy hồi vẫn thế (chỉ khác ở các số hạng đầu).

Vì vậy nên nếu gọi u_n  s_n t_n là số hành trình của ếch có tổng là n thì

1 2 3

4 4

n n n n

u  u _  u _ u _ với n3.

Ta có u₀ 1,u₁6,u₂ 28 và từ công thức truy hồi thì m u ₂₀₁₇  u₁ 2(mod 4) nên m không thể là số chính phương, ta có đpcm.

Nhận xét. Bài toán có thể giải bằng cách gọi 6 dãy truy hồi a b c d e f_n, , , , ,_n _n _n _n _n chỉ số hành trình của ếch có tổng là n và kết thúc tại A B C D E F, , , , , . Tuy nhiên, cách tiếp cận đó khá phức tạp, đòi hỏi phải khai thác nhiều các liên hệ giữa các đường đi.

Một bài toán tương tự:

(Ả Rập TST 2017) Người ta đặt các số 1, 2,3, 4 trên vòng tròn theo thứ tự đó. Một con kiến xuất phát từ số 1 và ở mỗi bước, nó sẽ bò qua số bên cạnh. Hỏi con kiến có bao nhiêu cách bò sao cho 2

1

1 0

B

C D

E F

A

(5)

tổng tất cả các số mà nó bò qua (kể cả số ban đầu) bằng 21?

Tương tự bài trên, ta cũng tìm được hệ thức truy hồi là s_n s_n_₃2s_n_₅s_n_₇. Từ đó tính được

21 167.

s 

Bài 4. Cho dãy các số nguyên dương ( )u_n thỏa mãn điều kiện

0u_{m n}_ u_m u_n 1 với mọi ,m n^. Chứng minh rằng tồn tại a^ sao cho

 

1 u_n an 1

    với mọi n1, 2,3, , 2017. Phân tích. Hãy đưa điều cần chứng minh về

n n 1

u u

n a n

   .

Đến đây, gọi

min uⁿ 1 1, 2,3, ,2017

m n

n

  

   

  ^và

max uⁿ 1, 2,3, , 2017

M n

n

 

   

  ^.

Cần chỉ ra m M rồi chọn số a nằm giữa ( ,m M) là xong. Gọi ,p q lần lượt là các chỉ số nhỏ nhất để có dấu bằng xảy ra ở các BĐT trên. Khi đó

p 1

u   pm và u_q Mq.

Ngoài ra, u_k  1 km k,  p và u_k kq k q,  . - Nếu p q thì hiển nhiên đúng.

- Nếu p q , ta đặt p q k  thì k  p nên

k 1

u  km, vì u_p u_qu_k (theo giả thiết) nên

1 1 .

pm Mq km   m M

- Nếu p q thì cũng chứng minh tương tự với chú ý rằng u_q u_p u_k1.

0u_{m n}_ u_mu_n 2,

ta sẽ cần đến hai số a b, sao mới thỏa mãn được kết luận (vì khoảng chênh lệch của các số hạng rộng hơn một tí), cụ thể là tồn tại a b, 0 để

   

1 u_n an bn 1

     .

Bài 5. Hai dung dịch A B, có đặc điểm: số đo thể tích của 1 kg A bằng số đo khối lượng của 1 lít B. Ngoài ra, p lít A nặng bằng q lít B với ,p q nguyên tố khác nhau. Mỗi dung dịch được chia cho vào các bình nhỏ giống nhau, cùng chứa 1 lít và vỏ nặng 1 kg. Chứng minh rằng có đúng một cách ghép các bình cùng loại (A hoặc B) lại với nhau mà khối lượng của chúng thuộc khoảng

(2017; 2018).

Phân tích. Trước hết, ta xét định lý Beatty với nội dung như sau:

Cho hai số vô tỷ dương  , . Xét hai dãy số [ ],[2 ],[3 ],   _ tạo thành dãy A. [ ],[2 ],[3 ],   _ tạo thành dãy B. a) Nếu 1 1

 ^ ^1^thì^{A B}^, là phân hoạch của ^^. b) Chiều ngược lại vẫn đúng.

Định lý này có thể chứng minh bằng cách sử dụng các BĐT về phần nguyên. Dưới đây là cách chứng minh cho chiều đảo:

Với mỗi số nguyên dương k , gọi m n, là các số nguyên dương thỏa mãn

[m] k [(m1) ] và [n] k [(n1) ] . Đặt A{[ ],1i  i m} và B{[j],1 j n} thì A m B, n và A B, là phân hoạch của tập hợp



^{1, 2,3, ,} ^k



theo định nghĩa của đề bài.

Do đó m n k  . Theo bất đẳng thức phần nguyên

1 ( 1)

m  k m 

(6)

1 1 1

m m

k  k

  

 . Tương tự 1 1

1 .

n n

k  k

  



Suy ra 1 1 2

1

m n m n

k   k

  

  

 hay

1 1 2

1

k k

k   k

   

 .

Cho k , ta thu được 1 1

 ^ ^1.

Trở lại bài toán đã cho,

Gọi ,x y lần lượt là khối lượng riêng của các dung dịch thì 1

1 ,y px qy

x   nên q, p

x y

p q

  .

Khối lượng mỗi bình là 1 q, 1 p

p q

      . Dễ thấy 1 1

 ^ ^1, thỏa mãn định lý Beatty.

Suy ra hai dãy [m],[n] là phân hoạch của số nguyên dương nên ta có đpcm.

Nhận xét.

(APMO 2006) Với mỗi số nguyên dương n, gọi

n, n

a b lần lượt là số cách viết 10ⁿ trong hệ nhị phân, ngũ phân. Chứng minh rằng ( ),( )a_n b_n là phân hoạch của ^ \{1}.

Để giải bài này, chú ý rằng: số chữ số của M trong hệ p phân là [log_pM] 1 .

Ngoài ra,  log 10,₂  log 10₅ thỏa mãn điều kiện của định lý Beatty.

Từ đó, ta cũng có một nhận xét thú vị rằng: tổng số chữ số của 2ⁿ và 5ⁿ trong hệ thập phân là n1.

(VN TST 2000) Cho số nguyên dương k. Dãy số ( )u_n xác định bởi: u₁ 1 và u_n_₁ là số nguyên dương nhỏ nhất không thuộc tập hợp



u u1, , , ,2  u u_n 1k u, 22 , ,k  u_nnk



^.

Chứng minh rằng tồn tại  vô tỷ dương sao cho

n

 

u  n với mọi n.

Đây là một kết quả có từ 1959. Ta có thể phân tích cách tiếp cận như sau:

Xuất phát từ việc   2,  2 2 thỏa mãn điều kiện Beatty. Ta có hai dãy với công thức

2 , 2

n n n

a n  b a  n là phân hoạch của ^. Từ đó, để giấu dãy b_n đi, ta chỉ cần xét a_n2n. Để ý a₁1,a₂ 2,a₃ 4,b₁ 3,b₂ 6,b₃ 10 nên

a4 có thể định nghĩa là số nguyên dương nhỏ nhất không thuộc



a a a a1, , ,2 3 12,a24,a36



. Đó chính là cơ sở để có bài toán trên.

Việc chứng minh hai dãy trùng nhau chỉ cần dùng quy nạp, chú ý rằng 1 1

k 1

 ^  ^ chỉ có một nghiệm vô tỷ dương duy nhất.

(Dãy Wythoff) Cho chuỗi S₁1. Chuỗi S_n được tạo thành từ chuỗi S_n_₁ bằng cách thay 101 và 01. Các chuỗi S S S₁, , ,₂ ₃  được ghép liên tiếp lại với nhau thành một chuỗi vô hạn L. Gọi a_n là vị trí của số 1 thứ n trong chuỗi L. Chứng minh rằng tồn tại  vô tỷ dương sao cho

 

^, ^.

an  n n

Ở đây, ta có nhận xét rằng số 0 thứ n được sinh ra bởi số 1 thứ n nên nếu gọi k_n là số các số 0 đứng trước số 1 thứ n và b_n là vị trí của số 0 thứ ,n ta sẽ có a_n  n k_n và b_n 2n k _n nên b_n a_nn. Chú ý rằng ( ),( )a_n b_n chính là phân hoạch của ^ nên dễ dàng tìm được  là nghiệm của

1 1

 ^  ^ ^hay chính là tỷ số vàng.

(7)

Bài giảng Tổ hợp 2 trường Đông 2017

NGUYÊN LÝ DIRICHLET VÀ Ý TƯỞNG XÁC SUẤT

I) Giới thiệu.

Các ý tưởng Dirichlet thông dụng:

- Thỏ nhiều hơn chuồng thì có chuồng có 2 thỏ.

- Thỏ nhiều hơn x lần chuồng thì có chuồng có 1

x thỏ.

- Tổng của m số là n thì số lớn nhất sẽ n

m và số nhỏ nhất sẽ n

 m.

- Nếu một dãy vô hạn phần tử nhưng có hữu hạn giá trị thì có giá trị nào đó xuất hiện vô hạn lần.

II) Bài tập áp dụng.

Bài 1. Cho dãy Fibonacci. Chứng minh tồn tại số hạng của dãy tận cùng là 2017 chữ số 9.

Phân tích. Bài toán đưa về chứng minh tồn tại 1(mod102017)

Fn   .

Xét s_n là số dư của F_n khi chia cho k10²⁰¹⁷ thì các cặp số dư ( ,s s_n _n_₁) sẽ nhận tối đa k² giá trị, trong khi có vô hạn chỉ số như thế; chứng tỏ tồn tại m n mà ( ,s s_n _n_₁) ( , s s_m _m_₁). Suy ra dãy số dư tuần hoàn; và tuần hoàn từ số hạng đầu tiên. Vì

1 2 1

F F  thì F₀ 0,F_₁1,F_₂  1 nên tồn tại (vô số) số hạng thỏa mãn đề bài.

Nhận xét. Kỹ thuật xét số dư mod k như trên là rất phổ biến với dãy số nguyên. Chú ý rằng chỉ cần có hệ số của số hạng cuối trong công thức của dãy sai phân tuyến tính là nguyên tố cùng nhau với k thì sẽ có sự tuần hoàn từ số hạng đầu tiên.

Ngoài ra, để tránh xét chỉ số âm, ta có thể đặt

3

n n

E _ F thì công thức truy hồi của E_n giống F_n cho thấy trong ( )E có số thỏa mãn đề bài.

Bài 2. Cho các số nguyên dương a a₁, ,...,₂ a₆₃ là một hoán vị của 1, 2,3,...,63. Xét các số sau đây

1

1 2

1 2 63

2017 ,

2017 ( ),

...

2017 ( ).

a a a



 

   

Chứng minh rằng trong 63 số này, có không quá 38 số chính phương.

Phân tích. Xét dãy số chính phương không vượt quá 2017 là44 , 43 , 42 , ,3 , 2 ,1² ² ²  ² ² ² (*)

Đặt

1

2017 ^k

k i

i

b a



 



^với¹^{ }^k ⁶³^.

Giả sử có không ít hơn 39 số chính phương dãy ( )b_k thì trong dãy (*) ở trên, ta đã loại đi không quá 5 số chính phương phân biệt, đồng nghĩa với việc loại đi không quá 10 cặp số chính phương liên tiếp.

Chú ý rằng hiệu của hai số chính phương liên tiếp luôn lẻ; và do dãy b_k giảm nên cứ hai số chính phương liên tiếp xuất hiện trong dãy b_k thì nó phải là hai số liên tiếp của dãy, chẳng hạn b_t_₁, .b_t Khi đó, b b_t  _t_₁a_t_₁ là số lẻ.

Do đó, khi loại đi không quá 10 cặp số chính phương liên tiếp trong (*) gồm 43 cặp số chính phương liên tiếp thì còn lại ít nhất 43 10 33  cặp, tương ứng với 33 số lẻ trong a_k, vô lý vì từ 1 đến

63 chỉ có 32 số lẻ.

Bài 3. Trong một két sắt, có 7 người lính đang canh giữ một kho báu. Kho báu đặt sau 11 lớp cửa và mỗi cửa có 3 ổ khóa. Biết rằng tất cả các khóa đều khác nhau và mỗi bảo vệ có chìa khóa của một số ổ khóa. Biết rằng bất cứ 4 người nào cũng có chìa khóa cho tất cả các khóa. Chứng minh rằng có 3 người có chìa cho tất cả các khóa để mở kho báu.

Phân tích. Ta chỉ cần chứng minh nhận xét sau:

(8)

Với mỗi ổ khóa, có tối đa 1 nhóm 3 người không mở được. Thật vậy, vì nếu có 2 nhóm thì sẽ có ít nhất 4 người, và vì thế 4 người đó sẽ không mở được cửa kho báu.

Giả sử phản chứng không tồn tại bộ 3 thỏa mãn thì cứ mỗi bộ 3 sẽ có ít nhất một ổ khóa mà họ không cùng mở được. Theo nhận xét trên thì các ổ khóa như thế là khác nhau. Tuy nhiên, ta cũng có

3

7 35 3 11 33

C     là số ổ khóa nên vô lý.

Bài 3. (Bulgaria 2013) Chứng minh rằng tồn tại một số nguyên dương có không quá 9 chữ số mà có thể biểu diễn thành tổng của ba số chính phương phân biệt bởi ít nhất 1000 cách.

Phân tích. Với mỗi số nguyên dương N, xét tất cả tổng các bình phương có dạng

2 2 2

a b c với 1   a b c N.

Rõ ràng có tất cả C_N³ tổng như thế. Ngoài ra, vì , ,

a b c N nên tổng các bình phương này không vượt quá 3N². Theo nguyên lý Dirichlet, có ít nhất một tổng xuất hiện

3 2

( 1)( 2)

3 18

CN N N

N N

 

 lần.

Xét N 18003 thì ( 1)( 2) 18 1000

N N

N

   và hơn

nữa 3N² 10⁹ nên câu trả lời là khẳng định.

Nhận xét. Ở bài toán này, ta chủ động xây dựng các con thỏ (các bộ ba) để đưa vào các chuồng phù hợp (các giá trị). Vì số thỏ theo cách làm trên tăng theo đa thức bậc ba, còn số chuồng chỉ là bậc hai nên số 1000 có thể thay bằng số lớn tùy ý.

Bài 4. Cho bảng ô vuông 100 100 mà mỗi hàng/cột của bảng đều được tô bởi màu A B C D, , , với số lượng đều nhau.

a) Chứng minh rằng có 2 cột mà số cặp ô khác màu cùng hàng trên đó ít nhất là 76.

b) Chứng minh rằng có 2 cột, 2 hàng mà giao điểm của chúng là hình chữ nhất có 4 góc khác màu.

Phân tích.

a) Giả sử phản chứng rằng mỗi cặp cột tùy ý đều có ít nhất 25 cặp ô cùng màu.

Cố định cột 1, xét 99 cột còn lại. Gọi T là số bộ ( , )a b trong đó cột a2 có ô thứ b từ trên xuống là cùng màu. Theo giả sử trên thì T 99 25. Mặt khác, theo giả thiết thì T 100 24 (tính theo hàng). Suy ra 100 24 99 25   , vô lý.

b) Giả sử phản chứng rằng không có 2 hàng, 2 cột nào thỏa mãn. Xét 2 cột đã chọn được ở trên, giả sử đã có cặp ( , ),( , )A B A C thì sẽ không có ( , )C D và ( , )B D . Ta có hai khả năng:

- Nếu có ( , )A D thì không có ( , )B C , khi đó mỗi cặp trong 76 cặp đều có màu A; trong khi số lần màu A xuất hiện trên đó tối đa là 50, vô lý.

- Nếu có ( , )B C thì không có ( , )A D ; khi đó, trên 76 cặp sẽ có 76 2 152  màu, trong khi số màu tối đa là 25 2 3 150   .

Từ đây ta có đpcm.

Bài 5. Trong một hình vuông 10 10 , cho 51 điểm sao cho không có ba điểm nào thẳng hàng.

a) Chứng minh rằng có một tam giác tạo bởi ba điểm đó có diện tích không vượt quá 2.

b) Nối các điểm đó lại với nhau, cùng với các đỉnh của hình vuông (không có hai đoạn nào cắt nhau ở giữa) chia hình vuông thành các miền tam giác.

Chứng minh có một miền diện tích nhỏ hơn 1.

Phân tích.

a) Chia hình vuông thành 25 hình vuông con rồi sử dụng bổ đề: trong một hình bình hành, cho 3 điểm tùy ý thì diện tích tam giác không vượt quá

1

2 diện tích hình bình hành.

b) Gọi k là số miền thu được ứng với n điểm bên trong hình vuông. Ta tính tổng các góc T của các miền theo hai cách:

(9)

- Mỗi miền là tam giác nên T 180k.

- Do các góc xung quanh mỗi điểm đều được tính nên T 360  n 90 4.

Suy ra k 2n2. Ở bài toán này, số miền sẽ là 51 2 2 104   , mà diện tích hình vuông là 100 nên sẽ có một miền diện tích nhỏ hơn 1.

Bài 6. (IMO Shortlist 1993) Có 19 số nguyên dương x x₁, , ,₂  x₁₉ không vượt quá 93 và 93 số nguyên dương y y₁, , ,₂  y₉₃ không vượt quá 19.

Chứng minh rằng có thể chọn ra một số số x_i và một số số y_i sao cho tổng của chúng bằng nhau.

Phân tích. Bài toán trên là một dạng đặc biệt của:

Cho 2 dãy hữu hạn các số nguyên dương

1 2 ... _m , 1 2 ... _n

x x   x n y  y   y m. Chứng minh rằng tồn tại 1  i₁ i₂ m,1 j₁ j₂ n sao

cho ² ²

1 1

i j

i i j j

x y

 

 

 ^. Đặt

1 1

,1 , ,1

p q

p i q j

i j

a x p m b y q n

 





  



  ^{. Ta}

có thể giả sử rằng a_mb_n. Khi đó, với mỗi p như trên, tồn tại f p( )q là chỉ số bé nhất mà a_p b_q. Xét m hiệu b_f₍₁₎a b₁, _f_{ }₂ a₂,...,b_{f m}_{( )} a_m. (*) Dễ thấy rằng tất cả các hiệu này đều bé hơn m vì nếu ngược lại, tồn tại p mà b_{f p}_{( )}a_p m thì

( ) 1 ( )

( ) ( ) 1 ( ) 1

0

f p f p p

f p f p p p f p

m b y a

m y b a a b



 

  

      

mâu thuẫn với định nghĩa của số f p( ). Ta có hai trường hợp sau:

(1) Nếu tồn tại một trong các hiệu ở dãy (*) bằng 0 thì chọn i₁ j₁ 1,i₂  p j, ₂  f p( ).

(2) Nếu không thì tất cả các giá trị này đều thuộc {1, 2, , m1} là một tập hợp có m1 phần tử, nên

theo nguyên lí Diriclet thì tồn tại hai hiệu có giá trị bằng nhau.

Giả sử ta có b_{f r}_{( )}a_r b_{f s}_{( )}a s r_s,  . Ta tiến hành chọn i₁  s 1,i₂ r j, ₁ f s( ) 1, j₂  f r( ). Bài 7. (Bài toán về tập độc lập)

Một tập độc lập (independence set) của graph ( , )

G V E là tập con của V sao cho các đỉnh đó không được nối với nhau. Ta có 2 định lý:

(Định lý 1) Cho graph G( , )V E có V n và bậc các đỉnh không vượt quá d. Chứng minh rằng có một tập độc lập chứa ít nhất

1 n

d ^đỉnh.

(Định lý 2) Cho graph G( , )V E có V n và bậc các đỉnh là x x₁, , ,₂  x_n. Chứng minh rằng có một tập độc lập chứa ít nhất

1

1 1

n

i xi



^đỉnh.

Định lý 1 chứng minh dễ dàng bằng cách cực hạn như sau: Xét tập độc lập A có nhiều đỉnh nhất, giả sử là k và tập còn lại là B với n k đỉnh.

Do mỗi đỉnh trong B đều không được thêm vào A nên phải kề với đỉnh nào đó trong A. Vì A sinh ra không quá kd đỉnh nên n k kd  hay .

1 k n

 d

 Ở định lý 2, ta dùng ý tưởng xác suất như sau:

Xét một hoán vị của các đỉnh, đặt là v v₁, , ,₂  v_n^. Ta sẽ bắt đầu từ đỉnh v₁, đưa lần lượt vào tập độc lập A theo quy tắc sau: một đỉnh v chỉ được chọn nếu như trong A, không có đỉnh nào có cạnh nối với nó; nghĩa là v sẽ là đỉnh đầu tiên trong deg( ) 1v  đỉnh gồm chính nó và deg( )v đỉnh có cạnh nối với nó. Xác suất để xảy ra điều này là

1

deg( ) 1v  . Từ đó suy ra kỳ vọng của số đỉnh trong A sẽ là 1

1

n

x



. Định lý được chứng minh.

(10)

Cuối cùng, ta xét một ứng dụng cực kỳ thú vị của tập độc lập như sau:

Bài 8. (C7, IMO Shortlist 2011) Cho 2⁵⁰⁰ điểm chia đều một vòng tròn được đánh số 1, 2,3, , 2 ⁵⁰⁰ theo thứ tự nào đó. Giá trị của một cung là tổng 2 số trên đầu mút của cung đó. Chứng minh có 100 cung đôi một không cắt nhau và có cùng giá trị.

Phân tích. Đặt 2n2⁵⁰⁰ thì khi đó, trên vòng tròn sẽ có 2n điểm. Giá trị của các cung sẽ thuộc tập

{3, 4, , 4 1}

C  n với tổng cộng 4n3 giá trị.

Gọi G_c là graph con với đỉnh là các cung ứng với giá trị c C . Hai đỉnh của G_c (cũng chính là cung của đường tròn) được gọi là kề nhau nếu chúng biểu diễn cho các cung cắt nhau.

Mục tiêu của bài toán là chứng tỏ có một tập độc lập của G_c nào đó có ít nhất 100 phần tử. Theo định lý 2 thì sẽ có một tập độc lập có ít nhất

( ) 1

c 1

c

v G v

I G  d





 ^đỉnh.

Giá trị trung bình của kích cỡ của tập trên là

4 1 4 1

3 3

1 1 1

4 3 ( ) 4 3 _c 1

n n

c

c c v G v

M I G

n n d

 

  

 

 



 

 

  ^. Tổng trên cũng chính là 1

v G_ dv1



^với^G là tập hợp tất cả các cung của đường tròn (có C_2n² cung như thế). Ta sẽ đánh giá bậc của các đỉnh đó để chứng minh trung bình cộng trên lớn hơn 100.

Với mỗi cung L, ký hiệu m L( ) là số cung khác cắt .

L Dễ thấy số cung cắt L sẽ không vượt quá m L( ).

Với mỗi i{0,1, 2, , n1} thì có đúng 2n cung L có m L( )i. Chú ý rằng m L( ) 0 nghĩa là hai đầu mút của cung liên tiếp nhau. Còn m L( ) n 1 nghĩa là cung nhỏ tương ứng cũng chính là đường kính của vòng tròn. Từ đây ta có nhận xét:

Với mỗi i{0,1, 2, , n1}, sẽ có không quá 2n đỉnh v G mà d_v i. Suy ra

1 1

1 2 1

1 2

n n

v G v i i

n n

d i i

  

 





 

^.

Dễ chứng minh được

1

1 ln( 1)

n

i

i n



 



^nên

2 ln( 1)

ln( 1)

4 3 2

n n

M n

n

   

 ^.

Vì n2⁴⁹⁹ nên 499 ln 2

249,5 ln 2

M  2   . Ta chỉ

cần chứng tỏ 249,5 ln 2 100  , nhưng điều này là đúng vì ta có đánh giá e² 2,8² 2³ nên 2

ln 2 ,

3

suy ra 2

249,5 100.

M   3

Bài toán được giải quyết hoàn toàn.

Nhận xét.

Bài toán trên sẽ cực khó nếu ta không có khái niệm về tập độc lập và định lý liên quan ở trên.

Tổng quát của bài toán trên khi thay 2 thành ⁵⁰⁰ 2n thì số cung độc lập, cùng giá trị sẽ là 2 ln( 1)

4 3

n n n



 ^.

TP. Bảo Lộc, ngày 17/11/2017 GV. Lê Phúc Lữ

Chúc các thí sinh đạt kết quả tốt tại VMO 2018!

L

1 2 m(L)