Đến nội dung

Hình ảnh

TOPIC tổng hợp các bài toán tổ hợp rời rạc xuất phát từ các kì thi MO,các tạp chí các nước

- - - - -

  • Please log in to reply
Chủ đề này có 37 trả lời

#21
ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết

Bài 10 ( Balkan 2012 ):

Cho $n$ là số nguyên dương. Đặt tập hợp $P_n=\left \{ 2^n,2^{n-1}.3,2^{n-2}.3^2,...,3^n \right \}$. Với mỗi tập con $X$ của $P_n$, đặt $S_X$ là tổng tất cả các phần tử trong $X$, ở đây$S_\varnothing =0$. Cho $y$ là 1 số thực thỏa mãn điều kiện $0\leq y\leq 3^{n+1}-2^{n+1}$. Chứng minh rằng tồn tại một tập con $Y$ của $P_n$ thỏa mãn điều kiện $0< y-S_Y< 2^n$


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#22
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Bài 9 ( VMO ):
Cho tập $S=\left \{ 1,2,...,n \right \}$. Gọi $T$  là tập tất cả các tập con không rỗng của $S$. Với mỗi $X$ thuộc $T$, gọi $m(X)$ là trung bình cộng các phần tử của $X$. Tính $m=\frac{\sum m(X)}{\left | T \right |}$

Bài này ở đâyhttp://diendantoanho...xt/#entry462662

#23
Huy Thong

Huy Thong

    Binh nhì

  • Thành viên
  • 16 Bài viết

Bài 8 ( Liên Xô 1965 ) :

Trong cuộc hội thảo có 40 cuộc họp, mỗi cuộc họp có 10 thành viên. Cho biết hai thành viên bất kì chỉ cùng dự họp với nhau tối đa một lần. Chứng minh rằng cuộc hội thảo có nhiều hơn 60 thành viên.

Gọi số thành viên là $n.$

Ta xét bảng gồm $n$ cột và $40$ dòng. Mỗi cột tương ứng với $1$ thành viên và mỗi dòng ứng với $1$ cuộc họp.

Tại dòng $j$ cột $i$ ta viết số $1$ nếu thành viên $i$ tham gia cuộc họp $j$ và viết số $0$ nếu thành viên đó không tham gia.

Vì hai thành viên bất kì chỉ cùng dự họp với nhau tối đa một lần nên không tồn tại $4$ số $1$ trên bảng tạo thành một hình chữ nhật.

Gọi $a_i$ là số số $1$ trên cột $i.$ Vì mỗi cuộc họp có $10$ thành viên nên $\sum_{i=1}^{n}a_i=400.$

Ta đếm số cặp số $1$ trên từng cột theo hai cách.

   $\cdot$ Số cặp số $1$ trên cột $i$ là $\dfrac{a_i(a_i-1)}{2}$

Do đó tổng số cặp số $1$ trên từng cột trong bảng là $\sum_{i=1}^{n} \dfrac{a_i(a_i-1)}{2}$

   $\cdot$ Vì không tồn tại $4$ số $1$ trên bảng tạo thành một hình chữ nhật nên khi chiếu các cặp số $1$ xuống phương thẳng đứng sẽ không tồn tại hai cặp số $1$ trùng nhau nên số cặp số một trên từng cột trong bảng không vượt quá $C_{40}^{2}=780$

Do đó $\sum_{i=1}^{n} \dfrac{a_i(a_i-1)}{2}\leq 780 \Leftrightarrow \sum_{i=1}^{n}a_i^2 \leq 1560+\sum_{i=1}^{n}a_i=1960$

Theo bất đẳng thức $C-S,$ ta có $1960\geq \dfrac{\left ( \sum_{i=1}^{n}a_i \right )^2}{n} \Leftrightarrow n\geq \frac{400^2}{1960}>81>60.$

 

 

Bài 9 ( VMO ):

Cho tập $S=\left \{ 1,2,...,n \right \}$. Gọi $T$  là tập tất cả các tập con không rỗng của $S$. Với mỗi $X$ thuộc $T$, gọi $m(X)$ là trung bình cộng các phần tử của $X$. Tính $m=\frac{\sum m(X)}{\left | T \right |}$

Cách khác: Với mỗi tập con $X$ của $S.$ Ta xét tập con $X'=\left \{ n+1-a\ \mid a\in X \right \}.$ Suy ra $m(X)+m(X')=n+1.$

Vì mỗi tập con $X$ xác định được duy nhất tập $X'$ và $X'$ là tập con của $S$ nên $2\sum m(X)=\sum m(x)+m(X')=(n+1)\left | T \right |$

Từ đó ta có $m=\frac{n+1}{2}.$


Bài viết đã được chỉnh sửa nội dung bởi Huy Thong: 23-06-2015 - 21:38


#24
huonggiangcute

huonggiangcute

    Binh nhì

  • Thành viên
  • 15 Bài viết

Bài 2 ( Thụy Sĩ 2006 ): 

Tính số tập con $X=\left \{ 1,2,...,2n \right \}$ sao cho không tồn tại $2$ phần tử có tổng bằng $2n+1$

Nhờ xem đáp án em nghĩ ra hướng giải như sau  :luoi: 
Chia $X$ thành $n$ nhóm $(1,2n);\;(2,2n-1);\;...;(n,n+1)$
Cứ mỗi nhóm có 3 khả năng 
- Không chọn bất kì số nào
-Chọn 1 trong 2 số 
Chung quy lại có 3 cách 
Vì có $n$ nhóm nên đáp số sẽ là $3^{n}$ (vì tính cả tập rỗng)
Ps: Nếu không tính tập rỗng thì đáp án sẽ là 
$3^{n} -1$
 



#25
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Nhờ xem đáp án em nghĩ ra hướng giải như sau  :luoi: 
Chia $X$ thành $n$ nhóm $(1,2n);\;(2,2n-1);\;...;(n,n+1)$
Cứ mỗi nhóm có 3 khả năng 
- Không chọn bất kì số nào
-Chọn 1 trong 2 số 
Chung quy lại có 3 cách 
Vì có $n$ nhóm nên đáp số sẽ là $3^{n}$ (vì tính cả tập rỗng)
Ps: Nếu không tính tập rỗng thì đáp án sẽ là 
$3^{n} -1$
 

Cách làm không thể tuyệt vời hơn!



#26
ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết

Gọi số thành viên là $n.$

Ta xét bảng gồm $n$ cột và $40$ dòng. Mỗi cột tương ứng với $1$ thành viên và mỗi dòng ứng với $1$ cuộc họp.

Tại dòng $j$ cột $i$ ta viết số $1$ nếu thành viên $i$ tham gia cuộc họp $j$ và viết số $0$ nếu thành viên đó không tham gia.

Vì hai thành viên bất kì chỉ cùng dự họp với nhau tối đa một lần nên không tồn tại $4$ số $1$ trên bảng tạo thành một hình chữ nhật.

Gọi $a_i$ là số số $1$ trên cột $i.$ Vì mỗi cuộc họp có $10$ thành viên nên $\sum_{i=1}^{n}a_i=400.$

Ta đếm số cặp số $1$ trên từng cột theo hai cách.

   $\cdot$ Số cặp số $1$ trên cột $i$ là $\dfrac{a_i(a_i-1)}{2}$

Do đó tổng số cặp số $1$ trên từng cột trong bảng là $\sum_{i=1}^{n} \dfrac{a_i(a_i-1)}{2}$

   $\cdot$ Vì không tồn tại $4$ số $1$ trên bảng tạo thành một hình chữ nhật nên khi chiếu các cặp số $1$ xuống phương thẳng đứng sẽ không tồn tại hai cặp số $1$ trùng nhau nên số cặp số một trên từng cột trong bảng không vượt quá $C_{40}^{2}=780$

Do đó $\sum_{i=1}^{n} \dfrac{a_i(a_i-1)}{2}\leq 780 \Leftrightarrow \sum_{i=1}^{n}a_i^2 \leq 1560+\sum_{i=1}^{n}a_i=1960$

Theo bất đẳng thức $C-S,$ ta có $1960\geq \dfrac{\left ( \sum_{i=1}^{n}a_i \right )^2}{n} \Leftrightarrow n\geq \frac{400^2}{1960}>81>60.$

 

 
 

Cách khác: Với mỗi tập con $X$ của $S.$ Ta xét tập con $X'=\left \{ n+1-a\ \mid a\in X \right \}.$ Suy ra $m(X)+m(X')=n+1.$

Vì mỗi tập con $X$ xác định được duy nhất tập $X'$ và $X'$ là tập con của $S$ nên $2\sum m(X)=\sum m(x)+m(X')=(n+1)\left | T \right |$

Từ đó ta có $m=\frac{n+1}{2}.$

Bài 8 còn được giải ngắn gọn thế này:

Giả sử cuộc hội thảo có $n$ thành viên

Do đó có $C_n^2$ cách chọn 2 thành viên

Có $C_{10}^2$ cách chọn 2 thành viên từ 1 cuộc họp. Do 2 thành viên chỉ cùng dự họp với nhau tối đa 1 lần nên $C_n^2\geq 40.C_{10}^2$ tương đương $n(n-1)\geq 3600$ hay $n>60$


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#27
ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết

Bài 11 ( IMO 1988 ):

Cho $n,k$ là các số nguyên dương, $n\geq k$ và $S$ là tập hợp $n$ điểm trong mặt phẳng thỏa mãn 

$(i)$ Không có 3 điểm nào thẳng hàng

$(ii)$ Với mỗi điểm $P$ của hệ đều không có ít hơn $k$ điểm trong hệ cách đều $P$

Chứng minh rằng $k\leq \frac{1}{2}+\sqrt{2n}$


FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#28
Bui Ba Anh

Bui Ba Anh

    Thiếu úy

  • Thành viên
  • 562 Bài viết

Bài 11 ( IMO 1988 ):

Cho $n,k$ là các số nguyên dương, $n\geq k$ và $S$ là tập hợp $n$ điểm trong mặt phẳng thỏa mãn 

$(i)$ Không có 3 điểm nào thẳng hàng

$(ii)$ Với mỗi điểm $P$ của hệ đều không có ít hơn $k$ điểm trong hệ cách đều $P$

Chứng minh rằng $k\leq \frac{1}{2}+\sqrt{2n}$

Giải: Quy ước mỗi cặp điểm $(A,B)$ là những cặp không kể thứ tự

Dễ thấy với $n$ nguyên thì dấu bằng không thể xảy ra.Ta phản chứng rằng $k \geq \frac{1}{2}+\sqrt{2n}<=>(2k-1)^2 \geq 8n$

Với mỗi điểm thuộc $S$, chẳng hạn $A$ thì có ít nhất $k$ điểm cách đều $A$, như vậy có ít nhất $C_{k}^2$ cặp điểm thuộc $S$ mà $A$ thuộc đường trung trực của đoạn thẳng nối hai điểm này

Xét $M=\left \{ \left \{ (X,Y),A \right \}\in S^2.S|AX=AY \right \}$ thì mỗi bộ thuộc $M$ là phân biệt

Như vậy theo trên thì $|M| \geq n.C_{k}^2$ 

Mà $n.C_{k}^2=\frac{n(k-1)k}{2}>2.\frac{n(n-1)}{2}=2.C_{n}^2<=> (2k-1)^2 \geq 8n$ 

Như vậy ta liên tưởng đến ý nghĩa tổ hợp là: Số cách chọn cặp điểm sao cho tồn tại điểm khác thuộc $S$ nằm trên trung trực của đoạn nối $2$ điểm đó lớn hơn $2$ lần số cách chọn cặp điểm bất kì của $S$

Theo đi-rich-lê, ta suy ra tồn tại $3$ cặp điểm trong mỗi bộ của $M$ trùng nhau, tức là $XY$ là trung trực của $3$ điểm khác, suy ra $3$ điểm này thẳng hàng(vô lí) đpcm

Spoiler


Bài viết đã được chỉnh sửa nội dung bởi Bui Ba Anh: 25-06-2015 - 13:54

NgọaLong

#29
khanghaxuan

khanghaxuan

    Trung úy

  • Thành viên
  • 969 Bài viết

Bài 12 (IMO shortlist 2001) : Trong một kì thi chọn học sinh giỏi toán cấp nhà có $20$ thí sinh nữ và $20$ thí sinh nam . Trong đó , mỗi thí sinh chỉ được giải nhiều nhất $6$ bài toán , với mỗi cặp nam và nữ , có ít nhất 1 bài toán được giải bởi cả thí sinh nam và thí sinh nữ . Chứng minh rằng tồn tại một bài toán được giải bởi ít nhất 3 thí sinh nam và ít nhất 3 thí sinh nữ .

 

Spoiler

@BBAnh: Câu này đề chính luôn mà thím


Bài viết đã được chỉnh sửa nội dung bởi Bui Ba Anh: 26-06-2015 - 17:09

Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#30
GizmoIt

GizmoIt

    Lính mới

  • Thành viên
  • 6 Bài viết

Bài 13: Có 3 đống sỏi với số sỏi lần lượt là $5,49,51$ viên sỏi. Ta thực hiện các bước đi theo quy tắc: Tại mỗi bước ta chọn 2 đống và nhập thành 1 đống hoặc chọn một đống có sổ chẵn viên sỏi rồi chia đống đó thành 2 đống nhỏ bằng nhau. Hỏi có thể thu được 105 đống sỏi, mỗi đống 1 viên sau một số hữu hạn bước được hay không?


Bài viết đã được chỉnh sửa nội dung bởi GizmoIt: 26-06-2015 - 15:54


#31
khanghaxuan

khanghaxuan

    Trung úy

  • Thành viên
  • 969 Bài viết

Bài 14 : Ở mỗi ô của bảng $mxn$ ta điền một số nguyên không âm . Hai số được điền trong bảng được gọi kề  nhau nếu ô chứa hai số đó có chung cạnh (chú ý : Hai ô có chung bất kì góc nào cũng không gọi là kề) . Một cách điền được gọi là sung sướng nếu thỏa mãn đồng thời hai điều kiện sau : 

a) Trị tuyệt đối của hiệu của hai ô kề nhau chỉ là $0$ hoặc $1$

b) Nếu một số nhỏ hơn tất cả các ô kề với nó thì số đó phải là $0$

Hãy xác định số các cách điền sung sướng thỏa mãn đề bài . 


Bài viết đã được chỉnh sửa nội dung bởi khanghaxuan: 28-06-2015 - 16:55

Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#32
marcoreus101

marcoreus101

    Thượng sĩ

  • Thành viên
  • 235 Bài viết

Topic nhạt quá :(, em đóng góp 1 bài

Bài 15 (VMO 2010) Cho bảng $3\times 3$, $n$ là một số nguyên dương cho trước,tìm số cách tô màu không như nhau khi tô mỗi ô bởi 1 trong $n$ màu

Hai cách tô được gọi là như nhau nếu mỗi một cách nhận được từ cách kia bằng phép quay tâm



#33
hoangtubatu955

hoangtubatu955

    Sĩ quan

  • Thành viên
  • 429 Bài viết

Bài 2 ( Thụy Sĩ 2006 ): 

Tính số tập con $X=\left \{ 1,2,...,2n \right \}$ sao cho không tồn tại $2$ phần tử có tổng bằng $2n+1$

Các cặp có tổng thành $2n+1$ là:

$(1,2n); (2,2n-1);...;(n,n+1)$.
Các tập con của $X$ thỏa mãn thì đều không chưa cặp nào trong $n$ tập trên. Như vậy số tập con thỏa mãn chính là số cách chọn các phần tử sao cho không tồn tại cặp nào. Mỗi cặp thì hoặc là chọn 1 số trong 2 số hoặc không chọn bất kì số nào. Tức mỗi cặp có 3 cách chọn, hay số tập thỏa mãn là $3^n$.



#34
ducvipdh12

ducvipdh12

    Sĩ quan

  • Thành viên
  • 454 Bài viết

lời giải bài 10 :

Ta có $S_{P_n}=3^n+3^{n-1}.2+...+3^2.2^{n-2}+3.2^{n-1}+2^n=3^{n+1}-2{n+1}$

Bằng cách chia cách phần tử của $P_n$ cho $2^n$ ta đưa bài toán về dạng tương đương như sau:

Cho n là số nguyên dương, $a=\frac{3}{2}$, và $Q_n=\left \{ 1,a,a^2,...,a^n \right \}$. Chứng tỏ rằng với mỗi giá trị của x thỏa mãn $0\leq x\leq 1+a+a^2+...+a^n$ luôn tồn tại một tập con X của $Q_n$ sao cho $0\leq x-S_X< 1$. Ta chứng minh bằng quy nạp theo n. Khi n = 1 thì $S_0=0,S_1=1,S_a=\frac{3}{2},S_{1,a}=\frac{5}{2}$. Từ đây kiểm chứng thấy ngay là nếu x là một số thực thỏa $0\leq x\leq \frac{5}{2}$ thì luôn có một tập con X của $Q_1$ thỏa yêu cầu.

Giả sử kết quả bài toán đúng đến số nguyên dương n
Xét x là một số thực với $0\leq x\leq 1+a+a^2+...+a^{n+1}$
+/ Nếu $0\leq x\leq 1+a+...+a^n$ thì theo giả thiết quy nạp tồn tại tập con $X\subset Q_n\subset Q_{m+1}$ thỏa $0\leq x-S_X< 1$
+/ Xét với $x> 1+a+...+a^n$. Khi đó vì 
$\frac{a^{{n+1}}-1}{a-1}=\frac{a^{{n+1}}-1}{\frac{3}{2}-1}=2(a^{n+1}-1)=a^{n+1}-(a^{n+1}-2)> a^{n+1}$
khi đó bài toán được chứng minh 

FAN THẦY THÔNG,ANH CẨN,THẦY VINH :icon6: :icon6:

#35
longtrang00

longtrang00

    Lính mới

  • Thành viên
  • 4 Bài viết

Mình muốn tham gia góp 1 bài thế này:

  • Cho bảng ô vuông n*n (với n lẻ). CMR số nước đi mà không nhấc bút ra khỏi giấy để đi hết bảng là lớn hơn hoặc bằng 2n-1.


#36
IHateMath

IHateMath

    Thượng sĩ

  • Thành viên
  • 299 Bài viết

Bài 16 (IMOSL 1995):

Trong một cuộc họp, có $12k$ người tham gia, mỗi người bắt tay với đúng $3k+6$ người khác. Biết rằng với  bất kì một cách chọn cặp 2 người ta có số người bắt tay với cả 2 là như nhau. Hỏi có bao nhiêu người trong cuộc họp đó?


Bài viết đã được chỉnh sửa nội dung bởi IHateMath: 10-02-2016 - 21:30


#37
Mai Thanh Huy

Mai Thanh Huy

    Lính mới

  • Thành viên mới
  • 7 Bài viết

Bài 17: Cho |A|=n. Có bao nhiêu cách chọn 2 tập X,Y là tập con của A và X,Y không có phần tử nào chung



#38
tientethegioi

tientethegioi

    Binh nhì

  • Thành viên
  • 12 Bài viết

 

Bài 17: Cho |A|=n. Có bao nhiêu cách chọn 2 tập X,Y là tập con của A và X,Y không có phần tử nào chung

 

Chia thành 3 tập $X, Y, Z$ thì mỗi phần tử $a$ có 3 cách chọn lựa. Với $X,Y$ thì giao nhau là rỗng. Nhưng kể cả thứ tự thì $X,Y$ và $Y,X$ được đếm 2 lần. Chú ý tập rỗng cũng thỏa mãn $$\frac{3^n+1}{2}$






1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh