JUV

Gọi $1$ bảng $m\times n$ thoả mãn đề bài là bảng có tính chất $P$. Chứng minh quy nạp theo $m+n$ rằng tất cả bảng $m\times n$ có tính chất $P$ thì $m=n$. Dễ dàng kiểm tra với $m+n=2,3,4$. Giả sử mệnh đề đúng với $m+n=k$. Xét bảng $m\times n$ với $m+n=k+1$, ta thay những số dương trên bảng bằng dấu $+$ và giữ nguyên ô chứa số $0$. Bước đầu tiên xét $1$ cột bất kì và đánh dấu các ô chứa dấu $+$ của cột đó. Ta sẽ đánh dấu $1$ số ô chứa dấu $+$ của bảng theo quy tắc sau trong những bước sau: Xét $1$ ô được đánh dấu, đánh dấu tất cả các ô cùng hàng hoặc cùng cột với nó mà chứa dấu $+$(nếu chưa được đánh dấu). Gọi $1$ hàng hoặc cột là tốt nếu như nó có $1$ ô được đánh dấu, dễ thấy tất cả các ô chứa dấu $+$ của $1$ hàng hoặc cột tốt đều được đánh dấu. Giả sử có $a$ cột, $b$ hàng tốt thì xét $ab$ giao điểm của chúng. Dễ thấy nếu $1$ ô không nằm trong $ab$ giao điểm đó mà thuộc $1$ hàng hoặc cột tốt thì nó sẽ chứa số $0$. Vậy tổng tất cả các số trong các ô thuộc hàng và cột tốt bằng tổng tất cả các số nằm trong $ab$ giao điểm (đặt là $S$). Cũng thấy rằng tổng tất cả các số trong mỗi cột tốt bằng nhau và bằng tổng các số trong mỗi hàng tốt$\Rightarrow \frac{S}{a}=\frac{S}{b}\Rightarrow a=b=t$. Giờ xoá tất cả các hàng tốt và cột tốt ra khỏi bảng, ta còn lại $m-t$ hàng và $n-t$ cột, ghép lại thành $1$ bảng $(m-t)\times(n-t)$ cũng có tính chất $P$ $\Rightarrow m-t=n-t$ (do $m+n-2t<k$).Vậy $m=n$$\Rightarrow Q.E.D$

Câu a chính là bất đẳng thức Lubell- Yamamoto- Meshalkin, có thể tìm chứng minh trên mạng. Còn câu b thì ta có thể chứng minh trực tiếp từ KQ câu a: $1\geq \sum_{i=0}^{n}\frac{a_i}{\binom{n}{i}}\geq \left ( \sum_{i=0}^{n}a_i \right )\frac{1}{\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}}\Rightarrow \left | \Im \right |\leq \begin{pmatrix} n\\ \left \lfloor \frac{n}{2} \right \rfloor \end{pmatrix}$

Bài 4: Giả sử có $k$ điểm xanh, $2n-k$ điểm đỏ. Chọn ra bộ $4$ điểm $2$ xanh là $A_1,A_2$, $2$ đỏ là $B_1,B_2$. Xét các cặp đoạn thẳng $(A_1B_1;A_2B_2)$ và $(A_1B_2;A_2B_1)$. Dễ thấy rằng nếu $A_1B_1,A_2B_2$ cắt nhau thì $A_2B_1,A_1B_2$ không cắt nhau. Vậy trong $2$ cặp đoạn thẳng đó chỉ chứa nhiều nhất $1$ giao điểm. Vì vậy cứ chọn $4$ điểm thoả mãn $2$ điểm xanh ,$2$ đỏ thì sẽ tạo ra nhiều nhất $1$ giao điểm. Có tất cả $\binom{k}{2}\binom{2n-k}{2}\leq \binom{n}{2}^2$ cách chọn $4$ điểm nên có nhiều nhất $\binom{n}{2}^2$ giao điểm. Xét đa giác $A_1A_2...A_{2n}$ thì ta tô xanh $A_1,A_2,...,A_n$, đỏ $A_{n+1},...,A_{2n}$ thì số giao điểm sẽ lớn nhất (không có $3$ đoạn nào đồng quy)

Câu 5: Ta có $a_{i+1}-a_i\leq 1\Rightarrow (a_{i+1}-i-1)-(a_i-i)\leq 0$ $\forall \ i=\overline{1,2015}$. Gọi $i,j$ là $2$ số thoả mãn $a_i=i$,$a_j=j$ với $j>i$, có $0=a_i-i\geq a_{i+1}-i-1 \geq a_j-j=0$ và theo tính duy nhất của $i$ và $j$ thì $j=i+1$. Cũng theo tính duy nhất của $i$, $a_{i-1}>i+1$,$a_{i+2}<i$ và nếu tồn tại $t>i+1$ để $a_t>i$ thì vì$a_{i+2}<i$ nên sẽ tồn tại $p>i+1$ để $a_p<i$,$a_{p+1}>i$ và $a_{p+1}-a_p>1$(vô lí). Vậy các số $(a_{i+2},a_{i+3},...,a_{2016})$ là hoán vị của $(1,2,...,i-1)$$\Rightarrow$ $i-1=2015-i$ hay $i=1008$. Giờ ta sẽ tìm cách hoán vị các số $a_{1010}$ đến $a_{2016}$ thoả mãn đề bài. Gọi $s$ là số lớn nhất thoả mãn $a_{1010},a_{1011},...,a_s$ lập thành cấp số cộng công sai $1$. Nếu $a_s<1007$, lúc đó ta có $a_{s+1}<a_s$ và tồn tại $k>s$ thoả mãn $a_k>a_s$. Khi đó sẽ tồn tại $p>s$ thoả mãn $a_p<a_s$ và $a_{p+1}>a_s$ nên $a_{p+1}-a_p>1$. Vậy $a_s=1007$, tương tự nếu $s_1$ là số lớn nhất thoả mãn $a_{s+1},a_{s+2},...,a_{s_1}$ lập thành cấp số cộng công sai $1$ thì $a_{s_1}=a_{1010}-1$. Tương tự như thế thì dãy số $a_{1010},a_{1011},...,a_{2016}$ sẽ được tạo theo cách sau: Số hạng đầu tiên chọn ngẫu nhiên rồi các số tiếp theo sẽ chọn sao cho các số hạng tiếp theo sẽ lập thành cấp số cộng đến khi có $1$ số là số hạng lớn nhất chưa được chọn trong dãy; số hạng sau đó được chọn ngẫu nhiên trong các số còn lại và cứ tiếp tục như thế.Những cách chọn ngẫu nhiên trong dãy được gọi là cách chọn đặc biệt. Gọi $1$ nhóm $(i_1,i_2,...,i_t)$ được xác định rằng $i_1,i_2,...,i_t$ lần lượt là số đầu tiên, thứ $2$,...,thứ $t-1$,thứ $t$ là tất cả các số được dùng trong cách chọn đặc biệt để gắn cho một số số xác định trong dãy $a_{1010},a_{1011},...,a_{2016}$. Dễ thấy $i_1>i_2>...>i_t$ nên số cách chọn dãy đó là số cách chọn các tập con trong tập $\left \{ 1,2,...,1007 \right \}$ và bằng $2^{1007}$. Dễ thấy nếu chọn $1$ nhóm thì chỉ có $1$ dãy $a_{1010},a_{1011},...,a_{2016}$ được tạo thành nên số dãy thoả mãn là $2^{1007}$. Tương tự số cách chọn dãy $a_1,a_2,...,a_{1007}$ là $2^{1007}$. Vậy tổng số hoán vị thoả mãn là $2^{2014}$

