Trang chủ » Những bài toán thú vị » Graph – Learn form a mistake

Graph – Learn form a mistake

Tìm số tự nhiên n>4 nhỏ nhất sao cho 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.

Lời giải: (Hansongkyung – Mathscope)

1. Dễ dàng chứng minh được số người quen của mỗi người là bằng nhau (Tổ hợp & Rời rạc – Nguyễn Văn Thông)

2. Bài toán quy về 1 đồ thị có n đỉnh, m cạnh. Ứng với nó, mỗi đỉnh là 1 người, cạnh biểu thị cho sự quen biết giữa 2 người. Và điều kiện của đồ thị này là không có 3 cạnh này tạo thành 1 hình tam giác. Nếu 2 đỉnh không được nối với nhau thì tồn tại duy nhất 2 đỉnh khác cùng được nối với 2 đỉnh kia.

Gọi X là 1 đỉnh bất kì. Giả sử, X được nối với A_1,A_2,\cdots , A_m.

Mặt khác, trong $m$ đỉnh trên thì không có 2 đỉnh bất kì nào được nối với nhau.

-Với m = 1 thì chỉ có 2 đỉnh. Loại.

-Với m \ge 2.
1.Suy ra có duy nhất 1 điểm B_{i,j} \ne X là điểm chung giữa 2 điểm (A_i;A_j).

2. Đỉnh B_{i,j} này cũng không được nối với đỉnh nào khác thuộc tập X. Vì như vậy thì B_{i,j} sẽ có tới 3 người quen chung với X.

3. Nếu A_i được nối với 1 đỉnh C không thuộc tập B_i thì đỉnh C đó sẽ không đc nối với 1 điểm A_k nào thuộc X.

Vì nếu như C cùng được nối với A_i;A_k thì giữa 2 người A_iA_k sẽ cùng quen với người X, người B_{i,k} và người C kia.

Khi đó C sẽ chỉ được nối với A_i và không được nối với các đỉnh nào khác thuộc tập X. Suy ra giữa CX chỉ có mỗi 1 người quen. Vô lí.

\Rightarrow A_i sẽ không được nối với bất cứ điểm nào khác trừ X; B_{i,j} (j \ne i; j =1;m)

Vậy đồ thị đó chỉ chứa điểm X; A_i; B_{i,j}.

Từ những lập luận trên ta có được:

Tập những người không quen với X sẽ là \dfrac{m(m-1)}{2} Vì, với mỗi người trong X sẽ quen với m người khác, bỏ X ra thì còn m-1 người. Mà tập Xm người nên tổng cộng lại sẽ có (m-1)m nhưng vì đây là đồ thị vô hướng, nói các khác, sự quen biết là không có chiều nên ta phải chia cho 2.

Những người quen của Xm người

Thêm X nữa là 1 người.

Vậy tổng số người sẽ là:

n= \dfrac{m(m-1)}{2} + m +1

Giờ ta sẽ xét các trường hợp:

Với m=2 \Rightarrow n =4 loại

Với m=3, 4 ta đều chi ra được sự mâu thuẫn với điều kiện đề bài.

Với m=5 \Rightarrow n =16
Đáp án: n=16

Q.E.D

2 thoughts on “Graph – Learn form a mistake

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s