Chia các số thành các tập có tổng các phần tử bằng nhau
#1
Đã gửi 05-02-2013 - 21:15
$r_n$ là các số chỉ có thể nhận giá trị là $0$, $1$ hoặc $2$ đồng dư với $\sum_{k=1}^{n}{a_k}$ theo modulo $3$.
Chứng minh rằng với $n\ge 6$, tập $\left \{ a_1,a_2,\dots,a_n \right \}\setminus \left \{ r_n \right \}$ có thể được chia thành $3$ tập con với tổng các phần tử là bằng nhau.
Ví dụ: với $n=7$, thì $\left \{ 2,3,4,5,6,10 \right \}=\left \{ 2,3,5 \right \}\cup \left \{ 4,6 \right \}\cup \left \{ 10 \right \}$
- hxthanh, Zaraki và Phuong Mark thích
#2
Đã gửi 06-02-2013 - 01:01
$a_n$ là dãy số được xác định bởi: $a_n = n$ với $n\le 6$ và $a_n = \left \lfloor \frac{a_1 + a_2 + \cdots + a_{n-1}}{2} \right \rfloor$ với $n > 6$.
$r_n$ là các số chỉ có thể nhận giá trị là $0$, $1$ hoặc $2$ đồng dư với $\sum_{k=1}^{n}{a_k}$ theo modulo $3$.
Chứng minh rằng với $n\ge 6$, tập $\left \{ a_1,a_2,\dots,a_n \right \}\setminus \left \{ r_n \right \}$ có thể được chia thành $3$ tập con với tổng các phần tử là bằng nhau.
Ví dụ: với $n=7$, thì $\left \{ 2,3,4,5,6,10 \right \}=\left \{ 2,3,5 \right \}\cup \left \{ 4,6 \right \}\cup \left \{ 10 \right \}$
Em thử đưa ra một ý tưởngi xem đúng không nhé!
Trước tiên chỉ cần xét tính chẵn lẻ của $a_1 + a_2 + \cdots + a_{n-1}$ ta có thể suy ra tổng các phần tử của tập $\left \{ a_1,a_2,\dots,a_n \right \}\setminus \left \{ r_n \right \}$ là $3a_n$ và $r_n$ chỉ có thể nhận giá trị $0$ hoặc $1$.
Bây giờ ta sẽ chứng minh quy nạp rằng mọi số không vượt quá $a_n$ đều biểu diễn được dưới dạng tổng của một số số thuộc tập $\left \{ a_2,a_3, \dots,a_{n-1} \right \}$
Dễ dàng kiểm tra với $n=7$
Ta chỉ cần chú ý $a_n-a_{n-1}= \left \lfloor \frac{a_1 + a_2 + \cdots + a_{ -2} - a_{n-1}}{2} \right \rfloor <a_{n-1}$. Do đó nếu mệnh đề đúng với $n-1$ thì các số không vượt quá $\left \lfloor \frac{a_1 + a_2 + \cdots - a_{n-1}}{2} \right \rfloor <a_{n-1}$ đều biểu diễn được dưới dạng tổng của một số số thuộc tập $\left \{ a_2,a_3, \dots,a_{n-2} \right \}$. Từ đây suy ra mệnh đề cũng đúng với $n$.
Từ 2 nhận xét trên ta có thể suy ra đpcm.
Nếu lời giải này đúng thì ta thấy bài toán hoàn toàn có thể được làm chặt hơn.
#3
Đã gửi 06-02-2013 - 06:19
Em thử đưa ra một ý tưởngi xem đúng không nhé!
Trước tiên chỉ cần xét tính chẵn lẻ của $a_1 + a_2 + \cdots + a_{n-1}$ ta có thể suy ra tổng các phần tử của tập $\left \{ a_1,a_2,\dots,a_n \right \}\setminus \left \{ r_n \right \}$ là $3a_n$ và $r_n$ chỉ có thể nhận giá trị $0$ hoặc $1$.
Bây giờ ta sẽ chứng minh quy nạp rằng mọi số không vượt quá $a_n$ đều biểu diễn được dưới dạng tổng của một số số thuộc tập $\left \{ a_2,a_3, \dots,a_{n-1} \right \}$
Dễ dàng kiểm tra với $n=7$
Ta chỉ cần chú ý $a_n-a_{n-1}= \left \lfloor \frac{a_1 + a_2 + \cdots + a_{ -2} - a_{n-1}}{2} \right \rfloor <a_{n-1}$. Do đó nếu mệnh đề đúng với $n-1$ thì các số không vượt quá $\left \lfloor \frac{a_1 + a_2 + \cdots - a_{n-1}}{2} \right \rfloor <a_{n-1}$ đều biểu diễn được dưới dạng tổng của một số số thuộc tập $\left \{ a_2,a_3, \dots,a_{n-2} \right \}$. Từ đây suy ra mệnh đề cũng đúng với $n$.
Từ 2 nhận xét trên ta có thể suy ra đpcm.
Nếu lời giải này đúng thì ta thấy bài toán hoàn toàn có thể được làm chặt hơn.
Từ mọi số không vượt quá $a_{n-1}$ đều biểu diễn được dưới tổng của một số số trong các số $a_2,\dots,a_{n-2}$ suy ra mọi số không vượt quá $a_n$ cũng biểu diễn được dưới tổng của một số số trong các số $a_2,\dots,a_{n-1}$.
Đoạn này bạn nói rõ hơn được không? Nếu chỗ này chứng minh ổn là chuẩn rồi
#4
Đã gửi 06-02-2013 - 21:46
Thưa anh vì $a_n-a_{n-1}<a_{n-1}$ nên mọi số $k$ mà $a_{n-1}<k<a_n$ thì $k-a_{n-1}$ theo giả thiết quy nạp sẽ biểu diễn được dưới dạng tổng của một số số trong các số $a_2,a_3,...,a_{n-2}$. từ đó chỉ cần thêm $a_{n-1}$ vào biểu diễn của $k-a_{n-1}$ là ta được cách biểu diễn của $k$. Còn với $k<a_{n-1}$ thì hiển nhiên ta biểu diễn được theo giả thiết quy nạp rồi.Từ mọi số không vượt quá $a_{n-1}$ đều biểu diễn được dưới tổng của một số số trong các số $a_2,\dots,a_{n-2}$ suy ra mọi số không vượt quá $a_n$ cũng biểu diễn được dưới tổng của một số số trong các số $a_2,\dots,a_{n-1}$.
Đoạn này bạn nói rõ hơn được không? Nếu chỗ này chứng minh ổn là chuẩn rồi
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh