Đến nội dung

Hình ảnh

Tìm số tự nhiên $n>4$ nhỏ nhất sa0 ch0 tồn tại $n$ người thỏa mãn....

- - - - -

  • Please log in to reply
Chủ đề này có 4 trả lời

#1
WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản lý Toán Ứng dụ
  • 1323 Bài viết

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 !


“There is no way home, home is the way.” - Thich Nhat Hanh

#2
Stranger411

Stranger411

    Hạ sĩ

  • Thành viên
  • 85 Bài viết

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)$


#3
WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản lý Toán Ứng dụ
  • 1323 Bài viết

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:
56620119.untitled.png

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$


“There is no way home, home is the way.” - Thich Nhat Hanh

#4
Stranger411

Stranger411

    Hạ sĩ

  • Thành viên
  • 85 Bài viết

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)$


#5
hansongkyung

hansongkyung

    Lính mới

  • Thành viên
  • 3 Bài viết

Đây hé :P

 

http://forum.mathsco...ead.php?t=44060






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh