Đến nội dung

Hình ảnh

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$


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

#1
bimcaucau

bimcaucau

    Hạ sĩ

  • Thành viên
  • 84 Bài viết

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$



#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

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.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\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