Ứng dụng phương pháp ánh xạ trong giải toán tổ hợp

(1)

TRƯỜNG TRUNG HỌC PHỔ THỒNG CHUYÊN NGUYỄN DU

ỨNG DỤNG

PHƯƠNG PHÁP ÁNH XẠ TRONG GIẢI

TOÁN TỔ HỢP

NGƯỜI THỰC HIỆN : LÊ NGỌC ĐỨC LỚP : 10CT

NIÊN KHÓA : 2017-2020

(2)

Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du

MỤC LỤC

Mục lục ………..1

Lời cảm ơn ……….2

Giới thiệu và tổng quan về vấn đề nghiên cứu ………...4

Một số chữ viết tắt và các kí hiệu toán học trong tài liệu ………..……….5

Cơ sở lí thuyết ………. Ánh xạ ………...………6

Ứng dụng của ánh xạ trong các bài toán tổ hợp ………7

Lời kết ………...……28

Tài liệu tham khảo ………...….29

(3)

LỜI CẢM ƠN

Trong quá trình học tập, nghiên cứu và thực hiện dự án, chúng tôi đã nhận được nhiều sự giúp đỡ. Giờ đây khi nội dung dự án đã được hoàn thành, chúng tôi xin bày tỏ lòng biết ơn chân thành đến:

Quý Thầy, Cô của trường THPT chuyên Nguyễn Du tỉnh Đắk Lắk đã tận tình giảng dạy, hướng dẫn, giúp đỡ chúng tôi học tập và hỗ trợ chúng tôi trong việc thực hiện đề tài nghiên cứu.

Đặc biệt là thầy Nguyễn Văn Quang, giáo viên hướng dẫn khoa học, đã tận tình hướng dẫn chúng tôi trong suốt quá trình nghiên cứu và hoàn thành dự án.

Chúng tôi cũng xin bày tỏ lòng biết ơn đến các thầy, tuy không giảng dạy trực tiếp nhưng đã chia sẻ những bài toán tổ hợp hay với cách giải bằng phương pháp ánh xạ rất độc đáo để chúng tôi tham khảo.

Xin gửi tặng các bạn cùng lớp, những người đã dành cho chúng tôi những tình cảm, lời động viên, sự giúp đỡ trong cuộc sống và trong quá trình học tập vừa qua.

Lần đầu tiên chúng tôi tập làm nghiên cứu, nội dung có lẽ chưa được đầy đủ và còn nhiều thiếu sót, mong nhận được những góp ý bổ ích từ quý Thầy, Cô cùng các độc giả.

Xin trân trọng cảm ơn!

Buôn Ma Thuột, ngày 16 tháng 10 năm 2017 Tác giả

(4)

Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du A. LỜI GIỚI THIỆU VÀ TỔNG QUAN

Cùng với chương trình phát triển trọng điểm toán học giai đoạn 2010 – 2020 , toán học Việt Nam đã có nhiều phát triển và tiến bộ.Đi cùng với đó,phong trào chuyên toán phổ thông những năm gần đây đã có nhiều dấu hiệu khởi sắc với kết quả các kì thi HSG toán quốc gia và quốc tế của chúng ta ngày càng được nâng cao. Hằng năm các trường hè,trường đông được Viện toán học tổ chức ngày càng phát triển về quy mô và chất lượng. Cùng với những sự phát triển đó thì nhu cầu tài liệu càng được nhiều học sinh quan tâm. Đặc biệt là những tài liệu mang tính thời sự và chuyên môn sâu về các phân môn. Lịch sử và quá trình giảng dạy cho ta thấy điểm yếu của học sinh Việt Nam đó chính là toán tổ hợp và rời rạc. Trong các kìthi HSG toán phổ thông, số học sinh giải quyết trọn vẹn bài toán tổ hợp là rất ít, thậm chí không có học sinh nào. Trên thực tế như vậy, việc biên soạn một cuốn sách chuyên khảo sâu về tổ hợp và rời rạc là việc rất cần thiết.Và đó cũng là lý do chúng tôi biên soạn tài liệu này.Tài liệu này cung cấp những khái niệm về ánh xạ và ứng dụng của nó trong toán học.

Trong toán học, tổ hợp là một dạng toán rất khó nhưng lại rất thu hút vì những lài giải hay, độc đáo và có ý nghĩa quan trọng trong các nghành học công nghệ thông tin. Trong các kì thi học sinh giỏi, tổ hợp luôn là bài toán khó nhất nên hầu hết học sinh đều ngại học chủ đề này, vì mỗi kì chỉ có vài ba bạn giải được. Do đó có rất nhiều nghiên cứu về chủ đề này, từ đó có rất nhiều phương pháp để tiếp cận. Ánh xạ là một trong các công cụ đầu tiên, đơn giản nhưng hiệu quả trong bài toán đếm. Thông qua ánh xạ ta đưa một bài toán đếm phức tạp về một bài toán đếm đơn giản hơn ; tuy nhiên việc xây dựng ánh xạ phù hợp mới là việc khó khăn đòi hỏi phải và chạm nhiều và phải có kinh nghiệm. Bài nghiên cứu này nhằm mục đích ban đầu là tự học, tổng hợp các bài toán để có thêm nhiều kinh nghiệm; sau đó là một tài liệu tham khảo cho các bạn bước đầu học tổ hợp.

Tuy nhiên, dù đã cố gắng nhiều nhưng chắc chắn vẫn còn nhiều thiếu sót . Mong các bạn đọc góp ý để bài nghiên cứu hoàn thiện tốt hơn.

(5)

MỘT SỐ CHỮ VIẾT TẮT VÀ CÁC KÍ HIỆU TOÁN HỌC TRONG TÀI LIỆU I/Một số chữ viết tắt:

IMO International Mathematical Olympiad Olympic Toán học Quốc tế VMO Vietnam Mathematical Olympiad Olympic Toán học Việt Nam APMO Asian Pacific Math Olympiad Olympic toán Châu Á – Thái Bình Dương

II/Một số kí hiệu toán học A là số phần tử của tập hợp A

C_mⁿ là tổ hợp chập n của tập hợp gồm m phần tử

(6)

B. CƠ SỞ LÝ THUYẾT I/ÁNH XẠ

1/KHÁI NIỆM

Một ánh xạ f đi từ tập X đến Y là một quy tắc đặt tương ứng mỗi phần tử x của X với một (và chỉ một) phần tử của Y

Phần tử này được gọi là ảnh của x qua ánh xạ f và được kí hiệu là f(x).

(i) Tập X được gọi là tập xác định của f. Tập hợp Y được gọi là tập giá trị của f.

(ii) Ánh xạ f đi từ X đến Y được kí kiệu là f: X → Y x ↦y=f(x)

(iii) Khi X và Y là các tập số thực , ánh xạ f được gọi là một hàm số xác định trên X

(iv) Cho a thuộc X, b thuộc Y. Nếu f(a)=y thì ta nói y là ảnh của a và a là nghịch ảnh của y qua ánh xạ f

(v) Tập hợp Y = {y=Y : mọi x thuộc X, y=f(x)} gọi là tập ảnh của f.

2/Đơn ánh, toàn ánh, song ánh 2.1. Định nghĩa đơn ánh:

Ánh xạ f:X được gọi là đơn ánh nếu với a ∈ X,b ∈ Y mà a≠b thì f(a)≠f(b), tức là hai phần tử phân biệt sẽ có hai ảnh phân biệt.

Từ định nghĩa ta suy ta ánh xạ f là đơn ánh khi và chỉ khi với a ∈ X, b ∈ Y mà f(a)=f(b), ta phải có a=b.

2.2. Định nghĩa toàn ánh

Ánh xạ f: X ↦ Y được gọi là toàn ánh nếu với mỗi phần tử y ∈ Y đều tồn tại một phần tử x ∈ X sao cho y=f(x).

Như vậy f là toàn ánh nếu và chỉ nếu Y=f(X).

2.3. Định nghĩa song ánh

Ánh xạ f : X ↦ Y được gọi là song ánh nếu nó vừa là đơn ánh vừa là toàn ánh.

Như vậy ánh xạ f : X↦Y là song ánh nếu và chỉ nếu với mỗi y  Y , tồn tại và duy nhất một phần tử x  X để y = f(x)

3. Ánh xạ ngược của một song ánh 3.1.Định nghĩa

Ánh xạ ngược của f, được kí hiệu bởi ,là ánh xạ từ Y đến X gán cho mỗi phần tử y Y phần tử duy nhất x X sao cho y = f(x) . Như vậy

3.2. Chú ý. Nếu f không phải là song ánh thì ta không thể định nghĩa được ánh xạ ngược của f. Do đó chỉ nói đến ánh xạ ngược khi f là song ánh.

4. Ánh xạ hợp

4.1. Định nghĩa. Nếu g : A↦ B và f : B ↦ C và g(A)  B thì ánh xạ hợp

được xác định bởi .

Kí hiệu

(7)

Nguyên lý ánh xạ. Cho A và B là các tập hữu hạn khác rỗng và f : A B là một ánh xạ. Khi đó:

a) Nếu f là đơn ánh thì | A| |B | b) Nếu f là toàn ánh thì |A | |B | c) Nếu f là song ánh thì |A | |B |

Phương pháp ánh xạ dựa vào ý tưởng rất đơn giản:

- Nếu tồn tại một song ánh từ tập hữu hạn A vào tập hữu hạn B thì |A| = |B|. Do đó, muốn chứng minh hai tập hợp có cùng số phần tử, chỉ cần xây dựng một song ánh giữa chúng. Hơn nữa, ta có thể đếm được số phần tử của một tập hợp A bằng cách xây dựng song ánh từ A vào một tập hợp B mà ta đã biết cách đếm hoặc dễ đếm hơn.

- Nếu tồn tại một đơn ánh (tương ứng toàn ánh) từ A vào B thì |A| |B| (tương ứng

|A| |B |). Do đó, đơn ánh và toàn ánh chủ yếu được sử dụng để chứng minh các bài toán liên quan đến bất đẳng thức tổ hợp. Chuyển bài toán cần chứng minh về việc so sánh số phần tử của hai tập hợp, trong đó có một tập hợp đã biết cách đếm hoặc dễ đếm. Tương tự nguyên lý Dirichle, về mặt ý tưởng thì hết sức đơn giản tuy nhiên thực thế thì không phải đơn giản như thế. Để sử dụng phương pháp này ta cần xác định được một song ánh giữa tập cần đếm vào một tập đã biết cách đếm việc làm này không phải lúc nào cũng thực hiện dễ dàng. Sau đây là một số bài tập áp dụng phương pháp trên

II/ỨNG DỤNG CỦA ÁNH XẠ TRONG TỔ HỢP

Để khởi đầu cho phần này tôi xin gửi đến các bạn một định lí đơn giản nhưng có ứng dụng rất lớn trong giải toán tổ hợp đó là “Bài toán chia kẹo của Euler”

Định lí: Cho k,n là các số tự nhiên ; số nghiệm tự nhiên của phương trình + + … + = n là

Chứng minh

Ta cho tương ứng mỗi nghiệm nguyên không âm của phương trình + + … + = n (1) với một xâu nhị phân độ dài n+k-1 trong đó có n bit 1 và k-1 bit 0, cụ thể xâu gồm bit 1, sau đó là 1 bit 0,tiếp theo là bit 1, sau đó là 1 bit 0, cứ như thế, cuối cùng là bit 1. Dễ dàng chứng minh được đây là một song ánh từ tập A các nghiệm nguyên không âm của (1) vào tập hợp B các xâu nhị phân độ dài n+k-1 với n bit 1 và k-1 bit 0. Từ đó, theo nguyên lý song ánh ta có

(đpcm).

Ví dụ 1:

Có n người xếp thành hàng dọc.Hỏi có bao nhiêu cách chọn ra k người sao cho không có hai người liên tiếp được chọn ?

(8)

Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Lời giải

Ta lần lượt đánh số thứ tự của hàng người bằng các số nguyên dương là 1,2,3,...,n.

Vậy ta sẽ đưa đề về dạng : Cho n số nguyên dương 1,2,…,n.Hỏi có bao nhiêu cách chọn k số phân biệt trong n số đã cho sao cho không có 2 số nguyên liên tiếp nào?

Một cách chọn thích hợp chính là bộ số 1 ≤ …< ≤ n thỏa mãn

tức là .

Vậy ta cần tìm số phần tử của

A={( , , ,…, 1 ≤ …< ≤ n, với

i=1,2,…,k-1}

Xét ánh xạ : = với = thì rõ

ràng ta có:

i) ≥ 1 ii)

iii)

Suy ra là phần tử của tập hợp B

B={ │ 1 ≤ …< ≤ n – k +1}

Dễ thấy f là một đơn ánh

Ngoài ra ánh xạ g = với cho

chúng ta một đơn ánh từ B vào A.Vậy Ví dụ 2:

Cho 49 số tự nhiên liên tiếp 1,2,…,49 . Hỏi có bao nhiêu cách chọn ra một bộ 6 số khác nhau từ 49 số đó trong đó có ít nhất 2 số nguyên liên tiếp

Lời giải Giả sử bộ gồm 6 số tùy ý , ,

Không giảm tổng quát, ta giả sử …<

(1)

Ứng với dãy (1) xét tương ứng dãy sau : , , , , , (2)

Rõ ràng dãy (2) gồm các số khác nhau khi cà chỉ khi dãy (1) không chứa 2 số nguyên liên tiếp.Rõ ràng ta có các số trong dãy (2) được sắp xếp từ bé đến lớn.

Như vậy dãy 6 số trong đó không chứa 2 số nguyên liên tiếp được đặt tương ứng với dãy 6 số khác nhau được chọn từ các số 1 đến 44.

Từ đây ta hoàn toàn có thể tính được kết quả cần tính

Nhận xét: Bài toán đang xét với 1 tập 49 số và bạn đọc hoàn toàn có thể mở rộng ra với n số. Điểm nhấn đặc biệt đó là việc đặt tương ứng dãy (1) với dãy (2), điều này khá tự nhiên. Nhưng nó đã gắn kết bài toán và khiến mọi thứ trở nên tường minh hơn.

Bài tập ứng dụng : Cho 2018 số tự nhiên liên tiếp 1,2,…,2018 . Hỏi có bao nhiêu cách chọn ra một bộ 6 số khác nhau từ 2018 số đó trong đó có ít nhất 2 số nguyên liên tiếp

(9)

Các bạn đã bao giờ nghĩ rằng nếu kết hợp cả hai ví dụ trên thì bài toán sẽ như thế nào không? Vâng tôi xin được gửi đến bạn sự kết hợp vi diệu ấy ở Ví dụ 3.

Ví dụ 3:

Cho n số 1,2,3,...,n.Có bao nhiêu cách chọn m số phân biệt từ n số đã cho sao cho trong m số ấy có ít nhất 2 số liên tiếp với giả thiết n ≥ 2m-1

Lời giải

Gọi A là tập hợp tất cả các cách chọn m số từ n số phân biệt đã cho, ta có: = Gọi B là tập hợp các cách chọn m số phân biệt trong n số đã cho sao cho không có 2 số nguyên liên tiếp nào.

Gọi C là tập hợp các cách chọn m số phân biệt trong n số đã cho sao cho có ít nhất 2 số nguyên liên tiếp.

Áp dụng Ví dụ 1 , ta có : Kết quả :

Nhận xét :

Giả thiết n ≥ 2m-1 là cần thiết bởi vì khi đó n+1-m ≥ m.

Vì nếu ngược lại thì theo nguyên lí Dirichlet trong mọi cách chọn đều có 2 số nguyên liên tiếp được chọn (Bạn đọc hãy tự lí giải điều này). Một câu hỏi các bạn cần trả lời được đó là : Nếu bỏ đi điều kiện n ≥ 2m-1 thì cần phải có thêm quy ước gì?

Ví dụ 4:

Cho tập hợp E ={1;2;…;n}.Gọi g(n,k) là số các tập con gồm k phần tử của E mà không chứa 2 số nguyên liên tiếp nào. Còn là số tất cả các tập con của E mà không chứa 2 số nguyên liên tiếp nào. Chứng mình rằng:

a) g(n,k) = b)

Lời giải

Ở câu a) , ta có thể dễ dàng chứng minh như ở ví dụ trước Giờ ta chỉ việc xét câu b)

Kí hiệu P là tập hợp tất cả các tập hợp con của E thỏa mãn điều kiện mà tập hợp con đó đều không chứa 2 số nguyên liên tiếp nào của E

Đặt và A chứa n. và A không chứa n.

Như vậy ta có

Theo định nghĩa thì ta có

Nếu A thì n A. Vì a nên a cũng thuộc P mà theo định nghĩa của P thì n nên n-a không thuộc A. Vậy A\{n} ’, ở đây P’ là tập hợp tất cả các tập hợp con của A\{n,n-1} thỏa mãn điều kiện là mỗi tập hợp con đó đều không chứa 2

(10)

số nguyên liên tiếp nào của {1,2,3,…,n-2}. Như vậy với mỗi A tương ứng đúng với một tập con của P’. Vậy ta có : .

Nhưng theo định nghĩa thì ta lại có . Lập luận tương tự ta có được : .Như vậy ta có điều phải chứng minh.

Nhận xét :

Kết quả của bài toán cho ta phép định nghĩa dãy Fibonacci theo tư tưởng của phép đếm. Một lần nữa chung ta thấy được vẻ đẹp của tổ hợp, những yếu tố tưởng

chừng như không liên quan gì lại cho ta dãy Fibonacci. Từ đây đôi lúc khi làm việc với day Fibonacci ta có thể tổ hợp hóa và giải quyết bài toán theo hướng tổ hợp.

Ví dụ 5:(VMO 2002)

Cho tập S gồm tất cả các số nguyên trong đoạn [1,2001]. Gọi T là tập hợp tất cả các tập con không rỗng của S. Với mỗi X thuộc T, ký hiệu m(X) là trung bình cộng các phần tử của X. Tính m= .

Lời giải

Xét ánh xạ f :T → T như sau : f(X) = {2003 - x│x ∈ X}, X∈T.

Vì f là song ánh nên m(X)=m(f(X)). Do đó : 2m = Mà m(X) +m(f(X)) = 2003 nên m =

Ví dụ 6:( Trung Quốc 1994) Chứng minh rằng :

Lời giải

Bước 1 : Ta chọn ra n số từ 2n+1 số như sau. Trước hết từ 2n+1 số ta chia ra n cặp và số x.

Bước 2 : Ta chọn ra k cặp rồi từ mỗi cặp chọn ra một số.

Bước 3 : Chọn [ cặp trong n-k cặp còn lại.

Ngoài ra số x sẽ được chọn nếu n-k lẻ và sẽ không được chọn nếu n-k chẵn.Rõ ràng ở bước 2 có cách chọn và bước 3 có cách chọn. Lúc này, ta chọn được tổng cộng n số, trong đó k chạy từ 0 đến n.

Ví dụ 7:

Cho n là một số nguyên dương. Xét bảng ô vuông n × n. Hỏi trong bảng đã cho có bao nhiêu hình vuông

Lời giải

Xét hình vuông như trên ( chỉ mang tính minh họa)

(11)

Ta chiếu các điểm lên một đường thẳng song song với một trong các cạnh của hình vuông đã cho, giả sử là cạnh AB.

Đếm các hình vuông có hai cạnh song song với 2 cạnh còn lại của hình vuông ban đầu, giả sử là BC,CD,DA bằng cách chọn ra bốn điểm theo thứ tự trên đường thẳng đã chiếu.

Rõ ràng với hình vuông có cạnh được chia thành n phần thì số cách sẽ là nên tổng cộng có tất cả 4

Ví dụ 8:(Olympic 30/4 2000)

Hãy tính trung bình cộng tất cả các số N gồm 2002 chữ số thỏa mãn N 99 và các chữ số của N thuộc {1;2;3;4;5;6;7;8}

Lời giải Gọi M là tập các số N thỏa mãn điều kiện đề bài.

Ta xây dựng ánh xạ f:M→M như sau:

Nếu N= thì f(N)= ,với

Do N+f(N)= chia hết cho 9, nên f là song ánh Từ đó suy ra 2. ( ) ( ( ))

N M N M

N N N

 

 

  

^2. ^{( )} ⁽ ^{( ))}

N M N M

N N N

 

 

  

⁼

Cuối cùng ta nhận được trung bình cộng các số N là Ví dụ 9 : (APMO 1998).

Giả sử F là tập hợp tất cả các bộ gồm n tập { trong đó là tập con của tập {1,2,...,2012} . Tính

1 2

( , ,..., )

...

n

A A A F

A A A



  



^.

Lời giải

Với i phần tử {1,2,...,2012} ta đếm xem có bao nhiêu bộ { thỏa mãn A₁  A₂ ... A_n = { } (*)

Ta cho các phần tử đăng kí có mặt trong tập bằng cách với mỗi

phần tử ta gán cho 1 bộ số sao cho . Một

bộ đăng kí là hợp lệ nếu có ít nhất 1 số 1 (nếu không thì phần tử tương ứng không có mặt trong tập A₁  A₂ ... A_n. Với i phiếu đăng kí (ta gọi là nhóm phiếu đăng kí), ta sẽ lập được bộ . Ngược lại, với 2 nhóm phiếu đăng kí khác nhau ta sẽ có 2 bộ tập hợp ( khác nhau, do đó số bộ thỏa mãn (*) bằng số nhóm phiếu đăng kí hợp lệ. Vì phiếu đăng kí của gồm n chữ số 0 hoặc 1 và phải có ít nhất 1 số 1 nên có cách ghi phiếu cho , suy ra có nhóm phiếu đăng kí hợp lệ khác nhau. Có cách chọn i phần tử nên suy ra

(12)

1 2

( , ,..., )

...

n

A A A F

A A A



  



⁼²⁰¹² ²⁰¹² ^{(2012 1)} ²⁰¹¹

1

(2 1) 2012(2 1)2 2012(2 1)2

i n i n n n n

i

iC ^



    



^.

Nhận xét:

Bài toán này không dùng phương pháp song ánh theo nghĩa thường, ở đây sẽ

không có ánh xạ nào cả. Nguyên lý ánh xạ ở đây được dùng bằng cách, thay vì tính tổng này ta tìm cách tính một tổng khác dễ hơn và có giá trị bằng tổng đã cho. Với mỗi {1,2,...,2012} ta gọi i S là số các bộ trong F mà i thuộc hợp các phần tử của họ. Rõ ràng trong S thì i được đếm lần, do đó S=



S_i . Dễ thấy các bằng nhau và bằng (2ⁿ1)2²⁰¹¹ⁿ và tổng cần tính bằng 2012(2ⁿ1)2²⁰¹¹ⁿ.

Ví dụ 10:(Ucraina 1996)

Gọi M là số các số nguyên dương viết trong hệ thập phân có n chữ số, trong đó chỉ có n chữ số 1 và n chữ số 2 , Gọi n là số tất cả các số viết trong hệ thập phân có n chữ số, trong đó chỉ có các chữ số 1,2,3,4 và số chữ số 1 bằng số chữ số 2. Chứng minh rằng : M=N=

Lời giải

Kết luận của bài toán rõ ràng giúp ta nghĩ ngay đến việc xây dựng một song ánh từ 2 tập với nhau.

Số có n chữ số chỉ chứa các chữ số 1,2,3,4 và có số các số 1 bằng 2 như thế nào.

Ta cần tìm ra một cách để làm điều này . Đầu tiên gấp đôi số có n chữ số đó lên, nghĩa là nhân bản số đó 2 lần và viết cạnh nhau. Sau đó các chữ số 3 ở n số đầu được đổi thành số 1, chữ số 3 của n số sau được đổi thành chữ số 2, còn chữ số 4 ở n số đầu được đổi thành chữ số 2 và chữ số 3 ở n chữ số sau được đổi thành chữ số 1.

Ví dụ với A =123442. Ta thực hiện như sau:

123442→123442123442→12121221221112

Như thế ta thu được một số có đúng n số 1 và n số 2. Rõ ràng đây là một đơn ánh.

Để chứng minh đây là song ánh, ta xây dựng một ánh xạ ngược như sau: Với một số có n chữ số

1 và n chữ số 2. Ta cắt n số đầu và n số cuối rồi thực hiện phép cộng 2 số lại theo quy tắc sau: 1+1=1,2+2=2,1+2=3,2+1=4. Ta thu được một số có n chữ số được tạo thành từ 1,2,3,4 và thỏa mãn đề bài. Như vậy rõ ràng là ta chỉ ra được M=N

Tiếp theo, ta xét bài toán sau: Tìm số các số có n chữ số chỉ chứa các số 1,2,3,4 trong biểu diễn thập phân và có số 1 bằng số 2.

Bài toán này không hề đơn giản, cách giải quyết truyền thống vẫn là đếm bình thường như sau: Giả sử i là số các chữ số 1 và chữ số 2. Vậy có cách chọn vị trí cho i số 1 và i số 2 này. Ở đây rõ ràng ta cần có điều kiện của I, ta có i ≤ . Vậy còn lại n-2i vị trí trống để đặt các số 3 và 4. Vậy có cách xác định cho n- 2i vị trí còn lại.

(13)

Vậy số các số thỏa mãn là : N= ² ²

0

2

n

i i n i

n n i i

C C

  

  

 



Việc tính tổng này bằng bằng trực tiếp đại số quả là không dễ, để đơn giản ta cần phải dung đến kĩ thuật đếm bằng hai cách

Ví dụ 11: (Putnam 2002).

Cho n 1 là một số nguyên dương và là số các tập con khác rỗng của tập {1,2,...,n} sao cho trung bình cộng tất cả các phần tử của nó là một số nguyên.

Chứng minh rằng - n là một số chẵn.

Hướng dẫn.

Có n tập con 1 phần tử và các tập này đều thoả mãn điều kiện trong đầu bài. Vậy ta chỉ cần chứng minh số các tập con nhiều hơn một phần tử có tính chất đó là một số chẵn là xong. Ta hãy ghép các tập con này thành từng cặp như sau: Các tập có trung bình thuộc nó đi với một tập có trung bình không thuộc nó.

Ví dụ 12:

Có 20 người xếp thành một vòng tròn. Hỏi có bao nhiêu cách chọn ra 5 người sao cho không có hai người kề nhau được chọn.

Lời giải Ta giải các bài toán tổng quát sau

Ví dụ 12.1. Có n người xếp thành một hàng dọc. Có bao nhiêu cách chọn ra k người, sao cho không có hai người kề nhau được chọn?

Cách 1. (Phương pháp song ánh) Ta giải như ở ví dụ 1 Lời giải

Ta lần lượt đánh số thứ tự của hàng người bằng các số nguyên dương là 1,2,3,...,n.

Vậy ta sẽ đưa đề về dạng : Cho n số nguyên dương 1,2,…,n.Hỏi có bao nhiêu cách chọn k số phân biệt trong n số đã cho sao cho không có 2 số nguyên liên tiếp nào?

Một cách chọn thích hợp chính là bộ số 1 ≤ …< ≤ n thỏa mãn

tức là .

Vậy ta cần tìm số phần tử của

A={( , , ,…, 1 ≤ …< ≤ n, với

i=1,2,…,k-1}

Xét ánh xạ : = với = thì rõ

ràng ta có:

i) ≥ 1 ii)

iii)

Suy ra là phần tử của tập hợp B

B={ │ 1 ≤ …< ≤ n – k +1}

Dễ thấy f là một đơn ánh

(14)

Ngoài ra ánh xạ g = với cho

chúng ta một đơn ánh từ B vào A.Vậy

Cách 2 : (Sử dụng bài toán chia kẹo của Euler). Giả sử ta chọn được k người. Gọi là số người tính từng người đầu tiên đến trước người thứ nhất được chọn, là số người nằm giữa người thứ nhất và người thứ hai, …, là số người nằm giữa người thứ k-1 và người thứ k và +1 là số người nằm sau người thứ k đến cuối.

Khi đó ta có + + … + +1 = n – k (1) và , +1 là các số nguyên không âm, còn , …, là các số nguyên  1. Ngược lại, nếu ( , …, +1) là một nghiệm của (1) với , +1  0, , …,  1 thì ta cho tương ứng với cách chọn người thứ 1+ , 2+ + , …, k+ +…+ thì rõ ràng do (i + + …+ ) – (i-1 +

+ …+ -1) = 1 +  2 nên không có 2 người liên tiếp được chọn. Để hoàn tất lời giải bài toán, ta đặt = , +1 = +1 và = – 1 với i=2, …, k thì được

+ + … + +1 = n – 2k + 1 (2) với là các số nguyên không âm. Theo kết quả của định lý chia kẹo của Euler, ta có số nghiệm của (2) bằng Đó cũng chính là kết quả của bài toán ban đầu của chúng ta

Ví dụ 12.2. Có n người xếp thành một vòng tròn. Có bao nhiêu cách chọn ra k người, sao cho không có hai người kề nhau được chọn?

Bài toán này có thể giải bằng kết quả của bài toán trên và phương pháp « cắt đường tròn ». Giả sử n người đó được đánh số 1, 2, …, n. Ta xét các trường hợp sau : 1) Người số 1 được chọn. Khi đó người số 2 và số n không được chọn. Như vậy ta phải chọn thêm k-1 người từ 3 đến n-1 sao cho không có hai người kề nhau được chọn. Vì n-1 không kề 3 nên có thể coi đây là n-3 người xếp theo một hàng dọc.

Theo kết quả của bài toán trên, số cách chọn bằng =

2) Người số 1 không được chọn. Khi đó ta cần chọn k người từ số 2 đến n sao cho không có 2 người kề nhau được chọn. Vì 2 và n không kề nhau nên có thể coi đây là n-1 người xếp theo một hàng dọc. Theo kết quả của bài toán trên, số cách chọn bằng . Vậy đáp số của bài toán là:

=

Ví dụ 13:(Vô địch Trung Quốc - 1997)

Trong các xâu nhị phân có độ dài n, gọi an là số các xâu không chứa 3 số liên tiếp 0, 1, 0 và bn là số các xâu không chứa 4 số liên tiếp 0,0,1,1 hoặc 1,1,0,0. Chứng minh rằng bn+1 = 2an.

Lời giải

Ta gọi một xâu thuộc loại A nếu nó không chứa 3 số liên tiếp 0, 1, 0 và gọi một xâu thuộc loại B nếu nó không chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0,0.

Với mỗi xâu X = (x1, x2, ..., xn), ta xây dựng f(X) = (y1, y2, ..., yn+1) như sau:

1 k 1 2 k 1

y 0, y x x  ... x _ (mod 2)k {2, ..., n+1}. Rõ ràng X chứa 3 số liên tiếp

(15)

0, 1, 0 khi và chỉ khi f(X) chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0 tức là X thuộc loại A khi và chỉ khi f(X) thuộc B.

Vậy f là một song ánh đi từ tập các xâu loại A độ dài n đến tập các xâu loại B độ dài n+1 mà bắt đầu bằng 0. Nhưng từ mỗi xâu X thuộc B ta nhận được một xâu X cũng thuộc B bằng cách đổi các phần tử của X theo quy tắc 1  0, 0  1 nên số các xâu loại B độ dài n+1 gấp đôi số các xâu loại B độ dài n+1 mà bắt đầu bằng số 0. Từ đó ta có điều phải chứng minh.

Ví dụ 14:(Vô địch Ucraina - 1996)

Gọi M là số các số nguyên dương viết trong hệ thập phân có 2n chữ số, trong đó có n chữ số 1 và n chữ số 2. Gọi N là số tất cả các số viết trong hệ thập phân có n chữ số, trong đó chỉ có các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2.

Chứng minh rằng M = N = C₂ⁿ_n.

Lời giải

Hiển nhiên M = C₂ⁿ_n. Ta chỉ cần chứng minh M = N.

Với mỗi số có n chữ số gồm các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2, ta “nhân đôi” thành số có 2n chữ số theo quy tắc sau: đầu tiên, hai phiên bản của số này được viết kề nhau thành số có hai chữ số, sau đó các chữ số 3 ở n chữ số đầu và các chữ số 4 ở n chữ số sau được đổi thành chữ số 1, các chữ số 3 ở n chữ số sau và các chữ số 4 ở n chữ số đầu được đổi thành chữ số 2. Ví dụ:

12341421234142123414212121221221112.

Như thế, ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh từ tập các số n chữ số sang tập các số 2n chữ số. Để chứng minh đây là một song ánh, ta xây dựng ánh xạ ngược như sau: với mỗi số có n chữ số 1 và n chữ số 2, ta cắt n chữ số đầu và n chữ số cuối rồi cộng chúng theo cột với quy tắc:

1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được một số có n chữ số gồm các chữ số 1, 2, 3, 4 với số chữ số 1 bằng số các số 2.

Ví dụ 12121221221112 

1234142 1221112 1212122

 1234142.

Ví dụ 15: (IMO - 2005)

Cho các số nguyên dương n, k với n  k.

Xét phép toán f đối với bộ sắp thứ tự X = [x1, ..., xn] như sau: mỗi lần chọn k số liên tiếp tuỳ ý trong X và đổi dấu của chúng.

Tìm số các bộ thứ tự X =[x1, ..., xn] thoả mãn các điều kiện:

(i) Mọi phần tử của X đều thuộc tập {-1,1}.

(ii) Có thể thực hiện hữu hạn lần phép toán f để từ X nhận được bộ [1,1,...,1].

Lời giải

Xét bộ thứ tự X = [x1, ..., xn] tuỳ ý. Ta có hai nhận xét sau:

1) Có đúng n  k + 1 nhóm k số liên tiếp.

(16)

2) Sau một số chẵn lần thực hiện phép toán f cho một nhóm k số liên tiếp trong X thì giá trị k số đó không đổi.

Như vậy, mỗi phương án thực hiện hữu hạn lần phép toán f đối với X tương ứng với một bộ nhị phân A = [a1, a2, ..., an-k+1], trong đó ai tính theo modun 2 của số lần thực hiện f cho nhóm k số liên tiếp [xi, xi+1, ..., xi+k-1], và X trở thành



n



a n a a k

a a a k a a a a

a

a¹x,( 1)¹ ²x ,...,( 1)¹ ² ^kx,( 1)² ^k ^k¹x ,...,( 1)ⁿ^k ⁿ^k¹x ,( 1)ⁿ^k¹x )

1

( ₁  ^ ₂  ^ ^^...^  ^^...^ ^ ^ _₁  ^^ ^^ _₁  ^^

Từ đó, dễ thấy mỗi bộ A xác định duy nhất một bộ X thoả điều kiện bài toán nên đáp số bài toán chính là số các bộ A, tức là 2^{n k 1}^{ } .

Ví dụ 16:

Cho đa giác đều có 103 cạnh. Tô màu đỏ cho 79 đỉnh của đa giác và tô màu xanh cho các đỉnh còn lại. Gọi A là số cặp đỉnh đỏ kề nhau và B là số cặp đỉnh xanh kề nhau.

a. Tìm tất cả các giá trị có thể nhận được của cặp (A,B)

b. xác định số cách tô màu các đỉnh của đa giác để B =14 . Biết rằng, hai cách tô màu được xem là như nhau nếu chúng có thể nhận được từ nhau thông qua 1 phép quay quanh tâm đường tròn ngoại tiếp đa giác.

Hướng dẫn:

a. Số đỉnh màu xanh là 24 đỉnh (103-79). N ếu tất cả các đỉnh đỏ chia thành một cụm thì A=78. N ếu bị cắt thành 2 cụm thì A=77. Và cứ thế tiếp tục, tức là nếu có k cụm (mỗi cụm là các đỉnh cùng màu đỏ đứng sát nhau) thì A=74-k . N ếu có k cụm đỏ thì cũng có k cụm xanh nên có B= k-24. Các giá trị có thể của k là từ 1 đến 24, nên có 24 khả năng tất cả

b. Để có B=14 thì k = 10 (phải chia quân xanh thành 10 cụm, quân đỏ thành 10 cụm). Đếm số cách chia như thế nào ?

Gọi X là số cụm các điểm đỏ liền nhau, thì B=24-X. Do vậy B=24 thì X = 10 . Áp dụng công thức chia kẹo của pt chia kẹo, ta suy ra được số cách chia 24 điểm xanh vào 10 cụm là . Tiếp theo, ta sẽ xem xét việc xếp các điểm xanh- đỏ như là vệc có sẵn 79 điểm đỏ ở trên đường tròn, và ta bỏ đi 10 cụm điểm xanh và các khoảng trống giữa 2 điểm đỏ liên tiếp, mỗi khoảng có tối đa 1 cụm. Như vậy thì số cách chọn ra 10 khoảng trống trong 79 khoảng là . Sự trùng lặp theo phép quay là ở chỗ ta chọn 10 vị trí trong 79 vị trí theo đường tròn. Nhờ có (79,10)=1 mà ta không phải lo về “các cấu hình lộn xộn”, mỗi cách tô bị lặp đúng 79 lần, do vậy đáp số là

Định lý :

Cho A và B là 2 tập hợp hữu hạn, và f là 1 ánh xạ đơn ánh từ A vào B. Khi đó số phần tử của B ít nhất là bằng số phần tử của A. Và nếu f là song ánh thì A và B có cùng số phần tử

Ví dụ 17:

(17)

Với mỗi đỉnh của đa giác đều 9 đỉnh (cửu giác) được tô bởi màu đỏ hoặc xanh da trời. Chứng minh rằng tồn tại 2 tam giác đơn sắc đồng dạng , trong đó tam giác đơn sắc là tam giác có tất cả các đỉnh là cùng 1 màu

Lời giải

Ta gọi đơn giác đỏ (xanh) nếu tất các đỉnh của tam giác là đỏ hoặc xanh. Vì đa giác có 9 đỉnh, mỗi đỉnh chỉ tô 2 màu xanh hoặc đỏ nên có ít nhất 5 đỉnh có dùng 1 màu. Không mất tính tổng quát, giả sử đó là màu đỏ. Suy ra có it nhất = 10 đơn giác đỏ. Giờ ta chứng minh có 2

tam giác đỏ đồng dạng.

Đặt là các đỉnh của đa giác (Hình 1) và ω là đường tròn ngoại tiếp đa giác. 9 đỉnh đa giác chia đường tròn này thành 9 cung bằng nhau. Gọi mỗi cung trong 9 cung này là 1 mảnh. Gọi

là tam giác thỏa mãn . Định nghĩa là số mảnh của cung

không chứa điểm . Ta định nghĩa tương tự với và

. Khi đó Δ được xác định bởi bộ ba ( , . Do 1 tam giác có 3 đỉnh, nên ta dễ

thấy

(trường hợp góc lớn nhất là 3

đỉnh nằm kề nhau trên đường tròn). , do đó

. Ví dụ với tam giác Δ ta xác định được bộ ba tương ứng là (2,3,4).

Dễ thấy các tam giác đồng dạng cho cùng 1 bộ ba, trong khi 2 tam giác không đồng dạng có các bộ ba khác nhau. Từ đó ta xây dựng song ánh A →B như sau: A:

tập các tam giác đồng dạng B: tập các số tự nhiên a, b, c thỏa mãn

và a+b+c=9. Ta có thể liệt kê ra các phần tử của B là (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4), (3,3,3) có tất cả 7 phần tử. Suy ra A cũng có 7 phần tử hay có tất cả 7 dạng tam giác khác nhau. Trong khi đó ta có 10 tam giác đơn sắc, nên tồn tại ít nhất 2 tam giác đơn sắc đồng dạng.

Ví dụ 18:

Cho n nguyên dương. Hỏi có bao nhiêu các biểu diễn n thành tổng của ít nhất 2 số nguyên dương.

(18)

(Ví dụ có 3 cách biểu diễn số 3 thành tổng của các số nguyên dương:

3=1+1+1=1+2=2+1)

Lời giải

Ta viết n dưới dạng sau: (1_1_..._1) gồm n số 1. Xét n-1 khoảng trống trong đó là , khi đó các khoảng trống sẽ có 2 trạng thái là 0 hoặc 1. N ếu trạng thái là 0, thì ta sẽ thay khoảng trống bởi dấu “+”, nếu trạng thái là 1 thì thay bởi “)+(“.

Ví dụ như 4=(1_1_1_1)= ( . Khi đó nếu ( = (0,0,1) thì 4=(1+1+1)+(1)=3+1 là một cách biểu diễn.

Ta có tất cả cách biểu diễn cho dãy nhị phân (n-1) bit và mỗi dãy nhị phân cho một cách biểu diễn duy nhất của n. Trong dãy nhị phân này, chỉ có trường hợp duy nhất là dãy 00…0 là không biểu diễn dưới dạng tổng của ít nhất 2 số. Do đó có cách biểu diễn n dưới dạng tổng của ít nhất 2 số nguyên dương

Ví dụ 19: [AHSME 1992]:

Cho 10 điểm đặt trên phần dương trục x( ), 5 điểm đặt trên phần dương trục y ( ). Khi đó ta có tất cả 50 đoạn thẳng nối giữa 10 điểm trên với 5 điểm trên trục . Khi đó có tối đa bao nhiêu giao điểm của 50 đoạn thẳng nằm trong góc phần tư thứ nhất? (Hình 2)

Lời giải

Ta có, cứ 2 điểm trên và 2 điểm trên thì tạo thành 1 tứ giác và khi đó chỉ xác định được duy nhất 1 giao điểm. Khi đó số giao điểm lớn nhất có thể tạo

được là . Dấu bằng xảy ra ⇔

không có 3 đường nào cùng cắt nhau tại một điểm trong góc phần tư thứ nhất

Ví dụ 20: [China 1991, by Weichao Wu]:

Cho n là số tự nhiên với n≥ 2 , và đặt dãy S =(1,2,3,…,n) . Một dãy con của S được gọi là dãy con số học nếu nó có ít nhất 2 phần tử và nó là 1 cấp số cộng. Dãy con số học được gọi là cực đại nếu dãy này không thể kéo dài bằng cách thêm vào một phần tử khác của S. Xác định số dãy con số học cực đại

Lời giải

Ta có công sai phải lớn hơn để không thể điền thêm phần tử nào vào bên trái dãy con ( phía trước ), nên ≥ 2 . Lại có ≤ 2m nên ≤ m. Khi đó để một dãy con là cực đại thì và 2 (1). Ta cũng có, với

(19)

mỗi bộ ( thỏa mãn điều kiện trên thì cũng cho ra duy nhất 1 dãy con cực đại có phần tử ban đầu và công sai . Suy ra dãy số con cực đại và bộ

( thỏa mãn đk (1) là song ánh. Ta có, với mỗi cách chọn thì có

cách chọn . Do có m cách chọn nên số bộ ( thỏa mãn đk (1)

là:

1

2 2 2

1

2 ( 1)

( 2 1) 2

2

m

a

n a  mn m m  m m m m



1

2 2

1

2 ( 1)

( 2 1) (2 1)

2

m

a

n a  mn m m  m m m m m m



Vậy có 2 m dãy con cực đại với n=2m

Xét với n=2m+1, với m là số nguyên dương. Tương tự ta có: ≥ 2 , suy ra ≤ m . Lý luận tương tự, ta có số dãy con cực đại là:

1

2 2

1

2 ( 1)

( 2 1) (2 1)

2

m

a

n a  mn m m  m m m m m m



1

2 2

1

2 ( 1)

( 2 1) (2 1)

2

m

a

n a  mn m m  m m m m m m



Vậy, với mỗi số tự nhiên n, ta có dãy con số học cực đại .

Song ánh có thể được sử dụng giữa các tập hợp mà các tập hợp này không cần hữu hạn. Dưới đây là 1 ví dụ.

Ví dụ 21: [PEA Math Materials]

Giả sử rằng có 2 quản trị PEA, là những người duy nhất có quyền quay số truy cập vào tệp tài liệu Internet của học viện, biết rằng tại một thời điểm tệp này chỉ xử lý cho một yêu cầu truy cập. Với 15 phút sử dụng tệp cho 1 lần truy cập và tệp chỉ được sử dụng từ 4h chiều đến 6 giờ chiều trong ngày. Biết rằng không có yêu cầu truy cập nào được thực hiện sau 5h45 chiều, và 1 người không được yêu cầu truy cập quá 1 lần. Ít nhất 1 người trong số họ thực hiện thành công cuộc gọi. Hỏi xác suất là bao nhiêu để cả 2 người đều có thể thực hiện thành công cuộc gọi của mình?

Lời giải

Gọi An và Giang là 2 quản trị của PEA. Ta biết rằng yêu cầu truy cập vào tệp internet của học viện chỉ được thực hiện trong 105 phút. Giả sử An gọi sau 4h x phút, Giang gọi sau 4h y phút, khi đó ta có thể ánh xạ bộ thời gian gọi của 2 người tới điểm (x,y) trên mp tọa độ (Hình 3). Rõ ràng đây là một song ánh.

(20)

Lê Ngọc Đức – 10CT – Trường THPT Chuyên Nguyễn Du Tập hợp các điểm (x,y) là hình vuông

O . Rõ ràng một người không thể gửi yêu cầu truy cập thành công nếu người còn lại đang làm việc với tệp, do đó để cả 2 người có thể đều truy cập được tệp tài liệu thì ta phải có . Xét miền của tập hợp các điểm (x,y) được xác định bởi

. Đây là giao của 2 phương trình đường thẳng với hình vuông, cắt tại các điểm Ta xác định được

=(0,15), =(90,105), =(15,0),

=(105,90). Từ đó, xác suất để cả 2 người cùng truy cập được vào tệp là:

Hệ quả :

Cho 2 số nguyên dương m và n

a. Có bộ nguyên dương ( ) thỏa mãn phương trình

b. Có bộ nguyên không âm ( ) thỏa mãn phương trình

Ví dụ 22: [Aime 2000]:

Cho 8 chiếc nhẫn khác nhau, tìm số cách xếp 5 chiếc nhẫn xếp trên 4 ngón tay (không tính ngón cái) trên một bàn tay. Biết rằng thứ tự từng chiếc nhẫn trên một ngón tay là quan trọng và không bắt buộc ngón nào cũng phải có nhẫn.

Lời giải

Ta có cách chọn ra 5 chiếc nhẫn bất kỳ để đeo trong 8 chiếc nhẫn đã cho. Đăt a, b, c, d là số chiếc nhẫn trên từng ngón tay. Ta có a+b+c+d=5. Theo Hệ quả 1 ta có

cách sắp xếp các chiếc nhẫn vào 4 ngón tay (giả thiết là các chiếc nhẫn ko phân biệt). Lại có với mỗi cách sắp xếp 5 chiếc nhẫn ko phân biệt thì tương ứng có 5!

cách sắp xếp đối với 5 chiếc nhẫn phân biệt.

Vậy ta có số cách sắp xếp là: .

Ví dụ 23:

Ngân hàng Bảo Hiểm của nước cộng hòa Fatand có 15 nhân viên điều hành cấp cao. Mỗi nhân viên này có 1 thẻ truy cập vào kho của ngân hàng và trên mỗi thẻ bất kỳ đều có 1 bảng gồm m mã hóa khác nhau. Để mở được kho, mỗi người sẽ đặt thẻ của mình vào khóa điện tử của kho. Máy tính sẽ thu thập tất cả các mã khác nhau trên thẻ và hầm sẽ được mở khi và chỉ khi tập các mã hóa có n mã hóa

(21)

(khác nhau) đặt trước. Vì lý do bảo mật, hầm có thể được mở nếu và chỉ nếu có ít nhất thẻ của 6 nhân viên cao cấp. Tìm n và m thỏa mãn n nhỏ nhất để có thể thực hiện được chính sách bảo mật nêu như trên.

Lời giải

Dễ thấy với mỗi một nhóm gồm 5 nhân viên cao cấp thì sẽ thiếu ít nhất 1 mã hóa so với n mã hóa đặt trước để mở được hầm. Đặt A là tập hợp các nhóm có 5 nhân viên và B là tập hợp gồm n mã hóa cần để mở hầm. Xét ánh xạ từ A vào 1 trong các mã hóa có thể thiếu trong nhóm 5 người (số mã hóa thiếu có thể nhiều hơn 1, nhưng chỉ xét ánh xạ 1-1 để dễ thực hiện). Gọi ánh xạ này là f, ta sẽ chứng minh nó là đơn ánh. Thật vậy, gọi ∈ A là 2 nhóm khác nhau thỏa

mãn , c là mã còn thiếu. Do khác nên tồn tại nhóm 6 người lấy từ 2 nhóm và mà vẫn thiếu ít nhất 1 mã (mã c), (vô lý so với giả thiết). Vậy f là đơn ánh. Rõ ràng f là ánh xạ từ A vào B nên ta có:

Ta sẽ chứng minh n=3003 thỏa mãn. Khi đó cho mỗi nhóm 5 người 1 nhận được 1 mã c(a) khác nhau trong 3003 mã cho trước (điều này có thể thực hiện được vì ta có tất cả 3003 nhóm). Tiếp theo ta viết mỗi mã c(a) này vào thẻ của các thành viên không nằm trong nhóm . Khi đó, mỗi mã sẽ được viết cho 10 người không trong nhóm, suy ra ta viết tất cả 10. các mã, đồng thời được chia đều cho 15 người nên thẻ mỗi người sẽ có mã khác nhau.

Xét một nhóm gồm 6 người bất kỳ. Theo như cách sắp xếp mã như trên, với nhóm a gồm 5 người bất kỳ sẽ chỉ thiếu duy nhất một mã c(a). Ta sẽ chứng minh nhóm 6 người có đủ n mã khác nhau. Thật vậy, xét 2 nhóm 5 người bất kỳ và từ 6 người được chọn.

Khi đó ta có . Ta sẽ chứng minh rằng nhóm có mã c( ). Giả sử trong không có mã c( ), khi đó theo định nghĩa hàm c như ban đầu, ta có (vô lý). Vậy một nhóm 6 người sẽ có đủ mã để mở kho, hay m=2002

Kết luận: n=3003, m=2002

Ví dụ 24: [AIME 2001, by Richard Parris]:

Cho các số 1,2,3,4,5,6,7,8 được điền bất kỳ lên mặt của 1 bát phương sao cho mỗi một mặt là 1 số khác nhau. Tính xác suất để không có 2 số liên tiếp nào (8 và 1 cũng được cho 2 số liên tiếp) được viết trên 2 mặt có chung cạnh.

Lời giải

(22)

Để giải bài toán, ta xét thêm hình lập phương có các đỉnh là A,B,C,D,E,F,G, H như ở Hình 5, trong đó đỉnh hình lập phương là các trọng tâm các mặt của bát phương.

Khi đó ta sẽ kí hiệu như sau: các số 1,2,3,4,5,6,7,8 thứ tự tương ứng lần lượt là các đỉnh A,B,C,D,E,F,G,H. Cạnh của lập phương nối 2 đỉnh lập phương( nối 2 số) thể hiện mối liên hệ (chung cạnh) giữa 2 mặt bát phương. Ta thấy rõ ràng liên hệ này là 1-1. Khi đó thay vì đếm số trường hợp không có 2 số liên tiếp trên cùng một mặt, ta đếm số cách điền các đỉnh của hình lập phương để không có 2 đỉnh liền kề nào là lập thành 1 cạnh lập phương. Ta chia các đỉnh thành 2 nhóm,

và . Dễ thấy các đỉnh trong cùng 1 nhóm thì không liền kề với nhau.

Ví dụ 25:

Cho 1 lưới tam giác có chiều dài mỗi cạnh bên là n, được phủ bởi tam giác con đều có cạnh bằng 1. Xác định có bao nhiêu hình bình hành bị giới hạn bởi các đoạn thẳng của lưới.

Lời giải

Ta chia tất cả các hình bình hành thành 3 tập.

Có các cạnh của 1 hình bình hành bất kỳ phải song song với đúng 2 cạnh của tam giác. Gọi

là tập các hình bình hành có cạnh song song với 2 cạnh XY và ZX của tam giác. Các tập và xác định tương tự. Do tính đối xứng nên ta có

. Từ đó, đáp án của ta sẽ là 3 . Mở rộng các cạnh XY và XZ về phí Y và Z thêm 1 đơn vị, ta được các đoạn thẳng mới là XY’ và XZ’. Xét một hình bình hành bất kỳ thuộc , ta kéo dài các cạnh của hbh

đó, cắt đoạn thẳng Y’Z’ tại 4 điểm phân biệt (hiển nhiên). Từ đây ta xác định được rằng, cứ 4 điểm phân biệt trên đoạn thẳng Y’Z’ vẽ song song với XY và ZX, cắt nhau tại 4 điểm sẽ tạo được 1 hình bình hành thuộc . Vậy ta có ánh xạ từ ra bộ 4 điểm trên đoạn Y’Z’ là 1 song ánh, mà đoạn Y’Z’ có tất cả n+2 điểm, nên ta có . Vậy có tất cả 3 . Hình bình hành bị giới hạn bởi các cạnh của tam giác.

Ví dụ 26:

Bart hiện là nhân viên của rạp chiếu phim. Rạp này có sức chứa 200 chỗ ngồi.

Trong ngày khởi chiếu phần I Star War: The Phantom Menace, có 200 người đứng xếp hàng để mua vé xem phim. Giá mỗi vé là 5$. Trong 200 người mua vé, 100 trong số họ có hóa đơn loại 5$, nửa còn lại là hóa đơn loại 10$(mỗi người có 1

(23)

hóa đơn). Bart vốn bất cNn và vẫn không chịu thay đổi. 200 người đó xếp hàng 1 cách ngẫu nhiên và không ai muốn chờ để thay đổi vé của mình khi họ mua vé. Xác suất là bao nhiêu để Bart có thể bán được hết tất cả các vé có lợi nhất (thành công)

Lời giải

Để dễ dàng hơn ta thay 100 bằng n. Ta xem xét những người là không phâ biệt được. Ta cân nhắc sự sắp xếp của n người sở hữu hóa đơn 5$ và n người sở hữu hóa đơn 10$ (nói cách khác ta làm phép nhân lên tới cả hai mẫu số và tử số, việc này không ảnh hưởng tới giá trị của xác suất). Có cách sắp xếp xác số mà không hạn chế. Bart sẽ thành công khi và chi khi: ta sắp xếp 2n số vào một hàng ngang và đánh số vị trí của chúng từ trái qua phải từ 1,2,3,...,2n. Với , đặt là số người có hóa đơn 5$ (10$) đứng trước vị trí thứ i. Ta cần đếm số sự sắp xếp thỏa mãn với . Gọi S là tập hợp tất cả các sắp xếp như vậy. Gọi T là tập hợp các sự sắp xếp khác nhau như trên. Ta sẽ tìm .

Ta có Một phần tử t ∈ T , có số , thỏa

mãn . Gọi là ký hiệu của số chỉ đầu tiên. Bởi sự xác đinh cả ta,

và . Vì vậy có nhiều hơn số hóa đơn 10$ so với 5$ tính đến (tại) thời điểm thứ . Ta thay đổi toàn bộ các đồng 5$ thành 10$ và các đồng 10$ thành 5$ sau thời điểm thứ , thì khi đó ta thu được một hoán vị của n+1 đồng 10$ và n−1 đồng 5$ .

Ví dụ: với n=6 ta có: t = ( 5,10,10,5,10,10,10,5,10,5,5,5) Ta có

( (1,1,1,2,2,2,2,3,3,4,5,6) ( (0,1,2,2,3,4,5,5,6,6,6,6) f(t) = 3,

= (5,10,10,10,5,5,5,10,5,10,10,10)

Do đó ta xác định một ánh xạ từ T vào U là tập hợp hoán vị của n+1 đồng 10$ và n−1 đồng 5$. Ta sẽ chứng minh g là một song ánh

Đầu tiên ta chứng minh g là một toàn ánh. Xét u là một phần tử bất kỳ thuộc U. Ta đếm số lần xuất hiện của đồng 5$ và 10$ tính từ trái qua phải với i là các giá trị nguyên nhỏ nhất sao cho tính đến thời điểm thứ i số đồng 10$ là nhiều hơn số đồng 5$. Ta thay đổi toàn bộ các đồng 5$ thành 10$ và toàn bộ các đồng 10$ thành 5$

sau thời điểm thứ i. Vì số đồng 10$ có số lượng lớn hơn 2 so với số đồng 5$ trong U nên sẽ có số đồng 10$ nhiều hơn số đồng 5$ tại trước thời điểm i và số đồng 10$

nhiều hơn số đồng 5$ tại 2ni − thời điểm còn lại. Sau bước đổi 5 → 10 và 10 → 5 trên ta thu được số đồng 5$ và 10$ bằng nhau. Không khó để thấy dãy mới này thuộc T, do đó g là một toàn ánh. Bây giờ ta chứng minh g là đơn ánh. Xét t và ' t là 2 phần tử thuộc T. Giả sử rằng tại thời điểm thứ , là thời điểm đầu tiên t và ' t có sự khác nhau. Không giảm tính tổng quát g/s và , thì

(24)

. Nếu thì = bởi 1 i− vị trí đầu của t và ' t là hoàn toàn giống nhau. Khi đó tại thời điểm thứ i, g(t) và g(t') có giá trị là 10 và 5 tương ứng, do đó

. Ta lại xét . Thì tại thời điểm thứ i của g(t) là , có . Bởi vì ( i-1) vị trí đầu của t và t’ như nhau, . Dô đó tại thời điểm thứ i của g(t') là t’ , nó bằng 10. Do đó . Suy ra g là song ánh. Từ đó theo ta có:

Trở lại bài toán, ta có n = 200 , vậy xác suất là Ví dụ 27:

Cho n là số nguyên dương thỏa mãn các tính chất: nếu n cái domino được đặt trên 1 bàn cờ 6x6 với mỗi domino chiếm 2 đơn vị diện tích vuông, thì luôn luôn có thể đặt thêm 1 domino lên trên bàn mà không phải di chuyển bất kỳ domino nào khác.

Xác định giá trị lớn nhất của n.

Lời giải

Ta sẽ chứng minh giá trị lớn nhất của n là 11. Hình 7 là cách sắp xếp 12 domino trên bàn cờ thì không thể để thêm 1 domino nào nữa. Suy ra n≤ 11.

Ta sẽ chứng minh rằng với 11 domino trên bàn cờ thì luôn đặt thêm được 1 domino nữa.

Ta sẽ chứng minh bằng phản chứng. Giả sử rằng tồn tại cách đặt 11 domino trên bàn cờ mà không thể đặt thêm 1 domino nào nữa.

Khi đó số ô vuông trên bàn chưa bị phủ bởi 11 domino là: 36-22=14.

(25)

Đặt là phần trên của bàn cở ban đầu có kích thước 5x6 (Hình 8). Đặt A là tập các ô vuông trong mà không bị phủ bởi các domino, và là hàng cuối của bàn cờ (bàn cờ chia làm 2 phần và ). Vì ta không thể điền thêm 1 domino nào vào bàn cờ, nên một trong 2 ô vuông bất kỳ cạnh nhau sẽ được bao phủ bởi 1 domino, suy ra có nhiều nhất là 3 ô không bị phủ bởi domino (trống), suy ra có ít nhất

là 14-3=11 ô trống.

Đặt là phần dưới của bàn cờ và có kích thước 5x6 (Hình 8), B là tập tất cả các domino nằm trong . Ta sẽ định nghĩa một ánh xạ f từ A vào B. Ta có, với mỗi ô vuông trống s trong , sẽ tồn tại một ô vuông t nằm dưới s. Suy ra ô vuông t nằm trong và được phủ bởi một domino d. Rõ ràng domino d phải nằm trong (vì nếu ko thuộc thì nó sẽ gồm 2 ô t và s-vô lý). Khi đó ta xác định ánh xạ f là f(s) = d . Ta sẽ chứng minh rằng f là đơn ánh. Thật vậy, giả sử sao cho

. Suy ra d phủ 2 ô vuông ở dưới và . Suy ra và nằm cạnh nhau (Hình 9), như vậy khi đó ta có thể đặt thêm 1 domino phủ lên và (vô lý). Vậy f là đơn ánh, suy ra hay . Nhưng cả bàn cờ chỉ có 11 domino, suy ra =11 . Khi đó thì hàng trên cùng sẽ không bị phủ bởi 1

domino nào, và sẽ đặt được thêm 1 quân domino nữa (vô lý).

Vậy giá trị lớn nhất của n là 11.

Ví dụ 28: [China 2000, by Jiangang Yao]:

Cho số nguyên dương n và xác định Hỏi có

bao nhiêu ánh xạ f xác định trên M thỏa mãn i. là số tự nhiên với mọi (x,y)∈ M ii.

1

( , ) 1

n

x

x y n





  với mọi x thỏa mãn .

iii. N ếu > thì (

Lời giải

(26)

Có kết luận giá trị của hàm f . Ta coi một hàm f trên M như một ma trận với n hàng và n cột sao cho Điều kiện i,ii,iii trở thành i’. tất cả các thành phần của f M là các số tự nhiên

ii’. tổng của tất cả các thành phần của theo hàng ngang bằng n−1

iii’. tất cả các thành phần (nhập vào) của có thể đi theo 1 lối đi từ thành phần (nhập vào) trên cùng bên trái tới thành phần bên phải dưới bằng các bước dịch chuyển xuống hoặc sang phải một đơn vị mỗi lần. Điều đó là đúng vì nếu

và thì j ≤ k vì và hơn thế nữa mỗi

đường đi thỏa mãn xác định duy nhất một ma trận nếu đường đi đó đòi hỏi phải đi qua (xuống) tới nếu và với

Ta gọi ma trận thỏa mãn i’, ii’, iii’ là ma trận tốt. Rõ ràng có một song ánh giữa tập hợp tất cả các hàm thỏa mãn điều kiện bài toán với tập các ma trận tốt. Ta cần đếm tất cả các ma trận tốt. Do đó ta xét bài toán khác sau: Một công viên bị chia thành một lưới n × n các hình vuông đơn vị. Người làm vườn của công viên phải trồng n−1 cây vào mỗi hàng ngang của lưới. Anh ấy có thể trồng bất kỳ chiếc cây nào (các cây không phân biệt) vào một ô vuông. Và anh ta có thể trồng nhiều hơn 1 cây vào ô vuông . Anh ta làm việc trồng cây bắt đầu từ góc tây bắc( trên cùng bên trái) của công viên xuống góc đông nam (dưới cùng bên phải) của công viên. Anh ta trồng một hàng cây tại một thời điểm và khi hoàn thành 1 hàng, anh ta tự chuyển xuống hàng ngang phía dưới ( phía nam). Người làm vườn có 3 trạng thái

1. trồng 1 cây ở hình vuông anh ta đang đứng 2. chuyển tới một hình vuông ở phía đông (phải)

3. tự động xuống dưới (phía nam) nếu anh ta trồng đủ n−1 cây ở hàng anh ta đang đứng (trừ hàng cuối).

Chúng ta không phải lo lắng ở trường hợp (3) vì người làm vườn luôn cẩn thận đếm số cây đã trồng trong 1 hàng và chỉ chuyển xuống hàng tiếp theo nếu đã trồng đủ ( n-1) cây ở hàng đang đứng. Anh ta trồng ( n-1) cây ở mỗi hàng ngang nếu tổng số cây đã trồng là n(n-1) cây. Do đó anh ta thực hiện n(n-1) trạng thái loại (1).

Với trường hợp chuyển vị trí xuống góc dưới cùng phía bên phải anh ta phải thực hiện ( n-1) trạng thái loại (2). Và do đó anh ta có tất cả n(n-1)+n-1= trạng thái. Vì anh ta có thể biểu diễn trạng thái theo ý muốn nên số cách anh ta thực hiện công việc là (do phải trồng n−1 cây). Không khó để thấy rằng có sự tương ứng một-một giữa các ma trận tốt và số cách trồng của người làm vườn. Ví dụ với n=4 , nếu 1 và e là ký hiệu tương ứng cho trạng thái (1) và (2) thì coi dãy

11ee11111111e11,e1111111111e1e1,11111111e11e11e tương ứng với các hình vẽ sau:

(27)

Và có 3 ma trận tương ứng là

2 0 1 0 0 0 3 0 0 0 3 0 0 0 1 0

 

 

 

và

0 3 0 0 0 3 0 0 0 3 0 0 0 1 1 1

 

 

 

. Do đó số ma trận

bằng số các hàm số f và cùng bằng