Bài toán :
Tìm số tự nhiên $n>4$ nhỏ nhất sa0 ch0 tồn tại $n$ người thỏa mãn : 2 người quen nhau thì không có người quen chung còn 2 người không quen nhau thì có đúng 2 người quen chung !
Bài toán :
Tìm số tự nhiên $n>4$ nhỏ nhất sa0 ch0 tồn tại $n$ người thỏa mãn : 2 người quen nhau thì không có người quen chung còn 2 người không quen nhau thì có đúng 2 người quen chung !
Bài toán :
Tìm số tự nhiên $n>4$ nhỏ nhất sa0 ch0 tồn tại $n$ người thỏa mãn : 2 người quen nhau thì không có người quen chung còn 2 người không quen nhau thì có đúng 2 người quen chung !
Trước tiên ta chứng minh những người này có cùng người quen với nhau tại đây.
Cho mỗi người là một đỉnh của đồ thị. 2 người quen nhau thì được nối với nhau bằng 1 cạnh. Nên số người quen của mỗi người sẽ bằng với bậc của đỉnh. Suy ra đồ thì này có các đỉnh cùng bậc. Nói cách khác đây là một đồ thị đẳng cấu. Đồ thị này có $n$ đỉnh, các đỉnh có chung bậc $d$. Suy ra đồ thì có số cạnh là $m= \frac{nd}{2}$ với $d \ge 2$.
Ta tiếp tục chứng minh $|m| \leq 3(|n|-2)$.
Vì đồ thị này là liên thông nên theo định lí Euler suy ra: $|r|=|m|-|n|+2$ (r là số miền)
Gọi $n$ là tổng số cạnh thuộc các miền $r$ thì do mỗi cạnh chỉ thuộc nhiều nhất 2 miền nên $n \leq 2m$. Mỗi miền có ít nhất 3 cạnh nên $n \geq 3r$ từ đó suy ra $r \leq \frac{2}{3}m$. Thay vào công thức Euler ta đc đpcm.
Từ đó, ta có: $m= \frac{nd}{2} \le 3n-6$ $\rightarrow 12 \le (6-d)n$. Vậy $d \le 6$ (ta cần vế phải dương)
Theo các kết quả trên, ta thử chọn các trường hợp và chọn được $n_{min}=8$ với $d=3$.
Vậy $n_{min}=8$.
Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 07-07-2013 - 00:26
$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$
Trước tiên ta chứng minh những người này có cùng người quen với nhau tại đây.
Cho mỗi người là một đỉnh của đồ thị. 2 người quen nhau thì được nối với nhau bằng 1 cạnh. Nên số người quen của mỗi người sẽ bằng với bậc của đỉnh. Suy ra đồ thì này có các đỉnh cùng bậc. Nói cách khác đây là một đồ thị đẳng cấu. Đồ thị này có $n$ đỉnh, các đỉnh có chung bậc $d$. Suy ra đồ thì có số cạnh là $m= \frac{nd}{2}$ với $d \ge 2$.
Ta tiếp tục chứng minh $|m| \leq 3(|n|-2)$.
Vì đồ thị này là liên thông nên theo định lí Euler suy ra: $|r|=|m|-|n|+2$ (r là số miền)
Gọi $n$ là tổng số cạnh thuộc các miền $r$ thì do mỗi cạnh chỉ thuộc nhiều nhất 2 miền nên $n \leq 2m$. Mỗi miền có ít nhất 3 cạnh nên $n \geq 3r$ từ đó suy ra $r \leq \frac{2}{3}m$. Thay vào công thức Euler ta đc đpcm.Từ đó, ta có: $m= \frac{nd}{2} \le 3n-6$ $\rightarrow 12 \le (6-d)n$. Vậy $d \le 6$ (ta cần vế phải dương)
Theo các kết quả trên, ta thử chọn các trường hợp và chọn được $n_{min}=8$ với $d=3$.
Thử lại: Ta thấy đồ thị sau đây thỏa mãn bài toán:Vậy $n_{min}=8$.
Anh thử xem lại lời giải xem, người số 2 và 8 đâu thỏa mãn ạ. Đáp số $n=16$
Anh thử xem lại lời giải xem, người số 2 và 8 đâu thỏa mãn ạ. Đáp số $n=16$
khâu thử chọn anh làm sai @@!
đáp án đúng là $n=16$
$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$
0 thành viên, 1 khách, 0 thành viên ẩn danh