Bài Toán: Tồn tại chăng một nhóm người thỏa mãn điều kiện: mỗi người đều quen biết đúng $6$ người & $2$ người bất kỳ đều có đúng $2$ bạn chung?
MỖI NGƯỜI ĐỀU QUEN ĐÚNG 6 NGƯỜI VÀ 2 NGƯỜI BẤT KỲ CÓ ĐÚNG 2 BẠN CHUNG
#1
Đã gửi 13-09-2021 - 17:41
- Nesbit, perfectstrong, DOTOANNANG và 2 người khác yêu thích
#2
Đã gửi 16-09-2021 - 01:42
Hóa ra đây là một bài toán nổi tiếng Em tìm được một bài báo chứng minh bài toán tổng quát hơn tí (trong lý thuyết đồ thị): có đúng 3 đồ thị liên thông trong đó mỗi cặp đỉnh có đúng hai đỉnh chung.
http://www.kurims.ky...1/mb130_1_9.pdf
Trong 3 đáp án này, chỉ có 2 đáp án có bậc đồ thị là 6 nên suy ra câu trả lời là "Có" Đồ thị được miêu tả như sau:
Cách 1: Một đồ thị 16 đỉnh.
u: a b c d e f
a: u b c g h i
b: u a c j k l
c: u a b m n o
d: u e f g j m
e: u d f h k n
f: u d e i l o
g: a d h i j m
h: a e g i k n
i: a f g i l o
j: b d k l g m
k: b e j l h n
l: b f j k i o
m: c d n o g j
n: c e m o h k
o: c f m n i l
Cách 2: Cũng là một đồ thị 16 đỉnh.
u: a b c d e f
a: u b f g h i
b: u a c g j k
c: u b d j l m
d: u c e h l n
e: u d f k n o
f: u a e i m o
g: a b h k l o
h: a d g i l n
i: a f h m j n
j: b c k m i n
k: b e g j n o
l: c d m h g o
m: c f j l i o
n: d e h k i j
o: e f k m g
- supermember, DOTOANNANG và PDF thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#3
Đã gửi 16-09-2021 - 20:20
Sao anh kiếm được hay dữ vậy, em theo dõi hatenablog, với Twitter của người Nhật nhiều lắm. Trước đây em cũng từng có ghé thăm trang của khoa Toán đại học Kyoto bởi ông Shinichi Mochizuki chứng minh giả thiết ABC.
Anh di chuyển các chủ đề về Toán Đại cương đi anh, thêm một bài nữa của bé poset luôn.
#4
Đã gửi 16-09-2021 - 21:10
Sao anh kiếm được hay dữ vậy, em theo dõi hatenablog, với Twitter của người Nhật nhiều lắm. Trước đây em cũng từng có ghé thăm trang của khoa Toán đại học Kyoto bởi ông Shinichi Mochizuki chứng minh giả thiết ABC.
Anh di chuyển các chủ đề về Toán Đại cương đi anh, thêm một bài nữa của bé poset luôn.
Cái này anh kiếm trên google bằng cách gõ "graph theory pair of vertices has two common vertices" rồi dòm xuống vài cái link thì thấy
Về vị trí của bài toán này thì anh nghĩ để đây cũng được Anh supermember đã đăng ở đây thì hẳn là ảnh có ý đồ là bài này có thể giải bằng phương pháp sơ cấp. Bài báo anh tìm ra thì sử dụng các phương pháp cao cấp hơn nên không chắc sẽ dễ tiếp cận.
- supermember và DOTOANNANG thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#5
Đã gửi 16-09-2021 - 21:31
Bài này giải bằng đếm 2 cách:
Nếu ta minh họa nhóm $n$ người này là những đỉnh trên một đồ thị. Sau đó, nếu $2$ người quen nhau thì ta sẽ nối $2$ đỉnh đó bởi $1$ cạnh vô hướng.
Cứ $2$ người mà có $1$ người quen chung thì trên đồ thị, $3$ đỉnh tương ứng với $3$ người này cùng với $2$ cạnh thể hiện sự quen biết sẽ tạo thành $1$ hình chữ $V$
Trong đó có $1$ đỉnh ở vị trí là đỉnh của chữ $V$ . Đỉnh này chính là minh họa tương ứng cho người quen chung đó.
Ta sẽ đếm $2$ cách về số chữ $V$ có thể có:
Cách 1: Do cứ $1$ người lại quen biết $6$ người, nên nếu chọn ra các chữ $V$ có đỉnh là 1 đỉnh cho trước thì có tổng cộng: $ \binom{6}{2} = 15$ chữ $V$ như thế.
Graph này có $n$ đỉnh nên tổng số chữ $V$ có thể có là : $15n$ theo quy tắc nhân.
Cách 2: Do cứ $2$ người bất kỳ lại có $2$ người quen chung, tức là từ $1$ cặp $2 $ đỉnh tùy ý trong graph này thì xây dựng ra được $2$ hình chữ $V$ và có $\binom{n}{2}$ cách chọn ra $1$ cặp $2$ đỉnh tùy ý trong graph , nên theo quy tắc nhân thì tổng số hình chữ $V$ có thể có là $2 \cdot \binom{n}{2} =n(n-1)$ .
Từ đây suy ra: $15n = n(n-1) \Rightarrow n =16$
Ta xây dựng graph như sau:
Phân hoạch tập $16$ đỉnh này thành $4$ tập con : $ A= \{A_1 ; A_2 ; A_3; A_4 \} ; B= \{B_1 ; B_2 ; B_3; B_4 \} ; C= \{C_1 ; C_2 ; C_3; C_4 \} ; D= \{D_1 ; D_2 ; D_3; D_4 \}$
Ta tiến hành nối các đỉnh này theo quy tắc sau:
Quy tắc 1: Các đỉnh nằm trong cùng $1$ tập hợp đều được nối với nhau:
Quy tắc 2: Các đỉnh khác tập hợp thì sẽ được nối với nhau nếu chúng có cùng chỉ số. Tức là các đỉnh nằm trong $1$ bộ $4$ đỉnh $(A_k; B_k; C_k; D_k)$ sẽ được nối với nhau với mọi $k$ chạy từ $1$ đến $4$.
Dễ kiểm tra là với cấu hình này thì mỗi người sẽ đều có đúng $6$ người quen và $2$ người tùy ý sẽ đều có đúng $2$ người quen chung.
Bài toán theo đó có câu trả lời là tồn tại.
Bài viết đã được chỉnh sửa nội dung bởi supermember: 16-09-2021 - 22:02
- perfectstrong và DOTOANNANG thích
#6
Đã gửi 17-09-2021 - 03:59
Một kết quả có liên quan là nếu mọi cặp đỉnh trong đồ thị có đúng hai đỉnh chung thì đồ thị này đồng bậc (mọi đỉnh có bậc bằng nhau).
https://math.stackex...hbours-is-regul
- DOTOANNANG yêu thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh