Đề thi chọn đội tuyển Việt Nam tham dự kì thi Toán quốc tế Imo 2016

htt p:/ /m ath sco pe .or g ĐỀ THI CHỌNĐỘI TUYỂN VIỆT NAM THAMDỰKÌ THI TOÁNQUỐC TẾ IMO 2016 Ngày thứ nhất Bài 1 Tìm a,n nguyên dương với a > 2 để mỗi ước nguyên tố của an − 1 cũng là ước nguyên tố của a3 2016 −1. Bài 2 A là tập 2000 số nguyên phân biệt và B là tập 2016 số nguyên phân biệt. K là số cặp (m,n) có thứ tự vớim thuộc A và n thuộc B mà |m−n| ≤ 1000. Tìmmax K ? Bài 3 Cho tam giác ABC nội tiếp đường tròn (O) có B ,C cố định, A chuyển động trên cung BC của (O). Các phân giác AD,BE ,CF giao nhau tại I . Đường tròn qua D tiếp xúc vớiOA tại A cắt (O) tạiG.GE ,GF giao (O) lần thứ hai tạiM ,N . BM giao CN tại H . a) Chứng minh rằng AH đi qua một điểm cố định. b) BE ,CF giao (O) lần lượt tại K ,L. AH giao KL tại P . Q là một điểm trên EF sao cho QP =QI . J là điểm nằm trên (BIC ) sao cho I J ⊥ IQ. Chứng minh rằng trung điểm I J chuyển động trên một đường tròn cố định. Ngày thứ nhì Bài 4 Cho tam giác ABC nhọn có ∠ACB < ∠ABC < ∠ACB + ∠BAC 2 . Lấy điểm D thuộc cạnh BC sao cho ∠ADC =∠ACB + ∠BAC 2 . Tiếp tuyến với đường tròn ngoại tiếp tam giác ABC tại A cắt BC tại E . Phân giác ∠AEB cắt AD và cắt (ADE) tại G và F , DF giao AE tại H . a) Chứng minh rằng các đường tròn đường kính AE ,DF,GH có một điểm chung. b) Trên phân giác ngoài ∠BAC và trên tia AC lần lượt lấy các điểm K và M sao cho KB = KD = KM , trên phân giác ngoài ∠BAC và trên tia AB lần lượt lấy các điểm L và N sao cho LC = LD = LN .Đường tròn đi quaM ,N và trung điểm I của BC cắt BC tại P (P 6= I ). Chứng minh rằng BM ,CN ,AP đồng quy. Bài 5 Cho a1,a2, ...,an−1,an (n ≥ 3), trong đó mỗi số ai nhận giá trị ∈ {0;1}. Xét n bộ số S1 = (a1,a2, ...,an−1,an), S2 = (a2,a3, ...,an ,a1);...;Sn = (an ,a1, ...,an−2,an−1). Với mỗi bộ số r = (b1,b2, ...,bn), đặt ω(r )= b1.2n−1+b2.2n−2+ ...+bn .20. Giả sử các số ω(S1);ω(S2); ...;ω(Sn) nhận đúng k giá trị phân biệt. a) Chứng minh rằng n ...k và ω(Si ) ... 2n −1 2k −1 ∀i = 1,n. b) Kí hiệuM vàm lần lượt là max và min của ω(S1), ...,ω(Sn). Chứng minh rằng M −m ≥ (2 n −1)(2k−1−1) 2k −1 . Bài 6 Cho các số thực phân biệt α1,α2, ...,α16. Với mỗi đa thức hệ số thực P (x); đặt V (P )= P (α1)+P (α2)+ ...+P (α16). Chứng minh rằng tồn tại duy nhất đa thứcQ(x) bậc 8 có hệ số x8 bằng 1 thỏa mãn i) V (QP )= 0 với mọi đa thức P có bậc bé hơn 8. ii) Q(x) có 8 nghiệm thực (tính cả bội). htt p:/ /m ath sco pe .or g HƯỚNGDẪN VÀ LỜI GIẢI Tìm a,n nguyên dương với a > 2 để mỗi ước nguyên tố của an −1 cũng là ước nguyên tố của a3 2016 −1. Bài toán 1 TST 2016 Lời giải (trungnghia215) Bổ đề 1. gcd(am −1,an −1)= agcd(m,n)−1 Chứng minh bổ đề. Gọi d = gcd(am −1,an −1) Để ý agcd(m,n)−1 | am −1,an −1 =⇒ agcd(m,n)−1 | d =⇒ d ≥ agcd(m,n)−1 Mặt khác am ≡ 1 (mod d) và an ≡ 1 (mod p) nên ordd (a) |m,n =⇒ ordd (a) | gcd(m,n) Hay agcd(m,n) ≡ 1 (mod d) hay agcd(m,n)−1≥ d . Kết hợp lại ta có đpcm. Bổ đề 2. 33 u +1= 2t có nghiệm duy nhất là (u, t )= (0,2). Chứngminh bổ đề. Xét u ≥ 1, khi đó 33u = (33)3u−1 ≡ 33u−1 (mod 8). Đến đây lùi về sẽ thu được 33 u ≡ 3 (mod 8). Từ đó ta có u = 0 là nghiệm duy nhất. Giả thiết bài toán quy thành p là ước nguyên tố của an−1 thì p | d với d = gcd(an−1,a32016−1) Ta đặt n = 3u .v với gcd(v,3)= 1. TH1. u ≤ 2016. Khi đó theo bổ đề d = a3u −1 i) Nếu v = 1 thì ta dễ thấy a3u −1 | a32016 −1. ii) Xét v ≥ 2, khi đó ta có av −1 | an −1. Bài toán suy ra nếu p | av −1 thì p | a3u −1. Xét p là ước nguyên tố của a v−1 a−1 =⇒ p | av −1. Khi đó p | gcd(av−1,a3u−1)= a−1 theo bổ đề trên. Điều này có nghĩa là tập các ước nguyên tố của av−1+av−2+·· ·+1 phải là tập con của tập các ước nguyên tố của a−1 (∗) Bây giờ ta đặt A = av−1+av−2+·· ·+1= pd11 pd22 · · ·pdkk với pi < pi+1 là các ước nguyên tố. Theo (∗) thì a−1= pc11 pc22 · · ·pckk .P a) Nếu a chẵn thì toàn bộ pi ,P lẻ. Áp dụng bổ đề LTE, ta có vpi (A)= vpi (av −1)− vpi (a−1)= vpi (v). Nghĩa là v = pd11 pd22 · · ·pdkk Q Lúc này, A ≥ av−1+1= apd11 pd22 ···p dk k Q−1+1≥ 3pd11 pd22 ···p dk k Q−1+1> A. Vô lí. b) Nếu a = 4t+1. Lúc này ta vẫn có thể áp dụng bổ đề LTE như trên do 4 | a−1nên v2(av−1)= v2(a−1)+ v2(v). Đánh giá tương tự ta có điều vô lý. c) Nếu a = 4t +3. Khi đó để ý nếu v lẻ ta sẽ dẫn đến v2(A)= v2(v)= 0 nên đánh giá tương tự a) cho điều vô lý. Xét v chẵn, theo bổ đề LTE v2(av −1)= v2(a−1)+ v2(a+1)+ v2(v)−1= v2(a+1)+ v2(v). Đặt L = v2(v), K = v2(A) = d1 và J = v2(a+1) (J ≥ 2). Ta có K = v2(A) = v2(av −1)− v2(a−1) = L+ J −1 (lưu ý là do ta đã sắp xếp pi nên p1 = 2) Viết lại A = 2L+J−1pd22 · · ·pdkk và v = 2Lp d2 2 · · ·pdkk .Q. Mặt khác, để ý là v2(a+1)= J nên a+1≥ 2J ⇐⇒ a ≥ 2J −1. Ta có: A = av−1+av−2+·· ·+1≥ av−1+1≥ (2J −1)v−1+1= [(2J −2)+1]2Lpd22 ···p dk k Q +1 ≥ 2Lpd22 · · ·pdkk Q(2J −2)+2≥ 2L+J .p d2 2 · · ·pdkk −2L+1p d2 2 · · ·pdkk +2≥ A Để ý dấu đẳng thức xảy ra khi và chỉ khi v = 2, a = 2L−1. Từ đó ta cần đi tìm u sao chomọi ước nguyên tố của a2.3 u −1 là ước nguyên tố của a32016−1. 2 htt p:/ /m ath sco pe .or g Xét trường hợp u 6= 0, theo bổ đề 3 thì a3 u +1 có ước nguyên tố lẻ. Xét q là ước nguyên tố lẻ của a3u +1. Ta có q | a3 2016−1 a3u−1 , nếu ta đặt x = a 3u và y = 32016−u (y lẻ) thì viết lại q | x y−1x−1 = x y−1+x y−2+·· ·+1= x y−2(x+1)+x y−4(x+1)+·· ·+x(x+1)+1 (do y lẻ) từ đó suy ra q | 1 do q | x+1. Vô lí. Từ đó thu được u = 0 hay n = 2. Vậy nghiệm là (a,n)= (2L−1,2). TH2. n > 2016 Xét tương tự trên, với v > 1 ta cũng sẽ thu được n = 2. Vô lí. Xét v = 1. Khi đó ta cần chứng minh có 1 ước nguyên tố là ước của 33u −1 nhưng không là ước của 33 2016 −1 Tuy nhiên điều này không đúng vì nếu ngược lại, nghĩa là sẽ có một ước nguyên tố q sao cho vq (33 u )> vq (332016). Nếu q lẻ: mọi ước nguyên tố q của 33 u−1 và 332016−1 đều khác 3 nên theo bổ đề LTE vq (33u− 1)= vq (332016 −1)+ vq (3u−2016)= vq (332016) Do đó ta chỉ cần xét 33 u−1= 2i .(332016−1), tuy nhiên PT này vô nghiệm do đó ta có đpcm (có thể cm bằng cách chia qua) A là tập 2000 số nguyên phân biệt và B là tập 2016 số nguyên phân biệt. K là số cặp (m,n) có thứ ự vớim thuộc A và n thuộc B mà |m−n| ≤ 1000. Tìmmax K ? Bài toán 2 TST 2016 Lời giải (tikita) Có lẽ đáp án bài này là: 3016944. Lời giải vắn tắc như sau: Trước hết ta có hai bổ đề sau Bổ đề 1: Cho k là số nguyên dương thỏa k ≤ 2000−17 và a,b là hai số nguyên thỏa |a−b| ≥ 2000−k. Khi đó tổng của số các số nguyênm ∈B thỏa |a−m| ≤ 1000 và số các sốm ∈B thỏa |b−m| ≤ 1000 không vượt quá 2017+k. Bổ đề 2: Cho k là số nguyên dương sao cho k ≤ 16 và a,b là hai số nguyên thỏa |a−b| ≥ k. Khi đó tổng của số các số nguyênm ∈B thỏa |a−m| ≤ 1000 và số các sốm ∈B thỏa |b−m| ≤ 1000 không vượt quá 4002. Đặt S(a) là số các số nguyênm ∈B thỏa |a−m| ≤ 1000. Trở lại bài toán, gọi a1 < a2 < ...< a2000 là các phần tử của A. Khi đó ? |a1−a2000| ≥ 1999= 2000−1 nên theo bổ đề 1 ta có S(a1)+S(a2000)≤ 2017+1= 2018. ? |a2−a1999| ≥ 1997= 2000−3 nên theo bổ đề 1 ta có S(a2)+S(a1999)≤ 2017+3= 2020 ? |a3−a1998| ≥ 1995= 2000−5 nên theo bổ đề 1 ta có S(a3)+S(a1998)≤ 2017+5= 2022 ? ............ ? |a992−a1009| ≥ 17= 2000−1983 nên theo bổ đề 1 ta có S(a992)+S(a1009)≤ 2017+1983= 4000, ? |a993−a1008| ≥ 15 nên theo bổ đề 2 ta có S(a993)+S(a1008)≤ 4002. ? |a994−a1007| ≥ 13 nên theo bổ đề 2 ta có S(a994)+S(a1007)≤ 4002. ? .......... ? |a1000−a1001| ≥ 1 nên theo bổ đề 2 ta có S(a1000)+S(a1001)≤ 4002. Từ đây suy ra K = S(a1)+S(a2)+...+S(a2000)≤ (2018+2020+2022+...+4000)+8×4002= 3016944. 3 htt p:/ /m ath sco pe .or g Cho tam giác ABC nội tiếp đường tròn (O) có B ,C cố định, A chuyển động trên cung BC của (O). Các phân giác AD,BE ,CF giao nhau tại I . Đường tròn qua D tiếp xúc với OA tại A cắt (O) tạiG.GE ,GF giao (O) lần thứ hai tạiM ,N . BM giao CN tại H . a) Chứng minh rằng AH đi qua một điểm cố định. b) BE ,CF giao (O) lần lượt tại K ,L. AH giao KL tại P . Q là một điểm trên EF sao cho QP = QI . J là điểm nằm trên (BIC ) sao cho I J ⊥ IQ. Chứng minh rằng trung điểm I J chuyển động trên một đường tròn cố định. Bài toán 3 TST 2016 Lời giải (Nguyen Van Linh) a) Thực ra câu này cần chứng minh H thuộc phân giác AD và AD luôn đi qua trung điểm cung BC cố định. Do đường tròn Apollonius trực giao với (O) nên đường tròn đi qua D và tiếp xúc với (O) tại A chính là đường tròn A-Apollonius của tam giác ABC . Tâm của đường tròn là X -giao của tiếp tuyến tại A với BC . Ta có X A2 = XG2 = XB.XC nên tứ giác ABGC điều hòa. Gọi H ′ là giao của AD với EF . Ta có (AIH ′D)=−1 suy ra B(AIH ′D)=−1.Gọi W là giao của BH ′ với AC suy ra (AEWC )=−1⇒M(AEWC )=−1= (AGBC ). Do đó BM đi qua W hay BM đi qua H ′. Tương tự CN đi qua H ′. Vậy H ′ ≡H và H ∈ AD. b) Gọi Z là trung điểm cung BC chứa A. AZ giao BC tại V. Ta có A(XLF I ) = (ALBS) = C (ALBS)= (AIDS)=B(AIDS)= (AKCS)= A(XKEI ). Suy ra AX ,KL,EF đồng quy tạiU . Mà KL là trung trực AI nênUA =UI . Suy ra ∠UI A =∠UAI = 1/2A+C =∠ADX . Do đóUI ∥ BC . Gọi Y ,Y ′ là giao của đường thẳng qua I vuông góc với OI với BC và KL. Y Y ′ cắt AZ tại R. Y Y ′ giao EF tại Q ′. Áp dụng định lý con bướm cho (O), điểm I với hai dây BK và CL đi qua I ta có IY = IY ′. Mà Y ′A = Y ′I , ∠RAI = 90◦ nên Y ′R = Y ′I = Y I . Gọi T là giao củaUY ′ với BC . Ta có TY ′ ∥V R nên TVTY = 12 .UI là đường trung bình của tam giác TY Y ′ nênUT =UY ′. Áp dụng định lý Menelaus cho tam giác TY Y ′ với 3 điểm V ,U ,Q ′ suy raQ ′Y = 1/3Q ′Y hayQ ′ là trung điểm IY ′. Suy ra PQ ′ = IQ ′ hayQ ′ ≡Q. VậyO ∈ I J . GọiM ′ là trung điểm I J ta có ∠OM ′S = 90◦ nênM ′ nằm trên (OS) cố định. Lời giải (daovuquang) 4 htt p:/ /m ath sco pe .or g b) Ta chứng minh T ∈ (OS). Điều này tương đương với IO ⊥ IQ. Kẻ đường thẳng qua I vuông góc IO cắt BC ,KL tại X ,Y và cắt EF tại Q ′. Kéo dài EF cắt (O) tại M ,N . MI ,NI cắt lại (O) ở Z ,U . IY cắt ZU tại R. Áp dụng định lí con bướm cho 2 dây KL,BC , ta có: I X = IY . Áp dụng định lí con bướm cho 2 dâyMN ,ZT , ta có: IQ ′ = IR. Nhận thấy tam giác IPY vuông tại P nên để c/m Q ′ trùng Q, ta chỉ cần chứng minh Q ′P = Q ′I hayQ ′ là trung điểm IY . Điều này lại tương đương với R là trung điểm I X . Gọi V ,W lần lượt là trung điểm IB ,IC . Ta chứng minh Z ,U ,V ,W thẳng hàng. Lấy Ib , Ic là tâm bàng tiếp góc B ,C của tam giác ABC . Do AIC Ib nội tiếp nên EI .EIb = EA.EC = EM .EN , hay I ,M ,N , Ib đồng viên. Tương tự có Ic ,N , I ,M , Ib đồng viên. Lại có: IM .I Z = IB.IK = IV.I Ib nên Z ,V ,M , Ib đồng viên. Tương tự, IV.I Ib = IB.IK = IC .IL = IW.I Ic nên V ,W, Ib , Ic đồng viên. Từ đây ta nhận thấy: (V Z ,V Ib)≡ (MZ ,MIb)≡ (MI ,MIb)≡ (Ic I , Ic Ib)≡ (IcW, Ic Ib)≡ (VW,V Ib), nên Z ,V ,W thẳng hàng. Tương tựU ,V ,W thẳng hàng. Ta có đpcm. Lời giải (thaygiaocht) 5 htt p:/ /m ath sco pe .or g a) Có thể dùng tư tưởng phép chiếu xuyên tâm giải kiểu gọi điểm phẩy như sau: Rõ ràng GABC là tứ giác điều hòa (mô hình này từng xuất hiện trong VMO 2014 và VMO 2010). Đặt EF ∩ AD =H ′;BH ′∩ (O)=M ′,ME ∩ (O)=G ′. Ta chỉ cần chứng minh GB GC = c b . Thật vậy, ta có H ′E H ′F = AE AF = a+b a+ c . Suy ra (theo Định lý sin) M ′E1 M ′A = sin ƒH ′BE sinƒH ′BF = H ′E H ′F . BF BE = ca lb(c+a) . Do vậy (theo Định lý sin) GB GC = GB ME1 . ME1 MA . MA GC = lb ME . ca (c+a)lb . ME .ab (c+a) = c b . b) Sau khi vẽ hình chắc tay để phát hiện ra I J đi qua O, ta chuyển bài toán về ít điểm như sau: 6 htt p:/ /m ath sco pe .or g Cho tam giác ABC nội tiếp (O), ngoại tiếp (I ), phân giác trong BE ,CF ; D2 là trung điểm cung lớn BC . Đường thẳng qua O vuống góc OI cắt EF và AD2 tại Q và X . Chứng minh I X = 4IQ. Bài toán này giải qua 2 bước như sau: Bước 1. Gọi IQ∩BC = X1 và X ′ là trung điểm của AD2. Ta sẽ chứng minhQX =QX1. Thật vậy, theo một tính chất quen thuộc thì EF⊥IaO. Theo tiêu chuẩn song song trung điểm thìO(Ia ID1X ′)=−1. Theo tính chất chùm vuông góc, suy ra Y (I xB A)=−1 với Y x||X ′X1. Suy raQX =QX1. 7 htt p:/ /m ath sco pe .or g Bước 2. Chứng minh I X1 = 2IQ. Điều này dựa vào bước 1, cụ thể như sau: Do Y (X1QIX )=−1 nên QX QI = X1X X1I . Đặt X1X = 6a, I X1 = x thì tỷ lên trên được viết lại 3a 3a−x = 6a x . Giải phương trình đại số này được x = 2a hay bước 2 được chứng minh. Tóm lại bài toán được giải quyết Cho tam giác ABC nhọn có ∠ACB <∠ABC <∠ACB + ∠BAC 2 . Lấy điểm D thuộc cạnh BC sao cho∠ADC =∠ACB+∠BAC 2 . Tiếp tuyến với đường tròn ngoại tiếp tam giác ABC tại A cắt BC tại E . Phân giác ∠AEB cắt AD và cắt (ADE) tạiG và F , DF giao AE tại H . a) Chứng minh rằng các đường tròn đường kính AE ,DF,GH có một điểm chung. b) Trên phân giác ngoài ∠BAC và trên tia AC lần lượt lấy các điểm K và M sao cho KB = KD =KM , trên phân giác ngoài ∠BAC và trên tia AB lần lượt lấy các điểm L và N sao cho LC = LD = LN .Đường tròn đi quaM ,N và trung điểm I của BC cắt BC tại P (P 6= I ). Chứng minh rằng BM ,CN ,AP đồng quy. Bài toán 4 TST 2016 Lời giải (Nguyen Van Linh) a) Một lần nữa chúng ta lại thấy bóng dáng của định lý Brocard. Bổ đề. Cho tứ giác ABCD nội tiếp (O), AC giao BD tại P,AB giao CD tại E , AD giao BC tại F . Gọi M là điểm Miquel của tứ giác toàn phần ABCD.EF. Khi đó O,P,M thẳng hàng và M là hình chiếu củaO trên EF. Đây là một bổ đề rất quen thuộc xin dành cho bạn đọc tự chứng minh. Quay lại bài toán. Ta có ∠AEB =∠ABC −∠ACB nên ∠DAF =∠DEF = 1 2 (∠ABC −∠ACB)= 90◦− ( ∠ACB + 1 2 ∠BAC ) = 90◦−∠ADC . Do đó AF ⊥BC tại S. Suy ra (AE), (DF ) lần lượt là (ASE), (DSF ). 8 htt p:/ /m ath sco pe .or g Gọi J là giao điểm thứ hai của (ASE) và (DSF ). Khi đó J là điểmMiquel của tứ giác toàn phần AEDF.SH . Theo bổ đề trên ta có J ∈ SH và ∠GJH = 90◦. Suy ra (AE), (DF ), (GH) đồng quy tại J . b) Gọi B ′ đối xứng với B qua AK suy ra B ′ ∈ AC và B ′ ∈ (K ). Ta có ∠BDM =∠BB ′M =∠BAC/2=∠CAR (R là chân phân giác trong). Suy ra ADRM nội tiếp. Tương tự N ∈ (ADR). Gọi X là tâm (ADR) (không khó nhận ra X chính là F ). Do tam giác ADR cân nên AX ⊥BC . Ta có ∠XRA =∠X AR =∠RAO, suy ra XR ∥ AO. Mà AR là phân giác ∠NAM nên R là điểm chính giữa cungMN , suy ra XR ⊥MN . VậyMN ⊥ AO hayMN đối song với BC trong tam giác ABC . Suy ra tứ giác BNCM nội tiếp. Gọi Y là giao của BM và CN , Z là giao củaMN với BC . Ta có ZP.Z I = ZM .ZN = ZB.ZC , suy ra (PZBC )=−1, suy ra P ∈ AY . Ta có đpcm. Lời giải (thaygiaocht) a) Gọi AF ∩BC =H ′ thì dùng cộng góc thông thường được AH ′⊥BC . Gọi Q là điểm Miquel của tứ giác toàn phần trong hình thì theo trên ta có Q là giao của 2 đường tròn đường kính AE và BF . Theo tính chất của [B]điểmMiquel[/B] và [B]Định lý Brocard[/B] thìO′,G ,Q thẳng hàng và O′G⊥HH ′. Suy ra điểmQ thuộc đường tròn đường kínhGH . PS: ĐiểmMiquel thường là điểm đồng quy của các đường tròn cần chứng minh đồng quy và nó cũng thường là điểm tiếp xúc của các đường tròn cần chứng minh tiếp xúc. 9 htt p:/ /m ath sco pe .or g b) Sử dụng kỹ thuật gọi điểm phẩy (cụ thể là gọi P’) kết hợp hệ thức Maclaurin (kiểu VMO 2009) ta thấy mấu chốt là cần chứng minh tứ giác BNMC nội tiếp. Dùng phép chiếu song song sẽ thấy AK AL = AB AC . Suy ra tam giác ABK đồng dạng tam giác ACL (g − c − g ), chú ýƒK AM =LAN theo tính chất phân giác trong. Đến đây, ta cần chứng minh được tam giác AMK đồng dạng tam giác ANL. Điều đó đúng do các gócƒMAL,ƒNAK nhọn và theo Định lý sin thì sinƒAMK sinƒMAL = AKKM = AKKB = ALLC = ALLN = sinANLsinƒNAK . Cho a1,a2, ...,an−1,an (n ≥ 3), trong đó mỗi số ai nhận giá trị ∈ {0;1}. Xét n bộ số S1 = (a1,a2, ...,an−1,an), S2 = (a2,a3, ...,an ,a1);...;Sn = (an ,a1, ...,an−2,an−1). Với mỗi bộ số r = (b1,b2, ...,bn), đặt ω(r )= b1.2n−1+b2.2n−2+ ...+bn .20. Giả sử các số ω(S1);ω(S2); ...;ω(Sn) nhận đúng k giá trị phân biệt. a) Chứng minh rằng n ...k và ω(Si ) ... 2n −1 2k −1 ∀i = 1,n. b) Kí hiệuM vàm lần lượt là max và min của ω(S1), ...,ω(Sn). Chứng minh rằng M −m ≥ (2 n −1)(2k−1−1) 2k −1 . Bài toán 5 TST 2016 Lời giải (Zaraki) Trường hợp k = n thì hiển nhiên, ta sẽ đi xét cho k < n. Kí hiệu T = (b1b2 · · ·bl ), và nếuM = (c1c2 · · ·cn) thì TM = (b1b2 · · ·blc1c2 · · ·cn). Kí hiệu T >M ⇐⇒ l > n và T =M ⇐⇒ l = n; bi = ci , ∀1≤ i ≤ l và |T | = l . Kí hiệu Si = (aiai+1 · · ·ai−1). Khi đó ω(Si )=ω(S j ) ⇐⇒ Si = S j . 10 htt p:/ /m ath sco pe .or g Ta sẽ đi chứngminh rằngnếu tồn tạimột bộω(Si )=ω(S j ) thì S1 = AAA · · ·A với A = (b1b2 · · ·bl ) với bi ∈ {0,1}∀1≤ i ≤ l . Xét một cặp ω(Sx)=ω(Sy ) thì Sx = Sy hay AB =BA với A = (ax · · ·ay−1),B = (ay · · ·ax−1). Không mất tính tổng quát, giả sử A ≥ B thì đặt A = BC ta suy ra CB = BC . Tiếp tục xét nếu B ≤C hoặc B ≥C để đưa về CD = DC hay BD = DB . Quá trình cứ tiếp tục diễn ra nên theo thuật toán chia Euclid, sẽ đến một lúc mà tồn tại XY = Y X và ∣∣∣X ∣∣∣ = ∣∣∣Y ∣∣∣. Từ đây ta suy ra ngay X = Y . Do đó, ta dẫn đến A = X X · · ·X (u times),B = X X · · ·X (v times) suy ra Sx = Sy = X X · · ·X . Hay nói cách khác, nếu tồn tại hai bộ sốmàω(Sx)=ω(Sy ) thì bộ (a1,a2, · · · ,an) chính là vòng lặp của bộ (a1,a2, · · · ,ah) với h < n và h | n. Nếu ta gọi (a1,a2, · · · ,ah) chính là vòng lặp nhỏ nhất của bộ (tức không thể tìm được vòng lặp nhỏ hơn, (a1, · · · ,al ) với l < h, l | n) thì ta sẽ chứng minh h = k. Dễ dàng thấy rằng ω(Sx)=ω(Sh+x)= ·· · =ω(Sn−h+x) (1) với 1 ≤ x ≤ h. Ta sẽ chứng minh rằng nếu x 6≡ y (mod h) thì ω(Sx) 6= ω(Sy ). Thật vây, giả sử phản chứng, ω(Sx)=ω(Sy ) thì ta dẫn đến (ax · · ·aha1 · · ·ax−1)= (ay · · ·aha1 · · ·ay−1) ta suy ra từ đánh giá trên sẽ tồn tại vòng lặp cho bộ (ax · · ·aha1 · · ·ax−1), và vòng lặp này nhỏ hơn vòng lặp (a1a2 · · ·ah), mâu thuẫn với điều kiện nhỏ nhất của vòng lặp (a1a2 · · ·ah). Do đó, ω(Sx) 6=ω(Sy )∀x 6≡ y (mod h). Do đó từ (1) ta suy ra ω(Si ) (1≤ i ≤ n) có đúng h giá trị phân biệt, ta dẫn đến h = k. Do đó k = h | n. Do S1 = (a1,a2, · · · ,ak) là vòng lặp của bộ (a1,a2, · · · ,ak) nên Si cũng là một vòng lặp của bộ (ai ,ai+1 · · ·ak ,a1, · · · ,ai−1). Do đó ω(Si )= ( ai2k−1+ai+12k−2 · · ·+ai−22+ai−1 ) · 2n−1 2k−1 . Ta suy ra 2 n−1 2k−1 |ω(Si ). Cho các số thực phân biệt α1,α2, ...,α16. Với mỗi đa thức hệ số thực P (x); đặt V (P )= P (α1)+P (α2)+ ...+P (α16). Chứng minh rằng tồn tại duy nhất đa thứcQ(x) bậc 8 có hệ số x8 bằng 1 thỏa mãn i) V (QP )= 0 với mọi đa thức P có bậc bé hơn 8. ii) Q(x) có 8 nghiệm thực (tính cả bội). Bài toán 6 TST 2016 Lời giải (Traum) i) Phần 1: Chứng minh tồn tại đa thứcQ(x) thỏa mãn điều kiện a: Ta sẽ chứngminh rằng với mọi số nguyên dương k thì tồn tại đa thức bậcQk(x) bậc k và hệ số bậc cao nhất là 1 sao cho 16∑ i=1 α j iQk(αi )= 0 với mọi 0≤ j ≤ k−1. Với k = 1 chọnQ1(x)= x− 16∑ i=1 αi 16 , dễ thấy 16∑ i=1 Q1(αi )= 0. Với k = 2 chọnQ2(x)= x2+ax+b với a,b thỏa mãn hệ phương trình 16∑ i=1 α2i +a 16∑ i=1 αi +16b = 0 và 16∑ i=1 α3i +a 16∑ i=1 α2i +b 16∑ i=1 αi = 0 (dễ thấy là tồn tại a và b). Gỉa sử đã cóQk(x) bậc k vàQk−1(x). Ta xây dựngQk+1(x) từ chúng. ĐặtQk+1(x)= (x+a)Qk(x)+bQk−1(x) với a và b thỏa mãn: 11 htt p:/ /m ath sco pe .or g 16∑ i=1 αki Qk(αi )+b 16∑ i=1 αk−1i Qk(αi )= 0 và 16∑ i=1 (αk+1i +aαki )Qk(αi )+b 16∑ i=1 αki Qk(αi )= 0 (Dễ thấy là b xác định được trước, rồi xác định a). Bây giờ ta chứng minh rằng 16∑ i=1 α j iQk+1(α j )= 0 với mọi 0≤ j ≤ k. Thật vậy với 0≤ j ≤ k−2: 16∑ i=1 α j iQk+1(αi )= 16∑ i=1 (α j+1i +aα j i )Qk(αi )+b 16∑ i=1 α j iQk−1(αi )= 0. Với j = k−1 thì phải có 16∑ i=1 αki Qk(αi )+b 16∑ i=1 αk−1i Qk(αi )= 0. Với j = k cũng phải có 16∑ i=1 (αk+1i +aαki )Qk(αi )+b 16∑ i=1 αk−1i Qk(αi )= 0. Vậy theo quy nạp thì sẽ tồn tạiQ(x) bậc 8 và có hệ số cao nhất bằng 1 sao cho 16∑ i=1 α j iQ(αi )= 0 với mọi 0 ≤ j ≤ 7. Hơn nữa mọi đa thức P (x) có bậc nhỏ hơn 8 là tổ hợp tuyến tính của 1,x, ..,x7 nên có 16∑ i=1 P (αi )Q(αi )= 0. ĐPCM. ii) Phần 2: Chứng minhQ(x) có 8 nghiệm vàQ(x) là duy nhất. Bổ đề: đa thức R(x) bậc chẵn, có hệ số bậc lớn nhất là 1 và tồn tại a mà R(a)< 0 thì R có ít nhất hai nghiệm thực. Với P (x)= 1 thì 16∑ i=1 Q(αi )= 0. DoQ(x) bậc 8 nên không thể xảy r