15 bài toán số học cho học sinh chuyên Toán THPT

m at h. vn - 20 11 15 BÀI TOÁN SỐ HỌC CHO HỌC SINH CHUYÊN TOÁN PTTH Bài 1. Cho n là số lẻ, n> 1. Chứng minh rằng: 3n+1 không chia hết cho n. Lời giải Giả sử ord3n= s ta có 32n−1 ... n⇒ 2n ... s Nhưng vì 3n−1 ko chia hết cho n (nếu ko thế thì 2= 3n+1−(3n−1) ... n ) nên n ko chia hết cho s vậy s= 2t và ta có ngay n ... t đồng thời vì thế mà t lẻ. Lại vì 3s−1 ... n⇒ 32t−1= (3t−1)(3t+1) ... s= 2t bởi s= ord3n nên s ko thể chia hết 3t−1 tức 3t+1 ... t. Từ đây nhận thấy vai trò của t chính như n ta áp đặt tính tối đại vào là xong!  Bài 2. Cho số nguyên tố p > 3, với mỗi k ∈ {1,2........p−1}, chọn duy nhất 1 số xk : kxk ≡ 1 mod p. Các số nk xác định bởi kxk = 1+ pnk; ∀k ∈ {1,2........p−1}. Chứng minh rằng: n∑ k=1 k.nk ≡ p−1 2 mod p Lời giải Giả sử i ∈ {1,2, · · · , p−1}. Với αi ∈ {1,2, · · · , p−1} thỏa i ·αi ≡ 1( mod p) ở đây 1≤ i ≤ p−1. Rõ là (p− i)(p−αi)≡ 1( mod p) và i ·αi = p ·ni+1 với 1≤ i ≤ p−1. Vì thế mà ta có: p−1∑ i=1 i ·ni = p−1∑ i=1 i · ( i ·αi−1 p ) = 1 p p−1∑ i=1 (i2 ·αi− i)= 1p p−1∑ i=1 i2 ·αi− 1p p−1∑ i=1 i = 1 p p−1∑ i=1 i2 ·αi− p−12 = 1 p p−1 2∑ i=1 ( i2 ·αi+ (p− i)2 · (p−αi) )− p−1 2 = p−1 2∑ i=1 ( p2− (2i+αi)p+ (i2+2i ·αi) )− p−1 2 ≡ p−1 2∑ i=1 (i2+2i ·αi)− p−12 ( mod p)≡ p−1 2∑ i=1 (i2+2)− p−1 2 ( mod p) (bởi i ·αi ≡ 1( mod p) ≡ ( p−1 2 )( p+1 2 ) p 6 +2 · (p−1) 2 − p−1 2 ( mod p) Để ý là ( p−1 2 )( p+1 2 ) p 6 ≡ 0( mod p); p> 3 Do đó ta thấy là: n∑ i=1 i2 = n(n+1)(2n+1) 6 ≡ p−1 2 ( mod p)  Bài 3. Cho f (x) :N∗→N∗ thỏa mãn f (xy)= f (x). f (y) với mọi x; y, thỏa mãn (x; y)= 1. f (x+ y)= f (x)+ f (y) với x; y là các số nguyên tố tùy ý. Tính f (2); f (3); f (2009) Lời giải Có f (6)= f (3)+ f (3)= f (2). f (3) vậy f (2)= 2 Lại có f (3)= f (5)− f (2)= f (7)− f (2)− f (2)= f (12)− f (5)−4= f (12)− f (3)− f (2)−4 = f (4). f (3)− f (3)−6= ( f (2)+ f (2). f (3)− f (3)−6= 4. f (3)− f (3)−6⇒ f (3)= 3 f (2009)= f (49). f (41); f (4). f (11)= f (44)= f (3)+ f (41); f (4)= f (2)+ f (2)= 4; f (11)= f (14)− f (3)= f (2). f (7)− f (3) Còn f (7)= f (2)+ f (5)= f (2)+ f (2)+ f (3)= 7 Vậy f (11)= 11 và f (41)= 41 f (49)= f (2)+ f (47)= f (2)+ f (50)− f (3)= f (2)+ f (2) f (25)− f (3) f (25)= f (2)+ f (23)= f (2)+ f (26)− f (3)= f (2)+ f (2). f (13)− f (3) f (13)= f (11)+ f (2)= 13⇒ f (25)= 25⇒ f (49)= 49 Vậy f (2009)= 2009  1 m at h. vn - 20 11 Bài 4. Hãy khẳng định hoặc phủ định mệnh đề sau: Với mọi cặp số vô tỷ s; r luôn tồn tại m; n ∈N sao cho [sm]= [rn] Lời giải Ta sẽ khẳng định mệnh đề. Với mọi cặp số thực s; r luôn tồn tại m;n ∈N sao cho [sm]= [rn]. Ta chỉ cm với s 6= 0 và r 6= 0. Với hai số thực s, r chọn số số tự nhiên k>max|s|, |r|, ta xét hai dãy số (si); (r i) như sau: si = is − [ i s ] và r i = ir − [ i r ] với 0≤ i ≤ k, như vậy ta có k2+1 cặp số (si, r i) và tương ứng với nó là cặp số nguyên ([ksi], [kr i]) vơi mọi 0≤ i ≤ k. Mặt khác 0≤ si, r i < 1 nên chỉ có k2 cặp ([ksi], [kr i]), do đó tồn tại hai cặp (si1 , r i1); (si2 , r i2) với 0≤ i1 < i2 ≤ k sao cho [ksi1]= [ksi2]; [kr i1]= [kr i2]. Suy ra |ksi1 −ksi2 | = |ksi1 −ksi2 | < 1⇒|si1 − si2 | < 1 |s| , tương tự |r i1 − r i2 | < 1 |r| . Chọn m= [ i2 s ] − [ i1 s ] ; n= [ i2 s ] − [ i1 s ] và đặt p= i2− i1 ta có: ∣∣∣ p s −m ∣∣∣= |si1 − si2 | < 1|s| ⇒ |p−ms| < 1⇒ p−1<ms< p⇒ [ms]= p;∣∣∣ p r −n ∣∣∣= ∣∣r i1 − r i2∣∣< 1|r| ⇒ |p−nr| < 1⇒ p−1< nr < p⇒ [nr]= p. Vậy tồn tại hai số tự nhiên m,n để [ms]= [nr].  Bài 5. Olympic BaLan 1986 Chứng minh rằng với mỗi n ∈N,n≥ 3 thì n! luôn biểu diễn được bằng tổng của n ước số khác nhau của nó. Lời giải Viết n!= (n−1)!+ n−1∑ k=1 n! k(k+1) là xong! Bài 6. Tìm số nguyên tố p và các số nguyên dương x, y thỏa mãn phương trình x3+ y3 = p4. Lời giải Có ngay x+ y; x2− xy+ y2 là ước của p4 do đó x+ y; x2− xy+ y2 ∈ {1; p; p2; p3; p4} và hễ x+ y= pk thì x2− xy+ y2 = p4−k. Lại thấy (x+ y)2 > x2− xy+ y2 ≥ x 2+ y2 2 ≥ (x+ y).(x+ y) 4 do đó cả x; y đều phải bé hơn 4. Thay vào thử thấy có mỗi x= y= p= 2 thỏa. Bài 7. Cho x; y; n; p ∈N∗ thỏa xn+ yn = pk biết p; n; k > 1 và p; n cùng lẻ, p là số nguyên tố. Chứng minh rằng n là lũy thừa của p. Lời giải Không mất tính tổng quát ta chỉ xét trường hợp (x; p)= (y; p)= 1 Có x+ y là ước của pk đồng thời x+ y> 1 do đó x+ y= pl với 0< l ≤ k Ta thấy pk = xn+ yn = xn+ (pl − x)n = (pl)2. n∑ t=2 (−x)n−t.pl(t−2)Ctn+n.xn−1.pl ...pl+1 ⇒ n.xn−1.pl ...pl+1⇒ n...p⇔ n= p.n1. 2 m at h. vn - 20 11 Lại lặp lại suy luận này với phương trình nghiệm nguyên có nghiệm là: X n1 +Y n1 = pk với X = xp; Y = yp ta lại có n1 ...p .... từ đây có ĐPCM! Bài 8. Tính trung bình cộng của tất cả các số tự nhiên n thỏa mãn n có 2010 chữ số mà các chữ số đều thuộc tập {1,2,3,4,5,6,7,8} đồng thời n chia hết cho 99999. Lời giải Có r ∈ {1,2,3,4,5,6,7,8}⇔ 9− r ∈ {1,2,3,4,5,6,7,8} và rõ ràng 9− r!= r. Do đó hễ mà n= a1a2..a2010 là số có 2010 chữ số mà các chữ số đều thuộc tập {1,2,3,4,5,6,7,8} thì n′ = f (A)= b1b2..b2010 với bi = 9−ai cũng là số có 2010 chữ số mà các chữ số đều thuộc tập {1,2,3,4,5,6,7,8} đồng thời n!= n′ và n+n′ = 99...9...99999 (để ý 2010...5). Thêm nữa hễ n1!= n2 thì rõ ràng n′1 = f (n1)!= n′2 = f (n2). Tất cả lý luận trên cho thấy tập các số tự nhiên n thỏa mãn: n có 2010 chữ số mà các chữ số đều thuộc tập {1,2,3,4,5,6,7,8} đồng thời n chia hết cho 99999 được phân hoạch thành từng cặp rời nhau mà tổng các cặp đó là 99...9. Vậy trung bình cộng cần tính là 1 2 99...9= 10 2011−1 2 . Bài 9. Chứng minh rằng ∀n ∈N∗ thì giữa n2 và (n+1)2 luôn tồn tại ba số tự nhiên phân biệt a; b; c thỏa a2+b2... c. Lời giải Chọn a= n2+2,b= n2+n+1, c= n2+1 thì hiển nhiên n2 < a,b, c< n2+2n+1. Hơn nữa a2+b2 = (n2+1+1)2+ (n2+1+n)2 = (n2+1)2+2(n2+1)+ (n2+1)2+2n(n2+1)+n2+1= (n2+1).m. Bài 10. Cho các số nguyên dương a≥ b≥ c và d thỏa mãn các điều kiện sau: * abc= d3. * Số a+b+ c−d là một ước số nguyên tố của số ab+bc+ ca−d2 Chứng minh rằng b= d. Lời giải Từ giả thiết có ngay c≤ d ≤ a và p= a+b+ c−d|d.(ab+bc+ ca−d2)−d2.(a+b+ c−d) = d3− (a+b+ c)d2+ (ab+bc+ ca)d−d3 = d3− (a+b+ c)d2+ (ab+bc+ ca)d−abc= (d−a).(d−b).(d− c). Do p= a+b+ c−d là số nguyên tố nên buộc p phải là ước của 1 trong các số d−a; d−b; d− c. - Nếu a= c thì a= b= c= d kết luận của bài toán là hết sức tầm thường. - Nếu a> c p ko thể là ước của d−a vì 0< |d−a| p = a−d a+b+ c−d < 1. p lại càng không thể là ước của d− c đơn giản vì theo bdt Cauchy a+b+ c−d > 3d−d = 2d > d− c> 0 Vậy chỉ có thể p là ước của d−b lại cũng vì p> 2d > d−b nên nếu d > b thì p> d−b> 0 nên ko thể có d−b...p. Còn nếu b> d thì p= b−d < b−d+a+ c= p cũng ko thể thỏa. Tóm lại: b= d  Bài 11. Cho dãy số nguyên (an) xác định bởi: a0 = 1;a1 =−1; an = 6an−1+5an−2 với mọi n≥ 2. Chứng minh rằng a2012−2010 chia hết cho 2011 Lời giải 3 m at h. vn - 20 11 Phương trình đặc trưng của dãy đã cho là: x2−6x−5= 0 có hai nghiệm là 3−p14; 3+p14 do đó dễ dàng có được công thức số hạng tổng quát của dãy là: an = ( 7−2p14)(3+p14)n+ (7+2p14)(3−p14)n 14 =−un−2vn Với: un = ( 3+p14)n−1+ (3−p14)n−1 2 ; vn = ( 3+p14)n−1− (3−p14)n−1 2 p 14 Sử dụng khai triển Newton ta có được: u2012 = 1005∑ k=0 C2k20113 2011−2k14k = 32011+ 1005∑ k=1 C2k20113 2011−2k14k Do 1< 2k< 2011 với 1≤ k≤ 1005 vậy nên số nguyên C2k2011 = 2011 ( C2k−12010 2k ) ... 2011 vì 2011 là số nguyên tố. Vậy u2012 ≡ 3 (mod 2011) do 32011 ≡ 3 (mod 2011) (định lý Fermat bé). Cũng theo khai triển Newton thì: v2012 = 141005+∑1005k=1 C2k−12011 32012−2k14k−1 Để ý rằng: C2k−12011 = 2011 ( C2k−22010 2k−1 ) ... 2011 với k ∈ {1; 2; · · · 1005} do tính nguyên tố của 2011. Thế nên v2012 ≡ 141005 (mod 2011) Do ( 14 2011 ) =−1 nên ta có v2012 ≡ −1 (mod 2011) Vậy a2012−2010 ≡ −3−2(−1)−2010 ≡ 0 (mod 2011)  Bài 12. Cho p là số nguyên tố và dãy tăng các số nguyên dương {r i}mi=1 nhỏ hơn p thỏa: r m i ≡ 1 (mod p)∀ i ∈ {1; 2; · · · ;m}. Chứng minh rằng: xm−1≡ (x− r1)(x− r2) · · · (x− rm) (mod p)∀x ∈Z. Lời giải Bài này dùng khai triển Abel: f (x)= xm−1= b0(x− r1)...(x− rm)+ ...+bm−1(x− r1)+bm So sánh hệ số xm suy ra b0 = 1. Từ giả thiết suy ra: f (r1)= rm1 −1≡ 0 (mod p) ⇒ bm ≡ 0 (mod p) f (r2)= rm2 −1≡ 0 (mod p) ⇒ bm−1 ≡ 0 (mod p) . . . f (rm)= rmm−1≡ 0 (mod p) ⇒ b1 ≡ 0 (mod p) Suy ra: xm−1≡ (x− r1)(x− r2) · · · (x− rm) (mod p)∀x ∈Z.  Bài 13. Cho p là số nguyên tố lẻ. Chứng minh rằng không tồn tại các số nguyên x, y thỏa mãn hệ thức: xp+ yp = p[(p−1)!]p. Lời giải Giả sử có x; y ∈Z thỏa yêu p((p−1)!)p = xp+ yp thì theo định lý Fermat bé thì: p((p−1)!)p = xp+ yp ≡ x+ y mod p Vì thế sẽ dẫn đến biểu diễn x= kp− y với k ∈Z. Lúc ấy do Cp−1p = p nên: xp+ yp = (kp− y)p+ yp =∑p−2j=0 C jp(kp)p− j(−y) j+kp2yp−1 ≡ 0 mod p2 Vậy p((p−1)!)p ... p2 tức ((p−1)!)p ... p dẫn đến (p−1)! ... p Điều không thể xảy ra này dẫn ta đến sự khẳng định cho những gì cần chứng minh  Bài 14. Chứng minh tồn tại x; y; z : ax2+by2+ cz2 ... p 4 m at h. vn - 20 11 Lời giải Cách 1 Với p nguyên tố ta có nhận xét: * Tập p−1 2 số { i2 : i = 1; . . . ; p−1 2 } từng đôi không đồng dư mod p. * i2 = (p− i)2 mod p Do đó tập T = {1; 2; . . . ; p−1} chứa đúng p−1 2 số chính phương mod p và p−1 2 số không là chính phương mod p. Gọi L là tập các số chính phương mod p của T. Lúc ý dễ dàng kiểm tra: aL= L∀a ∈ L và aL=T \L∀a ∉ L (Thực ra L là nhóm con của nhóm nhân Zp và có hai loại lớp kề L và T \L ) Ta cần chỉ ra có thể chọn trong mỗi tập: aL∪ {0}, bL∪ {0}, cL∪ {0} một phần tử để tổng của chúng là bội p. Xét ba tập aL, bL, cL có vài trường hợp sau: * Có hai tập là L còn tập còn lại là T \L chẳng hạn aL= bL= L; cL=T \L lúc ý: * Nếu p−1 ∈ L thì 1+ p−1+0 thỏa mãn * Nếu p−1 ∈T \L thì 1+0+ p−1 thỏa mãn. * Có hai tập là T \L còn tập còn lại là L chẳng hạn aL = bL = T \L; cL = L lúc ý gọi u là phần tử của T \L thì: * Nếu p−u ∈ L thì u+0+ p−u thỏa mãn * Nếu p−u ∈T \L thì u+ p−u+0 thỏa mãn. * Ba tập đó đểu kiểu L, lúc ý xét p−1 2 cặp (1; p−2), (2; p−3), . . . , ( p−3 2 ; p+1 2 ) ), ( p−1 2 ; p−1 2 ) có: * Nếu có một cặp (i; p−1− i) cùng thuộc L thì tổng 1+ i+ (p−1− i) thỏa mãn * Ngược lại, nếu các cặp (i; p−1− i) đều có không quá một số thuộc L thì cặp cuối cùng ít nhất có một số thuộc L: * Nếu là p−1 ∈ L thì tổng 1+ (p−1)+0 thỏa mãn * Nếu là p−1 2 ∈ L thì tổng 1+ p−1 2 + p−1 2 thỏa mãn. * Ba tập đó cùng kiểu T \L, gọi u là phần tử của T \L. Xét các cặp (u; (p−2)u), (2u; (p−3)u), . . . , ( (p−1)u 2 ; (p−1)u 2 ) . * Nếu có một cặp (iu; (p−1− i)u) cùng thuộc T \L thì tổng u+ iu+ (p− i−1)u thỏa mãn * Ngược lại thì trong cặp cuối cùng có ít nhất một số thuộc T \L: * Nếu (p−1)u ∈T \L thì tổng u+ (p−1)u+0 thỏa mãn * Nếu (p−1)u 2 ∈T \L thì tổng u+ (p−1)u 2 + (p−1)u 2 thỏa mãn Tóm lại bài toán được chứng minh  Cách 2 Giả dụ có một trong ba số a; b; c kia mà là bội của p thì điều ta cần khẳng định là hết sức tầm thường. Thí dụ hễ a là bội của p thì chọn x= 1 còn y= z= 0 là xong. Khi cả a; b; c đều chả là bội của p lại xét hai khả năng sau: 1) Nếu tồn tại x; y không đồng thời là bội của p mà p |ax2+by2 thế thì chọn z= 0 là xong. 2) Nếu không tồn tại x; y không đồng thời là bội của p mà p |ax2+by2 khi đó xét hai tập sau: A = { ak2 : k= 1; 2; · · · ; p−1 2 } , B= { −bl2− c : l = 1; 2; · · · ; p−1 2 } Rất dễ dàng thấy là các phần tử của A không có đồng dư với nhau khi chia cho p và tất nhiên trong A không có bội của p. Tình hình bên tập B kia cũng vậy. * Hễ có một phần tử của A mà đồng dư với một phần tử của B thì xong ngay. * Hễ không thể chọn ra từ mỗi tập một phần tử để chúng có cùng số dư khi chia cho p. Thế thì dẫn đến:∑ a∈A a+ ∑ b∈A b ≡ 1+2+·· ·+ p−1 mod p 5 m at h. vn - 20 11 Khổ cái điều này dẫn đến: (a−b) p 2−1 24 p− c p−1 2 ≡ p−1 2 p ≡ 0 mod p Điều này thì đúng thế nào nổi do c p−1 2 không thể là bội của p  Bài 15. Cho dãy số (xn)n được xác định như sau: x1 = a,x2 = b,xn = x2n−1+ x2n−2 xn−1+ xn−2 ,∀n ≥ 3. Với a,b > 1 là các số nguyên tố phân biệt. Chứng minh rằng xn không phải là số nguyên với mọi n≥ 3. Lời giải Dãy trên dĩ nhiên là dãy con của dãy các số hữu tỷ dương, vậy nên ta có thể đặt: xn = anbn ; an; bn ∈Z+; GCD(an; bn)= 1∀n ∈Z+ Vì xn > 1∀n ∈Z+ vậy nên: an > bn ≥ 1∀n ∈Z+ (*). Việc của chúng ta là đi chứng minh: bn > 1∀n≥ 3; n ∈Z+ và GCD(an; an+1)= 1∀n ∈Z+ Điều này sẽ được khẳng định nhờ phép quy nạp như sau: Thật vậy ta thấy rằng với n= 1; 2; 3 thì mọi thứ là rõ ràng Bây giờ ta giả sử điều cần minh tỏ đã đúng tới n−1 khi đó ta thấy: an bn = a 2 n−1+a2n−2 bn−1bn−2 (an−1+an−2) Từ đẳng thức đó và việc GCD(an; bn)= 1 ta dẫn đến: an |a2n−1+a2n−2; bn |bn−1bn−2 (an−1+an−2). Từ GCD(an−2; an−1)= 1 ta có ngay GCD(an; an−1)= 1. Giờ gọi pn là ước nguyên tố nhỏ nhất của an−1+an−2 và dn =max { pn; an−1+an−2 pn } . Bởi vì (∗) và GCD(an−2; an−1)= 1 nên dn > 2. Mặt khác GCD ( a2n−1+a2n−2; an−1+an−2 ) là ước của GCD ( a2n−1+a2n−2; a2n−1−a2n−2 )≤ 2< dn (vì GCD(an−2; an−1)= 1). Vậy nên GCD(an; dn)=GCD(a2n−1+a2n−2; dn)= 1 từ đó dn |bn dẫn đến bn > 1  6