Chủ đề này có 1 trả lời

[NTMFlashNo1]

Cho $A=\left \{ 1,2,3,...2016 \right \}$ và $\Theta$ là một hoán vị của tập $A$.Gọi $X$ là tập các phần tử dạng $i\Theta(i)$ với $i$ là các phần tử nào đó của $A$ và thỏa mãn:$\forall x,y\in X;x\neq y$ thì $2017|(x-y)$.Tìm $Max$ của $|X|$.

[Dark Magician 2k2]

Cho $A=\left \{ 1,2,3,...2016 \right \}$ và $\Theta$ là một hoán vị của tập $A$.Gọi $X$ là tập các phần tử dạng $i\Theta(i)$ với $i$ là các phần tử nào đó của $A$ và thỏa mãn:$\forall x,y\in X;x\neq y$ thì $2017|(x-y)$.Tìm $Max$ của $|X|$.

Ta chứng mình bài toán qua 2 bước

a) Chứng minh $|X|\leq 2015$

Giả sử $|X|=2016$, khi đó $\forall i\neq j$ thoả mãn $i\delta(i)-j\delta(j)\not\vdots 2017$

Suy ra X là hệ thặng dư thu gọn mod $2017$

Ta có $\prod_{i=1}^{2016}i\delta(i)=(2016!)^2\equiv (-1)^2\equiv 1(mod 2017)$

Mà X là hệ thặng dư thu gọn nên $\prod_{x\in X}=\prod_{i=1}^{2016}(i\delta(i))=1.2....2016=2016!\equiv -1(mod 2017)$

Do đó có mâu thuẫn, vậy bước 1 được chứng minh.

b) Xây dựng hoán vị thoả mãn $|X|=2015$

Ta thấy (\delta(i),2017)=1,\forall i\in A$

Suy ra tồn tại i sao cho $i\delta(i)\equiv i+1(mod 2017)$

Giả sử tồn tại $x\neq y$ thoả mãn $\left\{\begin{matrix} x-y\vdots 2017\\ x=i\delta(i)\\ y=j\delta(j) \end{matrix}\right.,\forall i,j\in A$

Suy ra $x\equiv y(mod 2017)\Rightarrow i\delta(i)\equiv j\delta(j)(mod 2017)\Rightarrow i+1\equiv j+1(mod 2017)\Rightarrow i\equiv j(mod 2017)$, vô lý.

Do đó hệ ta đã xây dựng thoả mãn.

Vậy ta có $Max_{|X|}=2015\Leftrightarrow \forall i\in A, i\delta(i)\equiv i+1(mod 2017)$.