Tìm kiếm
Nam
Bài 4: (5 điểm)Trên một bảng đen, ban đầu người ta viết 2015 số tự nhiên phân biệt $0=a_0<a_1<a_2<...<a_{2014}$. Sau đó, người ta viết tiếp lên bảng tất cả những số tự nhiên $n$ thỏa mãn: $n$ có thể viết được dưới dạng tổng của $2$ số trong $2015$ số ban đầu (2 số này không nhất thiết phải phân biệt).Hỏi sau khi viết xong, trên bảng sẽ có ít nhất bao nhiêu số tự nhiên phân biệt, nếu:a. $a_{2014}=4028$b. $a_{2014}=4027$
a) Xét $A=\left\{ {{a}_{0}},{{a}_{1}},...,{{a}_{2014}} \right\}$ . Ta sẽ tìm giá trị nhỏ nhất của $\left| A+A \right|$
Ta có: $2{{a}_{0}}<{{a}_{0}}+{{a}_{1}}<{{a}_{0}}+{{a}_{2} }<...<{{a}_{0}}+{{a}_{2014}}<{{a}_{1}}+{{a}_{2014} }<...<2{{a}_{2014}}$
Suy ra $\left| A+A \right|\ge 4029$
Ta sẽ chứng mình tồn tại $\left| A+A \right|\ge 4029$.
Đặt ${{a}_{i}}=2i,\forall i=\overline{1,n}$ , ta có:
$A=\left\{ 0,2,...,4028 \right\}$ và $A+A=\left\{ 0,2,...,4028,4030,...,8056 \right\}\Rightarrow \left| A+A \right|=4029$
Vậy GTNN của $n$ là 4029
b)Định lý Cauchy-Davenport:
Nếu A là tập hợp các số mà không có số nào đồng dư với nhau modun p. Tương tự là tập B. Khi đó tập \[A+B\] chứa ít nhất $\min \left\{ \left| A \right|+\left| B \right|-1,p \right\}$ phần tử đôi một không đồng dư với nhau mod p.
Xét $A'=A\backslash \left\{ {{a}_{2014}} \right\}$
Ta có $A'$ là tập hợp các số mà không có số nào đồng dư mod 4027. Theo định lí Cauchy-Davenport, ta có $\left| A'+A' \right|$ phủ hết hệ thặng dư đầy đủ mod 4027$\Rightarrow \left| A'+A' \right|\ge 4027$
Xét tập $B={{a}_{2014}}+A$
Giả sử có $t$ bộ $i,j,k<2014$ sao cho ${{a}_{i}}+{{a}_{j}}={{a}_{2014}}+{{a}_{k}}$
Khi đó ${{a}_{0}}+{{a}_{k}}\equiv {{a}_{i}}+{{a}_{j}}\left( \bmod 4027 \right)$ và ${{a}_{0}}+{{a}_{k}}<{{a}_{i}}+{{a}_{j}}$ nên $\left| A'+A' \right|\ge 4027+t$ (vì các số ${{a}_{i}}+{{a}_{j}}$ và ${{a}_{0}}+{{a}_{j}}$ được tính là trùng nhau theo modun 4027 mặc dù chúng phân biệt)
$\left| A+A \right|=\left| A'+A' \right|+\left| B \right|-\left| \left( A'+A' \right)\cap B \right|\ge 4027+t+2015-t=6042$
Ta chứng mình tồn tại tập $A$ thỏa mãn yêu cầu đề bài
Xét $A=\left\{ 0,2,4,...,4026,4027 \right\}$
Khi đó $A+A=\left\{ 0,2,...,8052,4027,4029,...,8053,8054 \right\}$ $\Rightarrow \left| A+A \right|=6042$
Vậy GTNN của $n$ là 6042
