quocbaolqd11

Bạn giải sai rồi nhé

Đáp số đúng là : $2n!\left [ n!+\sum_{i=1}^{2n}\left ( -1 \right )^i\frac{2n}{2n-i}C_{2n-i}^{i}\left ( n-i \right )! \right ]$

anh góp ý là cách viết công thức có vấn đề. Nếu $i$ chạy tới $2n$ thì ta sẽ có $\frac{2n}{0}.\binom{0}{2n}.(n-2n)!$. Và chắc chắn công thức này sai.

----------------------------------------------------------------------

Đã sửa

Gọi $T'$ là tập không chứa $A_i$ sao cho $|T'|$ đạt max. Như vậy, với bất kì tập $T''=T \cup \{x\}$ thì $T''$ chứa $A_i$. 
Giờ ta sẽ đếm số bộ $(A_i,m,n)=k$ với $m \neq n \in T'$ và $m,n \in A_i$. Vì  $|A_i \cap A_j| \le 1$ nên:
                                                                $k \le C_{|T'|}^{2}$  
Mà với mỗi $p \in A\setminus T'$, ta xác định được duy nhất một phần tử thuộc bộ $(A_i,m,n)$. Vậy nên:
                                                                $k \ge n-|T'|$ 
Từ đó, ta có: $C_{|T'|}^{2} \ge n-|T'|$. Giải bpt, ta được đpcm.

Đề bài này có vấn đề.Có lẽ nên sửa lại như thế này :

Cho tập hợp $X=\left \{ 1,2,3,...,n \right \}\subset \mathbb{N}$.Gọi $A$ là tập con của $X$ thỏa mãn điều kiện $\forall a,b\in A$ ($a> b$) ta đều có $a\vdots b$

Tìm số nguyên dương $m$ NHỎ nhất (hay LỚN nhất) sao cho $\left | A \right |=m$.

 

Giải :

+ Nếu là tìm số nguyên dương $m$ NHỎ nhất sao cho $\left | A \right |=m$ thì dễ thấy $m=2$ (khi đó $A=\left \{ 1,k \right \}$ trong đó $k\in X$ và $k\neq 1$)

 

+ Nếu là tìm số nguyên dương $m$ LỚN nhất sao cho $\left | A \right |=m$ :

Khi đó các phần tử của $A$ sẽ là $2^0;2^1;2^2;2^3;...;2^{m-1}$

Trong đó $2^{m-1}\leqslant n< 2^m\Leftrightarrow m-1\leqslant log_{2}n< m$

Hay $m=p+1$ với $p$ là phần nguyên của $log_{2}n$

Bạn hiểu sai ý đề rồi. $m$ nhỏ nhất để luôn có hai phần tử $a,b$ và $a \vdots b$ chứ không phải là $m$ nhỏ nhất để có thể có 2 phần tử $a,b$ mà $a \vdots b$. Mình nghĩ đáp án là $m=t+1$ với t là số các số nguyên tố trong $[1;n]$. Mà việc tìm $t$ thì minh chưa nghĩ ra. Nếu cho $n$ cụ thể thì sẽ dễ hơn nhiều.

 Mình nghĩ là $k=3$ là đáp án, với $k=3$ thì có thể chia được thành các tập:
$A_1 =\{7,8,9,11,14,17,...\} \\
  A_2 =\{4,5,6,10,12,15,18,...\} \\
  A_3 =\{1,2,3,13,16,19,22,...\}  \\$

dễ thấy $A_1 \cup A_2 \cup A_3=N$ nên $k=3$ đúng.
Chứng minh $k \ge 4$ không chia được.
gọi $a_k^{(i)}$ là phần tử thứ $k \in A_i$.
giả sử tồn tại $k \ge 8$ chia được.
ta có 15 có 7 cách chia thành $a+b$ với $a \neq b$, mà có 8 tập nên phải có 2 tập có giao khác rỗng, vô lí.
vậy $k \le 7$.
dễ thấy $k=7$ cũng không đúng vì 15 có 7 cách chia thành dạng $a+b$ nên cả cách chia phải nằm vào 7 tập khác nhau.
Xét số 16, khi đó $a_k^{(i)}+a_{k'}^{(i)}=16$ với mọi $i \le 7; k \neq k'$
mà 16 cũng chỉ có 7 cách chia thành dạng $a+b$ nên sẽ tồn tại tập con có chung 2 phần tử (vô lí).
$k=6$, $k=5$, $k=4$ chứng minh tương tự (thực ra bạn chỉ cần chứng minh với TH $k=4$ là đủ rồi, chứng min hTH $k=4$ thì phải dùng đến phân tích của 17 thành $a+b$).
bài này là bài C4 IMO SL 2011, bạn có thể tham khảo thêm lời giải khác .

Gọi :

$P=A\B$ (gồm các phần tử thuộc $A$ mà không thuộc $B$)

$Q=B\A$ (gồm các phần tử thuộc $B$ mà không thuộc $A$)

$R=A\cap B$ và $S=\overline{A}\cap \overline{B}$ ($P,Q,R,S$ từng đôi một không giao nhau)

$A$ ko là tập con của $B$ và $B$ ko là tập con của $A$ khi và chỉ khi $P$ và $Q$ đều không rỗng.

Gọi số phần tử của $P,Q,R,S$ lần lượt là $p,q,r,s$ ---> $p+q+r+s=n$.Xét các TH sau :

$1)$ $p+q=2$ ($p,q\neq 0$) ; $r+s=n-2$

+ Chọn $2$ trong $n$ phần tử ---> $C_{n}^{2}$ cách

+ Xếp mỗi phần tử đẫ chọn vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{2}-2$ cách

+ Xếp mỗi phần tử còn lại vào $R$ hoặc $S$ ---> $2^{n-2}$ cách

$\Rightarrow$ TH 1 có $C_{n}^{2}.(2^2-2).2^{n-2}=C_{n}^{2}.(2^n-2^{n-1})$ cách chọn bộ $(A,B)$

 

$2)$ $p+q=3$ ($p,q\neq 0$) ; $r+s=n-3$

+ Chọn $3$ trong $n$ phần tử ---> $C_{n}^{3}$ cách

+ Xếp mỗi phần tử đẫ chọn vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{3}-2$ cách

+ Xếp mỗi phần tử còn lại vào $R$ hoặc $S$ ---> $2^{n-3}$ cách

$\Rightarrow$ TH 2 có $C_{n}^{3}.(2^3-2).2^{n-3}=C_{n}^{3}.(2^n-2^{n-2})$ cách chọn bộ $(A,B)$

 

$3)$ $p+q=4$ ($p,q\neq 0$) ; $r+s=n-4$

+ Chọn $4$ trong $n$ phần tử ---> $C_{n}^{4}$ cách

+ Xếp mỗi phần tử đẫ chọn vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{4}-2$ cách

+ Xếp mỗi phần tử còn lại vào $R$ hoặc $S$ ---> $2^{n-4}$ cách

$\Rightarrow$ TH 3 có $C_{n}^{4}.(2^4-2).2^{n-4}=C_{n}^{4}.(2^n-2^{n-3})$ cách chọn bộ $(A,B)$

...............................................................................

..............................................................................

 

$n-1)$ $p+q=n$ ($p,q\neq 0$) ; $r+s=0$

+ Xếp mỗi phần tử (trong $n$ phần tử) vào $P$ hoặc $Q$ sao cho $P$ và $Q$ đều không rỗng ---> $2^{n}-2$ cách

$\Rightarrow$ TH n-1 có $C_{n}^{n}.(2^n-2)$ cách chọn bộ $(A,B)$

 

Cộng tất cả n-1 TH trên lại $\Rightarrow$ tổng số cách chọn là :

$(C_{n}^{2}+C_{n}^{3}+...+C_{n}^{n}).2^n-(C_{n}^{2}.2^{n-1}+C_{n}^{3}.2^{n-2}+...+C_{n}^{n}.2)=(C_{n}^{2}+C_{n}^{3}+...+C_{n}^{n}).2^n-2(C_{n}^{2}.2^{n-2}+C_{n}^{3}.2^{n-3}+...+C_{n}^{n}.2^0)=(2^n-n-1).2^n-2(3^n-2^n-n.2^{n-1})=2^{2n}+2^n-2.3^n$ cách chọn.

 

Chẳng hạn khi $n=3$ thì có $2^6+2^3-2.3^3=18$ cách chọn 2 tập $A$ và $B$ thoả mãn ĐK bài toán (Ban LNH kiểm tra lại)

mình thấy cũng không cần phải giải cầu kì như thế.
để tính số cặp $(A,B)$ thỏa yêu cầu đề thì ta phải tính số bộ $(A,B)$ mà $A \subset B$ hoặc $B \subset A$.
nếu $B \subset A$. Xét phần tử $x \in X$ bất kì, khi đó $x$ luôn có 3 cách chọn là:"thuộc B; không thuộc B nhưng thuộc A và  không thuộc cả 2", mà có tất cả $n$ phần tử nên có $3^n$ bộ $(A,B)$ mà $B \subset A$. Tương tự vậy với các bộ mà $A \subset B $. Giờ xét bộ $(A,B)$ mà A vừa là con của B mà B cũng là con của A thì khi đó $A=B$ và số bộ $(A,B)$ là $2^n$ (số tập con của X). vậy số bộ $(A,B)$ mà $A \subset B$ hoặc $B \subset A$ = số bộ $B \subset A$+số bộ $B \subset A$-số bộ A vừa là con của B mà B cũng là con của A $=2.3^n-2^n$.
từ đó, số bộ thỏa ycđb là $4^n-2.3^n+2^n$.

cho tập hợp $A=\{1,2,...,2011^{2012}\}$. Chứng minh rằng tồn tại 1 hoán vị của A là $B=\{a_1,a_2,...,a_{2011^{2012}}\}$ sao cho với mọi $1 \le i<j<k \le 2011^{2012}$ thì $a_i+a_j \neq 2a_j$.

câu a mình có 1 cách làm rất thủ công .
Đầu tiên có nhận xét là không thể đưa về cấu hình (0,0,...,0) với 0 thay cho đèn tắt và 1 thay cho đèn bật.
khi đó để tất cả đèn bật thì ta phải đưa về cấu hình sao cho chỉ có duy nhất 1 số 1 trong dãy.
Ta sẽ chỉ ra sau 1 số bước thì nó sẽ về cấu hình trên.
gọi $a_i$ là vị trí của số 1 thứ i trong dãy. Ta có: số số 1 được thêm vào trong bảng là $a_2-a_1$ số 1 nếu $a_2>a_1+1$ và giảm 1 nếu $a_2=a_1+1$.  Tiếp tục như vậy với các bộ kia. Sau khi thực hiện qua bước $n+1$ (tức là thực hiện 1 vòng mới) thì khi đó bộ $a_2-a_1$ số 1 đầu tiên $(1,1,...,1)$ sẽ giảm còn 1 nửa nếu số các số 1 trong khoảng $a_2-a_1$ số đó chẵn và $[\frac{(a_2-a_1)}{2}]+1$ nếu $(1,1,1,1,1,...)$ lẻ. Với TH lẻ thì số cuối cùng không bị đổi nên qua các bước sẽ biến tất cả các số 0 đứng sau nó thành số 1 và sẽ dừng sau khi biến đổi số 1 thành số 0 (số 1 ở đây là số 1 đầu tiên giữa 2 bộ $a_2-a_1$ với bộ $a_3-a_2$). Tiếp tục biến đổi thì bộ $(1,0,1,0,...,1,0,1,1,1,1,...)$ sẽ dần thành bộ $(1,0,0,...,0,1,0,1,0,...)$ (được như vậy là do sau khi thực hiện với $n+1$ bước đầu, ta quay lại làm hết từ đầu)  mà có 1 số chẵn cặp $1,0$, từ 1 bộ chẵn $1,0$ đó biến đổi tiếp thành được bộ $(1,1,0,0,0,0,...)$ và từ đó số số 1 giảm đi so với ban đầu. Vậy nên áp dụng nhiều lần như vậy, ta sẽ đưa về được Th chỉ có 1 số 1 trong cấu hình.
Thực ra thì dài nữa, nhưng mà thấy trâu quá nên viết vậy thôi ...
câu b, câu c hơi thâm thúy nên chưa nghĩ ra (bạn post lời giải của bạn lên được không ?).

 

Ta giải bài này bằng pp đếm bằng 2 cách. Ta sẽ đếm số bộ (học sinh, clb, clb, clb, clb, clb, clb, clb)

Cách 1: Có $800$ cách chọn $1$ học sinh. Vì mỗi học sinh tham gia không quá $7$ CLB nên số bộ trên không quá $800$

Cách 2: Có $C^7_n$ cách chọn $7$ CLB. Vì $7$ CLB có ít nhất 1 học sinh tham gia nên số bộ lớn hơn hoặc bằng $C^7_n$

Suy ra $C^7_n\leq 800$

$\Rightarrow n \leq 12$

Vậy GTLN của $n$ là $12$

đến đây chưa xong đâu Hoàng. Em phải chỉ ra dấu bằng cho $n=12$ nữa, nếu không có bước này vẫn chưa khẳng định được $n=12$ max đâu. Thực ra không cần đếm số bộ như trên, chỉ cần giải thích :
vì cứ 7 câu lạc bộ lại có ít nhất 1 học sinh tham gia và số học sinh tham gia theo 7 clb bất kì (giao của 7 câu lạc bộ bất kì) không vượt quá số học sinh của trường (do đk 1) nên có bđt: $\binom{n}{7} \le 800 \rightarrow n \le 12$ .

gợi ý câu 1a): chứng minh quy nạp rằng các số N có dạng $2^{k}.p$ với $p=p_1.p_2...p_{n}$ là 1 "vị trí thua", từ đó suy ra người đi trước với $N=2010$ là người thua.

p/s: mình có nhầm 1 tí, chứng minh quy nạp các số dạng $2^a.k$ với k là số lẻ, $a \in \{1,3\}$ là những "vị trí thua", lưu ý $2^a.k$ với $a \in \{2,4,5,6,...\}$ không phải là 1 "vị trí thua". vì $2010=2.1005$ là 1 số có dạng "vị trí thua" nên người đi đầu luôn thua.

Xét bài toán tổng quát:

Tập $A=\{1,2,3,4,...,2N-1,2N\}$

Cần tìm số tập con có $n+m$ phần tử với $n$ phần tử chẵn, $m$ phần tử lẻ, và không có $2$ phần tử nào liên tiếp!

Gọi số đó là $S_N(n,m)$

Ta chia tập $A$ thành $N$ cặp liên tiếp:

$A=\{1,2\}\cup\{3,4\}\cup\ldots\cup\{2N-1,2N\}$

 

Giả sử ta chọn ra $n$ số chẵn trong $n$ cặp, khi đó các số lẻ trong các cặp đó sẽ không được chọn. Như vậy ta có $C_{N-n}^m$ cách chọn $m$ số lẻ. Lập luận tương tự ta cũng có số cách chọn ra $n$ số chẵn là $C_{N-m}^n$

 

Vậy $S_N(n,m)=C_{N-n}^m.C_{N-m}^n$.

 

Ví dụ $S_5(1,3)=C_4^3.C_2^1=8$

Cụ thể $A=\{1,2,3,4,5,6,7,8,9,10\}$

$\{1,3,5,8\};\quad\{1,3,5,10\};\quad\{1,3,6,9\};\quad\{1,3,7,10\};\quad\{1,4,7,9\};\quad\{1,5,7,10\};\quad\{2,5,7,9\};\quad\{3,5,7,10\}$

em nghĩ lời giải có chút vấn đề ở chỗ tô đỏ, nó không chỉ không được chọn số còn lại trong cặp đã phân hoạch mà còn không được chọn cả số ở trong tập liền kề nữa. Ví dụ như $\{2k-1,2k\}$ và $\{2k+1,2k+2\}$ nếu như ta chọn $2k$ thì không chỉ có $2k-1$ không được chọn mà kéo theo cả $2k+1$ không được chọn nên chưa chắc chỉ có $N-m$ số lẻ là được phép lựa vào tập hợp. Em nghĩ phải tách chỗ này ra thành các tập mà các số được lẻ (chẵn) chọn là các bộ số có dạng $(a,b)$ mà $a-b=2$ và các bộ mà $a-b \ge 4$.

Cho $m, n$ nguyên dương , $S = \{ 1, 2, ... , 2014 \}$ . Tìm số tập con của $S$ có $m$ số chẵn, $n$ số lẻ và không chứa $2$ số liên tiếp.

đề thi chọn đội tuyển khtn vừa rồi. Mình thấy có lời giải của 1 bạn trên diễn đàn nhưng chưa chính xác lắm vì lời giải ấy không đề cập gì đến $m, n$. Mong các thành viên của diễn đàn và các bạn khtn thi đợt vừa rồi giúp đỡ.

Giả sử $x_1,x_2,...,x_n$ là các phần tử của tập $X$. Kí hiệu $S_i$ là tập các tập $A_j$ mà chứa phần tử $x_i$.

Giả sử $n\geq 2^{m}$.

Ta có tất cả $n$ tập $S_i$, mỗi tập $S_i$ là một cách chọn ra một bộ $A_j_1,A_j_2,...A_j_k$ nên tối đa ta có $2^{m}-1$ cách chọn tập $S_i$   (là số các tập con của tập có $m$ phần tử)

Mà ta có $n\geq 2^{m}$ tập $S_i$, nên theo nguyên tắc Dirichle tồn tại hai tập $S_i$ và $S_t$ trùng nhau, hay khi đó các phần tử $x_i$ và $x_t$ là các phần tử chung của cùng một số tập trong các tập $A_i$.

Khi đó $2$ phần tử này không thỏa mãn điều kiện của bài toán nên ta có mâu thuẫn.

Vậy $n<2^{m}$.

mình nghĩ $S_i$ có thể rỗng vì điều kiện của bài toán là với $x,y \in X$ thì luôn tồn tồn tại $A_k$ thỏa $x \notin A_k$ và $y \in A_k$ nên mình sẽ cho $x_i$ không thuộc bất kì tập nào trong m tập con dạng $A_k$ và tất cả $n-1$ phần tử còn lại đều thuộc các tập trên.

Bài 4: IMO 2012 (kể ra tỉnh này cho đề đểu thật )

Bài 5: Gọi $u_k$ là số dãy số $\left ( x_1,...,x_{k} \right )$ thoả yêu cầu đề bài

Xét $u_{k+1}$

$x_{k}\neq a$

Có 2 TH:

TH1: $x_{k-1}=a$

Số dãy thoả mãn đk trên là $2u_{k-1}$

TH2: $x_{k-1}\neq a$

Số dãy thoả mãn đk trên là $u_{k}$

Vậy số dãy thoả mãn yêu cầu đề bài là $u_{k+1}=u_{k}+2u_{k-1}$ với $k \geq 3$

hoặc cũng có thể là $a_n+a_{n+1}=2^{n-1}$ nếu làm theo hướng : đặt $a_n$ là số dãy thỏa $x_1=1$ và $x_n=a$; $b_n$ là số dãy thỏa $x_n=b$ và $x_1=1$, $c_n$ là số dãy thỏa $x_n=c$ và $x_1=1$, khi đó dễ có ctth: $a_{n+1}=b_n+c_n$ và $a_n+b_n+c_n=2^{n-1}$ ($n \ge 3$). Suy ra ctth đã nêu ở đầu với $a_3=2$

Cái này hơi dở vì dễ quên cách tính sai phân. (trong thi quên mất công thức sai phân thế là không tìm được cttq, mất 0,5 điểm uổng phí)

Câu nghiệm nguyên , trước hết một số chính phương là $x^{2}$ thì $x^{2}\equiv 0,1(mod3)$

Nhưng $3^{n}+5\equiv 2(mod3)$ nên không có $n$ thỏa mãn 

Câu hình : mọi người tự vẽ nhé 

Giả sử $BH$ cắt $AC$ ở $D$ và $CH$ cắt $AB$ ở $E$ 

Theo hệ thức lượng trong tam giác vuông ta có $AB_{1}^{2}=AD.AC$ và $AC_{1}^{2}=AE.AB$

Ta lại chứng minh được hai tam giác $ACE$ và $ABD$ đồng dạng ( chung góc vuông và đỉnh $A$ )

Nên ta có đpcm .

Phần câu giới hạn thì mọi người có thể tự làm và cm nó hữu hạn , còn phần tìm giới hạn

Giả sử $lim u_{n}=a$ khi đó ta có $lim u_{n+1}=lim u_{n}^{2}-lim u_{n}$ hay $2lim u_{n}=lim u_{n}^{2}$ 

Hay $2a=a^{2}$ , bằng quy nạp ta chứng minh giới hạn của dãy không thể là $2$ , nên $a=0$ do đó $lim u_{n}=0$ 

cách chuyển qua giới hạn này không chính xác vì dãy $u_{2k+1}$ giảm và $u_{2k}$ tăng. Với lại bài này hay ở chứng minh được nó có giới hạn.

Cho tập hợp $ A=\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\} .$ Có thể phân hoạch $A$ thành $3$ tập con rời nhau, mỗi tập gồm $5$ phần tử sao cho trong mỗi tập không có số nào bằng tổng của hai số trong tập đó  ( hai số có thể giống nhau) được không (ví dụ:tập $ B=\{ 1,2,6,10,15 \} $ thì không thỏa mãn do $ 2=1+1$ ? Hãy chứng minh bài toán tổng quát với $3n$ (n lẻ ). Bài này mình có cách làm xét quá nhiều trường hợp, liệt kê ra chắc cũng phải hơn trang giấy, mong mọi người giúp đỡ cách hay hơn.

lời giải trên sai nhé, xét mấy TH đầu của bảng $2 \times n$ là thấy ngay. Và thêm nữa là bạn chưa xét trường hợp viên gạch chữ L phủ vào 3 ô $n,n+1,2n+2$ hay $n+1,2n+2,2n+1$.