Skip to content

Nhật ký Yale: Đố vui

Tháng Mười Hai 12, 2013

Hôm nay bác Noga Alon nói chuyện ở khoa toán. Nội dung thì hơi dài dòng, nhưng có một bài đố vui như sau:

Hai bạn A và B có chung một đồ thị phẳng G  trên 2^{1000} điểm. Bạn C đưa cho bạn A một cạnh e của đồ thị, và đưa cho bạn B một đỉnh v của cạnh e. (Bạn B không biết bạn A có cạnh nào, và bạn A không biết bạn B có đỉnh  nào trong hai đỉnh của $late x e$, nhưng hai bạn đều biết là đỉnh mà bạn B có là một đỉnh của cạnh của bạn A).  Làm thế nào bạn B có thể nói cho bạn A biết đinh của mình một cách nhanh nhất (tốn ít  lương thông tin nhất). Hai bạn có thể thoả thuận trước một protocol tuỳ ý. (Hai bạn có máy tính rất mạnh có thể giải bất kỳ bài toán nào trên G.)

Cách đơn giản nhất là hai bạn có thể thoả thuận môt cách  đánh số các đỉnh của đồ thị bằng các vector (0,1) có độ dài 1000, và bạn B chuyển 1000 bit của mình cho bạn A. Cách này sẽ tốn 1000 bit. Tìm những cách khác tốt hơn.

From → Khác

3 phản hồi
  1. Không biết protocal này có được không: tô mầu các đỉnh sao cho không có 2 đỉnh trên một cạnh có cùng mầu. Bạn B sẽ nói cho A biết mầu của đỉnh của mình. A sẽ suy ra đỉnh của B. Từ định lý 4-color của Appel và Haken, B chỉ cần dùng 2 bits.

  2. It is correct. What happens if A has 1000 edges and B has 1000 vertices ?

  3. Không thể có đến 2^1000 điểm được, vì số hạt trong vũ trụ nhìn thấy cũng chỉ khoảng 10^80 thôi !

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: