Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Số học - Phần 4

Nội dung text: Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Số học - Phần 4

1. Câu 1. Ký hiệu x là số nguyên lớn nhất không vượt quá x. Giải phương trình x2 1 x x 2015 0. Hướng dẫn giải Ta có x 0. x2 x 2015 x2 x 2015 pt x x 1 x x 2015. x x x a ¢ a 2015 x2 a 1 x 2015 0 a 1 a 1 2 8060 x * 2 Do a 2015 x2 a 1 x 2015 0 a 1 a 1 2 8060 x 2015 (t/ m); 2 a 1 a 1 2 8060 a 1 a 1 2 4a 2015 loai 2 2 2  a 1 a 1 8060 Vậy S ; a ¢ ;a 2015 2  Câu 2. Tìm tất cả các đa thức P x ¡ x thỏa mãn điều kiện P P x x P x P x 1 ,x ¡ . Hướng dẫn giải Giả sử deg P x n . So sánh bậc của x trong hai vế của (1) ta được n2 2n n 0 . n 2 2 c 0 Khi n 0 ta được đa thức hằng P x c . Thay vào (1) ta được c c . c 1 Vậy P x 0 và P x 1 là các đa thức hằng thỏa mãn yêu cầu. Khi n 2 ta giả sử P x ax2 bx c với a 0 . So sánh hệ số cao nhất trong (1) ta được a3 a2 . Do a 0 nên ta có a 1 . Vậy ta có P x x2 bx c . Thế vào (1) kiểm tra thấy thỏa mãn. Kết luận: P x 0 , P x 1 và P x x2 bx c . Câu 3. Tìm tất cả các số nguyên dương n sao cho (n - 1)! không chia hết cho n2. Hướng dẫn giải Nhận xét rằng khi n là số nguyên tố thì do (n - 1) < n nên (n - 1)! hiển nhiên không chia hết cho n, và do đó không chia hết cho n2. Ta sẽ tìm n không nguyên tố thỏa (n - 1)! không chia hết cho n2. Ta có: (n 1)!  n2 n! n3 . Điều này xảy ra khi và chỉ khi tồn tại ít nhất một ước số p của n sao cho bậc của p (số mũ lũy thừa của p trong phân tích thừa số nguyên tố) trong n! là bé hơn bậc của p trong n3 1
2. Giả sử n pt.k (với (p, k)=1). Theo lí luận trên ta có bất đẳng thức: n n n ... 3t (*) 2 3 p p p n n n n Suy ra: 3t ... 3t k.( pt 1 pt 2 ... 1) p 2 3 t p p p k( pt 1) 1.(2t 1) 3t (**). Suy ra: 3t 2t 1 t {1,2,3} p 1 2 1 Ta xét 3 trường hợp và dùng các phép thử lại để làm rõ kết quả bài toán • TH1: t = 1. Ta có: (**) 3 k . Suy ra k 2 hoặc k 3 (Do k 1 thìn trở thành số nguyên tố) + Với k = 2: n 2 p (p nguyên tố). 2 p 2 p Thử lại: p = 2 thì n = 4 (thỏa); : (*) ... 3 (đúng) p 2 2 2 3 p p + Với k = 3: n 3p (p nguyên tố) Thử lại: p = 2 thì n = 6 (thỏa); p = 3 thì n = 9 (thỏa); p 5 : 3p 3p (*) ... 3 3 3 (sai) 2 p p • TH2: t = 2. Ta có (**) 6 k( p 1) . Suy ra k 1 hoặc k 2 (Do ( p 1) 3 ) + Với k = 1, ta được ( p 1) 6 p {2,3,5} n {4,9,25} . Thử lại ta chọn: n = 4, n = 9. + Với k = 2, ta được ( p 1) 3 p 2 n 8 . Thử lại ta thấy n = 8 thỏa mãn. 2 • TH3: t = 3. Ta có (**) 9 k( p p 1) . Suy ra k 1 (Do p2 p 1) 7 ) + Với k = 1, ta được ( p2 p 1) 9 p 2 n 8 (thỏa) Vậy tập tất cả các giá trị của số tự nhiên n thỏa (n 1)! n2 là{p , 2 p , 8 , 9 } với p nguyên tố. Câu 4. Cho 2k 1 số nguyên lẻ a0 ,a1, L,a2k (k ¥ ) . Chứng minh rằng phương trình 2k 2k 1 a2k x a2k 1x L a1x a0 0 không có nghiệm hữu tỷ. Hướng dẫn giải p Giả sử phương trình a x2k a x2k 1 L a x a 0 (1) có nghiệm hữu tỷ x , 2k 2k 1 1 0 q ( p,q) 1. p Thay x vào (1) ta có a p2k a p2k 1q L a pq2k 1 a q2k 0 (2) q 2k 2k 1 1 0 2k Suy ra a2k p  q , vì ( p,q) 1 nên a2k  q . Tương tự ta có a0  p . Vì a2k , a0 là những số lẻ nên p,q lẻ. Vế trái của (1) là tổng của 2k 1 số lẻ vì vậy đẳng thức (1) không xảy ra nên phương trình không có nghiệm hữu tỷ. 2
3. Câu 5. Cho tập S gồm tất cả các số nguyên trên trong đoạn [1;2014]. Gọi T là tập hợp gồm tất cả các tập con không rỗng của S. Với mỗi tập hợp X T , ký hiệu m(X ) là trung bình cộng của tất cả m(X ) các số thuộc X . Đặt m  (ở đây tổng được lấy theo tất cả các tập hợp X T ). Hãy |T | tính giá trị của m. Hướng dẫn giải Với mỗi x [1,2, ..., 2014], đặt mk m(X) ở đây tổng được lấy theo tất cả các tập hợp X T mà | X | k . k 1 Xét số a bất kỳ thuộc S, suy ra a có mặt trong C2013 tập X T mà | X | k . k 1 k 1 Suy ra kmk (1 2 ... 2014)C2013 1007.2015.C2013 2014 2014 k 1 2014 2014 C2013 2015 k 2015 k Do đó m(X)  mk 1007.2015  C2014  C2014 k 1 k 1 k 2 k 1 2 k 1 2015 (22014 1) 2 2015 Mà |T | (22015 1) m 2 Cách 2. Xây dựng song ánh từ T vào T như sau X T f (X ) {2015- x / x X} m(X ) m( f (X )) 2015 Suy ra 2m(X) m(X) m(f(X)) | T |.2015 m(X) 2015 Suy ra m  | T | 2 Câu 6. Tìm tất cả các số nguyên dương k để phương trình x2 y2 kxy x y 0 có nghiệm nguyên dương. Giải phương trình nghiệm nguyên dương với k nhỏ nhất tìm được. Hướng dẫn giải Tìm k (dùng kĩ thuật pt Markov). +) Gọi k là một giá trị thỏa mãn. Với k đó, gọi (a,b) là nghiệm nguyên dương của pt đã cho sao cho a b nhỏ nhất. KMTTQ coi a b . Khi đó ta có đẳng thức a2 (kb 1)a b2 b 0 . 2 2 +) Xét pt bậc 2: x (kb 1)x b b 0 , dễ thấy pt có 1 nghiệm x1 a , nên có nghiệm 2 x2 a ' , với a a ' kb 1(1) và a.a ' b b (2). Do a,b,k đều nguyên dương nên 2 đẳng thức trên chứng tỏ a ' cũng nguyên dương. Điều đó suy ra (a ',b) cũng là một nghiệm nguyên dương của pt đã cho, do tính “nhỏ nhất” của (a,b) nên a ' a . Kết hợp (2) được a2 a.a ' b2 b. Lại có a b nên b2 a2 b2 b (b 1)2 , suy ra a2 b2 hay a b . 2 +) Kết hợp (1)(2) được k 2 là nguyên dương, từ đây a = 1 hoặc 2, tương ứng k chỉ có a thể là 3 hoặc 4. 3
4. +)(1đ) Giải pt Với k=3 là giá trị nhỏ nhất tìm được, pt cần giải tương đương x2 (3y 1)x y2 y 0 Để pt có nghiệm nguyên thì biệt thức là số chính phương hay 5y2 10y 1 t2 t2 5( y 1)2 4 . Bẳng cách giải pt kiểu Pell ta được nghiệm (t,y) thỏa mãn t ( y 1) 5 (u v 5)(9 4 5)n tương ứng với 3 nghiệm riêng (u,v) =(1,1), (4,2), (11,5) trong đó n N * (để thỏa mãn y nguyên dương) Từ đó ta có công thúc cụ thể cho giá trị y của nghiệm (x,y) (tất nhiên nguyên dương), còn giá trị x (3y 1 t) / 2 (đảm bảo là số nguyên dương). n n 1 Câu 7. Cho đa thức P x a0 x a1x ... an với hệ số thực. Chứng minh rằng nếu tất cả các n i 1 i 1 nghiệm của P x là số thực và phân biệt thì a2 . a a ,i 1,2,...,n 1. i n i i i 1 i 1 Hướng dẫn giải Xét đa thức Q y yn P y 1 có tất cả các nghiệm là số thực và phân biệt. Hơn nữa phương n 2 2 trình bậc 2 Q y n 2 n 3 ...4.3 n n 1 an y 2 n 1 an 1 y 2an 2 cũng có các 2 2 nghiệm thực phân biệt, suy ra n 1 an 1 2n n 1 anan 2 0 Với i n 1 thì (1) đúng, cũng có nghĩa mọi đa thức thỏa mãn đề bài thì hệ số của x thỏa mãn (1). n i 1 i 1 i 2 Với mỗi i 1,2,...,n 2 , xét đa thức P x b0 x b1x ... bi 1x bi x bi 1 cũng có tất cả các nghiệm là số thực và phân biệt. 2 i 1 Áp dụng BĐT cho b ta có b2 b b . i i i i 1 i 1 Trong đó bi 1 n i 1 ...4.3ai 1,bi n i ...3.2ai , bi 1 n i 1 ...2.1ai 1 2 2 i 1 Suy ra n i ...3.2ai n i 1 ...2.ai 1 n i 1 ...4.3ai 1 i i 1 n i 1 Hay a2 a a i i n i i 1 i 1 Ta có điều phải chứng minh. * 3 * Câu 8. Cho dãy số an : a1 ¥ ,an 1 an 2019,n ¥ . Chứng minh có nhiều nhất 1 số hạng của dãy là số chính phương. Hướng dẫn giải So sánh đồng dư của an , an 1 và an 2 theo modun 4 ta có (chú ý 2019  3 mod 4 ) Một số chính phương khi chia 4 có số dư là 0 hoặc 1. 4
5. Vì vậy từ số hạng thứ 3 trở đi, dãy không có số chính phương nào. 2 2 Nếu cả a1 và a2 đều chính phương, giả sử a1 a ,a2 b , suy ra b2 a6 2019 b a3 b a3 2019 hơn nữa khi phân tích 2019 thành tích chỉ có 2 cách 2019 1.2019 3.673 . b a3 1 b 1010 Trường hợp 1: 3 3 , vô lí do 1009 không là lập phương. b a 2019 a 1009 b a3 3 b 338 Trường hợp 2: 3 3 , vô lí do 335 không là lập phương. b a 673 a 335 Vậy điều giả sử sai, nghĩa là dãy trên có nhiều nhất 1 số chính phương. Câu 9. Với n là số nguyên dương, một tập con của tập 1,2,3,...,n được gọi là tốt nếu sau khi ta sắp xếp thứ tự tăng các phần tử của nó thì thu được các số lẻ, chẵn, lẻ, theo thứ tự. Ví dụ các tập con tốt là 1,4,5,6, 3,4,7, tập  . Tập 2,3,4,7không là tập con tốt do nó bắt đầu bởi số chẵn. Tính số tập con tốt của tập 1,2,3,...,n . Hướng dẫn giải Gọi fn là số tập con tốt của 1,2,3,...,n . Ta lập hệ thức truy hồi của fn . + Nếu tập con tốt của 1,2,3,...,n không lấy n thì fn fn 1 . + Nếu tập con tốt của 1,2,3,...,n lấy n thì fn fn 2 . Vậy ta có fn fn 1 fn 2 . Hơn nữa f1 2, f2 3 1 5 Phương trình đặc trưng x2 x 1 0 x 2 n n 1 5 1 5 Suy ra fn A B 2 2 1 5 1 5 2 2 5 1 A B 2 2 2 A Thay 2 giá trị đầu ta được 2 2 5 5 1 5 1 5 2 A B 3 B 2 2 5 5 Suy ra n n n 1 n 1 2 2 5 1 1 5 2 1 5 2 5 1 1 5 1 1 5 fn 5 5 2 5 5 2 5 2 5 2 Câu 10. Cho đa thức P x x3 14x2 2x 1. Chứng minh rằng với mỗi x Z tồn tại số tự nhiên n sao cho ta luôn có P P ...P x ... x101.   n Hướng dẫn giải 5
6. Cho x, y là hai số nguyên bất kỳ, ta chứng minh x  y mod101 P x  P y mod101 Thật vậy, hiển nhiên x  y mod101 P x  P y mod101 . 2 2 Biến đổi 4 P x P y 4 x y x xy y 14x 14 y 2 2 2 x y 2x y 14 3 y 29 101 2 y 27 , x  y mod101 1 Do đó, nếu P x  P y mod101 2 2 2x y 14 3 y 29  0 mod101 2 Nếu xảy ra (1) ta có ngay điều phải chứng minh. Nếu xảy ra (2), thì có hai khả năng 2 2 y 29 101 y 29;101 1, mà 2x y 14  3 . y 29 suy ra 3 là số chính phương mod 101 nên sử dụng ký hiệu Legendre có 3 3 101 2 1 1 (mâu thuẫn) 101 101 3 3 y 29101, thu được 2x y 14101, từ đó suy ra x  y  29 mod101 . Như vậy trong mọi trường hợp ta đều có x  y mod101 P x  P y mod101 . Xét 102 số P x , P P x ,..., P P ...P x ... . Theo nguyên lý Drichlet, tồn tại   102 m,n 1;2;...;102, m n sao cho P P ...P x ...  P P ...P x ... mod101 .     m n Từ nhận xét trên rút được P P ...P x ...  x mod101 .   m n Vậy suy ra điều phải chứng minh Câu 11. Với mỗi hoán vị p a1,a2 ,...,a9 của các chữ số 1, 2, , 9, kí hiệu s p là tổng của ba số có 3 chữ số a1a2a3 , a4a5a6 , a7a8a9 . Trong các s p có hàng đơn vị bằng 0, gọi m là giá trị nhỏ nhất của nó và n là số các hoán vị p thỏa mãn s p m . Tính m n . Hướng dẫn giải Với mỗi hoán vị p a1,a2 ,...,a9 của các chữ số 1, 2, , 9, kí hiệu s p là tổng của ba số có 3 chữ số a1a2a3 , a4a5a6 , a7a8a9 . Trong các s p có hàng đơn vị bằng 0, gọi m là giá trị nhỏ nhất của nó và n là số các hoán vị p thỏa mãn s p m . Tính m n . Để s p đạt giá trị nhỏ nhất thì 3 chữ số hàng trăm là 1, 2, 3, s p có chữ số tận cùng bằng 0 thì các chữ số hàng đơn vị có tổng là bội của 10. Và từ các chữ số 4, 5, 6, 7, 8,9 không có ba số nào có tổng bằng 10 và vì 7 8 9 24 30 nên 3 chữ số hàng đơn vị phải có tổng bằng 20, ta thấy 5 6 9 4 7 9 5 7 8 20 , có ba bộ số có thể xếp vào 3 chữ số ở hàng đơn vị, tương ứng các chữ số còn lại sẽ là hàng chục. Do đó giá trị nhỏ nhất của s p là m 1 2 3 100 19 10 20 810 6
7. Như vậy có 3 trường hợp, trong mỗi trường hợp có 6 cách chọn 3 chữ số hàng trăm, 6 cách chọn 3 chữ số hàng chục và 6 cách chọn 3 chữ số hàng đơn vị. Vậy số các hoán vị p thỏa mãn yêu cầu bài toán là n 3 6 6 6 648 . Vậy m n 162 . Câu 12. Cho x1, x2 , x3,, xn là các số nguyên thỏa mãn điều kiện: 2 2 2 3 2 x1 x2 xn n 2n 1 x1 x2 xn n Chứng minh tổng S x1 x2  xn n 1 không là số chính phương. Hướng dẫn giải Câu 13. Cho trước các số nguyên dương a,b. Chứng minh rằng phương trình x2 2axy a2 4b y2 4by z2 có vô số nghiệm nguyên dương. Hướng dẫn giải Câu 14. Một số nguyên dương n được gọi là có tính chất P nếu nó thỏa mãn với mọi số nguyên dương a tùy ý, n chia hết an 1 thì n2 cũng chia hết an 1. Chứng minh rằng có vô số hợp số có tính chất P. Hướng dẫn giải Kí hiệu pk là số nguyên tố thứ k . Với mọi k 3 ta có pk 5, như vậy luôn tồn tại một số qk là ước số nguyên tố nhỏ nhất của pk 2 . n Đặt n pk qk , ta sẽ chứng minh n có tính chất P. Thật vậy, giả sử a  1(mod n) . (n) Xét hàm Ơle (n) ( pk 1)(qk 1) , a  1(mod n) . Chú ý rằng (n; (n)) 1 nên suy ra a  1(mod n) . an 1 an 1 ... 1  n(mod n) an 1 (a 1)(an 1 an 1 ... 1) chia hết cho n2 Hiển nhiên n là một hợp số, và dễ thấy với hai số nguyên tố pk và pm đôi một khác nhau sẽ cho ta hai hợp số pk qk và pmqm khác nhau. Vìtập các số nguyên tố là vô hạn nên cũng có vô hạn hợp số có tính chất P Câu 15. 2 © ¬2 P x 1 «P x ® 1 b. Tìm đa thức P x với hệ số thực thỏa mãn P 2014 2046 và P x P x2 1 33 32 x 0 Hướng dẫn giải a. Đặt Q x P x x thì Q 0 0. Giả sử x k là nghiệm của Q x , khi đó P k k. Suy ra, P k 2 1 k 2 1 Q k 2 1 0 mà k 2 1 k nên Q x 0 có vô số nghiệm. Do đó, Q x 0 hay P x x. 7
8. b. Đặt Q x P x 32 thì Q 2014 2014 và 2 © ¬2 Q x 1 «Q x ® 1 Suy ra, Q x x hay P x x 32. Câu 16. Trên bảng có một số nguyên. Người ta ghi nhớ chữ số cuối cùng của số này, sau đó xoá đi và cộng thêm vào với số còn lại trên bảng 5 lần chữ số vừa xoá. Ban đầu có số 72014 . Hỏi có thể hay không sau một số lần thực hiện như thế thế ta thu được số 20147 ? Hướng dẫn giải Giả sử số đang có trên bảng là N 10a b 0 b 9 . Khi đó số nhận được sau một phép biến đổi là N a 5b Ta thấy 5N N 49a . Như vậy nếu N 7 thì N 7 . Do 72014 7 , còn 20147 không chia hết cho 7 nên qua các phép biến đổi đã cho từ 72014 không thể thu được 20147 . Câu 17. Cho phương trình x2 x 1 0 với là số nguyên dương. Gọi  là nghiệm dương của phương trình. Dãy số xn được xác định như sau x0 , xn 1  xn , n 0,1,2,3,... Chứng minh rằng tồn tại vô hạn số tự nhiên n sao cho xn chia hết cho . Hướng dẫn giải Đầu tiên ta chứng minh  là số vô tỉ. Thật vậy, nếu  là số hữu tỉ thì  là số nguyên (do hệ số cao nhất của x2 là 1) và  là ước của 1. Do đó  1 suy ra 0 , trái giả thiết. Do đó  xn 1   xn 1  xn 1  1 xn  xn 1 xn 1 x x 1 1 x n x n x n x  n 1   n 1   n 1 xn 2 1 xn 1 1 (1). Lại có   1 0 , suy ra    xn xn xn  xn xn xn 1 xn xn xn xn 1 1 (do (1))    * Vậy xn 1  xn 1 1 (mod ) . Từ đó bằng quy nạp ta có với mọi k ¥ , n 2k 1, thì xn 1  xn (2k 1) (k 1) (mod ) (2) Chọn k + 1 = la (l Î ¥ * ), n + 1 = 2la , từ (2) ta có x2l  x0 l l  0 (mod ) . * Vậy x2l chia hết cho , l ¥ . Câu 18. Với mỗi số nguyên dương m, kí hiệu C(m) là số nguyên dương k lớn nhất sao cho luôn tồn tại một tâp S gồm m số nguyên dương để mỗi số nguyên chạy từ 1 đến k hoặc thuộc S hoặc là tổng hai phần tử thuộc S (hai phần tử này không nhất thiết phân biệt). Chứng minh: m(m 6) m(m 3) C(m) 4 2 8
9. Hướng dẫn giải Trước tiên ta tính thử một vài giá trị ban đầu của C(m) để cảm nhận bài toán. Dễ thấy: C(1)=2; C(2)=4; C(3)=8 Nhận xét: Việc tính C(m) quy vềviệc đếm số phần tử của tập A xác định bởi: A S  (S S) ; S S x y | x, y S m(m 3) C(m) +)Chứng minh: 2 | S | (| S | 3) m(m 3) | A | | S | | S S | | S | | S | C 2 |S| 2 2 Chú ý: Để đánh giá số phần tử của tập S+S ta chia hai trường hợp x trùng y và x khác y.Rõ ràng {1;2;3;.;k} là một tập con của A nên ta được đpcm. m(m 6) C(m) +)Chứng minh: 4 Ta sẽ chỉ ra một tập B sao cho với mọi số nguyên chạy từ 1 đến m(m+6)/4 hoặc thuộc B hoặc là tổng hai số (không nhất thiết phân biệt) thuộc S(m). Khi đó C(m)>=m(m+6)/4. Xét hai trường hợp sau: TH1: m = 2n. Xét tập B(m) = {1; 2; 3;.; n; 2n+1; 3n+2;.; (n+1)n+n} gồm m phần tử và dễ thấy tập B  (B B) chứa dãy số liên tiếp từ 1 đến (n+1)n + 2n và rõ ràng (n+1)n + 2n = 2n(2n+6)/4 TH2: m =2n+1 Khi đó ta xây dựng tập B(m)={1;2;3;.; n+1;2n+3;3n+5;.;(n+1)n+2n+1}gồm m phần tử và tập B  B B chứa dãy số liên tiếp từ 1 đến (n+1)n+3n+2 và rõ ràng (n+1)n+3n+2 > (2n+1)(2n+7)/4 Từ hai TH trên ta được đpcm. Câu 19. Cho m > 1 là một số nguyên. Chứng minh rằng với mọi số nguyên n có thể biểu diễn dưới dạng n = a + b, trong đó a là một số nguyên nguyên tố cùng nhau với m và b là một số nguyên sao cho b2  b mod m . Hướng dẫn giải - Ta xét trường hợp thứ nhất với m p , trong đó p là số nguyên tố và 1 . Giả sử n là một số nguyên. Khi đó, xảy ra hai trường hợp: a) p không chia hết n. Trong trường hợp này thì ƯCLN m,n 1 và ta có thể chọn a,b n,0 . b) p chia hết n. Trong trường hợp này p không chia hết n - 1 (bởi vì ngược lại p sẽ chia hết 1). Từ đây suy ra ƯCLN m,n 1 1 và ta có thể lấy a,b n 1,1 1 2 r - Ta đi đến trường hợp tổng quát với m p1 p2 .....pr với các số nguyên tố phân biệt p 1, p 2, p3,., pr và các số nguyên dương 1, 2 ,...., r . Giả sử n là một số nguyên. Bằng cách sử dụng trường hợp ở trên, với mỗi k sao cho k 2 1 k r , thì có ak ,bk để n ak bk , ƯCLN pk ,ak 1và bk  b mod m k -Theo định lí Trung Hoa về phần dư thì tồn tại một số nguyên b sao cho b  bk mod pk với k = 1, 2,., r 9
10. 2 2 k Vì b b  bk bk  0 mod pk và p1, p2 ,....., pr  là các số nguyên tố phân biệt nên ta kết 2 1 2 r luận rằngb b  0 mod p1 p2 ......pr , tức là b2  b mod m . Câu 20. Điền 29 số nguyên dương đầu tiên vào các ô vuông con của bảng 6 x 5 bằng cách sau: Cho phép thay đổi vị trí của các số trong bảng theo quy tắc: Mỗi lần, lấy một số nằm ở ô kề với ô trống rồi chuyển số đó sang ô trống. Hỏi bằng cách thực hiện liên tiếp một số hữu hạn lần phép chuyển số nói trên đối với bảng số ban đầu ta có thể nhận được bảng số sau đó hay không? 1 2 3 4 5 29 2 3 4 5 6 7 8 9 10 6 7 8 9 10 11 12 13 14 11 12 13 14 15 16 17 18 19 15 16 17 18 19 20 21 22 23 24 20 21 22 23 24 25 26 27 28 1 25 26 27 28 29 Bảng 2 Bảng 1 Hướng dẫn giải Giả sử nhờ phép chuyển số theo qui tắc của đề bài, từ Bảng 1 ta có thể nhận được Bảng 2(*) Ta coi ô trống của mỗi bảng là ô được điển số 0. Với mỗi bảng số nhận được trong quá trình chuyển số, ta liệt kê tất cả các số trong bảng theo thứ tự từ hàng trên xuống hàng dưới và trong mỗi hàng thì từ trái qua phải. Khi đó ứng với mỗi bảng số ta sẽ có một hoán vị của 30 số tự nhiên đầu tiên. Và do đó, điều giả sử (*) tương đương với: Từ hoán vị (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29) (gọi là hoán vị a) có thể nhận được hoán vị (29, 2, 3, 4,.,11. 12, 0, 13, 14, 15,.27, 28, 1) (gọi là hoán vị b) nhờ việc thực hiện liên tiếp một số hữu hạn lần phép đổi chỗ hai số trong hoán vị theo qui tắc:Mỗi lần, lấy hai số 0 của hoán vị rồi đổi vị trí của số 0 đó cho một số liền kề với số 0 đó.(1) +) Giả sử (a1, a2, a3, , a30) là một hoán vị của 30 số tự nhiên đầu tiên. Ta gọi cặp số ai ;a j là cặp số ngược của hoán vị vừa nêu nếu ai a j và i j . Dễ thấy, sau một lần thực hiện phép đổi chỗ hai số kề nhau đối với hoán vị (a 1, a2, a3, , a30) thì số cặp số ngược của hoán vị đó sẽ tăng hoặc giảm đi một đơn vị. +) Khi chuyển chỗ hai số ai và ai n ( n 1 tùy ý) trong một hoán vị, cũng tức là chuyển ai liên tiếp qua n số kề với nó và chuyển ai n liên tiếp qua n – 1 số kề với nó, nghĩa là chuyển 2n – 1 (một số lẻ lần) hai số kề nhau, do đó cặp số ngược của hoán vị đó sẽ tăng hoặc giảm một số lẻ đơn vị.(2) +) Ta có: Số cặp số ngược của của hoán vị alà 12 và số cặp số ngược của hoán vị b là 67. Từ đó, kết hợp với (2), suy ra từ hoán vị a ta chỉ có thể nhận được hoán vị b sau một số lẻ lần thực hiện phép đổi chỗ hai số nào đó. Điều này cho thấy, nếu từ Bảng 1 ta nhận được Bảng 2 thì số lần đổi chỗ hai số ở hai ô nào đó phải là số lẻ.(3) +) Tô màu tất cả các ô vuông con của bảng 6 x 5 bởi hai màu xanh, đỏ sao cho hai ô kề nhau có màu khác nhau. Sau mỗi lần đổi chỗ hai số ở hai ô kề nhau, trong đó có số 0 ở ô trống, theo cột 10