Bài 5 (ngày 2): Xét $1$ cách chọn các bộ số thoả mãn không có $2$ bộ nào trội nhau và $1$ bảng $8\times 8$, đánh dấu các cột từ dưới lên trên $0$ đến $7$, các hàng từ trái sang phải $0$ đến $7$. Đánh dấu vài ô vuông $1\times 1$ trong đó, ô vuông $(y,z)$ được đánh dấu ($y$ là số hàng, $z$ là số cột) nếu có một bộ $(x,y,z)$ được chọn. Ta thấy rằng nếu có $2$ bộ $(x_1;y;z)$ và $(x_2,y,z)$ được chọn thì một bộ phải trội hơn bộ còn lại (với $x_1,x_2,y,z$ là 4 số trong các số từ $0$ đến $7$) nên với một ô $(y,z)$ được đánh dấu thì tồn tại duy nhất một số $x$ trong khoảng từ $0$ đến $7$ được chọn thoả mãn $(x,y,z)$ được chọn, hay số ô đánh dấu bằng số bộ số được chọn. Ta gọi một ô $(y_1,z_1)$ đến được một ô $(y_2,z_2)$ nếu $y_1\geq y_2,z_1\geq z_2$ và $2$ ô đó phân biệt.Dễ thấy $y_1+z_1>y_2+z_2$$(1)$. Ta thấy rằng không thể tồn tại $9$ ô $(y_1,z_1),(y_2,z_2),...,(y_9,z_9)$ sao cho $(y_i,z_i)$ có thể đến được $(y_{i+1},z_{i+1})$ $\forall i=\overline{1,8}$ vì như thế thì sẽ tồn tại $9$ bộ số $(x_i,y_i,z_i)$ và $x_9>x_8>...>x_1$(do không có 2 bộ nào trội nhau)(vô lí do $x_i$ chỉ chọn từ $0$ đến $7$). Gọi $S_1$ là tập tất cả các ô mà không thể đi từ một ô nào khác đến các ô đó và $S_{i+1}$ là tập các ô mà với mỗi ô bất kì từ tập $S_{i+1}$ thì có một ô thuộc $S_i$ đi đến được ô đó. Theo lập luận trên thì $S_9$ là tập rỗng. Xét các tổng tung độ và hoành độ trong các ô thộc $S_i$($(y,z)$ có tổng là $y+z$) và đặt $m_i$ là số lớn nhất trong các số đó. Vì không có $2$ số nào trong tập $S_i$ thuộc cùng $1$ hàng hoặc $1$ cột và vì có một ô trong $S_i$ thoả mãn tổng tung độ và hoành độ của nó là $m_i$ nên dễ chứng minh $\left | S_i \right |\leq t_i$ với $t_i=14+1-m_i$ nếu $m_i>6$,$t_i=m_i+1$ nếu $m_i<7$. Dễ thấy không có ô nào thuộc $S_9$ vì nếu không sẽ tạo ra $1$ đường đi $9$ ô nên và chú ý rằng $m_1>m_2>...>m_8$ do $(1)$ nên tổng số ô trên bảng là $\sum_{i=1}^{8}\left | S_i \right |\leq \sum_{i=1}^{8}t_i\leq 5+6+7+8+7+6+5+4=48$. Vậy có nhiều nhất $48$ ô được đánh dấu nên chỉ chọn được $48$ bộ số. Ta có cách chọn $48$ bộ số sau $(x,y,z)$ với mọi $y,z$ thoả mãn $4\leq y+z\leq 11$ và $x=y+z-4$. Vậy dễ dàng suy ra $n=49$ là giá trị nhỏ nhất

Câu 7: Dễ thấy $2017$ là số nguyên tố. Nếu $n=1008$, ta có $1008$ số $1,2,...,1008$ không thoả mãn đề bài. Giả sử tồn tại $1009$ số không thoả mãn đề bài. Nếu trong $1009$ số đó có $1$ số $a_i$ chia hết cho $2007$, $1$ số $a_j$ không chia hết thì đặt $a_i=2017c$, có$\frac{a_i+a_j}{(a_i;a_j)}> \frac{2017c}{(2017c;a_j)}=\frac{2017c}{(c;a_j)}\geq \frac{2017c}{c}=2017$(vô lí). Nếu tất cả các số đều chia hết cho $2017$ thì ta chia các số đó cho $2017$, ta cũng được $1009$ số không thoả mãn đề bài. Cứ chia như vậy cho đến khi có $1$ số không chia hết cho $2017$. Nếu lúc đó còn $1$ số chia hết cho $2017$ thì lập luận tương tự suy ra điều vô lí. Nếu tất cả các số đều không chia hết cho $2017$, giả sử tồn tại $a_i;a_j$ sao cho $a_i-a_j=2017c$ với $c$ là $1$ số nguyên dương thì $\frac{a_i+a_j}{(a_i;a_j)}= \frac{2017c+2a_j}{(a_j;2017c)}> \frac{2017c}{(a_j;c)}\geq \frac{2017c}{c}=2017$(vô lí). Nếu không có $2$ số nào đồng dư với nhau $\pmod{2017}$ thì xét $1008$ cặp $(1;2016),(2;2015);...;(1008;1009)$, lúc đó tồn tại $2$ số $a_i;a_j$ trong $1009$ số sao cho $a_i+a_j=2017d$ với $d$ nguyên. Vì vậy $\frac{a_i+a_j}{(a_j;a_i)}= \frac{2017d}{(a_j;a_i+a_j)}= \frac{2017d}{(2017d;a_j)}=\frac{2017d}{(d;a_j)}\geq \frac{2017d}{d}= 2017$ (vô lí). Vậy giả sử sai, hay luôn tồn tại $2$ trong $1009$ số thoả mãn đề bài. Vậy $n=1009$

Bài 2: Ta nhận xét rằng để biểu diễn số $n!-1$ thì cần ít nhất $\frac{n(n-1)}{2}$ lá bài. Thật vậy thì ta có thể biểu diễn $n!-1=(n-1)((n-1)!)+(n-2)((n-2)!)+...+2.2!+1.1!$. Xét cách biểu diễn $n!-1=a_1.1!+a_2.2!+...+a_{n-1}.(n-1)!$ trong đó ta dùng lần lượt $a_1,a_2,...,a_{n-1}$ quân bài $1!,2!,...,(n-1)!$ và $a_1+a_2+...a_{n-1}$ nhỏ nhất. Ta thấy rằng $a_i<i+1$$\forall 0<i<n$, nếu không thì ta chỉ cần thay $i+1$ lá bài $i!$ thành $1$ lá bài $(i+1)!$ thì sẽ tạo được $1$ cách chọn bài ít hơn. Cộng số các lá bài $a_i$ lại ta có số lá bài dùng để biểu diễn $n!-1$ ít nhất là $\frac{n(n-1)}{2}$ lá bài. Dễ thấy là để biểu diễn $n!-1$ dưới ít nhất $\frac{n(n-1)}{2}$ lá bài thì các lá bài đó chỉ có thể là $i$ lá bài $i!$ $\forall 0<i<n$, tuy nhiên các lá bài đó không thể biểu diễn được $n!$ nên ta sẽ cần $\frac{n(n-1)}{2}+1$ lá bài để có thể thoả mãn đề bài (có thể thêm $1$ lá bài $1!$ hoặc $n!$). Vậy cần ít nhất $\frac{n(n-1)}{2}+1$ lá bài

Nếu tồn tại $1$ đỉnh nối với ít hơn $5$ đỉnh thì sẽ có ít nhất $4$ đỉnh không nối với đỉnh đó, $4$ đỉnh đó sẽ đôi một nối với nhau.Nếu có $1$ đỉnh $A$ nối với ít nhất $6$ điểm $A_1,A_2,A_3,A_4,A_5,A_6$. Nếu một trong $6$ điểm đó nối với nhiều nhất $2$ trong $6$ điểm thì trong ít nhất $3$ điểm còn lại, các điểm đôi một nối với nhau nên $3$ điểm đó với điểm $A$ tạo $G4$. Nếu tồn tại $1$ điểm $B$ nối với ít nhất $3$ điểm trong $6$ điểm thì trong $3$ điểm đó tồn tại $1$ cạnh, từ đó có $G4$ là $A,B$ và $2$ điểm được nối.Nếu mỗi điểm trong $9$ điểm đó nối với đúng $5$ đỉnh thì tổng số cạnh là $\frac{5\times 9}{2}\notin \mathbb{N}$(vô lí) $\Rightarrow$ $(Q.E.D)$

Câu 4: Xét $11$ số $a+1,...,a+11 (a<2006)$. Chọn ra các số sao cho không có $2$ số nào có hiệu là $4$ hoặc $7$. Chia tập $D_a= \left \{ a+1;...;a+11 \right \}$ thành các nhóm $(a+1,a+8),(a+2,a+6),(a+3,a+7),(a+4,a+11),(a+5,a+9),(a+10)$.Không có $2$ số được chọn nào được thuộc cùng một nhóm và không thể chọn số $a+10$ rồi chọn mỗi nhóm $1$ số nên có nhiều nhất $5$ số được chọn . Chia tập $2016$ số nguyên dương đầu tiên thành các tập $(2016;2015;2014),A_0,A_{11},...,A_{2002}$, tâp đầu chọn nhiều nhất $3$ số, các tập tiếp theo, mỗi tập chọn được nhiều nhất $5$ số, lưu ý là nếu cả $3$ số $2013,2014,2015$ được chọn thì chỉ chọn được nhiều nhất $4$ số ở $A_{2002}$ nên tổng số cách chọn nhiều nhất là $183\times 5+2=917$, chẳng hạn khi ta chọn các số đồng dư $1,2,4,7,10 \pmod{11}$

