Áp dụng phương pháp hàm sinh giải toán trung học phổ thông.

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG



LÊ THANH THẢO

ÁP DỤNG PHƯƠNG PHÁP HÀM SINH

GIẢI TOÁN TRUNG HỌC PHỔ THÔNG

Chuyên ngành: Phương pháp Toán sơ cấp

Mã số: 60.46.01.13

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng – Năm 2015

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: TS. Trịnh Đào Chiến

Phản biện 1: TS. Cao Văn Nuôi

Phản biện 2: TS. Phạm Hữu Khánh

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Khoa học họp tại Phân hiệu Đại học Đà Nẵng tại Kon Tum

vào ngày 19 tháng 12 năm 2015

Có thể tìm hiểu luận văn tại:

 Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng

 Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Phương pháp hàm sinh là một phương pháp hiện đại, sử dụng

các kiến thức về chuỗi, chuỗi hàm (đặc biệt là công thức Taylor) để

giải khá nhiều lớp các bài toán sơ cấp, chẳng hạn: giải bài toán phân

hoạch tập số nguyên để tìm số nghiệm của phương trình nghiệm

nguyên, giải bài toán về phân hoạch tập hợp, tìm số hạng tổng quát

của dãy số, các bài toán nổi tiếng về dãy Catalan, tính tổng tổ hợp, giải

bài toán đếm tổ hợp và một số dạng toán tổng hợp khác.

Cho dãy số an  . Chuỗi hình thức

  2

0 1 2 ... ... n A x a a x a x a x       n

được gọi là hàm sinh của dãy an  .

Ý tưởng của phương pháp hàm sinh như sau:

Giả sử ta cần tìm công thức tổng quát của một dãy số an  nào

đó. Từ công thức truy hồi hoặc những lý luận tổ hợp trực tiếp, ta tìm

được hàm sinh

  2

0 1 2 ... ... n A x a a x a x a x       n

Trong trường hợp thuận lợi, từ biểu diễn trên, có thể tìm được

một công thức giải tích cho hàm A x . Khai triển A x  thành chuỗi

và tìm hệ số của n x trong khai triển đó ta tìm được n a .

Cho đến nay, trong nước đã có một số luận văn thạc sĩ toán học

liên quan đến hàm sinh và phương pháp hàm sinh bảo vệ thành công.

2

Luận văn này tiếp nối hướng nghiên cứu nêu trên, nhưng để

tránh trùng lặp nội dung nghiên cứu, sẽ không quá đi sâu vào lý thuyết

hiện đại của hàm sinh, mà chỉ tập trung áp dụng phương pháp hàm

sinh giải một số dạng toán về phân hoạch tập số nguyên để tìm số

nghiệm của phương trình nghiệm nguyên, giải một số dạng toán phân

hoạch tập hợp và một số dạng toán tổng hợp. Trong các bài toán trên

có các bài toán là đề thi trong các kỳ thi chọn học sinh giỏi các nước,

khu vực và quốc tế. Đây là những nội dung mà các luận văn trước đó

chưa hoặc ít đề cập.

Đồng thời, luận văn cũng sẽ áp dụng phương pháp trên đề xuất

các bài toán tương tự, phù hợp với toán phổ thông, đặc biệt đối với hệ

Chuyên Toán. Do đó, việc nghiên cứu của luận văn là cần thiết, có ý

nghĩa khoa học, mang tính thực tiễn và phù hợp với chuyên ngành

Phương pháp Toán sơ cấp.

2. Mục tiêu nghiên cứu

Luận văn sẽ đề cập đến hàm sinh và áp dụng phương pháp hàm

sinh để giải một số dạng toán về phân hoạch tập số nguyên để tìm số

nghiệm của phương trình nghiệm nguyên, một số dạng toán phân

hoạch tập hợp tổng hợp và một số dạng toán tổng hợp là đề thi trong

các kỳ thi chọn học sinh giỏi các nước, khu vực, Olympic toán quốc

tế.

Luận văn cũng sẽ đề xuất một số bài toán tương tự, nhằm phục

vụ cho cho công tác giảng dạy và bồi dưỡng học sinh giỏi ở phổ thông,

đặc biệt đối với hệ Chuyên Toán.

3. Đối tượng và phạm vi nghiên cứu

3.1. Đối tượng nghiên cứu

Hàm sinh và phương pháp hàm sinh.

3.2. Phạm vi nghiên cứu

3

Thuộc chuyên ngành Phương pháp toán sơ cấp. Luận văn không

quá đi sâu vào lý thuyết hiện đại của hàm sinh mà sơ cấp hóa nó, áp

dụng phương pháp hàm sinh để giải một số bài toán khó của toán phổ

thông.

4. Phương pháp nghiên cứu

Từ các tài liệu sưu tầm được, luận văn sẽ đề cập ngắn gọn về

hàm sinh và áp dụng phương pháp hàm sinh để tìm tòi lời giải, cùng

với việc đề xuất một số bài toán tương tự, phù hợp với toán phổ thông,

đặc biệt đối với hệ Chuyên Toán.

5. Ý nghĩa khoa học và thực tiễn của đề tài

Với mục đích nêu trên, việc nghiên cứu của luận văn là có ý

nghĩa khoa học, mang tính thực tiễn và phù hợp với chuyên ngành

Phương pháp Toán sơ cấp.

Có thể sử dụng luận văn như là tài liệu tham khảo cho giáo viên,

học sinh và bạn đọc quan tâm đến vấn đề này.

6. Cấu trúc luận văn

Nội dung của luận văn gồm có ba chương.

Chương 1. Kiến thức cơ sở

Chương này đề cập đến những kiến thức cơ bản nhất, sử dụng

cho những chương tiếp theo.

Chương 2. Áp dụng phương pháp hàm sinh giải bài toán về

phân hoạch tập hợp

Chương này trình bày việc áp dụng phương pháp hàm sinh để

tìm số nghiệm của phương trình nghiệm nguyên và giải một số dạng

toán tổng hợp, thực chất là việc áp dụng phương pháp hàm sinh để giải

bài toán về phân hoạch tập hợp.

Để tìm số nghiệm của một phương trình nghiệm nguyên nào đó,

ta thực hiện các bước như sau:

4

- Xét một hàm sinh F x  phù hợp;

- Khai triển F x  dưới dạng một chuỗi lũy thừa;

- Số nghiệm của phương trình nghiệm nguyên đã cho chính là hệ

số của số hạng n x phù hợp trong chuỗi lũy thừa nêu trên.

Tiếp theo là các bài toán, thực chất là dạng toán về phân hoạch

tập hợp, có thể giải bằng phương pháp hàm sinh.

Chương 3. Áp dụng phương pháp hàm sinh giải một số bài

toán tổng hợp

Chương này trình bày việc áp dụng phương pháp hàm sinh để

giải một số dạng toán về dãy số (đặc biệt, giới thiệu các bài toán nổi

tiếng liên quan đến dãy số Catalan), bài toán tính tổng tổ hợp, bài toán

đếm tổ hợp và một số bài toán tổng hợp khác.

CHƯƠNG 1

KIẾN THỨC CƠ SỞ

Chương này trình bày một số khái niệm về hàm sinh và phân

hoạch tập hợp. Nêu ra một số tính chất, kết quả liên quan đến việc áp

dụng hàm sinh vào giải các bài toán.

1.1. HÀM SINH

1.1.1. Khái niệm

Định nghĩa 1.1. Một chuỗi lũy thừa hình thức là biểu thức có

dạng

2

0 1 2

0

... n

n

n

a a x a x a x





     , (1.1)

5

dãy các số nguyên   0 n n a



được gọi là dãy các hệ số.

Định nghĩa 1.2. Cho dãy số 0 1 2 , , ,..., ,... n a a a a các số thực, và

x là một biến số. Hàm sinh của dãy   0 n n a



là

2

0 1 2

0

( ) ... ... k n

k n

n

F x a a x a x a x a x





        , (1.2)

với 0 1 2 , , ,..., ,... n a a a a gọi là các hệ số của hàm sinh.

Nhận xét 1.1.

a) Nếu 0

( ) n

n

n

F x a x





  là hàm sinh của dãy số  n n 0 a  thì ta còn

kí hiệu   ( ) n a F x  hay a F n   .

b) Việc xây dựng hàm sinh không chỉ dựa trên một biến (vì một

biến chỉ cho ta một thông tin duy nhất!). Đối với những bài toán đòi

hỏi nhiều thông tin ta cần xét hàm sinh với nhiều biến hơn (xem Bài

toán 2.2.10).

Hàm sinh có thể tổng quát cho nhiều chỉ số, cụ thể

Cho dãy số  ,  , 0 m n m n a  . Khi đó 0

( , ) (1.3) m n

mn

n

F x y a x y





 

Định nghĩa 1.3.

1.1.2. Tính chất

Cho a F x b G x n n    ( ), ( )   . Khi đó ta có các tính chất sau

  ( ) ( ) n n a b F x G x    . (1.6)

  ( ), n ka kF x k     . (1.7)

6

( 1) '( ) n a F x   n1  . (1.8)

 1  (1 ) ( ) n n a a x F x     . (1.9)

  '( ) n na xF x  . (1.10)

  2 3 1

0 1 2 3 1 ( ) ... ,

h

h

n h h

F x a a x a x a x a x

a h

x







         (1.11)

k a h b k F x h G x . . . ( ) . ( ) n n     . (1.12)

 0 1 2  ( ) ... 1 n

F x

a a a a

x

      . (1.13)

  0

( ). ( )

n

n i j k n k

i j n k

c a b a b F x G x 

  

   

             . (1.14)

1.1.3. Một số kết quả liên quan

a. Kết quả về hàm sinh

Mệnh đề 1.1. Cho hàm sinh   2 ( ) 1 ... n

F x x x     .

Khi đó ta có

a) Nếu r a là hệ số của r x trong khai triển của F x( ), thì

1

r

r r n a C    . (1.15)

b)   1 2 2 1 1 ... ( 1) n m m m n mn

n n        x C x C x x . (1.16)

c)       2 1 2 1 ... 1 1 ... n n n m m x x x x x x           . (1.17)

Mệnh đề 1.2. (Công thức xác định hệ số tích của hai hàm sinh)

Cho hai hàm sinh của hai dãy a b n n ,  lần lượt là

2

0 1 2 A x a a x a x ( ) ....    

7

2

0 1 2 B x b b x b x ( ) ....    

Đặt

F x( )  A x B x ( ) ( )

   2 2

0 1 2 0 1 2        a a x a x b b x b x .... ....

   

 

2

0 0 0 1 1 0 0 2 1 1 2 0

3

0 3 1 2 2 1 3 0 ...

a b a b a b x a b a b a b x

a b a b a b a b x

     

    

Khi đó hệ số của r x trong khai triển của F x( ) là

0 1 1 2 2 2 2 1 1 0 ... r r r r r r a b a b a b a b a b a b           . (1.18)

Nhận xét 1.2.

Định lý 1.1. (Công thức khai triển Taylor)

Giả sử f x( ) là hàm số liên tục, có đạo hàm mọi cấp trên

khoảng a b x a b , ; ,  0  .

Khi đó ta có công thức khai triển Taylor

 

 0 

0

( ) !

n

n

n

f x f x x  n   . (1.19)

Nhận xét 1.3.

Định lí 1.2.

Định lí 1.3.

Định lí 1.4. (Quy tắc xoắn)

Gọi A x( ) là hàm sinh cho cách chọn các phần tử từ tập hợp A

và B x( ) là hàm sinh cho cách chọn các phần tử từ tập hợp B . Nếu

A và B là rời nhau thì hàm sinh cho cách chọn các phần tử của

A B là A x B x ( ). ( ).

b. Khai triển đại số

Sau đây là một số kết quả khai triển đại số thường dùng trong

việc áp dụng giải bài toán về hàm sinh

8

   

   

2

1 1 1 ...

2!

1 ... 1 ...

!

n

x

x x

x

x n

n



  

   

     

     

(1.23)

1 2 2

0

(1 ) 1 ... ... n n n k k

n n n n

k

x C x C x C x C x





         . (1.24)

  0

1 n k k k

n

n

ax C a x





   . (1.25)

2 3

0

1 1 ...

1

n

n

x x x x

x





        . (1.26)

2 3

0

1 1 ... ( 1) 1

i i

i

x x x x

x





      

  . (1.27)

2 2 3 3

0

1 1 ... ...

1

n n n n

n

ax a x a x a x a x

ax





          . (1.28)

 

2 2 3 3

2

0

1 1 2 3 4 ... ( 1)

1

n n

n

ax a x a x n a x

ax





         . (1.29)

 

2 3

2

0

1 1 2 3 4 ... ( 1) ( 1)

1

n i

i

x x x n x i x

x





           . (1.30)

 

1 ( 1) ( 1)( 2) 2 3 1 ...

1 2! 3! n

n n n n n

nx x x

x

  

      . (1.31)

2 4 6 2

2 0

1 1 ...

1

i

i

x x x x

x





        . (1.32)

2 3

0

1 1 ...

1

r r r ir

r i

x x x x

x





        . (1.33)