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

[Math04]

Cho $n \geq 2$ là số nguyên sao cho tồn tại $n-1$ số nguyên $x_{1},...x_{n-1}$ thỏa mãn: nếu  $0<i, j<n, i \neq j$ và $n$ là ước của $2i+ j$ thì $x_{i} < x_{j}$. Chứng minh rằng $n=2^k, k \geq 1$ hoặc $n=3.2^k, k \geq 0$

[Hoang72]

Với mọi $m\in\mathbb N^*\setminus \{1\}$, đặt $A_m = \{(i,j)\in \{1;2;...;m-1\}^2,i\neq j: m\mid 2i+j\}$.

Gọi $P(n)$ là mệnh đề thoả mãn $P(n)$ đúng khi tồn tại các số nguyên $x_1,x_2,...,x_{n-1}$ thoả mãn yêu cầu thoả mãn, ngược lại $P(n)$ sai.

Trước tiên, ta chứng minh nếu $P(n)$ sai, với $n,p\in\mathbb N^*\setminus \{1\}$ thì $P(np)$ sai.

Thật vậy, giả sử $P(np)$ đúng. Ta thấy $A_n . p  \subset A_{np}$, trong đó kí hiệu $A_n . p$ là tập gồm tích các phần tử của $A_n$ với $p$.

Do $A_{np}$ đúng nên tồn tại các số $x_{p}, x_{2p},...,x_{(n-1)p}$ thoả mãn với mọi $0<i,j<n; i\neq j$ và $np\mid 2ip+jp$ thì $x_{ip} < x_{jp}$.

Đặt $y_i = x_{pi},\forall i = \overline{1,n-1}$. Thế thì $y_1,y_2,...,y_{n-1}$ thoả mãn với mọi $(i,j)\in A_n$, ta có $y_i < y_j$.

Từ đây ta suy ra $P(n)$ đúng, vô lí.

Do đó để chứng minh bài toán đã cho, ta chỉ cần chứng minh trường hợp $n$ là số nguyên tố lẻ lớn hơn $3$ thì không tồn tại các số nguyên $x_1,x_2,..,x_{n-1}$ thoả mãn.

Ta phát biểu lại mệnh đề trên như sau:

Cho đồ thị có hướng $G=(V;E)$ có $n$ đỉnh, trong đó $n$ là số nguyên tố lẻ lớn hơn $3$. Các đỉnh được đánh số từ $1$ đến $n$. Với mọi $i\neq j$, có một cạnh nối từ đỉnh $i$ đến đỉnh $j$ khi và chỉ khi $2i + j\in \{n; 2n\}$. Khi đó nếu đồ thị không có chu trình thì $n=2^k,k\in\mathbb N^*$ hoặc $n=3.2^k,k\in\mathbb N$.

Chứng minh:

Từ đề bài ta có các cạnh của đồ thị là: $\begin{cases}1\to 2u-1\\2 \to 2u-3 \\ ... \\ u\to 1 \end{cases}$ và $\begin{cases} u+1\to 2u \\ u+2\to 2u-2 \\ ... \\ 2u \to 2\end{cases}$.

Nhìn vào bảng trên, ta thấy mỗi đỉnh đều là xuất phát của đúng một cạnh và kết thúc của đúng một cạnh. Đồng thời, không có hai đỉnh nào có tính chất tự phản (Đỉnh này đi đến đỉnh kia và ngược lại).

Thế thì ta xét một đường đi bắt đầu từ đỉnh $1$: Đỉnh $1$ đến được duy nhất một đỉnh, đỉnh tiếp theo cũng đi đến được duy nhất một đỉnh... Nếu trong đường đi có gặp lại một đỉnh nào đó, ta được một chu trình. Ngược lại, đường đi này sẽ lặp lại vô hạn bước, và ta có điều vô lí.

Do đó đồ thị luôn có ít nhất một chu trình. Ta có đpcm.