Hai bạn Phúc và Ngân đi vắt sữa bò chung, sau khi vắt được đổ đầy bình 10 lít thì sau đó các bạn muốn chia đôi số sữa, nhưng các bạn chỉ có thêm hai bình 3 lít và 7 lít. Hai bạn đang loay hoay không biết chia thế nào, các bạn có thể giúp hai bạn được không?
Ví dụ 1: Giá của một chiếc máy tính bảng sau khi sử dụng $t$ năm được cho bởi công thức:
$T\left( t\right) =10000000-1250000t$ (đồng)
a) Hãy tính $T\left( 2\right) $ và cho biết $T\left( t\right) $ có nghĩa là gì?
b) Sau bao nhiêu năm thì giá trị của chiếc máy tính bảng là $5000000$ đồng.
Ví dụ 2: Một hình chữ nhật có hai kích thước là $20$ cm và $30$ cm. Gọi $y$ (cm) là chu vi hình chữ nhật sau khi đã giảm mỗi kích thước $x$ (cm).
a) Lập hàm số của $y$ theo $x$.
b) Hãy cho biết hàm số thiết lập ở câu a) là hàm số đồng biến hay nghịch biến.
c) Tính chu vi hình chữ nhật sau khi đã giảm mỗi kích thước $3$ cm.
Bài tập: Bài 1: Diện tích rừng nhiệt đới trên Trái Đất được cho bởi hàm số $A=718,3-4,6t$ trong đó $A$ tính bằng triệu héc-ta, $t$ tính bằng số năm kể từ năm $1990$. Hãy tính diện tích rằng nhiệt đới vào các năm $1990$ và $2000$. Bài 2: Bạn An hiện có số tiền là $32000$ đồng, bạn định sử dụng số tiền này để chơi game, mối giờ bạn chơi tốn $5000$ đồng. Gọi $t$ là số giờ chơi game của bạn An và $T$ là số tiền còn lại. a) Lập hàm số của $T$ theo $t$. b) Sau khi chơi $3$ giờ thì số tiền An còn lại là bao nhiêu? c) Với số tiền ban đầu thì An chơi tối đa được bao nhiêu giờ (chỉ tính tiền theo giờ không được đóng lẻ theo phút). Bài 3: Bảng giá cước gọi quốc tế của công ty viễn thông A được cho bởi bảng sau: Giá cước điện thoại (đồng/phút) Không quá $8$ phút $6500$ Từ phút thứ $9$ đến phút thứ $15$ $6000$ Từ phút thứ $16$ đến phút thứ $25$ $5500$ Từ phút thứ $26$ trở đi $5000$ a) Gọi $T$ (đồng) là số tiền khách hàng phải trả khi gọi quốc tế trong $t$ (phút). Lập hàm số của $T$ theo $t$. b) Bà Lan gọi cho người thân ở nước ngoài tốn tổng cộng $174000$ đồng. Hãy tính số phút bà Lan gọi điện cho người thân bên nước ngoài? Bài 4: Trong một xưởng sản xuất đồ gia dụng có tổng cộng $900$ thùng hàng và mỗi ngày nhân viên sẽ lấy $30$ thùng hàng để đi phân phối cho các đại lí. a) Gọi $y$ là số thùng hàng còn lại trong kho sau $x$ ngày. Hãy lập hàm số $y$ theo $x$. b) Sau bao nhiêu ngày thì xưởng sẽ vận chuyển hết được $900$ thùng hàng? c) Biết rằng một thùng hàng có giá trị là $2000000$ đồng và mỗi chuyến xe vận chuyển $30$ thùng hàng trong mỗi ngày sẽ tốn $2500000$ đồng. Hỏi sau khi bán hết tất cả thùng hàng thì xưởng sẽ lời bao nhiêu tiền? Bài 5: Một xí nghiệp may cứ mỗi tháng thì phải trả tiền lương cho công nhân viên, tiền vật liệu, tiền điện, tiền thuế,… tổng cộng là $410000000$ (đồng). Mỗi chiếc áo được bán với giá là $350000$ (đồng). Gọi số tiền lời (hoặc lỗ) mà xí nghiệp thu được mỗi tháng là $L$ (đồng) và mỗi tháng xí nghiệp sản xuất được $A$ chiếc áo. a) Lập hàm số của $L$ theo $A$. b) Nếu trong một tháng công ty bán được $1000$ chiếc áo thì công ty lời hay lỗ bao nhiêu? c) Mỗi tháng phải sản xuất ít nhất bao nhiêu chiếc áo để xí nghiệp không bị lỗ? d) Hỏi cần phải sản xuất trung bình bao nhiêu chiếc áo mỗi tháng để sau một năm xí nghiệp thu được tiền lời là $1380000000$ (đồng). Bài 6: Một cửa hàng sách cũ có chính sách như sau: nếu khách hàng đăng kí làm hội viên của cửa hàng sách thì mỗi năm phải đóng $50000$ (đồng) chi phí và chỉ phải mướn sách với giá $5000$ (đồng/cuốn sách), còn nếu khách hàng không phải hội viên thì sẽ mướn sách với giá $10000$ (đồng/cuốn sách). Gọi $T$ (đồng) là tổng số tiền mỗi khách hàng phải trả trong mỗi năm và $n$ là số cuốn sách mà khách hàng mướn. a) Lập hàm số của $T$ theo $n$ đối với khách hàng là hội viên và khách hàng không là hội viên. b) Phát là một hội viên của cửa hàng sách, năm ngoái Phát đã trả cho cửa hàng tổng cộng $90000$ đồng. Hỏi nếu Phát không phải là hội viên của cửa hàng thì số tiền Phát phải trả là bao nhiêu? c) Mỗi hội viên cần thuê tối thiểu bao nhiêu cuốn sách để có thể bù được phí hội viên?
Thời gian gọi (phút)
Chúc mừng trường Phổ thông Năng khiếu đã thành lập được đội tuyển toán, gồm 4 bạn lớp 12 và 6 bạn lớp 11. Tất cả các bạn vào đội tuyển đều rất xứng đáng, có một vài trường hợp hơi tiếc, hy vọng các em vẫn còn đam mê để bức phá ở thời gian sau.
Hoàng Sơn 10 Toán đã có một ngày thi thứ nhất rất xuất sắc nhưng chưa đủ giúp em vào đội tuyển, hy vọng năm sau em sẽ tỏa sáng.
Trong các bài toán đếm ta gặp bài toán sau: Một người vào cửa hang mua dụng cụ học tập để làm thành một món quà gồm viết, sách và tập, người đó chỉ mua tổng cộng 5 món đồ. Biết rằng trong cửa hàng có 5 cây viết giống nhau, 6 sách giống nhau và 10 cuốn tập giống nhau, hỏi có bao nhiêu cách chọn viết, sách tập để làm quà?
Ta thấy rằng số lượng các viết sách và tập đều lớn hơn số cần mua, do đó bài toán chỉ quay lại việc đếm là có bao nhiêu bộ sách viết tập mà tổng số là 5 cái, trong đó mỗi cái có hoặc không có.
Có ba đối tượng là viết, sách và tập, tạ kí hiệu là $A = { V, S, T }$. Một món quà gồm 5 cái, do đó quà có thể là $X = { V, V, V, S, T }$, gồm 3 cây viết và 1 sách, 1 tập, hoặc là tập $Y = { V, V, S, T, T }$, ta thấy các đối tượng $V, T$ là lập lại. Khi đó ta nói tổ hợp $X, Y$ là tổ hợp lặp.
Để định nghĩa rõ hơn ta có định nghĩa sau:
Định nghĩa. Cho tập $A = { a_1, a_2, \cdots, a_k }$. Một ánh xạ từ $p: A \mapsto \mathbb{N} $, khi đó $P$ được gọi là một multiset của A.
Ví dụ 1. Cho $A = { a, b, c }$. Ánh xạ $p: A \mapsto \mathbb{N}$ như sau: $p(a) = 2, p(b) = 1, p(c) = 1$. Khi đó ta có thể kí hiệu $p$ là $(aabc)$, hay $(baac)$,.., không tính đến thứ tự của các phần tử $a, b, c$.
Đặt $n = p(a_1) + p(a_2)+\cdots +p(a_k)$, bài toán đặt ra là có bao nhiêu ánh xạ $p: A \mapsto \mathbb{N}$ mà $n = p(a_1) + p(a_2)+\cdots +p(a_k)$.
Tiếp theo ví dụ trên, nếu $ p(a) + p(b) + p(c) = 2$ thì có các multiset sau: $(ab), (ac), (bc), (aa), (bb), (cc)$, 6 multiset.
Tính chất. Cho tập $A = { a_1, a_2, \cdots, a_k }$, số ánh xạ $p: A \mapsto \mathbb{N}$ thỏa $p(a_1) + \cdots + p(a_k) = n$ là $C^n_{n+k-1}$
Bài toán 2. Giải bài toán trên với cách chia sao cho mỗi người có ít nhất một viên.
Trước hết phát cho mỗi người một viên, thì còn $n-k$ viên kẹo, tiếp tục áp dụng bài toán trên với $n-k$. Khi đó số cách chia là
$C^{k-1}_{n-1}$
Ta có thể giải bài toán trên mà không cần sử dụng bài toán 1 bằng cách xây dựng dãy nhị phân thỏa: $a_1$ chữ số đầu là 0, tiếp theo là số 1, tiếp là $a_2$ chữ số 0, …., cuối cùng là $a_k$ chữ số 0. Dãy này có $k-1$ chữ số 1 đứng giữa $n$ chữ số 0 và không có hai chữ số $1$ nào đứng kề nhau. Khi đó số dãy nhị phân là: $C^{k-1}_{n-1}$.
Phần kế tiếp ta cùng tìm hiểu và giải một số bài toán có thể đưa về bài toán tổ hợp lặp hay bài toán chia kẹo Euler. Các bạn chờ nhé.
Bài toán 1 và 2 có thể phát biểu dưới dạng sau.
Bài toán 3. Cho phương trình $x_1 + x_2 + \cdots + x_k = n$ trong đó $k, n$ là các số nguyên dương.
a. Tìm số nghiệm tự nhiên của phương trình.
b. Tìm số nghiệm nguyên dương của phương trình.
Như bài toán trên ta đã biết, số nghiệm tự nhiên của phương trình là $C^{k-1}_{n+k-1}$.
Số nghiệm nguyên dương của phương trình là $C^{k-1}_{n-1}$.
Tính chất: Cho hai đường thẳng $\left( d_1\right) : y=a_1x+b_1$, $\left( d_2\right) : y=a_2x+b_2$.
Khi đó: $d_1$ cắt $d_2$ khi và chỉ khi $a_1\ne a_2$
và phương trình hoành độ giao điểm của $d_1$ và $d_2$ là:
$a_1x+b_1=a_2x+b_2$.
Ví dụ 1: Cho hàm số $y=2x+1$ và $y=3x+2$ có đồ thị là $d_1$ và $d_2$.
a) Vẽ $d_1$ và $d_2$ trên cùng một hệ trục tọa độ.
b) Tìm tọa độ giao điểm của $d_1$ với trục hoành, trục tung, $d_2$.
a) b) Ta có: $A\in Ox\Rightarrow y_A=0\Rightarrow A\left( x_A;0\right) $ $A\in d_1\Rightarrow y_A=2x_A+1\Rightarrow 2x_A+1=0\Rightarrow x_A=-\dfrac{1}{2}$ Vậy giao điểm của $d_1$ với $Ox$ có tọa độ là $A\left(- \dfrac{1}{2};0\right) $. Ta có: $B\in Oy\Rightarrow x_B=0\Rightarrow B\left( 0;y_B\right) $ $B\in d_1\Rightarrow y_B=2x_B+1\Rightarrow y_B=1$ Vậy giao điểm của $d_1$ với $Oy$ có tọa độ là $B\left( 0;1\right) $. Phương trình hoành độ giao điểm của $d_1$ và $d_2$ là: $2x_C+1=3x_C+2$ $\Rightarrow x_C=-1$ $\Rightarrow y_C=-1$ Vậy giao điểm của $d_1$ với $d_2$ có tọa độ là $C\left( -1;-1\right) $. Ví dụ 2: Cho $d_1: y=\left( 2m-1\right) x+1$ và $d_2: y=4x-1$. a) Tìm điều kiện của $m$ để $d_1$ cắt $d_2$. b) Tìm $m$ để $d_1$ cắt $d_2$ tại điểm có hoành độ bằng tung độ.
Bài tập: Bài 1: Cho $d_1: y=-x$ và $d_2: y=2x+3$. a) Vẽ $d_1$ và $d_2$ trên cùng một mặt phẳng tọa độ. b) Tìm giao điểm $A$ của $d_1$ và $d_2$. Tìm giao điểm $B$ của $d_2$ với trục tung. c) Tính diện tích tam giác $OAB$. Bài 2: Cho đường thẳng $\left( d_1\right) : y=x$, $\left( d_2\right) : y=2x+1$, $\left( d_3\right) : y=3x+2$. a) Tìm tọa độ giao điểm của $\left( d_1\right) $ và $\left( d_2\right) $. b) Chứng minh rằng ba đường thẳng đã cho đồng quy. Bài 3: Cho đường thẳng $d_1: y=2x-1$ và $d_2: y=\left( m-1\right) x+3$. a) Tìm điều kiện của $m$ để $d_1$ cắt $d_2$. b) Chứng minh rằng khi $m$ thay đổi thì $d_2$ luôn đi qua điểm $A\left( 0;3\right) $. c) Tìm $m$ để $d_1$ cắt $d_2$ tại điểm có hoành độ bằng $1$. Bài 4: Tìm phương trình đường thẳng $\left( d\right): y=ax+b$ biết rằng: a) $\left( d\right) $ đi qua hai điểm $A\left( 1;-2\right) $ và $B\left( 3;2\right) $. b) $\left( d\right) $ song song với $\left( d_1\right): y=3-x $ và đi qua điểm $C\left( 1; -\dfrac{1}{2}\right) $. c) $\left( d\right) $ đi qua điểm $D\left( -1;4\right) $ và cắt đường thẳng $\left( d_2\right): y=2x-1 $ tại điểm có hoành độ $x=2$. Bài 5: Cho hai đường thẳng $d_1: y=-\dfrac{1}{2}x$ và $d_2: y=\dfrac{1}{2}x+3$. a) Vẽ $d_1$ và $d_2$ trên cùng mặt phẳng tọa độ $Oxy$. b) Tìm tọa độ giao điểm của $d_1$ và $d_2$. c) Cho đường thẳng $d_3: y=2x+b$, tìm $b$ biết $d_3$ cắt $d_2$ tại điểm $M$ có hoành độ và tung độ đối nhau. Bài 6: Hai bạn Chánh và Hiệp cùng đi xe máy từ Thành phố Hồ Chí Minh đến Vũng Tàu. Chánh xuất phát từ $7$ giờ và đi với vận tốc $30$ km/h. Hiệp xuất phát lúc $7$ giờ $40$ phút và đi với vận tốc $40$ km/h. a) Gọi $s$ (km) là quãng đường đã đi được, $t$ (giờ) là thời gian đã đi tính từ lúc Hiệp xuất phát. Viết biểu thức liên hệ giữa $s$ và $t$ đối với mỗi bạn. Hai bạn gặp nhau lúc mấy giờ. b) Biết quãng đường từ Thành phố Hồ Chí Minh đến Vũng Tàu dài $90$ km. Hỏi ai đến Vũng Tàu trước và khi đó là mấy giờ?Giải
TÍnh chất: Cho hai hàm số $y=a_1x+b_1$ có đồ thị là $d_1$ và $y=a_2x+b_2$ có đồ thị là $d_2$. Khi đó:
Ví dụ 1: Cho $d_1: y=2x+1$ và $d_2: y=2x-2$. Chứng minh rằng $d_1//d_2$.
Ví dụ 2: Cho hai hàm số $y=\left( m-2\right)x-3$ $\left( d_1\right) $ và $y=\left( 2m+5\right)x-3$ $\left( d_2\right)$. Tìm $m$ để $d_1$ và $d_2$ trùng nhau.
Bài tập: Bài 1: Cho $d_1: y=\left( 2m-1\right)x+1$ và $d_2: y=4x-1$. a) Tìm $m$ để $d_1//d_2$. b) Tìm $m$ để $A\left( 1;3\right) \in d_1$. Bài 2: Cho hàm số $y=-2x+3$ có đồ thị $d_1$ và $y=x-1$ có đồ thị $d_2$. a) Vẽ $d_1$ và $d_2$ trên cùng mặt phẳng tọa độ. b) Xác định hệ số $a$, $b$ biết đường thẳng $d_3: y=ax+b$ song song với $d_2$ và đi qua điểm $A\left( 1;2\right) $. Bài 3: Cho đường thẳng $d_1: y=4x-6$, $d_2: y=3x-4$ và $d_3:y=ax+2a+1$ a) Tìm $a$ để $d_3//d_1$. b) Tìm $a$ để $d_3//d_2$. Bài 4: Tìm phương trình đường thẳng $\left( d\right) : y=ax+b$ biết rằng: a) $\left( d\right) $ đi qua hai điểm $A\left( -1;3\right) $ và $B\left( 2;0\right) $. b) $\left( d\right) $ song song với $\left( d_1\right) : y=-4x+3$ và đi qua điểm $C\left(-1;2\right) $. Bài 5: Cho ba điểm $A\left( 2;1\right) $, $B\left( 3;3\right) $, $C\left( 4;5\right) $. a) Viết phương trình đường thẳng $d$ đi qua hai điểm $A$ và $B$. Chứng minh rằng ba điểm $A$, $B$, $C$ thẳng hàng. b) Viết phương trình đường thẳng qua $M\left( 0;1\right)$ và song song với $d$.
PHƯƠNG PHÁP ĐẾM BẰNG HAI CÁCH
(Dành cho học sinh lớp 10 chuyên toán)
Lời nói đầu
Đếm bằng hai cách là một phương pháp hay gặp trong đời sống, ví dụ bài toán sau: Một công ty nhập vào 3 xe hàng $ A, B, C $ gồm hai loại hàng $ I $ và $ II $. Trong đó xe $ A $ có 3 loại $ I $ và 2 loại $ II $, xe $ B $ có 4 loại $ I $ và 6 loại $ II $, xe $ C $ có 4 loại $ I $ và 6 loại $ II $. Tính số lượng hàng mà công ty nhâp vào. Đây là bài toán khá đơn giản, để giải bài toán ta có thể lập bảng và khi đó ta có thể tính bằng 2 cách như sau: Tính tổng số hàng trên mỗi xe rồi cộng lại; hoặc ta có thể tính tổng số hàng loại $ I $ trên 3 xe,tổng số hàng loại 2 trên 3 xe, rồi sau đó cộng lại.
Trên đây là một ví dụ của tính bằng hai cách, ta có thể tính tổng theo dòng hoặc có thể tính tổng theo cột. Tổng quát hơn ta có công thức đại số sau: $\sum_{i \in I,j \in J}a_{ij}=\sum_{j \in J}(\sum_{j \in J}a_{ij})=\sum_{j \in J}(\sum_{i \in J}a_{ij})$
Trong một số tình huống đề bài yêu cầu đếm số phần tử của một tập hợp mà không quan tâm ta đếm bằng cách nào, khi đó đếm bằng hai cách cho ta cùng một đáp số giống nhau, khi đó ta sẽ thiết lập được một đẳng thức tổ hợp. Một ví dụ đơn giản như đếm số tập con của tập có $ n $ phần tử, ta có thể đếm số tập có $ k $ phần tử với $ k = 0,1,…,n $, lấy tổng ta được $ C^0_n +C^1_n +….+C^n_n $. Nhưng nếu ta đếm bằng cách khác như sau: xét một tập hợp $ A $ bất kì, khi đó phần tử $ i $ có thể thuộc $ A $ hoặc $ i $ không thuộc $ A $, mỗi phần tử có 2 trường hợp, mà có $ n $ phần tử nên số tập $ A $ là $ 2^n $. Từ đó ta có đẳng thức $ C^0_n + C^1_n + …. + C^n_n = 2^n $. Đếm bằng hai cách cho ta một phương pháp để chứng minh đẳng thức liên quan tới hệ số khai triển nhị phân hay các đẳng thức tổ hợp.
Ngoài ra đếm bằng hai cách có thể áp dụng trong các bài toán bất đẳng thức, cực trị tổ hợp hay một số bài toán chứng minh sự tồn tại.
Để sử dụng phương pháp đếm bằng hai cách, đòi hỏi học sinh phải biết và vận dụng tốt các phép đếm cơ bản. Bài viết này được sử dụng để giảng dạy cho học sinh lớp 10 chuyên Toán, các em mới bước đầu làm quen với các bài toán tổ hợp nói chung và các bài toán đếm nói riêng nên ví dụ được nêu ra có độ khó không cao giúp các em làm quen với phương pháp này. Vì thời gian quá gấp rút nên không tránh khỏi sai sót, bạn đọc có thắc mắc xin liên hệ địa chỉ nguyentangvu@gmail.com,cảm ơn.
1. Chứng minh các đẳng thức tổ hợp
Ví dụ 1. Cho các số nguyên dương $ n $ và $ k $ với $ 0 < k \leq n $. Chứng minh các đẳng thức tổ hợp sau:
a) $ C_n^k=C^k_{n-1}+C^{k-1}_{n-1} $
b) $ \sum_{k \geq 0}C^{2k}_n=2^{n-1} $
a) Dễ thấy vế trái của đẳng thức là số cách chọn $ k $ phần tử từ $ n $ phần
tử. Để chọn $ k $ phần tử từ $ n $ phần tử ta có thể làm như sau: Xét phần tử
$ a $, nếu $ a $ được chọn thì ta cần chọn thêm $ k−1 $ phần tử từ $ n−1 $
phần tử còn lại ta có $ C^{k−1}_{ n−1} $ cách. Nếu $ a $ không được chọn,
ta chọn $ k $ phần tử từ $ n−1 $ phần tử còn lại, ta có $ C^k_ {n−1} $. Do
đó số cách chọn trong hai trường hợp là $C^k_{n-1}+C^{k-1}_{n-1} $. Từ
đó ta có điều cần chứng minh.
b) Ta xét bài toán “đếm số cách chọn một số chẵn phần tử từ $ n $ phần tử”.Ta có thể đếm theo cách sau:
Cách 1: Ta có số cách chọn $ 2k $ phần tử từ $ n $ phần tử là $ C^{2k}_n $ . Khi
đó $ \sum_{k \geq 0}C^{2k}_n $ lần tổng số cách chọn một số chẵn phần tử từ
$ n $ phần tử.
Cách 2: Xét một phần tử $ a $, thì có hai khả năng $ a $ được chọn hoặc $ a $
không được chọn, ta có 2 trường hợp. Khi đó với $ n−1 $ phần tử đầu tiên, thì
số trường hợp là $ 2^{n−1} $. Tới phần tử thứ $ n $, nếu ta đã chọn được một
số chẵn phần tử thì ta không chọn, còn nếu ta đã chọn được một số lẻ phần
tử thì phần tử này sẽ được chọn, do đó số cách chọn là $ 2^{n−1} $.
Ví dụ 2. Cho các số nguyên dương $ n $ và $ k $ với $ 0 \leq k \leq n $. Chứng minh rằng:
a) $ kC^k_n=nC^{k-1}_{n-1} $
b) $ \sum_{k=0}^{n}kC^k_n=n2^{n-1} $
Ví dụ 3. Cho các số nguyên dương $ n $ và $ k $ với $ 0 \leq k \leq n $. Chứng minh rằng:
a) $ \sum_{m=k}^{n}C^k_m=C^{k+1}_{n+1} $
b) $ \sum_{m=k}^{n-k}C^k_mC^k_{n-m}=C^{2k+1}_{n+1} $
với $ 0 \leq k \leq\dfrac{n}{2} $.
Bài tập
Bài 1 Cho $ 0 \leq k \leq m \leq n. $ Chứng minh các đẳng thức sau:
a) $ C^k_mC^m_n=C^k_nC^{m-k}_{n-k} $
b) $ \sum_{k \geq 0}k(C^k_n)^2=nC^{n-1}_{2n-1} $
c) $ \sum_{k \geq 0}C^k_nC^{m-k}_{n-k}=2^mC^m_n $
Bài 2. Chứng minh các đẳng thức sau:
a) $\sum_{i=0}^{k} C^i_n C^{k-i}_{n-i} = 2^kC^k_n$
b) $ kC^k_m C^0_p+(k-1)C^{k-1}_m C^1_p+…+C^1_mC^{k-1}_p$
$=\dfrac{m}{m+p}.k.C^k_{m+p} $
Ví dụ 4. Trong một hội nghị, mỗi thành viên tham gia đúng 3 cuộc họp và mỗi cuộc họp thì có đúng 6 thành viên tham gia. Chứng minh rằng số cuộc họp thì bằng nửa số thành viên tham gia hội nghị.
Dựa vào trên, ta thấy mỗi dòng có 6 số 1 và mỗi cột có 3 số 1. Khi đó ta có $ 6m = 3n $ hay $ n = 2m $.
Bảng trên được gọi là một ma trận nhị phân, dùng để biểu diễn các mối quan hệ hai ngôi như phần tử thuộc tập hợp, quen nhau, đồ thị… và là mô hình biểu diễn rất hữu dụng trong các bài toán tổ hợp. Trong mỗi bảng nhị phân trên, nếu gọi $ r_i $ là số số 1 ở dòng thứ $ i $ và $ c_j $ là số số 1 ở cột thứ $ j $, ta có :
$ \sum_{i=1}^{m}r_i=\sum_{j=1}^{n}cj $
Ví dụ 5 (HK 1994) Trong một trường học có $ m $ giáo viên và $ n $ học sinh thỏa điều kiện sau:
i) Mỗi giáo viên dạy đúng p học sinh.
ii) Với hai học sinh phân biệt thì có đúng $ q $ giáo viên dạy họ.
Chứng minh rằng $ \dfrac{m}{q}=\dfrac{n(n-1)}{p(p-1)} $
Định lý 1. Nếu trong một bảng nhị phân $ m \times n, $ mỗi dòng có $ k $ số 1, hai cột bất kỳ có đúng $ p $ cặp $ (1;1) $ cùng một dòng.
Khi đó ta có $ pC^2_n=kC^2_m. $
Bài tập
Bài 1. Cho tập $ X = {1,2,…,8} $ và các tập $ A1,A2,…,A6 $ là các tập con của $ X $ sao cho mỗi tập $ Ai $ có $ 4 $ phần tử và mỗi phần tử của $ S $ thuộc $ m $ tập $ Ai $. Tìm $ m $.
Bài 2. Trong một vòng thi toán chung kết tại trường PNTK, các thí sinh phải giải 9 bài toán. Biết rằng mỗi thí sinh giải được đúng 6 bài, và với hai thí sinh bất kì thì giải đúng chung 3 bài. Tìm số thí sinh dự thi.
Bài 3. Gọi $ p(n,k) $ là số hoán vị của $ {1,2,…,n} $ có $ k $ điểm bất động. Chứng minh rằng:
$ \sum_{k=1}^{n}kp(n,k)=n! $
2. Chứng minh các bài toán bất đẳng thức và cực trị tổ hợp
Ví dụ 6. (Iran 2011) Cho $ n $ điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng số tam giác có diện tích bằng 1 có các đỉnh thuộc $ n $ điểm trên không vượt quá $ \dfrac{2}{3}(n^2-n) $. Ví dụ 7.(USA TST 2005) Cho $ n > 1 $. Với số nguyên dương $ m $. Đặt $ X_m = {1,2,…,mn} $. Xét họ $ T $ gồm $ 2n $ tập hợp thỏa các điều kiện sau: Xét bảng vuông sao cho gồm $ 2n $ dòng và $ mn $ cột sao cho $ a_{ij} =1$ nếu số $ j $ thuộc $ a_i $ và bằng $ 0 $ trong trường hợp ngược lại. Ví dụ 9. Cho $ n $ điểm trong mặt phẳng. Chứng minh rằng số cặp điểm có khoảng cách bằng 1 không quá $ \dfrac{n}{4}+\dfrac{\sqrt{2n^3}}{2}. $
3 Các bài toán tồn tại Ví dụ 11. Cho tập $ X $ có $ n $ phần tử, gọi $ A_1,A_2,…,A_m $ là một họ các tập con của $ X $, sao cho $ |Ai| = 3 $ và $ |A_i \cap A_j| \leq 1 $ với $ i \neq j $. Chứng minh rằng tồn tại một tập con $ A $ của $ X $ có ít nhất $ [\sqrt{2n}] $ phần tử và không chứa bất kì tập $ A_i $ nào.
Bài tập rèn luyện Bài 2. Cho 16 bạn học sinh làm một bài kiểm tra trắc nghiệm, trong đó mỗi câu hỏi có 4 lựa chọn. Sau bài kiểm tra, ta thấy rằng với hai học sinh bất kì có nhiều nhất một câu trả lời giống nhau. Hỏi bài kiểm tra có nhiều nhất bao nhiêu câu hỏi? Bài 3. Một hội nghị có n thành viên tham gia, hội nghị đã tổ chứng $ n + 1 $ cuộc họp, trong đó mỗi cuộc họp có đúng 3 người và không có cuộc họp nào có thành viên giống nhau. Chứng minh rằng có hai cuộc họp mà có chung đúng một thành viên. Bài 4. (China 1996) Trong một hội nghị có 8 người tham gia, hội nghị tổ chức $ m $ cuộc họp, mỗi cuộc họp có đúng 4 người tham gia. Hơn nữa hai người bất kì thì cùng tham gia một số cuộc họp như nhau. Tìm giá trị nhỏ nhất của $ m $. Bài 6. (IMO 2001) Có 21 bạn nam và 21 bạn nữ tham dự một kì thi học sinh giỏi toán. Biết rằng: Bài 7. (USAMO 2001) Có 8 hộp, mỗi hộp chứa 6 viên bi. Mỗi viên bi được tô màu sao cho: Bài 8. (IMO 1989) Cho $ n $ và $ k $ là các số nguyên dương và $ S $ là tập $ n $ điểm trong mặt phẳng sao cho: Bài 9. (IMO 2005) Trong một cuộc thi toán trong đó đề thi có 6 bài. Mỗi một cặp bài toán được giải bởi nhiều hơn $ \dfrac{2}{5} $ số thí sinh. Không có ai giải được 6 bài. Chứng minh rằng có ít nhất 2 thí sinh giải được đúng 5 bài. Bài 10. Trong một hội nghị có 35 người tham gia. Biết rằng có 111 cặp đôi một quen nhau. Chứng minh rằng có thể chọn ra 4 thành viên xếp ngồi vào một bàn tròn sao cho hai người ngồi gần nhau thì quen nhau.
i) Mỗi phần tử của $ T$ là một tập con có $ m $ phần tử của $ X_m. $
ii) Mỗi cặp thuộc $ T $ có nhiều nhất một phần tử chung.
iii) Mỗi phần tử thuộc $ X_m $ thuộc đúng hai tập của $ T. $
Tìm giá trị lớn nhất của $ m $ theo $ n. $
Ví dụ 8. (IMO 1998, P2) Trong một cuộc thi có $ a $ thí sinh và $ b $ giám khảo, với $ b $ là số lẻ lớn hơn 3. Mội giám khảo có thể đánh giá thí sinh rớt hay đậu.Giả sử với hai giám khảo bất kì thì quyết định giống nhau nhiều nhất là $ k $ thí sinh. Chứng minh rằng $ \dfrac{k}{a} \geq \dfrac{b-1}{2b} $Giải
Ta xét bài toán đếm số cặp $ (1;1) $ cùng một cột. Do (i) nên ta có số cặp nhiều nhất là $ C^2_{2n} $.
Do (ii) nên ta có số cặp là $ mn $.
Do đó $ mn \geq C^2_ {2n} $, suy ra $ m \geq 2n−1 $. Nếu $ m = 2n−1 $, ta xét mô hình sau. Cho $ 2n $ đường thẳng không có 3 đường nào đồng quy và không có hai đường nào song song. Khi Xm là tập các giao điểm và $ T $ là họ gồm các điểm thuộc một đường thẳng. Rõ ràng đây là mô hình thỏa đề bài. Bảng sau cho ví dụ $ n=2, m=3 $.
Ví dụ 10. Cho 133 số nguyên dương, có ít nhất 799 cặp số là nguyên tố cùng nhau. Chứng minh rằng tồn tại 4 số nguyên dương phân biệt $ a,b,c,d $ sao cho $ a $ và $ b; b $ và $ c, c $ và $ d; d $ và $ a $ nguyên tố cùng nhau.
Bài 1. Cho 7 tập $ A1,A2,…,A7 $ là các tập con của $ X = {1,2,3,4,5,6,7} $, sao cho mội cặp phần tử thuộc $ X $ thuộc đúng một tập con, và $ |Ai|\geq 3 $ với mọi $ i $. Chứng minh rằng $ |A_i \cap Aj| = 1 $ với mọi $ i,j. $
Bài 5. Cho $ A1,A2,…,Ak $ là các tập con của $ S = {1,2,…,10} $ sao cho:
i) $ |A_i| = 5,i = 1,2,…,k. $
ii) $ |A_i \cap A_j| \leq 2, 1 \leq i < j \leq k. $ Tìm giá trị lớn nhất của $ k $.
a) Mỗi bạn giải được nhiều nhất sáu bài.
b) Mỗi cặp một nam và một nữ thì có ít nhất một bài toán được giải bởi hai người đó.
Chứng minh rằng có môt bài toán mà giải được bởi ít nhất 3 nam và 3 nữ.
i) Mội hộp chứa các viên bi khác màu.
ii) Không có hai màu nào cùng xuất hiện nhiều hơn trong một hộp.
Tìm số màu ít nhất cần dùng.
i) Không có 3 điểm nào thẳng hàng,
ii) Với điểm $ P $ bất kì thuộc $ S $ thì có ít nhất $ k $ điểm của $ S $ cách đều $ P $.
Chứng minh rằng: $ k<\dfrac{1}{2}+\sqrt{2n} $
Tính chất: Đồ thị của hàm số $y=ax+b$ $\left( a\ne 0\right) $ là một đường thẳng:
Đồ thị của hàm số $y=ax+b$ còn được gọi là đường thẳng $y=ax+b$, $b$ được gọi là tung độ gốc của đường thẳng.
Cách vẽ đồ thị của hàm số $y=ax+b$ $(a\ne 0)$
Ví dụ 1: Vẽ đồ thị hàm số $y=2x-1$
Bảng giá trị:
Vẽ đồ thị:
Chú ý:
Ví dụ 2: Cho đường thẳng $d: y=x+2$, $A\left( 1;3\right) $. Chứng minh điểm $A$ thuộc đường thẳng $d$.
Bài tập: Bài 1: Cho hàm số $y=2x+1$ và $y=-3x-1$ có đồ thị là đường thẳng $d_1$ và $d_2$. Hãy vẽ $d_1$ và $d_2$ trên cũng một hệ trục tọa độ. Bài 2: Cho hàm số $y=\left( 2m-1\right)x +2$. a) Tìm điều kiện để hàm số đồng biến trên $\mathbb{R}$. b) Vẽ đồ thị hàm số khi $m=2$. c) Tìm $m$ để đồ thị hàm số đi qua điểm $A\left( 1;-3\right) $. Bài 3: Cho đường thẳng $d: y=ax+b$. TÌm $a$, $b$ biết rằng đường thẳng $d$ đi qua hai điểm $A\left( -1;3\right) $ và $B\left( 2;-5\right) $. Bài 4: Vẽ đồ thị của các hàm số sau: a) $y=\left|x\right|$. b) $y=\left|x-2\right|$.
Định nghĩa: Hàm số bậc nhất là hàm số được cho bởi công thức
$y=ax+b$
trong đó $a$, $b$ là các số cho trước và $a\ne 0$.
Ví dụ 1: Để ủng hộ cho các người dân trong đợt lũ lụt, lớp 9A quyết định trích tiền quỹ của lớp ra $500000$ và mỗi bạn trong lớp có thể đóng góp số tiền như nhau là $20000$. Gọi $x$ là số học sinh đóng góp và $y$ là số tiền đóng góp được. Khi đó số tiền lớp 9A đóng góp là:
$y=20000x+500000$
$y=20000x+500000$ là hàm số bậc nhất với $a=20000$, $b=500000$.
Ví dụ 2: Bạn Uyên có số tiền là $500000$, bạn định sử dụng số tiền này để mua truyên tranh, mỗi quyển truyện tranh có giá $15000$. Gọi $h$ là số quyển truyện tranh Uyên mua được và $t$ là số tiền còn lại của Uyên. Khi đó ta có:
$t=500000-15000h=-15000h+500000$
$t=-15000h+500000$ là hàm số bậc nhất với $a=-15000$, $b=500000$.
Tính chất 1: Hàm số bậc nhất $y=f(x)=ax+b$ xác định với mọi $x$ thuộc $\mathbb{R}$ và thỏa mãn:
Ví dụ 3:
a) Hàm số $y=20000x+500000$ là hàm số bậc nhất có $a=20000>0$ nên hàm số đồng biến trên $\mathbb{R}$.
b) Hàm số $t=-15000h+500000$ là hàm số bậc nhất có $a=-15000<0$ nên hàm số nghịch biến trên $\mathbb{R}$.
Bài tập:
Bài 1: Trong các hàm số sau, hàm số nào là hàm số bậc nhất? Xác định các hệ số $a$, $b$ của các hàm số bậc nhất vừa tìm được.
a) $y=4x-2$
b) $y=-3-x$
c) $y=\dfrac{1}{x}+7$
d)$y=\dfrac{2x}{3}$
e) $y=5\left(2-x\right) +3$
Bài 2: Xét tính đồng biến, nghịch biến của các hàm số sau:
a) $y=2x-7$
b) $y=3-5x$
c) $y=\left( \sqrt2-\sqrt3\right)x+1$
d) $y=\left( 2+m^2\right)x-4$
Bài 3: Cho hàm số $y=\left( 2m-1\right)x+3$. Tìm $m$ để hàm số đồng biến trên $\mathbb{R}$.
Bài 4: Cho hàm số $y=\left( 2m+5\right)x+m-2$. Tìm $m$ để hàm số nghịch biến trên $\mathbb{R}$.
Bài 5: Cho hàm số $y=\left( m+1\right)x+3m+1$. Tìm $m$ để hàm số trên là hàm số bậc nhất.
Bài 6: Để đổi từ nhiệt độ $F$ sang độ $C$, ta dùng công thức sau:
$C=\dfrac{5}{9}\left( F-32\right) $
a) $C$ có phải là hàm số bậc nhất theo biến số $F$ không?
b) Hãy tính $C$ khi $F=30$, $F=70$.
Bài 7: Cây cà chua lúc đầu cao $20$ cm, mỗi ngày cao thêm $10$ cm, cây đu đủ lúc đầu cao $50$ cm và mỗi ngày cao thêm $\dfrac{20}{3}$ cm. Gọi $x$ là số ngày, $y$ là chiều cao của mỗi cây, hãy lập hàm số của $y$ theo $x$ đối với mỗi cây.
Bài 8: Hai bạn $A$, $B$ đi cùng hướng trên một con đường, lúc đầu $A$, $B$ cách bến xe buýt lần lượt là $200$ m và $500$ m cùng đi ngược hướng với trạm xe buýt. Mỗi giờ $A$ đi được $3$ km và $B$ đi được $1$ km. Gọi $d_1$ và $d_2$ là khoảng cách của $A$, $B$ đối với trạm xe buýt sau khi đi được $t$ giờ. Hãy tính $d_1$ và $d_2$ theo $t$.
1.Định nghĩa
Ví dụ 1. Cho $A = { 1, 2, 3, 4 }$. Các tổ hợp chập 3 của là $A$ là $ {1, 2, 3}, {1, 2, 4}, {1, 3, 4 }, {2, 3, 4 }$.
2.Các ví dụ.
Ví dụ 1. Lớp 11A có 15 bạn nam và 20 bạn nữ, hỏi có bao nhiêu cách chọn một nhóm 5 bạn để đi làm việc biết
a. Có 3 bạn nam và 2 bạn nữ.
b. Có ít nhất 2 bạn nữ.
Lời giải.
a.
b. Bài này ta có thể sử dụng phần bù.
Ví dụ 2. Trong hộp có 5 bi xanh, 4 bi đỏ và 5 bi vàng. Lấy ra 4 viên bi, hỏi có bao nhiêu cách lấy thỏa:
a. Có cùng một màu.
b. Có đầy đủ 3 màu.
Lời giải.
a.
b.
3.Bài tập
Bài 1. Một nhóm học sinh có 10 bạn. Có bao nhiêu cách chọn
a) 3 bạn đi dọn vệ sinh trường lớp.
b) 5 bạn để lập một nhóm tình nguyện, trong đó có một đội trưởng.
Bài 2. Trong hộp có 7 bi xanh và 8 bi vàng. Có bao nhiêu cách lấy ra 5 bi thỏa:
a) Lấy tùy ý.
b) Có ít nhất 2 bi vàng.
c) Các bi cùng màu.
Bài 3. Có 3 hộp, trong đó hộp thứ nhất chứa 5 viên bi xanh, hộp thứ hai chứa 6 viên bi đỏ và hộp thứ ba chứa 8 viên bi vàng, các viên bi đều khác nhau. Chọn ra 5 viên bi từ 3 hộp. Hỏi có bao nhiêu cách chọn
a) 5 viên bi đều màu vàng.
b) 2 viên bi màu đỏ, 3 viên bi màu xanh.
c) Có đầy đủ 3 màu.
d) Không có bi màu đỏ hoặc màu xanh và ít nhất 2 viên bi màu vàng.
Bài 4. Từ 5 bông hồng vàng, 3 bông hồng trắng, và 4 bông hồn đỏ (các bông hoa xem như đôi một khác nhau) người ta muốn chọn ra 1 bó hoa gồm 7 bông. Có bao nhiêu cách chọn 1 bó hoa trong đó có ít nhất 3 bông hồng vàng và ít nhất 3 bông hồng đỏ.
Bài 5. Bạn An mời tiệc sinh nhật, vì nhà nhỏ nên trong 20 người bạn của mình An chỉ có thể mời được 8 bạn. Biết rằng trong các bạn của An thì có Nam và Long không thích nhau nên An không thể mời cả hai bạn dự cùng lúc. Hỏi An có bao nhiêu cách mời?