Chủ đề này có 3 trả lời

[ducvipdh12]

Đây là nơi để tổng hợp các bài toán phần tổ hợp rời rạc chọn lọc trên VMF,các bài toán sẽ được các ĐHV cập nhật liên tục,các thành viên xem bài toán bằng cách ấn vào BÀI...

BÀI 1: Cho $n\in \mathbb{Z^*}$.Xét tất cả các tổng:

$S=x_1y_1+x_2y_2+...+x_ny_n$ với $x_i,y_i\in \left \{ 0;1 \right \},\forall i=\overline{1,n}$

Gọi $S_n$ là số tổng lẻ,$P_n$ là số tổng chẵn.CMR:

$\frac{S_n}{P_n}=\frac{2^n-1}{2^n+1}$

BÀI 2: Một con châu chấu nhảy trên một đường thẳng .Bước đầu tiên nhảy được $1$ cm ,bước thứ hai nhảy được $2$ cm ... cứ tiếp tục nhảy về trái hoặc phải .CMR sau $2015$ bước nó không về được vị trí ban đầu

BÀi 3 : Có bao nhiêu cách bỏ 35 viên bi giống nhau vào 5 hộp khác nhau sao cho: mỗi hộp 1 và 2 không có 0, 1, 2, 7, 8, 9 hoặc 10 bi; hộp 3 ít nhất 2 và nhiều nhất 9 bi; và hộp 4 và 5 không giới hạn bi.

BÀI 4 : Một ngân hàng mini (rất khan hiếm tiền lẻ) chỉ có $13$ tờ tiền mệnh giá $1.000$ đồng, 16 tờ tiền mệnh giá $2.000$ đồng,11 tờ tiền mệnh giá $5.000$ đồng,còn lại số tiền mệnh giá $20.000$ đồng là không hạn chế!

Có $90$ khách hàng đến giao dịch rút tiền,đều cần rút đến số tiền lẻ ( dưới $100.000$ đồng )  tất cả đều khác nhau và đặc biệt không có số nào chia hết cho  $10.000$ đồng ( $1...9;11...19;...;91...99$ đồng )

Hỏi ngân hàng trên đáp ứng được yêu cầu tối đa bao nhiêu khách hàng?

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 15-07-2015 - 10:45

[ducvipdh12]

BÀI 5 : CMR: $\sum_{i=k}^{n}\frac{1}{C_i^k}=1+\frac{1}{k-1}-\frac{C_{n-1}^{k-1}}{C_{n-1}^{k-2}.C_n^k}$

BÀI 6 : Gọi $A$ là tập hợp các số tự nhiên thỏa mãn đồng thời các tính chất sau : 

1. Phần tử nhỏ nhất của A là 1 , phần tử lớn nhất của $A$ là 100

2. Mọi phần tử khác 1 của A đều bằng tổng 2 phần tử thuộc A (có thể bằng nhau)

Gọi $S(n)$ là số phần tử của A . Tìm GTNN của $S(n)$

BÀI 7 : Với $n,m$ là các số nguyên dương, chứng minh đẳng thức sau:

$$\Large \sum_{k=0}^n (-1)^k{m-1\choose k}{m\choose n-k}=(-1)^{\left\lfloor\frac{n}{2}\right\rfloor} {m-1\choose \left\lfloor\frac{n}{2}\right\rfloor}$$

BÀI 8 : Có 3366 nhà phê bình điện ảnh bỏ phiếu cho giải Oscar. Mỗi một nhà phê bình bỏ phiếu cho đúng 1 nam diễn viên và đúng 1 nữ diễn viên. Sau khi các nhà phê bình bỏ phiếu xong, người ta thấy rằng với mỗi n thuộc {1, 2, ..., 100} đều có một nam diễn viên hoặc 1 nữ diễn viên được đúng n phiếu. Chứng minh rằng tồn tại 2 nhà phê bình bỏ phiếu như nhau (tức là bỏ phiếu cho cùng 1 nam diễn viên và 1 nữ diễn viên).

(Balkan MO 2015)

BÀi 9 : Cho 1 đa giác đều 20 cạnh nội tiếp 1 đường tròn, chọn ngẫu nhiên 3 đỉnh. Tính xác suất để thu được 1 tam giác tù.

BÀI 10 : Trên mặt phẳng lấy cho 1999 điểm phân biệt tùy ý. Chứng minh rằng có một đường thẳng đi qua một điểm duy nhất trong 1999 điểm đã cho chia mặt phẳng thành hai miền không giao nhau sao cho mỗi miền chứa đúng 999 điểm trong các điểm đã cho.

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 22-07-2015 - 10:58

[ducvipdh12]

BÀI 11 : Cho hình vuông có kích thước $9x9$. Hỏi phải tô màu ít nhất bao nhiêu ô vuông đơn vị để luôn chọn được $1$ hình vuông $2x2$ có ít nhất $3$ ô màu đỏ

BÀI 12 : Trong một cuộc hội thảo, cứ $10$ người thì có đúng 1 người quen chung. Tìm số người quen lớn nhất của $1$ người

BÀI 13 : Có thể lập được bao nhiêu số có 6 chữ số, sao cho số 1 có mặt tối đa 5 lần, các số 2, 3, 4 mỗi số có mặt tối đa 1 lần.

BÀI 14 : Có bao nhiêu  tam giác nhọn có đỉnh là đỉnh của đa giác đều 2014 cạnh

BÀI 15 : Có bao nhiêu tam giác có độ dài các cạnh là các số tự nhiên không vượt quá $2n$

[Near Ryuzaki]

BÀI 11 : Cho hình vuông có kích thước $9x9$. Hỏi phải tô màu ít nhất bao nhiêu ô vuông đơn vị để luôn chọn được $1$ hình vuông $2x2$ có ít nhất $3$ ô màu đỏ

BÀI 12 : Trong một cuộc hội thảo, cứ $10$ người thì có đúng 1 người quen chung. Tìm số người quen lớn nhất của $1$ người

BÀI 13 : Có thể lập được bao nhiêu số có 6 chữ số, sao cho số 1 có mặt tối đa 5 lần, các số 2, 3, 4 mỗi số có mặt tối đa 1 lần.

BÀI 14 : Có bao nhiêu  tam giác nhọn có đỉnh là đỉnh của đa giác đều 2014 cạnh

BÀI 15 : Có bao nhiêu tam giác có độ dài các cạnh là các số tự nhiên không vượt quá $2n$

Bài 15 . Em thấy bài cuối cùng  bài 15) hay hay xử lí luôn ,nếu đổi thành tam giác không cân có lẽ bài toán sẽ hay hơn

Tam giác bình thường đã có lời giải ở link rồi em chém trường hợp không cân như em đã nói.

Đặt độ dài các cạnh : $2n-i,2n-j,2n-k$ với $i\neq j \neq k$

Xét các tập $X=\begin{Bmatrix}1;2;3;...;2n\end{Bmatrix}$

$A=\begin{Bmatrix}{(x,y,z)\in X^3\mid x<y<z;x+y>z}\end{Bmatrix}$

và $A_k=\begin{Bmatrix}(x,y,z)\in A\mid z=k \end{Bmatrix}$

Khi đó $\left | A_1 \right |=\left | A_2 \right |=\left | A_3 \right |=0$

Xét $k \geq 4$. Chia ra làm 2 trường hợp :

TH1: $k=2m.$ Vì $x+y> 2x$ nên ta phân ra làm 2 trường hợp nhỏ :

TH1.1 : $2x\leq z\Rightarrow x\leq \frac{z}{2}=m\Rightarrow 1\leq x\leq m$

Mặt khác $x+y>z\Rightarrow y\geq z-x+1=2m-x+1$

Do đó suy ra $2m-x+1\leq y\leq 2m-1$

Có $(2m-1)-(2m-x+1)+1=x-1$ giá trị $y.$

Suy ra có $\sum_{x=1}^{m}(x-1)=\frac{m(m-1)}{2}$ bộ $(x,y,z)\in A_k$ 

TH1.2 : $2x>z\Leftrightarrow x>m\Leftrightarrow x\geq m+1\Rightarrow m+1\leq x\leq 2m-2$

Vì $x<y<z$ suy ra $x+1\leq y\leq z-1$

Có $(z-1)-(x+1)+1=2m-x-1$ giá trị $y.$

Suy ra có $\sum_{x=m+1}^{2m-2}(2m-x-1)=\frac{(m-1)(m-2)}{2}$ bộ $(x;y;z)\in A_k$

Do vậy $\left | A_k \right |=\frac{m(m-1)}{2}+\frac{(m-1)(m-2)}{2}=(m-1)^2;k=2m$

TH2: $k=2m+1$

Tương tự ta được $\left | A_k \right |=m(m-1);k=2m+1$

Vậy nên $\left | A \right |=\sum_{i=1}^{n}\left | A_{2i} \right |+\sum_{i=0}^{n-1}\left | A_{2i+1} \right |=...$

P/s: ủng hộ anh tiếp tục sưu tầm thêm nhiều bài

Bài viết đã được chỉnh sửa nội dung bởi Near Ryuzaki: 30-07-2015 - 16:39