Đến nội dung

Hình ảnh

Chứng minh có thể chọn ra một vài số trong $n$ số này mà có tổng bằng $S$

- - - - -

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

#1
Math04

Math04

    Trung sĩ

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

Cho $S$ là một bội nguyên dương của tất cả các số từ $2$ đến $2019$ và $n$ số nguyên dương $a_{1},...,a_{n}$ thuộc $M=\left \{ 1,2,...,2019 \right \}$ có tổng bằng $2S$. Chứng minh có thể chọn ra một vài số trong $n$ số này mà có tổng bằng $S$.



#2
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

Đặt $m = 2019$.

Do $m(m-1)(m-2)\mid S$ nên $S\geq m(m-1)(m-2)$.

Nếu trong các số $a_1,a_2,...,a_n$, mỗi số trong tập $\{1;2;...;m\}$ chứa nhiều nhất $m-2$ số thì $$2S \leq (m-2)(1 + 2 + ... + m)< 2m(m-1)(m-2)\text{ (vô lí)}$$

Do đó tồn tại $i\in \{1;2;...;m\}$ sao cho $i$ xuất hiện ít nhất $m-1$ lần.

Đặt $A$ là đa tập chứa $m-1$ số $i$ này và $B$ là đa tập chứa các số còn lại. Ta có $|A| = m-1$ và $|B| = n - (m-1)$.

Nếu $n - (m-1) \leq i$ thì $a_1+a_2+...+a_n \leq mi + (m-1)i = (2m-1)i<2S$, vô lí.

Suy ra $n-(m-1) > i$. Do đó ta chọn được một lượng số không quá $i$ phần tử từ $B$ có tổng chia hết cho $i$.

Cho các phần tử này vào đa tập mới là $C$ và xoá các phần tử này trong $B$. 

Do $\sum_{x\in B}x = 2S - (m-1)i$ nên ta làm được thao tác trên liên tục cho đến khi tổng các phần tử của $T$ lớn hơn $S - mi$ thì dừng lại.

Thật vậy, nếu $\sum_{x\in T} x \leq S - mi$ thì khi đó tổng các phần tử của $B$ ít nhất là $S + i$, tức $|B| \geq i$, vô lí.

Đồng thời nếu $\sum_{x\in T} x > S$ thì trước đó ta đã thêm vào $T$ một số số có tổng lớn hơn $mi$, tức ta đã thêm vào ít nhất $i+1$ số, vô lí vì mỗi lần ta thêm không quá $i$ số.

Do đó ta điều chỉnh được sao cho $S - mi < \sum_{x\in T} x \leq S$.

Vì $i\mid S$ và $i\mid \sum_{x\in T} x$, ta có thể đặt $\sum_{x\in T}x = S - ki$, với $k\in \{0;1;...;m-1\}$.

Bổ sung $k$ phần tử $i$ của $A$ vào $T$, ta được một tổng bằng $S$. (đpcm)


Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 30-12-2022 - 15:13





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

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