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

[dunglamson]

 

Bài 1: Một số nguyên dương n được gọi là số thân thiện nếu tồn tại một số tập con khác rỗng A1,A2,…,An của tập hợp {1,2,3,…,n} thỏa mãn:

i∉Ai,

i∈Aj⇔j∉Ai(i≠j),

Ai∩Aj≠∅.

Chứng minh rằng n≥7 khi và chỉ khi n là số thân thiện.

 

Bài 2: Có bao nhiêu tập con gồm 3 phần tử của tập X là n số nguyên dương đầu tiên sao cho tổng phần tử chia hết cho n. 

đây là hai bài tổ hợp rất khó, ai làm được thì quá giỏi luôn, mời mọi người thử sức

[hxthanh]

to dunglamson

Không định trả lời bạn vì topic đã vi phạm nội quy tiêu đề, không gõ LATEX + spam thêm một bài viết thừa. Nếu VMF mà giống như MS thì topic này đã bị đóng lại

Lời giải Bài 2:

Diễn đạt lại bài toán:

Từ tập $X=\{1,2,...,n\}$ có bao nhiêu tập con $M=\{a,b,c\}$ sao cho $a+b+c=n$ hoặc $a+b+c=2n$

 

Xét hệ điều kiện thứ nhất:

$\begin{cases}a+b+c=n\\a<b<c\\ a,b,c\in\{1,2,...,n\}\end{cases}$

 

Ta có: $n=a+b+c\ge a+(a+1)+(a+2)\Rightarrow a\le \left\lfloor\frac{n}{3}\right\rfloor-1$

Với mỗi giá trị của $a$, đặt $b=a+x$ còn lại $c=n-2a-x$

Từ điều kiện $b<c$ suy ra $a+x<n-2a-x$ Suy ra $x\le \left\lfloor\frac{n-3a-1}{2}\right\rfloor$

Như vậy ta có số nghiệm của hệ là:

$A=\sum_{a=1}^{\left\lfloor\frac{n}{3}\right\rfloor-1}\left\lfloor\frac{n-3a-1}{2}\right\rfloor$

Tổng này sau khi tính toán rồi rút gọn lại thì được (cái này khá dài dòng)

 

$A=(n-2)\left\lfloor\frac{n}{6}\right\rfloor-3\left\lfloor\frac{n}{6}\right\rfloor^2-\left\lfloor\frac{n-1}{6}\right\rfloor$

 

Xét hệ điều kiện thứ hai

$\begin{cases}a+b+c=2n\\a<b<c\\ a,b,c\in\{1,2,...,n\}\end{cases}$

Tương tự ta cũng có: $a\le \left\lfloor\frac{2n}{3}\right\rfloor-1$

Rồi ta cũng đặt các số $a;\; a+x;\; 2n-x-2a$

với chú ý là $2n-x-2a\le n\Rightarrow x\ge n-2a$

$a+x<2n-x-2a\Rightarrow x<n-\frac{3a}{2}$

Từ đây với $a$ chẵn thì $x$ nhận $\frac{a}{2}$ giá trị, với $a$ lẻ thì $x$ nhận $\frac{a+1}{2}$ giá trị

 

 

Hệ này hơi phức tạp hơn...

... đang tìm cách xử lý!

[hxthanh]

Bài toán:

Cho tập $X=\{1,2,...,n\}$. Có bao nhiêu tập con $M=\{a,b,c\}$ thỏa mãn $n\; \mid\; a+b+c$

Sau một ngày "hại não" tôi đã giải quyết được trọn vẹn bài này

 

Diễn đạt theo các điều kiện của bài toán, ta có bài toán đếm nghiệm của hai hệ sau:

$\begin{cases}a+b+c=n\\ 1\le a<b<c\le n\end{cases}\quad(1){}\quad$ và ${}\quad\begin{cases}a+b+c=2n\\1\le a<b<c\le n\end{cases}\quad(2)$

 

$\boxed{\text{Xét Hệ điều kiện }(1)}$

Như lập luận ở trên, ta dẫn đến tổng:

$A=\sum_{a=1}^{\left\lfloor\frac{n}{3}\right\rfloor-1}\left\lfloor\frac{n-3a-1}{2}\right\rfloor$

$\quad =\sum_{a=1}^{\left\lfloor\frac{n}{3}\right\rfloor-1}\left(\left\lfloor\frac{n-1-a}{2}\right\rfloor-a\right)$

$\quad =-\frac{1}{2}\left\lfloor\frac{n}{3}\right\rfloor\left(\left\lfloor\frac{n}{3}\right\rfloor-1\right)+\underbrace{\sum_{a=1}^{\left\lfloor\frac{n}{3}\right\rfloor-1}\left\lfloor\frac{n-1-a}{2}\right\rfloor}_{S_1}$

Ta có:

$\quad S_1=\sum_{a=2}^{\left\lfloor\frac{n}{3}\right\rfloor}\left\lfloor\frac{n-a}{2}\right\rfloor\quad\text{(Tịnh tiến)}$

$\Rightarrow 2S_1=\left\lfloor\frac{n-2}{2}\right\rfloor+\left\lfloor\dfrac{n-\left\lfloor\frac{n}{3}\right\rfloor}{2}\right\rfloor+\sum_{a=2}^{\left\lfloor\frac{n}{3}\right\rfloor-1}\left(\left\lfloor\frac{n-1-a}{2}\right\rfloor+\left\lfloor\frac{n-a}{2}\right\rfloor\right)$

$\Rightarrow 2S_1=\left\lfloor\frac{n-2}{2}\right\rfloor+\left\lfloor\dfrac{n-\left\lfloor\frac{n}{3}\right\rfloor}{2}\right\rfloor+\sum_{a=2}^{\left\lfloor\frac{n}{3}\right\rfloor-1}(n-1-a)\quad\text{(Hermite's identity)}$

Đến đây ta gặp tổng cơ bản rồi! Tuy nhiên biểu thức nhận được của tổng này khá dài dòng.

Sử dụng phép thế $n=6p+r$ với $p=\left\lfloor\frac{n}{6}\right\rfloor$ và $r=n-6\left\lfloor\frac{n}{6}\right\rfloor=\{0,1,2,3,4,5\}\quad(*)$

$(*)$ mỗi giá trị tương ứng với các số dư của $n$ khi chia cho $6$.

Thay vào biểu thức tìm được rồi rút gọn lại ta được:

 

$A=3p^2+p\{-3,-2,-1,0,1,2\}+\{1,0,0,0,0,0\}$

$\quad=3p^2+p(r-3)-\left\lfloor\frac{r-1}{6}\right\rfloor$

$\quad=3\left\lfloor\frac{n}{6}\right\rfloor^2+\left\lfloor\frac{n}{6}\right\rfloor\left(n-6\left\lfloor\frac{n}{6}\right\rfloor-3\right)-\left\lfloor\frac{n-6\left\lfloor\frac{n}{6}\right\rfloor-1}{6}\right\rfloor$

$\quad=(n-2)\left\lfloor\frac{n}{6}\right\rfloor-3\left\lfloor\frac{n}{6}\right\rfloor^2-\left\lfloor\frac{n-1}{6}\right\rfloor$

 

$\boxed{\text{Xét Hệ điều kiện }(2)}$

Ta có:

$2n=a+b+c\ge a+(a+1)+(a+2)\Rightarrow a\le\left\lfloor\frac{2n}{3}\right\rfloor-1$

$a+1\le b\le c-1\le n-1$

$b+1\le c\le n$

Lưu ý rằng với $x,y$ nguyên dương thì

$\quad\Delta_x\left(\left\lfloor\frac{x}{y}\right\rfloor\right)=\left\lfloor\frac{x+1}{y}\right\rfloor-\left\lfloor\frac{x}{y}\right\rfloor=\begin{cases}1\quad\text{nếu } y\mid x+1\\0\quad\text{các trường hợp khác}\end{cases}\quad(**)$

Do đó ta quy các điều kiện về tổng:

$B=\sum_{a=1}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\sum_{b=a+1}^{n-1}\sum_{c=b+1}^n \Delta_c\left(\left\lfloor\frac{a+b+c-1}{2n}\right\rfloor\right)$

$\quad =\sum_{a=1}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\sum_{b=a+1}^{n-1}\left(\left\lfloor\frac{a+b+n}{2n}\right\rfloor-\left\lfloor\frac{a+2b}{2n}\right\rfloor\right)$

$\quad=\underbrace{\sum_{a=1}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\sum_{b=a+1}^{n-1}\left\lfloor\frac{a+b+n}{2n}\right\rfloor}_{S_2}-\underbrace{\sum_{a=1}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\sum_{b=a+1}^{n-1}\left\lfloor\frac{a+2b}{2n}\right\rfloor}_{S_3}$

 

Đối với 2 tổng $S_2$ và $S_3$ ta cần vận dụng tới các kỹ thuật tính toán SPTP, phân đoạn modul-2 và tính chất $(**)$ nữa mới giải quyết ổn thỏa!

 

$\boxed{\text{Xét Tổng }S_2}$

Ta có:

$S_2=\sum_{a=1}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\sum_{b=a+1}^{n-1}\left\lfloor\frac{a+b+n}{2n}\right\rfloor\Delta(b)$

$\quad=\sum_{a=1}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\left(b\left\lfloor\frac{a+b+n}{2n}\right\rfloor\Bigg|_{b=a+1}^n-\underbrace{\sum_{b=a+1}^{n-1}(b+1)\Delta_b\left(\left\lfloor\frac{a+b+n}{2n}\right\rfloor\right)}_{S_4}\right)$

 

Theo tính chất $(**)$ thì tổng $S_4$

 

$S_4=\sum_{b=a+1}^{n-1}(b+1)\Delta_b\left(\left\lfloor\frac{a+b+n}{2n}\right\rfloor\right)=\begin{cases}\sum_{b=a+1}^{n-1}(b+1)\quad\text{với } 2n\mid a+b+n+1 \text{ và } a+1\le b\le n-1\\ 0\quad\text{ các trường hợp khác}\end{cases}$

 

Nên với $a+b+n+1=2n$ hay $b=n-1-a\ge a+1$ suy ra $a\le \left\lfloor\frac{n}{2}\right\rfloor-1$ thì

$S_4=b+1=n-a$. Các trường hợp khác $S_4=0$

Do đó:

$S_2=\sum_{a=1}^{\left\lfloor\frac{n}{2}\right\rfloor-1}\left(b\left\lfloor\frac{a+b+n}{2n}\right\rfloor\Bigg|_{b=a+1}^n-(n-a)\right)+\sum_{a=\left\lfloor\frac{n}{2}\right\rfloor}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}\left(b\left\lfloor\frac{a+b+n}{2n}\right\rfloor\Bigg|_{b=a+1}^n\right)$

$=\sum_{a=1}^{\left\lfloor\frac{n}{2}\right\rfloor-1}(n-n+a)+\sum_{a=\left\lfloor\frac{n}{2}\right\rfloor}^{\left\lfloor\frac{2n}{3}\right\rfloor-1}(n-(a+1).1)$

(Căn cứ vào đoạn biến thiên của $a$ để có được điều trên)

Đến đây ta coi như đã tính được $S_2$

 

$\boxed{\text{Xét Tổng }S_3}$

Tổng này ta phải phân loại tính chẵn lẻ của $a$ để rồi chia $S_3$ thành $2$ tổng nữa. Sau đó mỗi tổng được tính tương tự như $S_2$

....

Cuối cùng ta được kết quả (chưa rút gọn là

 

$B=S_2-S_3$

$\quad =\left\lfloor\frac{n}{2}\right\rfloor^2-n\left\lfloor\frac{n}{2}\right\rfloor+\frac{1}{2}\left((2n-1)\left\lfloor\frac{2n}{3}\right\rfloor-\left\lfloor\frac{2n}{3}\right\rfloor^2+\left\lfloor\frac{n}{3}\right\rfloor-\left\lfloor\frac{n}{3}\right\rfloor^2-\left\lfloor\frac{n-2}{3}\right\rfloor\left\lfloor\frac{n-1}{3}\right\rfloor\right)$

 

Sử dụng phép thế $n=6p+r$ với $p=\left\lfloor\frac{n}{6}\right\rfloor$ và $r=n-6\left\lfloor\frac{n}{6}\right\rfloor=\{0,1,2,3,4,5\}$

Thay vào biểu thức tìm được rồi rút gọn lại ta được:

 

$B=3p^2+p\{0,1,2,3,4,5\}+\{0,0,0,1,1,2\}$

$\quad =(n-3)\left\lfloor\frac{n}{6}\right\rfloor-3\left\lfloor\frac{n}{6}\right\rfloor^2+\left\lfloor\frac{n}{3}\right\rfloor+\left\lfloor\frac{n+1}{6}\right\rfloor$
 

CUỐI CÙNG TA CÓ ĐÁP SỐ CỦA BÀI TOÁN LÀ

Số các tập con 3 phần tử của tập $n$ số nguyên dương đầu tiên thỏa mãn điều kiện tổng các phần tử chia hết cho $n$ là:

 

$S_n=A+B=\boxed{\displaystyle (2n-5)\left\lfloor\frac{n}{6}\right\rfloor-6\left\lfloor\frac{n}{6}\right\rfloor^2+\left\lfloor\frac{n}{3}\right\rfloor+\left\lfloor\frac{n+1}{6}\right\rfloor-\left\lfloor\frac{n-1}{6}\right\rfloor}$

 

Một số giá trị của $S_n$

 

 NoSwFF.pdf   221.26K   113 Số lần tải

[ntuan5]

Bài 2 ý tưởng của em là dùng số phức, không biết có đúng không : Xét đa thức $x^{n}-1=0$ có n nghiệm phức: $a,a^2,...,a^{n}; a^{n}=1$ . Lấy tâp $ A= L \subset X |L|=3 $ sao cho $A_{j}=L \in A: S(L) = j (mod n)$.

Ta có : $x^{n}-1=(x-a)...(x-a^n)$ hệ số của $n-3$ đồng nhất được : $0=(-1)^{3} \sum_{A}a^{S(A)}= \sum_{A} a^j=\sum_{j=0}^{n-1}|A_j|a^i=0 (mod n)$. Mà $a$ cũng là nghiệm của $x^{n-1}+...+1$ nên $A_i=A_j$.

Vậy $A_{0}=\frac{{}_{n}^{3}\textrm{C}}{n}$.

[hxthanh]

Bài 2 ý tưởng của em là dùng số phức, không biết có đúng không : Xét đa thức $x^{n}-1=0$ có n nghiệm phức: $a,a^2,...,a^{n}; a^{n}=1$ . Lấy tâp $ A= L \subset X |L|=3 $ sao cho $A_{j}=L \in A: S(L) = j (mod n)$.

Ta có : $x^{n}-1=(x-a)...(x-a^n)$ hệ số của $n-3$ đồng nhất được : $0=(-1)^{3} \sum_{A}a^{S(A)}= \sum_{A} a^j=\sum_{j=0}^{n-1}|A_j|a^i=0 (mod n)$. Mà $a$ cũng là nghiệm của $x^{n-1}+...+1$ nên $A_i=A_j$.

Vậy $A_{0}=\frac{{}_{n}^{3}\textrm{C}}{n}$.

Không rõ em làm có "chuẩn" không nhưng có vẻ như đúng ý tưởng thật!

Kết quả của lời giải phía trên, được biểu diễn qua $n=6p+\{0,1,2,3,4,5\}$ là

$S=6p^2+p\{-3,-1,1,3,5,7\}+\{1,0,0,1,1,2\}$

 

Trong khi đó, với biểu diễn tương đương, ta cũng có:

 

$\left\lceil\frac{(n-1)(n-2)}{6}\right\rceil=1+\left\lfloor\frac{n(n-3)}{6}\right\rfloor=6p^2+p\{-3,-1,1,3,5,7\}+\{1,0,0,1,1,2\}$

[ntuan5]

Cảm ơn thầy! Bài làm của em bị sai ở chỗ phương trình không có nghiệm phân biệt, có vẻ nó chỉ đúng khi n nguyên tố.

[hxthanh]

Sau khi tìm được cách rút gọn hơn nữa biểu thức kết quả thì tôi tìm được
$S=1+ \left\lfloor \frac{n(n-3)}{6} \right\rfloor = \left\lceil \frac{(n-1)(n-2)}{6} \right\rceil$

 

Nhìn kết quả cuối cùng là khá đẹp, quả thực tôi không thể hài lòng với lời giải hết sức phức tạp của mình, tôi đã post bài này lên AoPS, hy vọng một cao thủ nào đó "xử đẹp" được bài này.
Cuối cùng thì admin Dưa bở! (MelowMelon) đã làm cho tôi toại nguyện với một lời giải vô cùng tinh tế, và đậm chất TỔ HỢP.

Tôi xin tạm dịch lời giải của MelowMelon như sau:

- Trước tiên ta đếm số bộ ba $(a, b, c)$, $1\le a,b,c\le n$ có tổng chia hết cho $n$ bao gồm cả việc bị lặp lại.
+ Với mỗi cặp $(a, b)$ thì có duy nhất $c$ thỏa mãn tổng chia hết cho $n$. Kết quả của phép đếm này là $A=n^2$
+ Xét các bộ 3 dạng $(a, a, b)$. Cũng vậy với mỗi $a$ thì có duy nhất $b$ thỏa mãn $n\mid 2a+b$. Kết quả phép đếm này là $B=n$
+ Xét các bộ 3 dạng $(a, a, a)$.

• Nếu $3\nmid n$ thì có duy nhất bộ $(n, n, n)$ thỏa mãn
• Nếu $3\mid n$ thì có $3$ bộ thỏa mãn là $(n/3, n/3, n/3);\;\;(2n/3, 2n/3, 2n/3)$ và $(n, n, n)$

Kết quả phép đếm này là $C= \begin{cases}1:\quad 3\nmid n \\ 3:\quad 3\mid n \end{cases}$
 
Theo nguyên lý bao gồm-loại trừ ta có:
Số bộ 3 $(a, b, c)$ trong đó $a,b,c$ đôi một khác nhau có tổng chia hết cho $n$ là:
$T=A-3B+2C= \begin{cases} n^2-3n+2\; :\quad 3\nmid n \\ n^2-3n+6\; :\quad 3\mid n \end{cases}$
Kết quả của $T$ đem chia cho $3!=6$ (hoán vị của $a,b,c$), ta được số tập con cần tìm!

 

 
Hoàn toàn phù hợp với kết quả mà tôi tìm được!