Lâu lắm rồi mình chưa thấy người lập ra topic này - Bạn Hoangkhanh2002 và các mem qua topic. Vì vậy, hôm nay mình sẽ quyết định viết tiếp chuyên đề mới; mình nghĩ chuyên đề PT-BĐT kết thúc ở đây được rồi do PT thì các bài tập trên topic + kiến thức HSG là đủ thi chuyên, còn BĐT thì đang được thảo tiếp tục thảo luận tại topic của bạn Tăng trong box BĐT - Cực trị. Mong các bạn hưởng ứng
$\boxed{\text{Chuyên đề}}$ Tổ hợp - Toán rời rạc
I)Một số phương pháp giải cơ bản
1, Nguyên lý Dirichlet: Giả sử dùng n hộp để cất r vật thì tồn tại 1 hộp chứa ít nhất $[\frac{r}{n}]$ vật
Ví dụ : Chứng minh tồn tại $k\in \mathbb{N}$ sao cho $1983^k-1\vdots 10^5$
Cho k lần lượt $10^5+1$ giá trị liên tiếp từ 1 trở đi ta được $10^5+1$ giá trị khác nhau của $1983^k-1$. Theo nguyên lý Dirichlet thì tồn tại hai số trong các số trên có cùng số dư khi chia cho $10^5$; giả sử là $1983^i-1$ và $1983^j-1$ (i>j)
$\Rightarrow (1983^i-1)-(1983^j-1)\equiv 0(mod 10^5)\Rightarrow 1983^j(1983^{i-j}-1)\equiv 0(mod 10^5)$
mà $gcd(1983,10)=1$ nên ta có $1983^{i-j}\equiv 0(mod 10^5)$(đpcm)
2,Nguyên tắc cực hạn: Trong một tập hợp hữu hạn các phần tử; luôn tồn tại một phần tử có giá trị lớn nhất; một phần tử có giá trị nhỏ nhất
Ví dụ: Trên một đường thẳng cho 1 tập hợp điểm M sao cho mỗi trung điểm của đoạn nối hai điểm thuộc M là một điểm thuộc M. Chứng minh tập hợp M là một tập hợp vô hạn
Giả sử đường thẳng đã cho được đặt nằm ngang và tập hợp M hữu hạn
Khi đó trong M tồn tại một điểm nằm tận cùng bên trái. Giả sử là A, rõ ràng vì A nằm tận cùng bên trái nên A không thể là trung điểm của bất cứ đoạn nào nối hai điểm thuộc M (vô lý). Vậy tập hợp M vô hạn
3,Đại lượng bất biến : có thể hiểu là một đại lượng không đổi sau một hoặc một số thao tác
Ví dụ: Trên một cái bảng ghi các số : 1;2;3;...;2002. Ta thực hiện các thao tác sau: xóa hai số bất kì trên bảng và thay bằng tổng hoặc hiệu của chúng. Hỏi số còn lại cuối cùng trên bảng có thể là số 0 hay không?
Ta thấy rằng khi thay hai số a và b bằng $a-b$ (hoặc $a+b$) thì tổng các số trên bảng giảm (hoặc tăng) 2b là một số chẵn. Do đó tính chẵn lẻ
của tổng các số trên bảng luôn không đổi tính chẵn lẻ (Đây chính là bất biến)
mà $1+2+3+...+2002$ là một số lẻ nên số cuối cùng trên bảng phải là số lẻ. Vậy số cuối cùng trên bảng không thể là số 0
Mình khởi đầu bằng hai bài
$\boxed{1}$ Chứng minh rằng trong 5 số mà trong mỗi số chỉ có ước nguyên tố là 3 và 5 tồn tại hai số mà tích của chúng là số chính phương
$\boxed{2}$ Cho một hình chữ nhật 5 x m gồm các ô vuông 1 x 1. Cho biết rằng có thể đặt các quân domino kích thước 1 x 2 vào hình chữ nhật sao cho quân domino phủ kín hình chữ nhật và trong hai ô 1 x 1 của quân domino; có một ô chứa dấu $(+)$ và một ô chứa dấu $(-)$; tích của dấu trong các ô trong cùng một hàng và trong cùng một cột đều dương.
Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 13-05-2017 - 21:27
)
