Tài liệu Thiết lập hệ thức truy hồi trong bài toán đếm

CHUYÊN ĐỀ THIẾT LẬP HỆ THỨC TRUY HỒI TRONG BÀI TOÁN ĐẾM A. PHẦN MỞ ĐẦU 1.Lý do chọn đề tài: Các bài toán đếm nhiều năm nay thường có trong các kì thi chọn học sinh giỏi quốc gia, thi Olympic Toán quốc tế và khu vực. Các em học sinh bậc THPT và nhiều giáo viên thường gặp một số khó khăn khi tiếp cận bài toán này, đặc biệt là các bài toán đếm phải dùng đến các phép đếm nâng cao như truy hồi, song ánh, quỹ đạo v.v… vào việc giải quyết bài toán. Học sinh mới bắt đầu làm quen với khái niệm phép đếm thường chưa hiểu tường tận tư tưởng cũng như hướng tiếp cận các bài toán dạng này, đặc biệt là khâu vận dụng kiến thức về dãy số vào bài toán phép đếm cho những tình huống cụ thể. Để hiểu và vận dụng được kiến thức về dãy số vào giải bài toán đếm thì học sinh phải có kiến thức nền tảng về dãy số tương đối đầy đủ và chắc chắn. Đặc biệt là việc xác định công thức số hạng tổng quát của dãy số (CTTQ). Trong các phép đếm nâng cao thì phép đếm bằng cách thiết lập hệ thức truy hồi có nhiều ứng dụng cho việc giải bài toán đếm. Chuyên đề “Thiết lập hệ thức truy hồi trong bài toán đếm” sẽ góp thêm một phương pháp vào giải bài toán đếm một cách ngắn ngọn, hiệu quả, khoa học và có thể tạo hứng thú cho học sinh. Chuyên đề có tính ứng dụng cho học sinh các lớp chuyên toán. 2.Mục đính của đề tài: Mục đích của chuyên đề nhằm tìm cách đưa các bài toán đếm trong toán tổ hợp về các bài toán xác định số hạng tổng quát của dãy số thông qua hệ thức truy hồi của dãy, khi đó việc giải quyết bài toán đếm sẽ trở nên đơn giản. Thông qua chuyên đề cũng giúp cho học sinh nhìn thấy mối quan hệ giữa các phần kiến thức cơ bản đã học. B.PHẦN NỘI DUNG Nội dung cơ bản của phương pháp “Thiết lập hệ thức truy hồi trong bài toán đếm” như sau: thay vì ta đếm trực tiếp S n theo yêu cầu bài toán, ta sẽ thiết lập hệ thức liên quan giữa Sn với Sn-1, Sn-2, … để từ đó tính được Sn. Tóm tắt kiến thức cơ bản về việc xác định CTTQ của số dãy số cho bởi hệ thức truy hồi thường gặp: 1 I. Những kiến thức cần nhớ. 1. Hai quy tắc đếm cơ bản. + Quy tắc cộng: Nếu có m1 cách chọn đối tượng x1, m2 cách chọn đối tượng x2, …, mn cách chọn đối tượng xn và cách chọn đối tượng xi không trùng với bất kỳ cách chọn đối tượng xj nào ( xi  x j , i  j, i, j  1, n ) thì có m1 + m2 + …+mn cách chọn một trong các đối tượng. + Quy tắc nhân: Nếu có m1 cách chọn đối tượng x1, sau đó với mỗi cách chọn x1 có m2 cách chọn đối tượng x2, sau đó với mỗi cách chọn x 1 và x2 như thế có m3 cách chọn đối tượng x3, …, cuối cùng với mỗi cách chọn x 1, x2, x3,…,xn-1 như thế có mn cách chọn đối tượng xn thì có m1.m2.m3…mn cách chọn dãy x1,x2,…,xn. 2. Cấp số cộng (CSC) + Định nghĩa: Cấp số cộng là một dãy số (hữu hạn hay vô hạn) mà trong đó, kể từ số hạng thứ hai, mỗi số hạng đều bằng tổng của số hạng đứng ngay trước nó và một số d không đổi, nghĩa là: (un) là cấp số cộng  un = n  2, un  un 1  d . Số d được gọi là công sai của cấp số cộng. + Định lý1: Một cấp số cộng có số hạng đầu u1 và công sai d thì số hạng tổng quát u n được tính theo công thức: un = u1 +(n-1)d + Định lý 2: Gọi Sn là tổng của n số hạng đầu tiên của CSC (un) có công sai d, ta có: Sn  n  2u1  (n  1)d  2 3. Cấp số nhân (CSN) + Định nghĩa: Cấp số nhân là một dãy số (hữu hạn hay vô hạn) mà trong đó, kể từ số hạng thứ hai, mỗi số hạng đều bằng tích của số hạng đứng ngay trước nó và một số q không đổi, nghĩa là: (un) là cấp số nhân  un = n  2, un  un 1.q . Số q được gọi là công bội của cấp số nhân. 2 + Định lý 3: Một cấp số nhân có số hạng đầu u1 và công bội q  0 thì số hạng tổng quát un được tính theo công thức un = u1.qn-1. + Định lý 4: Gọi Sn là tổng của n số hạng đầu tiên của CSN (u n) có công bội q  1, ta có : 1  qn S n  u1 1 q 4. Các dạng cơ bản để xác định CTTQ của dãy số cho bởi hệ thức truy hồi: Dạng 1: Cho dãy số (un ) xác định bởi: u1  x0 , un  aun 1  b, n  2,(a, b  0) là các hằng số, ta có CTTQ của dãy số là:  u1  (n  1)b,(a  1)  un   n1 a n 1  1  u1a  b a  1 (a  1) Dạng 2: Cho dãy số (un ) xác định bởi: u1  x0 , un  aun1  f (n), n  2,( a, b  0) trong đó f(n) là đa thức bậc k theo n; a là hẳng số, để xác định CTTQ của dãy ta thực hiện như sau: -Ta phân tích f(n) = g(n) – a.g(n-1) với g(n) là đa thức bậc theo n. Khi đó, ta đặt n 1 vn  un  g (n) ta có được: un   u1  g (1) a  g ( n) Lưu ý: Nếu a =1, ta chọn g(n) là đa thức bậc k+1 có hệ số tự do bằng không, còn nếu a  1 ta chọn g(n) là đa thức bậc k, sau đó dùng đồng nhất thức để tìm ra g(n). Dạng 3: Cho dãy số (un ) xác định bởi : u1  x0 , un  aun1  b. , n  2,(a, b  0) trong n đó  , a, b là hằng số, để xác định CTTQ của dãy ta thực hiện như sau: 3 -Nếu a    un  b(n  1)  u1 n n 1 -Nếu a   ta phân tích   k  ak . n un  a (u1  bk )  bk . , ta tìm được n 1 n n 1 , khi đó k   a Dạng 4: Cho dãy số (un ) xác định bởi: u1  x0 , un  aun1  b.  f (n), n  2,(a, b  0) n trong đó f(n) là đa thức theo n bậc k, để xác định CTTQ của dãy ta phân tích  và n f(n) như phân tích ở dạng 2 và dạng 3 Dạng 5: u , u un   0 1  un  aun1  bun2  0 Cho dãy số (un ) xác định bởi 2 trong đó a, b, c là các số khác không; a  4b  0 , Để xác định CTTQ của dãy (un ) ta thực hiện như sau: Gọi x1, x2 là nghiệm của phương trình đặc trưng : x2+ ax+b=0 n n x  x u  k . x  l . x 1 2 n 1 2 Nếu thì , trong đó k,l được xác định là nghiệm của hệ:  k  l  u0   x1 .k  x2 .l  u1  l   u0  n 1 k  l  u1 x  x   u  ( nk  l ).  2 Nếu 1 thì n , trong đó k,l là nghiệm của hệ  Dạng 6:  u0 , u1 un    un  aun1  bun2  f (n) Cho dãy số (un ) xác định bởi 4 Trong đó a, b, c là các số khác không; f(n) là đa thức theo n bậc k và a  4b  0 , để 2 xác định CTTQ của dãy ta thực hiện như sau: k k 1 g ( n )  a n  a n  ...  a1n  a0 , xét phương trình đặc k k  1 Xét g(n) là đa thức bậc k: trưng x  ax  b  0 (1) 2 - Nếu phương trình (1) có hai nghiệm phân biệt khác 1 thì ta đặt f (n)  g (n)  ag (n  1)  bg (n  2) rồi đặt vn  un  g (n) đưa về dạng 5 - Nếu phương trình (1) có hai nghiệm phân biệt trong đó một nghiêm bằng 1 thì ta đặt: f (n)  ng (n)  a(n  1) g (n  1)  b(n  2) g (n  2) rồi đặt vn  un  g (n) đưa về dạng 5 - Nếu phương trình (1) có hai nghiệm bằng 1 thì ta đặt f (n)  n 2 .g (n)  a (n  1) 2 g ( n  1)  b( n  2) 2 g (n  2) rồi đặt vn  un  n 2 .g ( n) đưa về dạng 5 Dạng 7:  u0 , u1 un   n  un  aun 1  bun 2  c. Cho dãy số (un ) xác định bởi Trong đó a, b, c là các số khác không; để xác định CTTQ của dãy trên ta thực hiện như sau: Xét phương trình đặc trưng x  ax  b  0 (1) 2 - Nếu phương trình (1) có hai nghiệm phân biệt khác  thì : 2 un  p.x1n  q.x2n  kc. n với k   2  a  b - Nếu phương trình (1) có hai nghiệm phân biệt trong đó một nghiêm bằng  thì 5 un  p.x1  q.x2  kcn. với n n n k  2  a - Nếu phương trình (1) có hai nghiệm bằng  thì ta đặt 1  un  ( p  qn  cn 2 ) n k 2 2  a với Dạng 8: u , u , u un   0 1 2  un  aun 1  bun 2  cun 3  0 Cho dãy số (un ) xác định bởi Trong đó a, b, c là các số khác không, để xác định CTTQ của dãy trên ta thực hiện như sau: Gọi x1,x2 ,x3 là nghiệm của phương trình đặc trưng : x3+ ax2+bx+c=0(2) n n n u  k . x  l . x  m . x n 1 2 3 -Nếu phương trình (2) có ba nghiệm phân biệt x 1,x2 ,x3 thì , trong đó k,l,m được xác định dựa vào u0,u1,u2. n n x  x   x   u  ( nk  l ). x  m . x 1 2 3 n 1 3 - Nếu , thì , trong đó k,l,m được xác định dựa vào u0,u1,u2. - Nếu x1  x2  x3   , thì un  (l  k .n  m.n ) x1 , trong đó k,l,m được xác định 2 n dựa vào u0,u1,u2. II. Các ví dụ áp dụng phương pháp “Thiết lập hệ thức truy hồi trong bài toán đếm” Ví dụ 1: Cho n ( n  1) điểm phân biệt trên mặt phẳng, hỏi có bao nhiêu véctơ khác véctơ không được lập từ n điểm phân biệt nói trên: Giải: Gọi Sn là số véctơ được lập từ n điểm nói trên, xét hệ n-1 điểm phân biệt thì số véctơ là Sn-1. Nếu ta bổ xung hệ n-1 điểm đó thêm một điểm thì ta có thêm 2(n-1) véctơ mới được tạo thành do đó ta có hệ thức truy hồi : S n = Sn-1 +2(n-1), mà S1=0; 6 S2=2. Từ đó áp dụng cách xác định số hạng tổng quát của dãy số dạng 2, suy ra Sn = n( n  1) . Ví dụ 2: Cho các số 1,2,3,4...,n ( n>3) được viết liên tiếp trên một vòng tròn. Hai số không kề nhau được gọi là liên thông nếu 1 trong 2 cung tạo bởi chúng chứa toàn các số bé hơn chúng. Tìm số cặp liên thông? Giải : Gọi số cặp liên thông tạo bởi n số là S n; ta có S4=1 trước hết ta bỏ đi số 1 thì còn n-1 số từ 2 đến n. Số cặp liên thông là S n-1, Bây giờ ta cho số 1 vào một vị trí nào đó thì số cặp liên thông tăng lên 1 vì cặp liên thông bất kỳ trước khi cho số 1 vẫn liên thông khi cho thêm số 1 vào, hơn nữa nó sẽ sinh ra thêm một cặp liên thông nữa đó là 2 số ở hai bên số 1. Vậy ta có công thức S n = Sn-1 +1, do S4=1, từ đây áp dụng cách xác định số hạng tổng quát của CSC suy ra Sn = n-3. Trong ví dụ này, ta thiết lập hệ thức truy hồi xuất phát từ S n-1 đi đến Sn . Trong một số trường hợp khác ta lại đi theo hướng ngược lại, như ví dụ sau. Ví dụ 3. Xét {x1, x2, …,xn } với xi  {0, 1, 2, 3}. Gọi an là số các dãy như vậy mà số phần tử 0 trong mỗi dãy là số chẵn. Tính an ? Giải. Gọi bn là số các dãy như vậy nhưng số phần tử 0 trong mỗi dãy là một số lẻ số 0 Xét dãy {x1, x2, …,xn+1 }với xi Nếu xn+1   {0, 1, 2,3} mà số phần tử 0 trong dãy là chẵn số 0. {1, 2,3} thì {x1, x2, …,xn } cũng có số các phần tử 0 là chẵn số 0, do đó trong trường hợp này có 3an dãy. Nếu xn+1 = 0 thì {x1, x2, …,xn } có số các phần tử 0 là một số lẻ số 0, do đó trong trường hợp này có bn dãy. Như vậy ta có hệ thức an+1 = 3an + bn Tương tự ta cũng chứng minh được bn+1 = an + 3bn, ta tính được a1=3,a2=10,a3= 36, b1=1,b2=6,b3= 28 Đến đây ta có thể sử lý theo 2 cách: 7 Cách 1: theo quy tắc đếm an + bn = 4n , ta có phương trình an+1 = 2an + 4n , từ đây áp 1 an  (2n  4 n ) 2 dụng cách xác định số hạng tổng quát dạng 3, suy ra Cách 2: Ta có an 2  3an1  bn1  3an 1  an  3bn  3an 1  8an  9an  3bn  6an 1  8an , từ đó 1 an  (2n  4 n ) 2 áp dụng cách xác định số hạng tổng quát dạng 5, suy ra . Ví dụ 4: Có bao nhiêu xâu nhị phân độ dài n mà không có 2 bit 1 đứng cạnh nhau: Giải: Gọi cn là số xâu nhị phân độ dài n mà hai bít 1 không đứng cạnh nhau, ta xét một xâu x1 x2 ...xn của cn. - Nếu xn = 0 thì x1x2...xn-1 là cn-1. - Nếu xn =1, thì xn-1 = 0 do đó x1x2...xn-2 là cn-2, do đó ta có hệ thức truy hồi cn  cn 1  cn 2 , c1 =2, c2= 3. Từ đây áp dụng cách xác định số hạng tổng quát dạng 5 ta được cn  5  3 5 1 5 n 5  3 5 1 5 n .( )  .( ) 10 2 10 2 . Ví dụ 5. Tìm số các bộ số nguyên (a1, a2, ...,an ) với n > 1 thoả mãn | ai | i = 1,2,…,n và | ai – ai + 1 |   1 với mọi 1 với mọi i = 1,2,…, n – 1 Giải. Trong tập Sn là tập hợp các bộ số nguyên (a1, a2, ...,an ) thoả mãn đề bài, gọi An, Bn, Cn là tập hợp các bộ (a1, a2, ...,an ) có an bằng – 1, 0, 1 tương ứng. Ta có ngay | Sn | = | An | + | Bn | + | Cn| Mặt khác, dễ thấy từ mỗi bộ thuộc An hoặc Bn, ta có thể bổ xung an + 1 = - 1 để được một bộ thuộc An +1 nên | An + 1| = |An | + | Bn |. Tương tự ta có | Cn + 1| = |Cn | + | Bn | và | Bn +1 | = | An | + | Bn | + | Cn| = |Sn | Từ đó ta có | Sn + 1 | = | An + 1 | + | Bn +1 | + | Cn + 1| = ( | An | + | Bn | + | Cn| ) + | Bn + 1 | + | Bn | 8 = 2 | Sn | + | Sn – 1 | Kết hợp với | S2 | = 7, | S3 | = 17, từ đó áp dụng cách xác định số hạng tổng quát dạng 5, ta tính được | Sn | =  1 √ 2  n 1   1−√ 2 2 Ví dụ 6. Xét {x0, x1, …,xn } với xi   n 1 {0, 1, 2}. Gọi an là số các dãy như vậy mà số phần tử 1 trong mỗi dãy là bội của 3. Tính an ? Giải. Gọi bn, cn là số các dãy như vậy nhưng số phần tử 1 trong mỗi dãy là một số mà khi chia cho 3 có số dư lần lượt là 2, 1 Xét dãy {x0, x1, …,xn }với xi Nếu xn   {0, 1, 2} mà số phần tử 1 trong dãy là bội của 3. {0, 2} thì {x0, x1, …,xn - 1 } cũng có số các phần tử 1 là một bội của 3, do đó trong trường hợp này có 2an – 1 dãy. Nếu xn = 1 thì {x0, x1, …,xn - 1 } có số các phần tử 1 là một số chia 3 dư 2, do đó trong trường hợp này có bn – 1 dãy. Như vậy ta có hệ thức an = 2an – 1 + bn – 1 Tương tự ta cũng chứng minh được bn = 2bn – 1 + cn – 1 cn = 2cn – 1 + an – 1 Ta có số các dãy {x0, x1, …,xn }với xi  {0, 1, 2} là 3n + 1, do đó an + bn + cn = 3n + 1 Từ các hệ thức trên ta suy ra a n + 1 – 3an + 3an – 1 = 3n và a1 = 4, a2 = 9. Từ đây áp dụng cách xác định số hạng tổng quát dạng 7, ta tính được an Ví dụ 7. (Bài toán tháp Hà Nội) Tương truyền rằng tại một ngôi tháp ở Hà Nội có một tấm đế bằng đồng, trên đó có đặt ba chiếc cọc bằng kim cương. Lúc khai thiên lập địa, trên cọc số 1, Phật tổ Như Lai đã xếp 64 chiếc đĩa bằng vàng có đường kính khác nhau sao cho các đĩa có đường kính lớn hơn xếp ở dưới, các đĩa ở phía trên càng ở trên cao càng nhỏ dần. Các nhà sư được yêu cầu chuyển tất cả các chiếc đĩa ở cọc số 1 sang cọc số 2 với quy tắc sau: 9 - Mỗi lần chỉ được chuyển đi một chiếc đĩa. - Trong quá trình di chuyển không được đặt đĩa lớn lên trên đĩa nhỏ (do đó cần thiết phải có thêm chiếc cọc trung gian thứ ba). Giả sử mỗi lần chuyển một chiếc đĩa mất một giây. Hỏi các nhà sư cần ít nhất là bao nhiêu năm để chuyển tất cả các chiếc đĩa ở cọc số 1 sang cọc số 2? Giải. Giả sử lúc đầu trên cọc số 1 có n chiếc đĩa. Gọi un là số lần ít nhất để chuyển tất cả các chiếc đĩa ở cọc số 1 sang cọc số 2. Ta thử tính một vài giá trị của un Với n  2 . Ta cần thực hiện ba phép chuyển sau - Chuyển đĩa bé sang cọc số 3 - Chuyển đĩa lớn sang cọc số 2 - Chuyển đĩa bé về cọc số 2 Vậy u2  3 Với n  3 . Ta cần thực hiện theo ba giai đoạn sau - Chuyển hai đĩa ở phía trên sang cọc số 3. Như đã thấy ở trường hợp n  2 , ta cần 3 phép chuyển. - Chuyển đĩa lớn nhất sang cọc số 2. - Chuyển hai đĩa ở cọc số 3 về cọc số 2. Như đã thấy ở trường hợp n  2 , ta cần 3 phép chuyển. Vậy ta cần 3+1+3 = 7 phép chuyển. Do đó u3  7 10 Trường hợp n  3 gợi ý cho ta thiết lập hệ thức truy hồi mà dãy ( un ) phải thoả mãn. Để chuyển được n chiếc đĩa theo quy tắc trên, ta phải thực hiện theo ba công đoạn sau: - Công đoạn 1: Chuyển (n  1) đĩa ở phía trên chiếc đĩa lớn nhất sang cọc số 3 theo quy tắc trên. Ta cần un 1 phép chuyển. Chiếc đĩa lớn nhất vẫn giữ nguyên ở cọc số 1 khi di chuyển (n  1) chiếc đĩa ở trên nó. - Công đoạn 2: Chuyển đĩa lớn nhất sang cọc số 2 - Công đoạn 3: Chuyển (n  1) đĩa ở cọc số 3 về cọc số 2 và đặt lên trên chiếc đĩa lớn nhất. Ta cần un 1 phép chuyển. Do vậy để chuyển n chiếc đĩa từ cọc số 1 sang cọc số 2, ta cần un 1  1  un 1  2un 1  1 Vậy ta có hệ thức truy hồi sau un  2un 1  1 Từ hệ thức truy hồi này, ta có thể lập được công thức của số hạng tổng quát của dãy là: un  2 n  1 . 64 Với n  64 thì u64  2 1 18.446.744.073.709.531.615 Ví dụ 8 : Cho số nguyên dương n. có bao nhiêu số chia hết cho 3, có n chữ số và các chữ số đều thuộc {3, 4, 5, 6} ? Giải : Cách 1. Gọi An tập hợp các số có n chữ số lập từ các chữ số {3, 4, 5, 6} và chia hết cho 3 và Bn là tập hợp các số có n chữ số lập từ các chữ số {3, 4, 5, 6} và không chia hết cho 3. Ta cần tìm an = |An|. Đặt bn = |Bn| Ta thấy rằng một số thuộc An+1 có thể thu được (và chỉ có thể thu được) bằng 2 cách sau đây: 1) Lấy 1 số thuộc An rồi thêm 3 hoặc 6 vào phía sau (cả hai đều được) 11 2) Lấy 1 số thuộc B n rồi thêm hoặc 4, hoặc 5 vào phía sau, hơn nữa, chỉ có duy nhất 1 cách thêm. Từ đây suy ra an+1 = 2an + bn (1). Lý luận hoàn toàn tương tự với B n+1, ta được bn+1 = 2an + 3bn (2). Rút bn = an+1 – 2an (và bn+1 = an+2 – 2an+1) từ (1) và thay vào (2), ta được an+2 – 2an+1 = 2an+ 3(an+1 – 2an)  an+2 – 5an+1 + 4an = 0 (3) Giải phương trình sai phân (3) với điều kiện a 1 = 2 (có hai số là 3, 6), a 2 = 6 (có các số 33, 66, 36, 63, 45, 54), từ đây áp dụng cách xác định số hạng tổng quát dạng 5 ta được an = (4n+2)/3. Cách 2. Lý luận tương tự như trên nhưng chú ý rằng, do số tất cả các số có n chữ số lập từ {3, 4, 5, 6}, theo quy tắc nhân, bằng 4 n nên ta có bn = 4n - an. Và như vậy có thể thu được công thức truy hồi an+1 = 2an + 4n - an. Từ đó an = 4n-1 + an-1 = 4n-1 + 4n-2 + an-2 = … = 4n-1 + … + 4 + a1 = (4n-1)/3 + 1 = (4n+2)/3. Ví dụ 9(TST Phú Thọ 2015 dự bị): Tìm số các số tự nhiên chia hết cho 3 , mỗi số gồm 2015 chữ số lấy từ tập X   2,3,4,6,9 . n Giải Vì X có 5 phần tử khác 0 nên từ các chữ số của X ta viết được 5 số tự nhiên, mỗi số gồm n chữ số. Gọi Sn là số các số tự nhiên chia hết cho 3 , mỗi số gồm n chữ số lấy từ X . Dễ thấy S1  3 (đó là 3,6,9 ). Gọi Pn là số các số tự nhiên không n chia hết cho 3 , mỗi số gồm n chữ số lấy từ X . Ta có Sn  Pn  5 ,n  1,2,... . Ta tính Sn1 như sau: Giả sử A là số tự nhiên bất kỳ gồm n chữ số lấy từ X , có các trường hợp sau: +) Nếu A chia hết cho 3 thì ta viết thêm chữ số 3 hoặc chữ số 6 hoặc chữ số 9 vào bên phải của A được một số chia hết cho 3 , gồm n  1 chữ số lấy từ X . +) Nếu A  1 mod3 thì ta viết thêm chữ số 2 vào bên phải của A để được một số chia hết cho 3 , gồm n  1 chữ số lấy từ X . +) Nếu A  2 mod3 thì ta viết thêm chữ số 4 vào bên phải của A để được một số chia hết cho 3 , gồm n  1 lấy từ X . 12 1 1  2n1  5n  Sn1  3Sn  Pn  2Sn  5n  Sn1  .5n1  2 Sn  .5n   Sn  3 3  3  Do đó .( áp dụng cách xác định số hạng tổng quát dạng 3) Vậy số các số tự nhiên chia hết cho 3 , mỗi số gồm 2015 chữ số lấy từ tập X   2,3,4,6,9 là S2015  22016  52015 3 Trong trường hợp trong các số trên có chứa số 0 , thì bài toán sẽ phức tạp hơn. Ví dụ 10 (VMO 2015): Cho số nguyên dương k, tìm các số tự nhiên n không vượt qua 10k thỏa mãn đồng thời các điều kiện sau: 1) n chia hết cho 3 2) Các chữ số trong biểu diễn thập phân của n thuộc tập  2,0,1,5 Giải - Vì 10k không chia hết cho 3 nên ta chỉ cần xác định các số từ 0 đến 999...9. co k chữ số, tức là các số không có qua k chữ số. Đặt S   2,0,1,5 , ta bổ sung các chữ số 0 vào trước nếu cần thiết, ta đưa về xét các số có dạng a1a2 ...ak với ai  S . Ta cần đếm các số như vậy chia hết cho 3, nghĩa là 3 tìm các bộ ( a1 , a2 ,..., ak )  S sao cho a1  a2  ...  ak M k Với mỗi i  0,1,2 ta đặt A(n, i )   (a1 , a2 ,...an )  S n | a1  a2  ...  an  i(mod3) và đặt an  A(n,0), bn  A(n,1), cn  A(n, 2) , ta có a1  1, b1  1, c1  2 Xét phần tử ( a1 , a2 ,..., an )  A( n  1,0) - Nếu an1  0 thì (a1 , a2 ,..., an )  A(n,0) - Nếu an1  2 hoặc an 1  5 thì (a1 , a2 ,..., an )  A( n,1) 13 - Nếu an1  1 thì (a1 , a2 ,..., an )  A(n,2) từ đây ta suy ra an1  an  2bn  cn (1) tương tự bn1  an  bn  2cn (2) , cn1  2an  bn  cn (3) từ đây ta tính được a2=5,b2=6,c2=5, a3=22,b3=21,c3=21. Trừ (1) cho (2), trừ (2) cho (3), trừ (3) cho (1) ta được an1  bn1  bn  cn , bn1  cn1  cn  an , cn1  an1  an  bn , do đo : an3  bn3  bn 2  cn 2  cn1  an1  an  bn tương tự ta có bn3  cn3  bn  cn ; cn3  an3  cn  an Sử dụng các giá trị ban đầu ai, bi,ci ,với i=1,2,3 và tính chất trên ta được - Nếu k chia hết cho 3 thì bk  ck  ak  1 - Nếu k chia cho 3 dư 1 thì ak  bk  ck  1 - Nếu k chia cho 3 dư 2 thì ak  ck  bk  1 Mặt khác ak  bk  ck  4 . Do đó áp dụng cách xác định số hạng tổng quát dạng 3 k ta có kết quả của bài toán: 4k  1 ak  3 +) Nếu k không chia hết cho 3 thì 4k  2 ak  3 +) Nếu k chia hết cho 3 thì Ví dụ 11. Cho số nguyên n  2. Hãy tìm số các hoán vị ( a 1, a2, ..., an) của 1, 2, ..., n sao cho tồn tại duy nhất một chỉ số i  {1, 2,..., n – 1 } thoả mãn ai > ai + 1? Giải. Gọi Sn là số các hoán vị thoả mãn điều kiện bài toán. Số các hoán vị mà a n = n là Sn – 1, còn số các hoán vị (a1, a2, …, an) mà ai = n ( 1  i  i−1 n – 1 ) là C n−1 . Do vậy n−1 Sn = S n – 1 + ∑ C i−1 n−1 i1 14 = S n – 1 + 2n – 1 – 1 Mặt khác S2 = 1, áp dụng cách xác định số hạng tổng quát dạng 4, suy ra Sn = 2n – n –1. Ví dụ 12. Giả sử Fk là tập hợp tất cả các bộ ( A1, A2, ..., Ak), trong đó Ai ( i = 1, 2, ..., k) là một tập con của { 1, 2, ..., n} ( các tập A 1, A2, ..., Ak có thể trùng nhau). Hãy tính Sn =  ∑  A1 ,A2 ,.. ., A k F k  A1 ∪A 2 ∪...∪ Ak  Giải. Do có 2n tập con của {1, 2, ..., n} nên có 2 nk bộ ( A1, A2, ..., Ak). Với mỗi k - bộ ( A1, A2, ..., Ak) của tập {1, 2, ..., n – 1 }, ta có thể thêm hoặc không thêm n vào tập A i để được k – bộ ( A1, A2, ..., Ak) của tập {1, 2, ..., n }. Chú ý rằng số k- bộ ( A1, A2, ..., Ak) của tập {1, 2, ..., n – 1 } là 2(n – 1)k và có 2k – 1 cách thêm n vào k - bộ ( A1, A2, ..., Ak) của tập {1, 2, ..., n – 1 } thì ta có: Sn = 2k Sn - 1 + (2k – 1) 2k (n – 1). Dễ thấy S1 = 2k – 1. Từ đó bằng quy nạp, ta chứng minh được Sn = n.2k(n – 1) (2k – 1) Ví dụ 13. Có n quả bóng b1, b2, ..., bn và 2n hộp h1, h2, ..., h2n. Biết rằng quả bóng bi ( i = 1,2,...,n) chỉ bỏ được vào các hộp h 1, h2, ..., h2i. Hỏi có bao nhiêu cách bỏ k ( 1  k  n ) quả bóng vào các hộp, biết rằng mỗi hộp chứa nhiều nhất một quả bóng ? ( Hai cách bỏ bóng được gọi là khác nhau khi ít nhất một quả bóng được bỏ vào hai hộp khác nhau trong hai cách đó ) Giải. Đặt Sn, k là số cách bỏ k quả bóng vào các hộp. Giả sử 2  k  n. Nếu một trong k quả bóng được chọn là bn thì k – 1 quả bóng còn lại có thể bỏ vào các hộp bằng Sn – 1, k – 1 cách. Đồng thời, bn có 2n – ( k – 1 ) = 2n – k + 1 cách chọn một hộp trong các hộp còn lại để bỏ. Do đó số cách bỏ bóng trong trường hợp này là: ( 2n – k +1).Sn -1 ,k – 1 Trường hợp quả bóng bn không được chọn. Lưu ý rằng k  n – 1. Mọi quả bóng trong các quả bóng b1, b2, ..., bn – 1 đều có thể bỏ vào các hộp bằng Sn – 1 , k cách, suy ra Sn,k = Sn – 1,k + (2n – k + 1)Sn – 1, k – 1 (n 15  3, 2  k  n) Dễ thấy Sn, n = (n + 1)Sn – 1, n – 1 ; Sn, 1 = n(n + 1) ; S1, 1 = 2 Từ đó bằng quy nạp ta chứng minh được Sn, k =  n1.k ! C kn 2 n−k 1 Ví dụ 14. Có n ( n > 1 ) thí sinh ngồi xung quanh một bàn tròn. Hỏi có bao nhiêu cách phát đề sao cho hai thí sinh ngồi cạnh nhau luôn có đề khác nhau, biết rằng trong ngân hàng đề có đúng m ( m > 1) đề và hiển nhiên mỗi đề có nhiều bản? Giải. Do thí sinh ngồi theo vòng tròn, nên một cách tự nhiên chúng ta nghĩ tới việc tìm cách “cắt” và “nắn” vòng tròn thành hàng thẳng. Kí hiệu P n là số cách phát đề hợp lệ cho n thí sinh a1, a2, ..., an ngồi theo vòng tròn ( một cách phát đề được coi là hợp lệ nếu mỗi thí sinh chỉ được nhận một đề và hai thí sinh bất kì ngồi gần nhau thì nhận được hai loại đề khác nhau). Ta viết ai = aj ( i trường hợp ngược lại, ta chứng minh  j) nếu ai và aj cùng loại đề và ai  aj trong Pn + 1 = ( m – 2)Pn + (m – 1)Pn – 1 . Xét một cách phát đề hợp lệ cho n + 1 thí sinh a1, a2,…,an + 1 Nếu a1  an thì bỏ an + 1 đi, ta có một cách phát đề hợp lệ cho n thí sinh a 1, a2, ..., an, và có m – 2 cách phát đề cho an + 1. Nếu a1 = an thì bỏ an + 1 và an đi, ta có một cách phát đề hợp lệ cho n – 1 thí sinh a1, a2, ..., an - 1, ta có m – 1 cách phát đề cho an + 1 và an để hợp lệ với an= a1. Vậy ta có Pn + 1 = ( m – 2)Pn + (m – 1)Pn – 1 Mặt khác dễ thấy P2 = m(m – 1); P3 = m(m – 1)(m – 2) Bằng quy nạp ta chứng minh được Pn = (m – 1)n + (m – 1)( - 1)n Ví dụ 15. Cho bảng ô vuông n  n ( n > 1 ). Hỏi có bao nhiêu cách đánh dấu các ô vuông trong bảng sao cho trong mỗi hình vuông 2  2 có đúng hai ô vuông được đánh dấu? ( Hai cách đánh dấu được coi là khác nhau nếu có một ô vuông nào đó mà trong cách này thì được đánh dấu còn trong cách kia thì không). Giải. Gọi Sn là số cách đánh dấu trong bảng n  n. Xét tập T gồm các ô vuông nằm trong cột cuối cùng ( tính từ phải sang) và hàng cuối cùng ( tính từ trên xuống), ta gọi A n là 16 các cách đánh dấu mà có hai ô vuông kề nhau trong T cùng được đánh dấu hoặc cùng không được đánh dấu và Bn là các cách đánh dấu mà các ô vuông trong T được đánh dấu xen kẽ. Dễ thấy mỗi cách đánh dấu thuộc Bn sẽ ứng với một cách đánh dấu thuộc B n – 1, còn mỗi cách đánh dấu thuộc An sẽ ứng với một cách đánh dấu thuộc An – 1 và một cách đánh dấu thuộc Bn – 1. (Điều này suy ra khi xét bảng ô vuông (n – 1) từ bảng n   (n – 1) có được n sau khi bỏ T). Từ đó ta có | Bn | = | Bn – 1 |, | An | = | An – 1| + | Bn – 1 | ( n > 2). Mặt khác Sn = |An| + |Bn| với mọi n > 1, nên Sn = 2Sn – 1 – Sn – 2 với mọi n > 3 Dễ thấy rằng S2 = 6, S3 = 14. Từ đó áp dụng cách xác định số hạng tổng quát dạng 5 ta có Sn = 8n – 10 với mọi n > 1. Ví dụ 16. Tìm các số nguyên dương n thoả mãn các điều kiện a) n có 2k chữ số b) Tất cả các chữ số của n là lẻ c) Hiệu của hai số liên tiếp bất kỳ của n luôn bằng 2. Giải. Trong tập hợp Sk các số nguyên dương n có k chữ số thoả mãn b) và c), gọi A k, Bk, Ck, Dk, Ek lần lượt là tập hợp các số tận cùng bởi1, 3, 5, 7, 9. Từ mỗi số thuộc A k nếu ta bỏ đi chữ số tận cùng thì nhận được một số thuộc Bk – 1, mặt khác từ mỗi số thuộc B k – 1 nếu ta bổ xung thêm số 1 là chữ số tận cùng thì nhận được một số thuộc Ak, do đó | Ak | = | Bk – 1 |. Từ mỗi số thuộc Bk nếu ta bỏ đi chữ số tận cùng thì nhận được một số thuộc Ak – 1 hoặc Ck – 1 , nếu ta bổ xung thêm số 3 làm chữ số tận cùng thì nhận được một số thuộc B k. Do đó | Bk | = | Ak – 1 | + | Ck – 1 |. Tương tự ta có | Ck | = | Bk – 1 | + | Dk – 1 | , | Dk | = | Ck – 1 | + | Ek – 1 | và | Ek | = | Dk – 1 | với mọi k > 1 Sử dụng năm đẳng thức trên, bằng cách thế liên tục, ta có | Sk | = | Ak | + | Bk | + | Ck | + | Dk | + | Ek | = | Ak – 1 | + 2| Bk – 1 | + 2| Ck – 1 | + 2| Dk – 1 | + | Ek – 1 | 17 = 2| Ak – 2 | + 3| Bk – 2 | + 4| Ck – 1 | + 3| Dk – 2 | + 2| Ek – 2 | = 3 | Ak – 3 | + 6| Bk – 3 | + 6| Ck – 3 | + 6| Dk – 3 | + 3| Ek – 3 | Suy ra | Sk | = 3| Sk – 2 | với mọi k > 3. Áp dụng công thức xác định số hạng tổng quát của cấp sô nhân ta được: Do | S2 | = 8 nên | S2k | = 8.3k-1. Ví dụ 17. Một hình tròn được chia thành 6 hình quạt bằng nhau. Trong mỗi hình quạt đặt một quân cờ. Mỗi lần cho phép chuyển 1 quân cờ ở 1 hình quạt sang 1 trong 2 hình quạt bên cạnh. Chứng minh rằng không thể dồn các quân cờ vào 1 hình quạt sau 2006 lần thực hiện? Giải. Ta tô màu các hình quạt bởi 2 màu xanh ( X) và đỏ (Đ) sao cho 2 hình cạnh nhau không cùng màu. Gọi Sn là số tất cả các quân cờ ở các ô xanh sau bước thực hiện phép chuyển thứ n, thì ta có S 0 = 3. Ta thấy Sn+1 = Sn  1, do đó S2007 là một số lẻ. Do vậy, nếu sau 2006 bước thực hiện mà dồn hết các quân cờ vào một hình quạt thì S 2006 = 0 hoặc S2006 = 6, vô lí, suy ra điều phải chứng minh Ví dụ 18. Giả sử P1, P2, ..., Pn theo thứ tự là các điểm trên cùng một đường thẳng. Người ta tô màu các điểm đó bằng 5 màu xanh (X), đỏ (Đ), tím (T), vàng (V), cam (C), mỗi điểm tô một màu sao cho trong 2 điểm Pi, Pi + 1, i = 1, 2, ..., n – 1 luôn hoặc là cùng màu hoặc là 1 trong 2 điểm được tô màu xanh. Hỏi có bao nhiêu cách tô như vậy? Giải. Gọi an là số cách tô cho n điểm đã cho mà điểm cuối được tô màu xanh và b n là số cách tô mà điểm cuối không được tô màu xanh. Nếu Pn được tô X thì Pn – 1 hoặc tô X hoặc không tô X, suy ra an = an – 1 + bn – 1 Nếu Pn không tô X thì nó có khả năng được tô bởi 1 trong 4 màu còn lại. Khi đó P n – 1 hoặc là cùng màu với Pn hoặc là được tô màu X, từ đó suy ra 18 bn = 4an – 1 + bn – 1 Ta dễ tính được a1 = 1, b1 = 4. Từ các hệ thức truy hồi trên ta suy ra bn + 2an = 3( bn – 1 + 2an – 1 ) = ... = 3n – 1( b1 + 2a1) = 2. 3n bn - 2an = ( - 1 )( bn – 1 - 2an – 1 ) = ... = ( - 1)n – 1( b1 - 2a1) = - 2. ( - 1)n n Do vậy ta tính được an  3 −1 2 n n và bn 3 −−1 n n 1 Vậy số cách tô màu thoả mãn bài toán là Ví dụ 19. Cho P1, P2, ..., Pn là n  n 3 −−1 2 a n + bn = 5 điểm trên cùng một đường tròn. Có bao nhiêu cách tô màu n điểm đã cho bằng 5 màu sao cho 2 điểm kề nhau được tô bởi 2 màu khác nhau? Giải. Gọi an là số cách tô màu thoả mãn bài toán. Nếu P2 và Pn khác màu thì có an – 1 cách tô màu cho n – 1 điểm P 2, P3, ..., Pn bằng 5 màu. Khi đó vì P1 có 3 cách tô màu nên số cách tô trong trường hợp này là 3an – 1 Nếu P2 và Pn cùng màu thì có an – 2 cách tô n – 2 điểm P3, P4, ..., Pn ứng với mỗi cách tô như vậy thì có 1 cách tô P 2 vì P2 và Pn cùng màu và 4 cách tô điểm P 1, do đó trong trường hợp này có 4an – 2 cách tô màu thoả mãn. Từ đó suy ra a n = 3an – 1 + 4an – 2 với a1 = 0, a2 = 5(5 – 1) = 20, từ đó áp dụng cách xác định số hạng tổng quát dạng 5, ta tìm được an Tổng quát: Cho P1, P2, ..., Pn là n điểm trên cùng một đường tròn. Cho p  2, p   N, p n Có bao nhiêu cách tô màu n điểm đã cho bằng p màu sao cho 2 điểm kề nhau được tô bởi 2 màu khác nhau. Giải. Tương tự BT trên ta có đáp số an = (p – 1)an – 2 + (p – 2)an – 1 , a1 = 0, a2 = p(p – 1) Ví dụ 20. Xét đa giác đều 12 đỉnh A1, A2, ..., A12 với tâm O. Người ta tô màu các miền tam giác OAiAi+1 ( 1  i  12) ( A13 = A1) bằng 4 màu xanh (X), đỏ (Đ), tím 19 (T), vàng (V) sao cho 2 miền kề nhau được tô bởi 2 màu khác nhau. Hỏi có bao nhiêu cách tô như vậy ? Giải. Xét trường hợp tổng quát: cho đa giác đều n đỉnh và tô bằng k màu ( k  3). Gọi S(n, k) là số cách tô màu thoả mãn bài toán. Ta có k cách tô màu miền OA 1A2, k – 1 cách tô màu miền OA2A3, …, k – 1 cách tô màu miền OAnA1. Do đó có tất cả k(k – 1)n –1 cách tô. Tuy nhiên, chúng ta phải trừ đi các cách tô sai, chẳng hạn khi OA nA1 và OA1A2 cùng màu, khi đó ta coi OA nA2 như là một miền tam giác ( bỏ qua đỉnh A 1), số cách tô như vậy là S(n – 1, k). Do đó ta có hệ thức S(n, k) = k(k – 1)n -1 – S(n – 1, k) = k(k – 1)n -1 - [ k(k – 1) n -2 – S(n – 2, k) ] = .... = k(k – 1)n – 1 - k(k – 1)n - 2 + ... + ( -1 )n – 4 [k(k – 1)3 – S(3, k)] Suy ra S(n, k) = (k – 1)n + ( -1)n (k – 1) Trở lại BT, số cách tô thoả mãn đề bài là S( 12, 4) = 312 + 3 Ví dụ 21. Ký hiệu f(n) là số hoán vị {a1, a2, ..., an } của {1, 2, ..., n} thoả mãn: a) a1 = 1 b) | ai – ai +1 |  2 với 1  i  n–1 Hỏi f( 2007) có chia hết cho 3 không ? Giải. Ta xét với n  5. Do a1 = 1 và | a1 – a2 |  2 nên a2 = 2 hoặc a2 = 3. +) Nếu a2 = 2 thì { a2, a3, ..., an } là hoán vị của {2, 3, ..., n} thoả mãn a) a2 = 2 b) | ai – ai +1 |  2 với 2  i  n–1 Số các hoán vị như vậy chính là f(n – 1). +) Nếu a2 = 3 thì a3  {2, 4, 5}. Giả sử có ak = 2 ( 3 < k < n) thì do | a k – 1 – ak |  2, | ak – ak + 1 | 1, 2, 3 nên ak – 1 = ak + 1 = 4 , vô lí. Vậy a3 = 2 hoặc an = 2. 20  2 và ak -1 , ak 