Cho $n$ số nguyên dương $a_{1},a_{2},a_{3},...,a_{n}$ có tổng bằng $2n-1$. Chứng minh rằng luôn tồn tại $m$ số ($m\leq n$) trong $n$ số đã cho có tổng bằng $n$
Chứng minh rằng luôn tồn tại $m$ số ($m\leq n$) trong $n$ số đã cho có tổng bằng $n$
Bắt đầu bởi bimcaucau, 24-07-2021 - 21:13
#1
Đã gửi 24-07-2021 - 21:13
#2
Đã gửi 24-07-2021 - 22:57
Xét $n$ tổng $S_k$ như sau:
$S_1=a_1$
$S_2=a_1+a_2$
$\ldots$
$S_k=a_1+a_2+\ldots+a_k$
Ta có nhận xét rằng $1 \le S_i \le 2n-1 \forall i$. Do đó nếu $S_i \vdots n$ thì $S_i = n$.
Nếu tồn tại chỉ số $i$ sao cho $S_i \vdots n$ thì bài toán được giải quyết.
Ngược lại, nếu không có chỉ số $i$ nào để $S_i \vdots n$ thì theo nguyên lý Dirichlet, tồn tại 2 chỉ số $i,j (i<j)$ sao cho $S_i \equiv S_j (\mod n) \Rightarrow S = S_j - S_i = a_{i+1} + \ldots + a_j \vdots n$.
Mặt khác $1 \le S \le 2n - 1$ nên $S$ chỉ có thể bằng $n$.
Ta có đpcm.
- Hoang72, bimcaucau và Duy Quang Vu 2007 thích
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!!
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh