Đến nội dung

Hình ảnh

MỖI NGƯỜI ĐỀU QUEN ĐÚNG 6 NGƯỜI VÀ 2 NGƯỜI BẤT KỲ CÓ ĐÚNG 2 BẠN CHUNG

- - - - -

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

#1
supermember

supermember

    Đại úy

  • Hiệp sỹ
  • 1644 Bài viết

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?


Khi bạn là người yêu Toán, hãy chấp nhận rằng bạn sẽ buồn nhiều hơn vui :)

#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

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

Hóa ra đây là một bài toán nổi tiếng :D 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ó" :D Đồ 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


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#3
DOTOANNANG

DOTOANNANG

    Đại úy

  • ĐHV Toán Cao cấp
  • 1609 Bài viết

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
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

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

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 :D

 

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.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#5
supermember

supermember

    Đại úy

  • Hiệp sỹ
  • 1644 Bài viết

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

Khi bạn là người yêu Toán, hãy chấp nhận rằng bạn sẽ buồn nhiều hơn vui :)

#6
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

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

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


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.




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

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