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ó đỉnh, 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 là 1 đỉnh bất kì. Giả sử, được nối với .

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 thì chỉ có đỉnh. Loại.

-Với .
1.Suy ra có duy nhất 1 điểm là điểm chung giữa 2 điểm .

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

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

Vì nếu như cùng được nối với thì giữa 2 người và sẽ cùng quen với người , người và người kia.

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

sẽ không được nối với bất cứ điểm nào khác trừ ()

Vậy đồ thị đó chỉ chứa điểm .

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

Tập những người không quen với sẽ là Vì, với mỗi người trong sẽ quen với người khác, bỏ ra thì còn người. Mà tập có người nên tổng cộng lại sẽ có 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 là người

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

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

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

Với loại

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

Với
Đáp án:

Q.E.D