Câu hỏi 30
Cho số nguyên dương $n$. Trong một mạng có $n$ máy tính, được đánh số bởi các số tự nhiên $1, 2, \dots, n$. Các máy tính được nối với nhau bằng các đường truyền một chiều sao cho thông tin có thể được gửi từ bất kỳ máy tính nào đến tất cả các máy tính khác, trực tiếp hoặc thông qua các máy tính khác trong mạng. Ban đầu, mỗi máy tính chỉ biết số hiệu của chính nó. Khi một thủ tục nhất định được kích hoạt trên một máy tính, máy tính đó xuất ra tất cả các số hiệu máy tính mà nó biết và truyền chúng đến tất cả các máy tính mà nó có đường truyền trực tiếp tới. Người vận hành kích hoạt thủ tục này trên các máy tính tùy chọn theo thứ tự tùy ý (có thể nhiều lần trên cùng một máy tính).
Chứng minh rằng số lần kích hoạt thủ tục tối thiểu để có thể làm cho mọi máy tính đều đã xuất ra số hiệu của tất cả các máy tính ít nhất một lần không phụ thuộc vào mạng đường truyền mà chỉ phụ thuộc vào số $n$, và tìm số lần kích hoạt đó.
Chứng minh rằng số lần kích hoạt thủ tục tối thiểu để có thể làm cho mọi máy tính đều đã xuất ra số hiệu của tất cả các máy tính ít nhất một lần không phụ thuộc vào mạng đường truyền mà chỉ phụ thuộc vào số $n$, và tìm số lần kích hoạt đó.