You are here: Home »
Trò chơi ô chữ trên tờ New York Times hàng ngày là một ô vuông kích thước15×15. Số gợi ý nhỏ nhất từng được xuất bản trên báo này là 52 (vào 23 tháng 12 năm 2008), số gợi ý lớn nhất là 86 (21 tháng 1 năm 2005).
Nhà toán học Kevin Ferland ở Bloomsburg University đặt ra câu hỏi: Trên lý thuyết, số gợi ý ít nhất và nhiều nhất có thể lấp đầy một trò chơi ô chữ chuẩn kích thước 15×15, dùng các quy tắc chuẩn (liên thông, đối xứng và ba+) là bao nhiêu?
Số gợi ý ngắn nhất có thể suy ra dễ dàng: Một lưới vuông không có ô đen nào sẽ được lấp đầy với 30 gợi ý, mỗi gợi ý gồm 15 kí tự, 15 nằm ngang và 15 nằm dọc.
Số gợi ý lớn nhất thì khó xác định hơn, nhưng với bài báo 9 trang, Ferland đã cho câu trả lời là 96: Hình trên là một ví dụ.
Để tôn vinh kết quả này, ông đã tạo ra một câu đố ô chữ dùng mẫu này và đăng trong số tháng 6 và 7 năm 2014 của American Mathematical Monthly.
Tham khảo
Kevin K. Ferland, “Record Crossword Puzzles,” American Mathematical Monthly 121:6, 534-536.
* Một số câu đố đã đăng trên New York Times vi phạm tiêu chuẩn này.
Nhà toán học Kevin Ferland ở Bloomsburg University đặt ra câu hỏi: Trên lý thuyết, số gợi ý ít nhất và nhiều nhất có thể lấp đầy một trò chơi ô chữ chuẩn kích thước 15×15, dùng các quy tắc chuẩn (liên thông, đối xứng và ba+) là bao nhiêu?
Tiêu chuẩn:
1. Liên thông: Tâm của các hình vuông trắng bất kỳ trong lưới có thể nối với nhau bởi các đoạn thẳng nằm ngang hoặc nằm dọc chỉ đi qua và gặp nhau ở các ô trắng.*
2. Đối xứng: Ô vuông không thay đổi nếu xoay 180 độ.
3. Ba+: Mỗi gợi ý tối thiểu ba kí tự
Số gợi ý ngắn nhất có thể suy ra dễ dàng: Một lưới vuông không có ô đen nào sẽ được lấp đầy với 30 gợi ý, mỗi gợi ý gồm 15 kí tự, 15 nằm ngang và 15 nằm dọc.
Số gợi ý lớn nhất thì khó xác định hơn, nhưng với bài báo 9 trang, Ferland đã cho câu trả lời là 96: Hình trên là một ví dụ.
Để tôn vinh kết quả này, ông đã tạo ra một câu đố ô chữ dùng mẫu này và đăng trong số tháng 6 và 7 năm 2014 của American Mathematical Monthly.
Tham khảo
Kevin K. Ferland, “Record Crossword Puzzles,” American Mathematical Monthly 121:6, 534-536.
* Một số câu đố đã đăng trên New York Times vi phạm tiêu chuẩn này.
Bài toán:
Từ các chữ số $1, 3, 5, 9$ có thể lập được bao nhiêu số tự nhiên 2014 chữ số và chia hết cho 3.
Hướng dẫn giải.
Cách 1:
Gọi $a_n$ là số các số tự nhiên chia hết cho 3 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$; $b_n$ là số các số tự nhiên chia 3 dư 1 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$ và $c_n$ là số các số tự nhiên chia 3 dư 2 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$. Dễ thấy $a_1=2;\,b_1=c_1=1$.
Một số tự nhiên chia hết cho 3 và có $n+1$ chữ số lập ra từ các chữ số $1, 3, 5, 9$, chỉ có 3 cách tạo như sau:
Mặt khác, $a_n+b_n+c_n=4^n$ vì đó là số cách tạo nên một số có $n$ chữ số từ $1, 3, 5, 9$, do đó $${a_1} = 2;\,\,{a_{n + 1}} = {a_n} + {4^n} = {a_1} + 4 + 4^2 + \ldots + {4^n} = \frac{{{4^{n + 1}} + 2}}{3}.$$
Từ đó ta suy ra kết quả cần tìm là $\frac{4^{2014}+2}{3}$.
Cách 2:
Một số tự nhiên chia hết cho 3 khi và chỉ khi tổng các chữ số của nó chia hết cho 3.
Xét đa thức
$ P(x) = (x + x^3 + x^5 + x^9)^{2014} =\sum x^{a_1+a_2+...+a_{2014}} $ trong đó $ a_i \in \{1, 3, 5, 9\}$. Số các số có 2014 chữ số lập từ các chữ số 1, 3, 5, 9 và chia hết cho 3, kí hiệu là $S_{2014}$, bằng tổng các hệ số của các số mũ chia hết cho 3 của P(x).
Đặt
$$\epsilon= \cos \frac{{2\pi }}{3} + i\sin \frac{{2\pi }}{3}.$$
Ta có $\epsilon^3 = 1$ và $\epsilon^2+\epsilon +1=0$ và $P(1)+P(\epsilon)+P(\epsilon)=3S$.
Từ $ P(1) = 4^{2014}, P(\epsilon) = 1, P(\epsilon^2) = 1$ kết quả cần tìm là $ S= \frac{4^{2014}+2}{3}$.
Một số bài tập tương tự
1. Có bao nhiêu số tự nhiên khác nhau nhỏ hơn 2.10^8, chia hết cho 3, có thể được viết bởi các chữ số 0, 1, 2.
2. (PTNK 2009) Có bao nhiêu số tự nhiên gồm n chữ số được lập từ các chữ số:3,4,5,6 và chia hết cho 3.
3. Có bao nhiêu số có 6 chữ số không chứa số 0 và chia hết cho 7.
4. Có bao nhiêu số có n chữ số được lập từ các chữ số 1, 3, 4, 6, 7, và 9 có tổng các chữ số chia hết cho 7.
5. (ĐH Huế 2000) Có bao nhiêu số có 3 chữ số khác nhau chia hết cho 9. Có bao nhiêu số có 5 chữ số khác nhau chia hết cho 9.
6. Có bao nhiêu số có 9 chữ số không chứa số 0 và chia hết cho 11.
Từ các chữ số $1, 3, 5, 9$ có thể lập được bao nhiêu số tự nhiên 2014 chữ số và chia hết cho 3.
Hướng dẫn giải.
Cách 1:
Gọi $a_n$ là số các số tự nhiên chia hết cho 3 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$; $b_n$ là số các số tự nhiên chia 3 dư 1 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$ và $c_n$ là số các số tự nhiên chia 3 dư 2 và có $n$ chữ số tạo thành từ các chữ số $1, 3, 5, 9$. Dễ thấy $a_1=2;\,b_1=c_1=1$.
Một số tự nhiên chia hết cho 3 và có $n+1$ chữ số lập ra từ các chữ số $1, 3, 5, 9$, chỉ có 3 cách tạo như sau:
- Thêm chữ số 3 hoặc 9 vào cuối số tự nhiên chia hết cho 3 và có $n$ chữ số lập ra từ các chữ số $1, 3, 5, 9$. Trường hợp này có $2a_n$ khả năng.
- Thêm chữ số 5 vào cuối số tự nhiên chia 3 dư 1 và có $n$ chữ số lập ra từ các chữ số $1, 3, 5, 9$. Trường hợp này có $b_n$ khả năng.
- Thêm chữ số 1 vào cuối số tự nhiên chia 3 dư 2 và có $n$ chữ số lập ra từ các chữ số $1, 3, 5, 9$. Trường hợp này có $c_n$ khả năng.
Mặt khác, $a_n+b_n+c_n=4^n$ vì đó là số cách tạo nên một số có $n$ chữ số từ $1, 3, 5, 9$, do đó $${a_1} = 2;\,\,{a_{n + 1}} = {a_n} + {4^n} = {a_1} + 4 + 4^2 + \ldots + {4^n} = \frac{{{4^{n + 1}} + 2}}{3}.$$
Từ đó ta suy ra kết quả cần tìm là $\frac{4^{2014}+2}{3}$.
Cách 2:
Một số tự nhiên chia hết cho 3 khi và chỉ khi tổng các chữ số của nó chia hết cho 3.
Xét đa thức
$ P(x) = (x + x^3 + x^5 + x^9)^{2014} =\sum x^{a_1+a_2+...+a_{2014}} $ trong đó $ a_i \in \{1, 3, 5, 9\}$. Số các số có 2014 chữ số lập từ các chữ số 1, 3, 5, 9 và chia hết cho 3, kí hiệu là $S_{2014}$, bằng tổng các hệ số của các số mũ chia hết cho 3 của P(x).
Đặt
$$\epsilon= \cos \frac{{2\pi }}{3} + i\sin \frac{{2\pi }}{3}.$$
Ta có $\epsilon^3 = 1$ và $\epsilon^2+\epsilon +1=0$ và $P(1)+P(\epsilon)+P(\epsilon)=3S$.
Từ $ P(1) = 4^{2014}, P(\epsilon) = 1, P(\epsilon^2) = 1$ kết quả cần tìm là $ S= \frac{4^{2014}+2}{3}$.
Một số bài tập tương tự
1. Có bao nhiêu số tự nhiên khác nhau nhỏ hơn 2.10^8, chia hết cho 3, có thể được viết bởi các chữ số 0, 1, 2.
2. (PTNK 2009) Có bao nhiêu số tự nhiên gồm n chữ số được lập từ các chữ số:3,4,5,6 và chia hết cho 3.
3. Có bao nhiêu số có 6 chữ số không chứa số 0 và chia hết cho 7.
4. Có bao nhiêu số có n chữ số được lập từ các chữ số 1, 3, 4, 6, 7, và 9 có tổng các chữ số chia hết cho 7.
5. (ĐH Huế 2000) Có bao nhiêu số có 3 chữ số khác nhau chia hết cho 9. Có bao nhiêu số có 5 chữ số khác nhau chia hết cho 9.
6. Có bao nhiêu số có 9 chữ số không chứa số 0 và chia hết cho 11.
Trong những năm gần đây, các bài toán của Đại số tổ hợp thường xuất hiện trong các đề thi tuyển sinh vào Đại học và Cao đẳng khá nhiều. Trong nội dung này có một số bài toán ứng dụng tích phân để giải quyết. Tuy nhiên, tích phân được học ở trong chương trình lớp 12, còn tổ hợp được học ở trong chương trình lớp 11. Hệ thống các bài tập ở sách giáo khoa và sách bài tập về ứng dụng tích phân để giải các bài toán tổ hợp thì không được trình bày, học sinh không được rèn luyện kỹ năng này trên lớp. Do đó, khi gặp bài toán này ở các đề thi Đại học và Cao đẳng, học sinh phần lớn không làm được.
Nhằm giúp học sinh vận dụng được tích phân để giải các bài toán tổ hợp, chuẩn bị tốt cho các kỳ thi tuyển sinh vào Đại học và Cao đẳng sắp tới, tôi chọn đề tài “Ứng dụng tích phân để giải các bài toán tổ hợp” làm sáng kiến kinh nghiệm của mình.
Tải về SKKN Ung dung tich phan de giai toan to hop của thầy Nguyễn Hữu Quyết. Download.
Tải về SKKN Ung dung tich phan de giai toan to hop của thầy Nguyễn Hữu Quyết. Download.
VNMATH.COM giới thiệu các dạng toán về Hoán vị, Chỉnh hợp, Tổ hợp, Nhị thức Newton của ThS. Phan Văn Danh. Tài liệu rất hay, dày 63 trang gồm các dạng toán luyện thi dại học như các phương trình liên quan đến Hoán vị, Chỉnh hợp, Tổ hợp, hệ số của khai triển nhị thức Newton, các phuuwong pháp đếm từ cơ bản đến nâng cao... thích hợp cho học sinh lớp 11 tự học, học sinh luyện thi đại học.
Tải về file PDF: Download.
Chuyên đề Nhị thức Newton, Xác suất, tổ hợp dùng cho luyện thi Đại học của thầy Huỳnh Chí Hào, Đồng Tháp.
Tải về file PDF: Download.
Tải về file PDF: Download.
Trước hết ta nhắc lại khái niệm giai thừa, trong tất cả các số, hãy chọn ngẫu nhiên một số tự nhiên dương $n$ bất kỳ thì $n!$ (đọc là n giai thừa) bằng với tích $n.(n-1).(n-2).(n-3).......3.2.1$, ví dụ như $5!=5.4.3.2.1=120$.
Vậy câu hỏi đặt ra là giá trị của $0!$ bằng bao nhiêu? Chắc hẳn sẽ có nhiều bạn nghĩ :"Ôi dào, dễ quá, theo khái niệm thì ta suy ra $0!=0$, vậy thôi", nghe cũng có lý chứ nhỉ. Thế nhưng bạn hãy nhìn kỹ lại khái niệm nhé, nếu viết đầy đủ ra thì $0!=0.(0-1).(0-2).......$ và rõ ràng chúng ta không thể tìm ra tích số cuối cùng là $3.2.1$ được.
Nếu thế thì $0!$ bằng bao nhiêu? Theo như sách giáo khoa Giải tích 11 của Nhà xuất bản giáo dục có ghi quy ước $0!=1$, thế nhưng cơ sở nào dẫn đến quy ước này? Tiến sĩ James Grime đến từ Đại học Cambridge, thành viên nhóm Numberphile sẽ có câu trả lời cho chúng ta.
Bây giờ chúng ta thử một vài giá trị giai thừa sau:
$$4!=1.2.3.4=\frac{1.2.3.4.5}{5}=\frac{5!}{5}=24$$
Tương tự, ta được:
$$3!=\frac{4!}{4}=6$$.
$$2!=\frac{3!}{3}=2$$.
$$1!=\frac{2!}{2}=1$$.
Và phần thú vị là đây, chắc hẳn bạn đã thấy một quy luật xuất hiện rồi chứ, vậy từ đó ta được $0!=\frac{1!}{1}=1$ dẫn đến kết quả $0!=1$.
Mở rộng thêm, giả sử số giai thừa áp dụng được cho số nguyên âm thì sao? Nếu thế thì theo quy luật trên, ta có $-1!=\frac{0!}{0}=\frac{1}{0}$, điều này là hoàn toàn vô lý do mẫu số không thể bằng $0$.
Một cách lý giải khác cho kết quả $0!=1$, nếu như bạn nào học về Tổ hợp thì sẽ biết được $n!$ tương ứng với số cách mà bạn có thể hoán đổi vị trí của $n$ vật thể, giả sử tôi có $3$ đồng xu như thế này:
Sẽ có $3!=6$ cách đổi thứ tự các đồng xu, cụ thể:
Nếu ta lấy 1 đồng xu ra, ta còn lại 2 đồng xu và có $2!=2$ cách đổi chỗ 2 đòng xu này, cụ thể:
Lấy thêm 1 đồng xu nữa, ta còn 1 đồng xu, và ta có $1!=1$ cách đổi chỗ đồng xu này.
Bây giờ ta lấy đi đồng xu cuối cùng, cái này hơi trừu tượng một chút, ta lấy đi đồng xu cuối, bây giờ ta có $0$ vật thể, vậy có bao nhiêu cách hoán vị $0$ vật thể đó? Có 1 cách, chính là đây:
Khá là trừu tượng, nhưng thực sự chỉ có $1$ cách để dịch chuyển $0$ vật thể, vì vậy một lần nữa ta được $0!=1$.
Bây giờ ta thử biểu diễn trên trục tọa độ $Oxy$ xem sao, trục $Ox$ ứng với các giá trị $1; 2; 3; ...$, còn trục $Oy$ ứng với kết quả của $1!, 2!, 3!, ...$, vẽ các điểm và nối lại, ta được hình sau:
Từ hình vẽ, tôi dự đoán đồ thị cắt trục $Oy$ tại $1$ từ đó dẫn đến kết quả $0!=1$
Nhắc đến đồ thị, về lý thuyết, mỗi điểm trên đồ thị ứng với 1 giá trị $x;y$, giả sử tôi chọn 1 điểm bất kỳ trên trục $Ox$, giữa $1$ và $2$, giả sử là $\frac{3}{2}$, thế $\frac{3}{2}!$ bằng bao nhiêu? Các nhà toán học hiện thực hóa ý tưởng về phép tính này bằng hàm Gamma, chẳng hạn $\frac{3}{2}!=\Gamma(?)$ hay tổng quát hơn là $\Gamma (n)$, người ta nói
$$\Gamma (n)=\int_{0}^{\infty }t^{n-1}.e^{-t}\ dt$$.
Lúc này sẽ có 1 số người thấy quen thuộc phép tích phân này, một số thì chưa, đây là 1 ý tưởng rất là phức tạp, nhưng điều này có thể giải thích cho phép tính giai thừa.
Còn một vấn đề nữa, điều này thì không mấy ai mong đợi xảy ra, nhưng nếu chúng ta lấy tất cả các giá trị để tính giai thừa (tức tập $\mathbb{R}$), giả sử giá trị đó là $\Gamma (z), z\in\mathbb{R}$
Ta được $\Gamma (n)=(n-1)!$. Một số giá trị đặc biệt của hàm Gamma là:
Vậy ý nghĩa của việc có được 1 hàm số giúp bạn tính giai thừa cho mọi giá trị mà bạn không thể thực hiện được phép hoán vị vật thể là gì? Chẳng hạn có bao nhiêu cách hoán vị $\frac{3}{2}$ vật thể? Đó là hàm số có tính tổng quát và rất hữu ích trong nhiều vấn đề, đơn cử như toán xác suất nơi bạn có thể tìm thấy cách tính giai thừa.
