Tổng phần nguyên - Vũ Phương Thúy

Khóa tập huấn giáo viên THPT chuyên toán năm 2016 Báo cáo chuyên đề Các phương pháp tính tổng phần nguyên Giáo viên: Trường: Vũ Phương Thúy THPT chuyên Đại học Sư phạm Hà Nội Email: [email protected] 8/2016 Tóm tắt Trong số học, phần nguyên là một trong những nội dung rất hấp dẫn. Nó cũng thường xuyên xuất hiện trong nhiều bài thi chọn học sinh giỏi toàn quốc, quốc tế với những nội dung khác nhau. Trong số đó, các bài toán về tính tổng phần nguyên xuất hiện khá đa dạng và phong phú. Vì vậy, tôi viết chuyên đề này để tổng hợp lại một số phương pháp thường gặp trong các bài toán về tính tổng phần nguyên. Trong báo cáo, tôi đề cập đến các phương pháp tính tổng phần nguyên như sau: 1. Phương pháp áp dụng định lý Hermite trong tính tổng. 2. Sử dụng định lý về điểm nguyên và phần nguyên trong các bài toán tính tổng. 3. Tính tổng phần nguyên dựa vào tính chia hết . 1 Mục lục 1 Một vài kiến thức cơ bản về phần nguyên 1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Các tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 2 Các phương pháp tính tổng phần nguyên 2.1 Định lý Hermite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Sử dụng định lý về điểm nguyên và phần nguyên trong các bài toán tính tổng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Tính tổng phần nguyên dựa vào tính chia hết . . . . . . . . . . . . . . 4 4 2 7 12 Chương 1 Một vài kiến thức cơ bản về phần nguyên 1.1 Định nghĩa Cho x là một số thực. Phần nguyên của x là số nguyên lớn nhất không vượt quá x. Kí hiệu phần nguyên của x là bxc. Như vậy bxc là số nguyên duy nhất có tính chất: bxc ≤ x < bxc + 1. Ngoài ra, người ta cũng gọi {x} = x − bxc là phần lẻ của số thực x. Khi đó: 0 ≤ {x} < 1. 1.2 Các tính chất cơ bản 1. Nếu x > y thì bxc ≥ byc. Như vậy, phần nguyên là hàm không giảm. 2. bx + nc = bxc + n với n là số nguyên. 3. bxc + byc ≤ bx + yc ≤ bxc + byc + 1. ( 0 nếu x ∈ Z 4. bxc + b−xc = −1 nếu x ∈ /Z c = b nx c với n ∈ Z 5. b bxc n 6. Cho x là số thực dương và n là một số nguyên dương. Khi đó, số các số nguyên dương là bội của n và không vượt quá x là b nx c. 3 Chương 2 Các phương pháp tính tổng phần nguyên 2.1 Định lý Hermite Định lý 2.1.1. Với n là số nguyên dương, x là số thực bất kì, ta có:       2 n−1 1 + x+ + ... + x + . bnxc = bxc + x + n n n       Chứng minh. Xét hàm f (x) = bxc + x + n1 + x + n2 + ... + x + n−1 − bnxc. n Ta có         1 1 2 1 n−1 1 f (x + ) = x + + x+ + ... + x + + − n(x + ) n n n n n n     1 n−1 = x+ + ... + x + + bx + 1c − bnx + 1c n n =f (x) Do đó, với mọi x, tồn tại 0 ≤ t < n1 sao cho f (x) = f (t). Mặt khác trong [0, n1 ) thì tất     cả các số hạng bxc, x + n1 , ... x + n−1 , bnxc đều bằng 0. n Từ đó f (x) = 0, ∀x ∈ R. P j x+i k Bài toán 2.1.1. Tính tổng . j 0≤i2 thì 2n + 1 chia 8 dư 1, suy ra A chia 8 dư 3, không thể là số chính phương. Do đó n=1. Thử lại thấy đúng. Với n=6k+2 hoặc 6k+4, 31 (2n − 1). Nếu n>2 thì 2n − 1 chia 8 dư 7, suy ra A chia 8 dư 5, không thể là số chính phương. Do đó n=2. Thử lại thấy đúng. Vậy n=1 hoặc n=2 là các giá trị cần tìm. 6 2.2. SỬ DỤNG ĐỊNH LÝ VỀ ĐIỂM NGUYÊN VÀ PHẦN NGUYÊN TRONG CÁC BÀI TOÁN TÍNH TỔNG 2.2 Sử dụng định lý về điểm nguyên và phần nguyên trong các bài toán tính tổng Định lý 2.2.1. Cho a, c là các số thực dương. Giả sử f : [a, b] → [c, d] là hàm đơn điệu tăng và là song ánh. Khi đó ta có: X X bf (k)c + bf −1 (k)c − n(Gf ) = bbcbdc − α(a)α(c) a≤k≤b (2.1) c≤k≤d Trong đó k là số nguyên, n(Gf ) là số ( điểm nguyên của đồ thị hàm số f trên đoạn [a,b] bxc khi x ∈ R+ \ N∗ và α : R+ → N∗ xác định bởi α(x) = x − 1 khi x ∈ N∗ . Chứng minh. Do f là hàm đơn điệu tăng và song ánh nên f là hàm liên tục. Kí hiệu n(M) là số điểm nguyên của miền M. Theo hình minh họa, ta có X bf (k)c = n(M1 ), a≤k≤b X bf −1 (k)c = n(M2 ), c≤k≤d n(M3 ) = bbcbdc, n(M4 ) = α(a)α(c) trong đó M1 = {(x, y) ∈ R2 |a ≤ x ≤ b, 0 < y ≤ f (x)} M2 = {(x, y) ∈ R2 |c ≤ y ≤ d, 0 < x ≤ f −1 (y)} M3 = {(x, y) ∈ R2 |0 < x ≤ b, 0 < y ≤ d} M4 = {(x, y) ∈ R2 |0 < x < a, 0 < y < c} Khi đó: n(M1 ) + n(M2 ) − n(M1 ∩ M2 ) = n(M1 ∪ M2 ) hay n(M1 ) + n(M2 ) − n(Gf ) = n(M3 ) − n(M4 ) 7 2.2. SỬ DỤNG ĐỊNH LÝ VỀ ĐIỂM NGUYÊN VÀ PHẦN NGUYÊN TRONG CÁC BÀI TOÁN TÍNH TỔNG Từ đó ta rút ra điều phải chứng minh. Định lý 2.2.2. Cho a, c là các số thực dương. Giả sử f : [a, b] → [c, d] là hàm đơn điệu giảm và song ánh. Khi đó ta có: X X bf (k)c − bf −1 (k)c = bbcα(c) − bdcα(a) a≤k≤b (2.2) c≤k≤d ( bxc khi x ∈ R+ \ N∗ Trong đó α : R+ → N∗ xác định bởi α(x) = x − 1 khi x ∈ N∗ . Chứng minh. Do f là hàm đơn điệu giảm và song ánh nên f là hàm liên tục. Kí hiệu: N1 = {(x, y) ∈ R2 |a ≤ x ≤ b, 0 < y ≤ f (x)} N2 = {(x, y) ∈ R2 |c ≤ y ≤ d, 0 < x ≤ f −1 (y)} N3 = {(x, y) ∈ R2 |0 < x ≤ b, 0 < y < c} N4 = {(x, y) ∈ R2 |0 < x < a, 0 < y ≤ d} Khi đó: X bf (k)c = n(N1 ) a≤k≤b X bf −1 (k)c = n(N2 )) c≤k≤d bbcα(c) = n(N3 ), bdcα(a) = n(N4 ) Từ đó suy ra điều phải chứng minh. n √ P b kc. Bài toán 2.2.1. Tính k=1 8 2.2. SỬ DỤNG ĐỊNH LÝ VỀ ĐIỂM NGUYÊN VÀ PHẦN NGUYÊN TRONG CÁC BÀI TOÁN TÍNH TỔNG √ √ Chứng minh. Xét hàm f : [1, n] → [1, n], f (x) = x. Đây là hàm đơn điệu tăng và có hàm ngược là f −1 (x) = x2 . Do đó ta có: √ b nc n X X √ √ bk 2 c − n(Gf ) = nb nc. b kc + k=1 k=1 √ Đăt b nc = a, ta có n X √ a(a + 1)(2a + 1) . b kc = (n + 1)a − 6 k=1 n(n+1) 2 Bài toán 2.2.2. Tính P j √8k+1−1 i 2 k=1 . h i Chứng minh. Xét hàm f : 1, n(n+1) → [1, n] sao cho 2 √ 8k + 1 − 1 . f (k) = 2 Ta có f là hàm đơn điệu tăng và f −1 (k) = k(k+1) . 2 Áp dụng định lý ta có: √  n  X  8k + 1 − 1  X k(k + 1) n2 (n + 1) + − n(Gf ) = . 2 2 2 k=1 k=1 n(n+1) 2 Do đó n(n+1) √ 2 X k=1    8k + 1 − 1 n2 (n + 1) 1 n(n + 1) n(n + 1)(2n + 1) n(n2 + 2) = +n− + = 2 2 2 2 6 3 Bài toán 2.2.3. Cho m, n , s là các số nguyên dương, m ≤ n. Khi đó:  s  j ms k  (m, n)s  X X  kn  km + =s + , n m n n ms k=1 1≤k≤ n trong đó (m,n) là ước chung lớn nhất của m và n.  ms  , sao cho f (x) = m x. Chứng minh. Xét hàm f : [1, s] → m n n n n −1 Dễ thấy f là hàm đơn điệu tăng, khả nghịch và f (x) = m x. Theo định lý ta có  s  j ms k X X  kn  km + − n(Gf ) = s n m n ms k=1 1≤k≤ Ta sẽ chứng minh n(Gf ) = j (m,n)s n k n . 1 = km là số Thật vậy: Đặt m = (m, n)m1 , n = (m, n)n1 , (n1 , m1 ) = 1. Khi đó km n n1 m 2m sm nguyên j k khijvà chỉkkhi k chia hết cho j n1 . Do k đó số các số nguyên trong dãy n , n , ..., n là s n1 = (m,n)s n , hay n(Gf ) = (m,n)s n . Từ đó ta có điều phải chứng minh. 9 2.2. SỬ DỤNG ĐỊNH LÝ VỀ ĐIỂM NGUYÊN VÀ PHẦN NGUYÊN TRONG CÁC BÀI TOÁN TÍNH TỔNG Hệ quả 2.2.1. Trong trường hợp s=n, ta có kết quả sau:  X  n  m  X km kn + = (m, n) + mn n m k=1 k=1 Từ hệ quả trên và định lý, ta rút ra kết quả là bài toán trong kì thi 1998 Taiwanese Mathematical Olympiad Bài toán 2.2.4. Cho m, n là các số nguyên dương, chứng minh rằng  n−1  X km + m + n − mn. (m, n) = 2 n k=1 n   P km Chứng minh. Trước hết ta đi tính với (m ≤ n). n k=1   sao cho Xét hàm f : [1, n] → 1, m + 1 − m n f (x) = m + 1 − m x. n n Khi đó, f là hàm đơn điệu giảm và có hàm ngược là f −1 (x) = n + m (1 − x). Theo định lý, ta có:    n  X X km (1 − k)n m+1− − n+ =0 n m m k=1 1≤k≤m+1− n    n m  X X (k − 1)m kn ⇔ − =0 1+ n m k=1 k=1  X  n  m  X km kn ⇔n − m + − =0 n m k=1 k=1 Mặt khác, theo bài tập trên n  X k=1  X  m  km kn + = (m, n) + mn n m k=1 Từ đó suy ra:  n  X km k=1 n = 1 (mn + m − n + (m, n)) 2 Kết quả trên có thể viết dưới dạng  n−1  X km 1 = (mn − m − n + (m, n)) , n 2 k=1 với mọi m,n. Từ đó ta rút ra được đẳng thức cần chứng minh. Bài tập đề nghị 10 (2.3) 2.2. SỬ DỤNG ĐỊNH LÝ VỀ ĐIỂM NGUYÊN VÀ PHẦN NGUYÊN TRONG CÁC BÀI TOÁN TÍNH TỔNG Bài toán 2.2.5. Tính n−1 P k=1 Bài toán 2.2.6. Tính { km } (Japan MO-1995) n n   P k k=1 3 . Bài toán 2.2.7. Chứng minh rằng n  2 X n k=1 k2 2  n  X n √ = k k=1 Bài toán 2.2.8. Cho λ là số vô tỷ, n là số nguyên dương. Chứng minh rằng: bnλc   n X X k = nbnλc bkλc + λ k=1 k=1 Bài toán 2.2.9. Cho p, q là 2 số nguyên dương nguyên tố cùng nhau và m là số thực thỏa mãn 1 ≤ m < p. 1. Nếu s = j mq p k thì  [m]  X kq k=1 p +  s  X kp k=1 q = bmc.s 2. Nếu p, q là các số lẻ thì p−1 q−1  2  X kq k=1 p +  2  X kp q k=1 11 = (p − 1)(q − 1) 4 2.3. TÍNH TỔNG PHẦN NGUYÊN DỰA VÀO TÍNH CHIA HẾT 2.3 Tính tổng phần nguyên dựa vào tính chia hết Định lý 2.3.1. Cho p là số nguyên tố lẻ, q là số nguyên không chia hết cho p. Giả sử f : N∗ → R thỏa mãn đồng thời các điều kiện sau: a. f (k) p không là số nguyên với mỗi k=1,2,...,p-1. b. f (k) + f (p − k) là số nguyên chia hết cho p, với mỗi k=1,2,...,p-1. Khi đó ta có p−1  X k=1  X p−1 q q p−1 f (k) = f (k) − p p 2 k=1 Chứng minh. Ta có: Với mỗi k=1,2,...,p-1 thì qfp(k) + qf (p−k) ∈ Z và p Do đó, từ tính chất phần lẻ suy ra     qf (k) qf (p − k) 0< + < 2, p p qf (k) qf (p−k) , p p ∈ / Z. hay  qf (k) p   + qf (p − k) p  = 1. Lấy tổng các giá trị này từ 1 đến p-1 ta có  X  p−1  p−1  X qf (p − k) qf (k) + = p − 1, p p k=1 k=1 suy ra  p−1  X qf (k) k=1 p = p−1 . 2 Từ đó ta rút ra đẳng thức cần chứng minh. Bài toán 2.3.1. Cho p, q là 2 số nguyên tố cùng nhau. Chứng minh rằng  p−1  X p (p − 1)(q − 1) (Gauss) k = q 2 k=1 Chứng minh. Xét hàm f(x)=x. Dễ thấy f(x) thỏa mãn các điều kiện của định lý trên và theo đó ta có  X p−1  p−1 X kp kq p − 1 q p(p − 1) p − 1 (p − 1)(q − 1) = − = . − = q p 2 p 2 2 2 k=1 k=1 Bài toán 2.3.2. Cho p là số nguyên tố lẻ. Chứng minh rằng p−1  3  X k (p − 1)(p + 1)(p − 2) = p 4 k=1 (German MO-2002) 12 2.3. TÍNH TỔNG PHẦN NGUYÊN DỰA VÀO TÍNH CHIA HẾT Chứng minh. Xét hàm f (x) = x3 . Dễ thấy f(x) thỏa mãn các điều kiện của định lý. Do đó, ta có p−1  3  p−1 3 X X k k p−1 1 (p − 1)2 p2 p − 1 (p − 1)(p + 1)(p − 2) = − = . − = p p 2 p 4 2 4 k=1 k=1 Bài toán 2.3.3. Cho p là số nguyên tố lẻ. Tính tổng √ b 3 kpc (p−1)(p−2) P k=1 √ p Chứng minh. Xét f (x) : [1, (p − 1)(p − 2)] → [ 3 p, 3 p(p − 1)(p − 2)] sao cho f (x) = 3 √ 3 xp. Khi đó f là hàm đơn điệu tăng và f −1 (x) = x Khi đó ta có p (p−1)(p−2) X b p 3 X kpc + √ 3 k=1 √ p≤k≤ 3 p(p−1)(p−2)   k3 − n(Gf ) p p = (p − 1)(p − 2)b 3 p(p − 1)(p − 2)c (2.4) p 3 3 Dễ thấy b p(p − 1)(p − 2)c = (p−2) và do k không chia hết cho p với mọi k=1,2,...,p1 nên n(Gf ) = 0 Do đó (p−1)(p−2) X X  k3  p 3 b kpc + = (p − 1)(p − 2)2 p k=1 1≤k≤p−2 (p−1)(p−2) ⇔ X k=1   p (p − 1)3 (p − 1)(p + 1)(p − 2) 3 2 b kpc = (p − 1)(p − 2) + − p 4 (2.5) (p−1)(p−2) ⇔ X k=1 p (p − 1)(p + 1)(p − 2) b 3 kpc = (p − 1)(p − 2)2 + (p − 1)(p − 2) − 4 (p−1)(p−2) ⇔ X k=1 p (p − 1)(p − 2)(3p − 5) b 3 kpc = 4 Bài toán 2.3.4. Cho p là số nguyên tố có dạng 4n+1, (m,p)=1. Chứng minh  X p−1  p−1 X mk 2 mk 2 p − 1 = − p p 2 k=1 k=1 Chứng minh. Vì p là số nguyên tố có dạng 4n+1 nên với mỗi i ∈ {1, 2, ..., p−1 }, tồn tại 2 p+1 2 2 duy nhất j ∈ { 2 , ..., p − 1} sao cho i + j ≡ 0 (mod p). Do đó  X  2   2  X  2  X p−1 p−1  X mk 2 mi mj mi mj 2 mi2 p − 1 = + = + −1 = − p p p p p p 2 i=1 k=1 (i,j) (i,j) Bài toán được chứng minh 13 2.3. TÍNH TỔNG PHẦN NGUYÊN DỰA VÀO TÍNH CHIA HẾT Áp dụng kết quả trên với m=1 ta được bài toán sau là bài toán trong Vietnam TST 2005 Bài toán 2.3.5. Chứng minh rằng  p−1 2 j 2k  P  i  = (p−1)(p−5)  p 24 i=1 j k p−1 P i2  (p−1)(7p−11)    p+1 p = 24 i= 2 Chứng minh. Áp dụng bài toán trên với m=1 ta có: p−1  2  p−1 2 X X i i p−1 (p − 1)p(2p − 1) p − 1 (p − 1)(p − 2) = − = − = p p 2 6p 2 3 i=1 i=1 Mặt khác lại có p−1  2  X i p i=1 p−1 = p−1 2  2  X i p i=1 (p − i)2 + p   =2 p−1 2  2 X i i=1 p + 2 X (p − 2k) i=1 Từ đó ta có p−1 2  2 X i i=1 p 1 = 2  (p − 1)(p − 2) p(p − 1) p2 − 1 − + 3 2 4  = (p − 1)(p − 5) 24 Từ đó ta có điều phải chứng minh. Tổng quát của bài toán 2.3.4 ta có: Với p là số nguyên tố chia 4 dư 1, với hai hàm số f(x), g(x) thỏa mãn (f(x),p)=(g(x),p)=1 với mọi x. Khi đó    p−1  X g(x)f (x)i2 f (x)i2 (g(x) − 1)(p − 1) − g(x) = p p 2 i=1 Bài toán 2.3.6. Cho p là số nguyên tố lẻ. Chứng minh rằng p−1 p X k −k k=1 p ≡ p+1 (mod p) 2 p Chứng minh. Xét f (x) = xp . Dễ thấy f(x) thỏa mãn các điều kiện của định lý. Lấy q=1, khi đó ta có p−1  p  p−1 p X X k k p−1 = − p2 p2 2 k=1 k=1 p−1 p−1 1 X kp − k 1 X k p − 1 = + − p k=1 p p k=1 p 2 p−1 1 X k p − k (p − 1)2 = − p k=1 p 2p 14 2.3. TÍNH TỔNG PHẦN NGUYÊN DỰA VÀO TÍNH CHIA HẾT Do đó p−1 p X k −k p k=1 p−1  p  X k (p − 1)2 = +p 2 p k=1 hay p−1 p X k −k p k=1 ≡ (p − 1)2 p2 + 1 p+1 ≡ ≡ (mod p) 2 2 2 Chú ý 2.3.1. Từ bài tập trên ta có chú ý sau: Với mỗi k=1,2,...,p-1, kí hiệu rk là số dư của k p khi chia cho p2 . Khi đó ta có  p k p k = 2 .p2 + rk , k = 1, 2, ..., p − 1. p Do đó p−1 X p k =p k=1 2 p−1  p  X k k=1 p2 p−1 p−1 X −p2 (p − 1) X kp rk + rk = + + 2 k=1 k=1 k=1 p−1 X Từ đó suy ra p−1 X rk = k=1 p2 (p − 1) 2 Bài tập đề nghị Bài toán 2.3.7. Cho p là số nguyên tố lẻ. Tính tổng √ b 3 kpc (p−1)(p−2) P k=1 Bài toán 2.3.8. Cho p là số nguyên tố lẻ, q là số nguyên dương không chia hết cho p. Chứng minh rằng  p−1  X (p − 1)(q − 1) k 2q (−1) k = p 2 k=1 Chú ý: Với q=1, ta thu được kết quả p−1  X kk (−1) k=1 2 p  =0 Bài toán 2.3.9. Cho p là số nguyên tố lẻ, q là số nguyên dương không chia hết cho p. Tính tổng  p−1  X k 4q (−1) k p k=1 Bài toán 2.3.10. Cho p là số nguyên tố chia 4 dư 1, khi đó ta có các hệ thức sau p−1 P j i2 1 k (p−1)(2p−1) 1. +2 = p 6 i=1 15 2.3. TÍNH TỔNG PHẦN NGUYÊN DỰA VÀO TÍNH CHIA HẾT 2. 2 p−1 Pj i=1 3. p−1 ∞ PP 2i2 p 4. i=1 j=0 = p +2j 2j+1 j p−1 Pj i=1  i2 i=1 j=0 p−1 ∞ PP k  = 3i2 p k + p−1 Pj i=1 i2 p k (p−1)(p−2) 3 2i2 +p+2j+1 p 2j+2 p k = (p−1)(2p−1) 6 16 Tài liệu tham khảo [1] T. Andreescu and D. Andrica, Number Theory:Structures, Examples, and Problems. Birkhauser 2009. [2] PEN Team, Problems in Elementary Number Theory. [email protected], 2009. [3] Đặng Hùng Thắng, Nguyễn Văn Ngọc, Vũ Kim Thủy, Bài giảng số học. Tái bản lần thứ năm. NXB Giáo dục Việt Nam, 2010. [4] Andreescu, T., Kedlaya, K., Mathematical Contests, 1995-1996: Olympiad Problems from around the World, with Solutions, American Mathematics Competitions, 1997. [5] Andreescu, T., Kedlaya, K., Mathematical Contests, 1997-1998: Olympiad Problems from around the World, with Solutions, American Mathematics Competitions, 1999. 17