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

[reddevil1998]

Đây là một bài toán rất hay , sẽ không khó với nhừng ai đã quen với khái niệm sum set và nhất là định lí Cauchy Davenport

Bài toán:Cho G là một đồ thị đầy đủ trên $1000p$ dỉnh ($p$ nguyên tố ), các cạnh được đánh dấu bởi các số nguyên .CM có một chu trình mà tổng các số được đánh dấu chia hết cho $p$

Bài viết đã được chỉnh sửa nội dung bởi reddevil1998: 05-12-2013 - 11:07

[LNH]

Đây là một bài toán rất hay , sẽ không khó với nhừng ai đã quen với khái niệm sum set và nhất là định lí Cauchy Davenport

Bài toán:Cho G là một đồ thị đầy đủ trên $1000p$ dỉnh ($p$ nguyên tố ), các cạnh được đánh dấu bởi các số nguyên .CM có một chu trình mà tổng các số được đánh dấu chia hết cho $p$

Đúng là nếu biết định lí Cauchy-Davenport thì sẽ giải quyết bài này trong một nốt nhạc

Xét $p-1$ $K_3$ thoả mãn tính chất sau:

Ta gọi các đỉnh của $K_3$ thứ $i$ là $e_i,v_i,u_i$

$e_iv_i+e_iu_i \not \equiv v_iu_i$, $\forall i=\overline{1,p-1}$

$v_i\equiv u_{i+1}$, $\forall i=\overline{1,p-1}$, $u_p \equiv u_1$

Gọi $A_i=\left \{ e_iv_i+e_iu_i;v_iu_i \right \}$

Theo định lí Cauchy-Davenport, $A_1+A_2$ có ít nhất $min\left \{ \left | A_1 \right |+\left | A_2 \right |-1;p \right \}$ phần tử đôi một không đồng dư mod $p$

Bằng quy nạp, ta có $A_1+A_2+...+A_{p-1}$ có ít nhất $min\left \{ \left | A_1 \right |+\left | A_2 \right |+...+\left | A_{p-1} \right |-p+2;p \right \}$ phần tử đôi một không đồng dư mod $p$

$\left | A_1 \right |+\left | A_2 \right |+...+\left | A_{p-1} \right |-p+2=3\left ( p-1 \right )-p+2=2p-1>p$

Vì vậy, tồn tại một chu trình có tổng các số trên các cạnh chia hết cho $p$