Bài 7: Xét số $k$ bất kì với $1\leq k\leq 2017^2-2017$. Gọi $A_k=\left \{ 1,2,...,k \right \}$,$B_k=\left \{ k+1,k+2,...,k+2016 \right \}$,$C_k=\left \{ k+2017,k+2018,...,2017^2 \right \}$. Vì $\left | B_k \right |=2016$ nên tồn tại một hàng không chứa số nào thuộc $B_k$, tương tự với cột. Gọi tập các ô nằm trong hình chữ thập tạo bởi hàng và cột đó là $D_k$, dĩ nhiên $\left | D_k \right |=4033$.Nếu tồn tại $k$ để $D_k$ chứa $2$ số $a\in A_k,c\in C_k$ và ô chứa $2$ số đó nằm cạnh nhau thì dễ thấy $\left | a-c \right |\geq 2017$. Nếu không thì hoặc $D_k$ chỉ chứa toàn các số hoặc thuộc $A_k$, hoặc các số thuộc $C_k$. Có $A_1$ có $1$ phần tử, $C_{2017^2-2017}$ có $1$ phần tử nên $D_1$ chỉ chứa số thuộc $C_1$,$D_{2017^2-2017}$ chỉ chứa các số thuộc $A_{2017^2-2017}$. Vậy tồn tại $c$ sao cho $D_c$ chỉ chứa số thuộc $C_c$,$D_{c+1}$ chỉ chứa số thuộc $A_{c+1}$. Hai hình chữ thập đó cắt nhau tại ít nhất $1$ ô có số $e$ thoả mãn $k+2016<e<k+2$(do $e$ nằm trong cả $C_c$,$A_{c+1}$) vô lí, $Q.E.D$.Còn câu b thì đáp số đơn giản là $2017$, chỉ cần xét bảng mà hàng đầu có các số từ $1$ đến $2017$ từ trái sang phải, hàng $2$ có số $2018$ đến $4034$ từ trái sang phải rồi tương tự với các hàng kế tiếp

Bài 2: Ta sẽ chứng minh rằng với số $x$ bất kì với $0<x<n+1$ thì $x$ sẽ được đứng cuối nhiều nhất $2^{x-1}$ lần (Số lần đứng cuối của $x$ được tính bằng số bước mà sau mỗi bước đó, ta thu được $1$ hoán vị với số $x$ là số sẽ được chọn để chuyển về đúng vị trí trong bước sau). Với $x=1$ thì ta thấy ngay rằng $1$ chỉ đứng cuối nhiều nhất $1=2^0$ lần vì sau lần đầu tiên đứng cuối, nó sẽ chyển về vị trí thứ nhất và sẽ không di chuyển nữa. Với $x=2$ thì sau lần đứng cuối đầu tiên, số $2$ sẽ đi về vị trí thứ $2$. Nếu lúc đó trước số $2$ là số $1$ thì nó sẽ không di chuyển nữa, nếu không thì lúc đó số $1$ đứng đằng sau số $2$ nên trước khi số $2$ đứng cuối $1$ lần nữa thì số $1$ sẽ đứng cuối trước số $2$ $1$ lần và di chuyển về vị trí $1$. Sau đó số $2$ sẽ đứng cuối $1$ lần nữa và di chuyển về vị trí $2$ trước vị trí $1$ mà số $1$ đang đứng, tức số $2$ đứng cuối nhiều nhất $2=2^1$ lần. Mệnh đề đúng với $x=1,2$, giả sử mệnh đề đúng với $x=k<n$. Xét số $k+1$ trong dãy số, nếu nó không đứng cuối lần nào thì ta có ngay điều phải chứng minh. Xét lần đứng cuối đầu tiên của $k+1$ và nó di chuyển về vị trí $k+1$, ta thấy rằng để nó có thể thay đổi vị trí của mình một lần nữa thì cần phải đến $1$ lúc nào đó có $1$ số $x<k+1$ đứng cuối rồi di chuyển về vị trí $x$ trước $k+1$ làm vị trí của $k+1$ tăng thêm $1$. Nghĩa là sau lần đứng cuối đầu tiên thì để $k+1$ đứng cuối $1$ lần nữa thì cần có $1$ số $x<k+1$ đứng cuối trước nó. Mỗi số $1$ đến $k$ tổng cộng đứng cuối nhiều nhất $2^0+2^1+...+2^{k-1}=2^k-1$ lần theo quy nạp và trước khi để $k+1$ đứng cuối lần nữa thì cần phải có $1$ số trong $k$ số đó đứng cuối trước nên số lần $k+1$ đứng cuối sau lần thứ nhất nhiều nhất $2^k-1$ lần. Vậy $k+1$ đứng cuối nhiều nhất $2^k$ lần. Bước chứng minh quy nạp hoàn tất. Ta thấy số bước bằng tổng số lần các số $1,2,...,n$ đứng cuối nên số bước nhiều nhất là $2^0+2^1+...+2^{n-1}=2^n-1<2^n$ lần

Bài 2 ngày 2. Ý tưởng chính là quy nạp

Dễ thấy với $n=2$ thì ít hơn $2$ bước di chuyển nên bài toán đúng với $n=2$.

Giả sử đúng đến $n$, ta chứng minh đúng với $n+1$.

Xét $n+1$ ở vị trí $k$ với $k$ khác $n+1$.

Nhận thấy rằng ta không thể lấy một số ở vị trí trước $k$ rồi thêm vào sau $k$ trước khi đưa số $n+1$ vào vị trí cuối cùng nên khoảng cách từ vị trí của số $n+1$ đến vị trí cuối cùng chỉ có thể giảm hoặc không đổi.

Sau mỗi bước di chuyển, nếu một số ở sau vị trí $k$ nhỏ hơn hoặc bằng $k$ được chuyển về trước vị trí $k$ thì khoảng cách từ vị trí của số $n+1$ đến vị trí cuối cùng sẽ giảm xuống $1$. Do đó ta chỉ cần xét cho trường hợp xấu nhất là tất cả các số sau vị trí $k$ đều lớn hơn $k$.

Ta thấy tồn tại một song ánh giữa hai tập $\left \{ k+1,k+2,...,n+1 \right \}\to\left \{ 1,2,...,n-k+1 \right \}$ nên để tất cả các số sau vị trí $k$ về vị trí đúng thì cần ít hơn $2^{n-k+1}$ bước. Do đó để số $n+1$ về đúng vị trí của nó thì cần ít hơn hoặc bằng $2^{n-k+1}$.

Theo giả thiết quy nạp để chuyển dãy là hoán vị của $\left \{ 1,2,3,..,n \right \}$ về vị trí đúng thì cần ít hơn $2^n$ bước nên để chuyển dãy là hoán vị của $\left \{ 1,2,3,..,n+1 \right \}$ thì cần ít hơn $2^n+2^{n-k+1}\leq 2^n+2^n=2^{n+1}$ (bước).

Do đó ta có đpcm.

Đoạn trường hợp xấu nhất là tất cả các số sau vị trí $k$ lớn hơn $k$ có vấn đề rồi: Cho dù số $x$ nhỏ hơn $k$ được chọn và di chuyển về sau $n$ thì cũng đã tốn $1$ bước rồi, ví dụ cho số $1$ ở vị trí cuối thì khi di chuyển về vị trí đầu là cũng mất $1$ bước và còn làm xáo trộn trật tự của các số đứng đằng sau $k$ nên tất nhiên số bước để $n$ đến vị trí $n$ cũng thay đổi không rõ như thế nào dù khoảng cách $n$ cần phải di chuyển giảm, huống hồ những số nhỏ hơn $k$ lại phân bố không biết lối nào mà lần (không phải khoảng cách càng nhỏ thì số bước càng nhỏ)

Câu 4: Ta sẽ chứng minh rằng $a_i=min\left \{ a_1;a_2;...;a_i \right \}$ hoặc $a_i=max\left \{ a_1;a_2;...;a_i \right \}$ ,$i=\overline{4,2016}$. Thật vậy vì $2\sum_{i=1}^{2016}a_i=2016.2017$ nên $2a_{2016} \equiv 2 \pmod{2015}$ nên $a_{2016}$ nhận giá trị là $1$ hoặc $2016$. Mệnh đề đúng với $i=2016$, giả sử mệnh đề đúng đến $i=k>4$. Ta thấy rằng $(a_1,a_2,...,a_{i-1})$ là $1$ hoán vị của $i-1$ số nguyên liên tiếp $a+1;...;a+i-1$.Nếu $i$ là số lẻ thì ta có $2\sum_{t=1}^{i-2}a_t =2\sum_{t=1}^{i-1}(a+t)-2a_{i-1} \vdots i-2$ nên $2a_{i-1} \equiv 2a+2 \pmod{i-2} \Rightarrow a_{i-1}\equiv a+1 \pmod{i-2}$ (do $i-2$ là số lẻ). Vậy $a_{i-1}$ nhận giá trị $a+1$ hoặc $a+i-1$. Nếu $i$ là số chẵn, lập luận tương tự ta có  $2a_{i-1} \equiv 2a+2 \pmod{i-2}$ nên $a_{i-1}$ nhận $1$ trong $3$ giá trị $a+1,a+i-1,a+1+\frac{i-2}{2}$. Nếu $a_{i-1}=a+1+\frac{i-2}{2}$ thì ta có $2\sum_{t=1}^{i-3}a_t =2\sum_{t=1}^{i-1}(a+t)-2a_{i-1}-2a_{i-2} \vdots i-3$ nên $2a_{i-2} \equiv 2a+i \pmod{i-3}$. Vậy $a_{i-3}=a+1+\frac{i-2}{2}=a_{i-2}$ (vô lí). Từ đó mệnh đề đúng với $i=k-1$. Mỗi cách chọn $(a_4;a_5;...;a_{2016})$ ứng với $1$ dãy nhị phân độ dài $2013$ với số thứ $i$ từ trái sang phải là $1$ nếu $a_{i+3}=max\left \{ a_1;a_2,...;a_{i+3} \right \}$, bằng $0$ trong trường hợp còn lại. Có tổng cộng $2^{2013}$ cách chọn dãy nhị phân nên có từng đấy cách chọn bộ số $(a_4;a_5;...;a_{2016})$. Với ba số $a_1;a_2;a_3$ có tổng cộng $6$ hoán vị nên tổng cộng số các hoán vị $2016$ số là $3.2^{2014}$

Giả sử $A$ có $n$ phần tử là $a_1<a_2<...<a_n$, xét các tổng $f(x;y;z;t)=a_xa_y+a_za_t$. Theo định nghĩa tập $A$ thì các số sau đều thuộc $A$: $f(1;3;2;4)<f(1;2;3;4)<f(1;2;3;5)<f(1;2;3;6)<...<f(1;2;3;n)<f(1;2;4;n)<f(1;2;5;n)<...<f(1;2;n-1;n)<...<f(n-3;n-2;n-1;n)$, tổng cộng $4n-14$ số. Vì vậy ta có $n\geq 4n-14$ hay $n\leq 4$. Vậy $n=4$, đến đây dễ thấy các tập $A$ thoả mãn là $\left \{ a,b,c,d\mid (a-b)(b-c)(c-d)(d-a)(a-c)(b-d)\neq 0; b\neq 1; a=\frac{-cd}{b-1}; a\geq 0;b\geq 0;c\geq 0;d\geq 0 \right \}$

Xét $1$ hoán vị $(a_1;a_2;...;a_n)$ thỏa mãn tính chất chỉ tồn tại duy nhất $1$ số $i$ sao cho $a_i>a_{i+1}$. Lúc này dễ thấy dãy $a_1,a_2,...,a_i$ và $a_{i+1},...,a_n$ tăng dần. Từ đó ta thấy rằng với $1$ cách chọn dãy $a_1,a_2,...,a_i$ tăng dần thì chỉ có nhiều nhất $1$ cách chọn dãy $a_{i+1},...,a_n$ tăng dần. Lưu ý là nếu $a_1,a_2,...,a_i$ là $i$ số tự nhiên đầu tiên thì không thể chọn được $a_{i+1}$ do $a_{i+1}>a_i$. Với mỗi cách chọn $i$ số $(a_1,a_2,...,a_i)$ trong $n$ số nguyên dương đầu tiên thì chỉ có $1$ cách sắp xếp chúng theo thứ tự tăng dần. Vậy số cách chọn một hoán vị $(a_1;a_2;...;a_n)$ thỏa mãn đề bài bằng số cách chọn $1$ bộ số $(a_1;a_2;...;a_i)$ với $i$ chạy từ $1$ đến $n$ và bộ số đó không phải là bộ các số tự nhiên đầu tiên liên tiếp, hay số cách chọn là bằng $2^n-n-1$