Ðề tài: Topic thử LaTeX
Xem bài viết đơn
Old 01-03-2014, 11:00 PM   #92
Kelacloi
+Thành Viên+
 
Tham gia ngày: Mar 2011
Bài gởi: 252
Thanks: 50
Thanked 164 Times in 114 Posts
Đáp số bài của em là $n!$


Anh xài điều sau:
NẾu $n$ có k ước nguyên tố $p_1,p_2,..,p_k$
$a_{l n}+\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|}.a_{l \frac{n}{\prod_{ i \in I} p_i}}=n$ nếu $l=n$ và bằng $0$ nếu $l<n$



Dưới đây là chứng minh bằng tập hợp, có lẽ xài quy nạp với 1 chút số học là ra nhưng mà anh lỡ làm bằng tập hợp rồi.
KHó hiểu lắm, em thử chứng minh cái đẳng thức trên bằng cách khác hén

Đặt $X_a( A)$ (với A là 1 tập hợp ) là hàm thỏa điều sau :$X_a(A)=| \{a\} \cap A | $

Đặt $S_n=\{ m: m|n,m>0\}$ tức là $S_n$ là tập hợp các ước của $S_n$.
Giả sử $n$ có $k$ ước nguyên tố là $p_1,p_2,...,p_k$.

Ta có điều sau đây:
i) $S_i \cap S_j= S_{(i,j)}$
ii) Nếu $I \subset \{ 1,2,...,k\}$ thì $ \bigcap_{ i \in I} S_{n/p_i}= S_{ \frac{n}{\prod_{ i \in I} p_i}}$
iii) Với $ A \subset B$ thì \sum_{a \in A} a= \sum_{a \in B} a.X_a(A)$
Quay lại bài toán , ta có chứng minh cái này trước:
I:) $ \bigcup_{ i \in \{ 1,2,...,k\} } S_{n/p_i}=$$\{ m : m|n , 0<m<n\}$$= S_n$\$ \{n\}$

II:)
Theo nguyên ly Inclusion-Exclusion thì :

$ X_a( \bigcup_{ i \in \{ 1,2,...,k\} } S_{n/p_i})=\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_a( \bigcap_{ i \in I} S_{n/p_i} ) $
$=\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_a(S_{ \frac{n}{\prod_{ i \in I} p_i}}) $ (theo ii )

rộng hơn là $X_a( \bigcup_{ i \in \{ 1,2,...,k\} } (C\cap S_{n/p_i}))=\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_a(C\cap S_{ \frac{n}{\prod_{ i \in I} p_i}})$

Trở lại bài toán.

Từ i) ta thấy điều sau: $ a_{ij} = \sum_{ x \in S_i \cap S_j } x=\sum_{x \in \overline {1,n}} x.X_x( S_i \cap S_j )$(*)

Từ I,II ,iii ta mở rộng được thành điều sau:

$ \sum_{x \in C\cap S_n} x=\sum_{ x \in \overline{1,n}} x.X_x( C\cap S_n)=n.X_n(C \cap S_n)+\sum_{ x \in \overline{1,n-1}} x.X_x( C\cap \bigcup_{ i \in \{ 1,2,...,k\} } S_{n/p_i} )$ (do I )
$=n.X_n(C \cap S_n)+ \sum_{ x \in \overline{1,n-1}} [x.\{\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_x(C\cap S_{ \frac{n}{\prod_{ i \in I} p_i}})\} ]$ (do II)
$=n.X_n(C \cap S_n)+\{\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1} [ \sum_{ x \in \overline{1,n-1}} x.X_x(C\cap S_{ \frac{n}{\prod_{ i \in I} p_i}})\} ] \} $

Lấy $C=S_l$ bất kì.
Ta rút gọn cái đẳng thức trên lại bằng cách sử dụng (*) thì được
$ a_{ l n}=n.X_n(S_l \cap S_n)+\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.a_{l \frac{n}{\prod_{ i \in I} p_i}}$
hay nói cách khác
$a_{l n}+\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|}.a_{l \frac{n}{\prod_{ i \in I} p_i}}=n$ nếu $l=n$ và bằng $0$ nếu $l<n$
------------------------------
Đáp số bài của em là $n!$


Anh xài điều sau:
$a_{l n}+\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|}.a_{l \frac{n}{\prod_{ i \in I} p_i}}=n$ nếu $l=n$ và bằng $0$ nếu $l<n$



Dưới đây là chứng minh bằng tập hợp, có lẽ xài quy nạp với 1 chút số học là ra nhưng mà anh lỡ làm bằng tập hợp rồi.
KHó hiểu lắm, em thử chứng minh cái đẳng thức trên bằng cách khác hén

Đặt $X_a( A)$ (với A là 1 tập hợp ) là hàm thỏa điều sau :$X_a(A)=| \{a\} \cap A | $

Đặt $S_n=\{ m: m|n,m>0\}$ tức là $S_n$ là tập hợp các ước của $S_n$.
Giả sử $n$ có $k$ ước nguyên tố là $p_1,p_2,...,p_k$.

Ta có điều sau đây:
i) $S_i \cap S_j= S_{(i,j)}$
ii) Nếu $I \subset \{ 1,2,...,k\}$ thì $ \bigcap_{ i \in I} S_{n/p_i}= S_{ \frac{n}{\prod_{ i \in I} p_i}}$
iii) Với $ A \subset B$ thì \sum_{a \in A} a= \sum_{a \in B} a.X_a(A)$
Quay lại bài toán , ta có chứng minh cái này trước:
I:) $ \bigcup_{ i \in \{ 1,2,...,k\} } S_{n/p_i}=$$\{ m : m|n , 0<m<n\}$$= S_n$\$ \{n\}$

II:)
Theo nguyên ly Inclusion-Exclusion thì :

$ X_a( \bigcup_{ i \in \{ 1,2,...,k\} } S_{n/p_i})=\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_a( \bigcap_{ i \in I} S_{n/p_i} ) $
$=\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_a(S_{ \frac{n}{\prod_{ i \in I} p_i}}) $ (theo ii )

rộng hơn là $X_a( \bigcup_{ i \in \{ 1,2,...,k\} } (C\cap S_{n/p_i}))=\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_a(C\cap S_{ \frac{n}{\prod_{ i \in I} p_i}})$

Trở lại bài toán.

Từ i) ta thấy điều sau: $ a_{ij} = \sum_{ x \in S_i \cap S_j } x=\sum_{x \in \overline {1,n}} x.X_x( S_i \cap S_j )$(*)

Từ I,II ,iii ta mở rộng được thành điều sau:

$ \sum_{x \in C\cap S_n} x=\sum_{ x \in \overline{1,n}} x.X_x( C\cap S_n)=n.X_n(C \cap S_n)+\sum_{ x \in \overline{1,n-1}} x.X_x( C\cap \bigcup_{ i \in \{ 1,2,...,k\} } S_{n/p_i} )$ (do I )
$=n.X_n(C \cap S_n)+ \sum_{ x \in \overline{1,n-1}} [x.\{\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.X_x(C\cap S_{ \frac{n}{\prod_{ i \in I} p_i}})\} ]$ (do II)
$=n.X_n(C \cap S_n)+\{\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1} [ \sum_{ x \in \overline{1,n-1}} x.X_x(C\cap S_{ \frac{n}{\prod_{ i \in I} p_i}})\} ] \} $

Lấy $C=S_l$ bất kì.
Ta rút gọn cái đẳng thức trên lại bằng cách sử dụng (*) thì được
$ a_{ l n}=n.X_n(S_l \cap S_n)+\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|-1}.a_{l \frac{n}{\prod_{ i \in I} p_i}}$
hay nói cách khác
$a_{l n}+\sum_{ I \subset \{ 1,2,...,k\} } (-1)^{ |I|}.a_{l \frac{n}{\prod_{ i \in I} p_i}}=n$ nếu $l=n$ và bằng $0$ nếu $l<n$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________

thay đổi nội dung bởi: Kelacloi, 01-03-2014 lúc 11:01 PM Lý do: Tự động gộp bài
Kelacloi is offline   Trả Lời Với Trích Dẫn
 
[page compression: 12.80 k/13.92 k (8.05%)]