Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Chứng minh ta có thể phân hoạch $\mathbb{N}^{*}$ thành 1 số tập hữu hạn

demonhentai000 nguyenta98

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

#1 WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản trị
  • 1319 Bài viết
  • Giới tính:Nam

Đã gửi 10-03-2013 - 00:24

Bài toán:
Cho dãy số nguyên $\{a_i\}^{n}_{i=1}$ thỏa mãn $a_{i_{1}}+a_{i_{1}}+....+a_{i_{k}}\neq 0\, \forall 1\leq i_1<i_2<...<i_{k}\leq n$.
Chứng minh ta có thể phân hoạch $\mathbb{N}^{*}$ thành 1 số tập hữu hạn sa0 ch0 $\sum^{n}_{i=1}a_i x_i\neq 0$ nếu $\{x_i\}^{n}_{i=1}$ thuộc cùng 1 tập.

Bài viết đã được chỉnh sửa nội dung bởi WhjteShadow: 10-03-2013 - 00:48

$$n! \sim \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$$

 

“We can only see a short distance ahead, but we can see plenty there that needs to be done.” - Alan Turing


#2 ntphuchus

ntphuchus

    Lính mới

  • Thành viên mới
  • 3 Bài viết
  • Giới tính:Nam

Đã gửi 28-04-2020 - 13:45

Gọi $p$ là một số nguyên tố thỏa mãn $p>|a_{i_1}+a_{i_2}+...+a_{i_k}|$ với mọi $1\leq i_1<i_2<...<i_k\leq n$. 

Vì mọi $m\in\mathbb{N}^{*}$ đều viết được duy nhất dưới dạng $p^kq$ $(k,q\in\mathbb{N}, (q,p)=1)$ nên $\mathbb{N}^{*}$ có thể được phân hoạch thành các $S_i=\{m=p^kq : q\equiv i \pmod p \}$ với $i=1,2,...,p-1$.

Ta chứng minh các tập $S_1,S_2,...,S_{p-1}$ thỏa mãn yêu cầu bài toán.

Thật vậy, phản chứng, giả sử tồn tại $x_1,x_2,...,x_n$ cùng thuộc một tập $S_t$ sao cho $a_1x_1+a_2x_2+...+a_nx_n=0$.

Giả sử $x_1=p^{k_1}q_1, x_2=p^{k_2}q_2,...,x_n=p^{k_n}q_n$ thì $q_1,q_2,...,q_n\equiv t \pmod p$. Thay vào ta có : $a_1p^{k_1}q_1+a_2p^{k_2}q_2+...+a_np^{k_n}q_n=0$.

Đặt $s=\min \{k_1,k_2,...,k_n\}$ và $i_1,i_2,...,i_r$ là tất cả các chỉ số mà $k_{i_1}=k_{i_2}=...=k_{i_r}=s$.

Khi đó ta có : $0=a_1p^{k_1}q_1+a_2p^{k_2}q_2+...+a_np^{k_n}q_n\equiv a_{i_1}p^{k_{i_1}}q_{i_1}+a_{i_2}p^{k_{i_2}}q_{i_2}+...+a_{i_r}p^{k_{i_r}}q_{i_r} \pmod {p^{s+1}}$ $\Longrightarrow$ $p^{s+1} | a_{i_1}p^{s}q_{i_1}+a_{i_2}p^{s}q_{i_2}+...+a_{i_r}p^{s}q_{i_r}$ $\Longrightarrow$ $p | a_{i_1}q_{i_1}+a_{i_2}q_{i_2}+...+a_{i_r}q_{i_r}$ $\Longrightarrow$ $0\equiv a_{i_1}q_{i_1}+a_{i_2}q_{i_2}+...+a_{i_r}q_{i_r} \equiv a_{i_1}t+a_{i_2}t+...+a_{i_r}t \pmod p$ $\Longrightarrow$ $p|a_{i_1}+a_{i_2}+...+a_{i_r}$ (vì $(t,p)=1$).

Mà $p>|a_{i_1}+a_{i_2}+...+a_{i_r}|$ $\Longrightarrow$ $a_{i_1}+a_{i_2}+...+a_{i_r}=0$ (mâu thuẫn với giả thiết bài toán).

Do đó bài toán được chứng minh.

P/s: Có thể thay điều kiện $a_{i_1}+a_{i_2}+...+a_{i_k}\ne 0 \forall 1\leq i_1<i_2<...<i_k\leq n$ thành điều kiện nhẹ hơn là $a_1+a_2+...+a_n\ne 0$.  


Bài viết đã được chỉnh sửa nội dung bởi ntphuchus: 28-04-2020 - 13:51






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

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