Cái chứng minh dùng entropy của bất đẳng thức Loomis-Whitney rất gọn nhưng hơi … phù thủy. Ta thử một chứng minh khác, cho trường hợp 3 chiều như trong bài lính bắn laser. Định lý. Cho ba tập hữu hạn . Định nghĩa Ta có . Chứng minh. Gọi các thành viên của là [...]
Ta tiếp tục với bài lính bắn laser. Nhờ định lý Loomis-Whitney, ta đã biết điều sau đây. Cho ba tập điểm thì không tồn tại nhiều hơn điểm sao scho , , và . Gọi các điểm này là các điểm ba màu. Với inputs là , để in ra các điểm ba màu [...]
Đôi khi nghĩ về một vấn đề thì lại nghĩ ra một bài toán (đố) thú vị chẳng liên quan gì đến vấn đề đầu tiên. Có anh lính đứng trên các tọa độ nguyên dương của trục . Mỗi anh bắn một tia xanh song song với trục lên hướng . Lại có anh [...]
Thấy ở đây: Cho , tổng số các điểm tọa độ nguyên thỏa điều kiện bằng Gợi nhớ công thức Hardy-Ramanujan-Rademacher.
Có đồng xu trông giống hệt nhau, trong đó có xu giả. Dĩ nhiên . Có một cái máy thử. Nếu nhét vào máy một mớ xu thì máy cho ta biết trong mớ đó có (ít nhất 1) xu giả hay không. (Máy kêu boong boong nếu có xu giả, và không kêu nếu [...]
1. Động cơ A. Công thức inclusion-exclusion nói rằng, để đếm tổng số nhóc tì có Chí Phèo là bố hoặc thị Nở là mẹ, thì ta cộng số con của chí Phèo với số con của thị Nở trừ đi số con chung. Nói cách khác cho tập thì Công thức này một số [...]
Bạn Huân hỏi về một bài toán đố cổ điển: bài toán cân xu tìm xu giả. Phiên bản thường nghe là như thế này: cho 12 đồng xu trong đó có 1 đồng xu giả (không biết nặng hay nhẹ hơn các đồng khác) và một cái cân thăng bằng, cân 3 lần tìm [...]
6. Thử nhóm bất ứng biến giải mã nhanh 6.1. Ý tưởng của Kautz-Singleton Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận -phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số trên cột) đủ lớn và nếu hai cột [...]
5. Sơ lược lý thuyết mã hóa Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc [...]
4. Chặn dưới Leonid Bassalygo là một học trò giỏi của người khổng lồ Kolmogorov. Từ những năm 1970, ông đã có nhiều đóng góp cơ bản trong lý thuyết thông tin, lý thuyết mã hóa, và lý thuyết các mạng chuyển mạch (switching networks). Có nhiều định lý và chặn mang tên ông. Ví [...]
( tiếp theo bài trước ). 2. Ma trận phân ly và ma trận phân cách Tiến Sĩ Nguyễn Quang A là một trong các trí thức hàng đầu của Việt Nam hiện nay. Tôi không biết gì về các công việc làm ăn của anh Quang A, nhưng tôi biết anh đã một tay [...]
Bài học máy qua góc nhìn của lý thuyết tính toán số 4 có chứng minh bổ đề Sauer (bổ đề 5.2) bằng quy nạp. Tuy nhiên, một chứng minh bằng quy nạp không hay lắm vì nó “giấu” trực quan của chứng minh. Trong bài này, chúng ta sẽ chứng minh bổ đề Sauer [...]
Hôm qua một phần bài giảng lớp randomized algorithms đẫn đến chứng minh đẳng thức sau đây: Có thể chứng minh đẳng thức này bằng cách viết lại vế trái thành Sau đó, chú ý rằng , ta khai triển tiếp thành: Đẳng thức cuối cùng có được là do . Có cách nào chứng [...]
Như mọi khi, tôi quan tâm đến bài tổ hợp trong đề năm nay: Let n and k be positive integers with k ≥ n and k−n an even number. Let 2n lamps labelled 1, 2, . . . , 2n be given, each of which can be either on or off. Initially all the [...]
Một người bạn gửi cho bài toán sau đây. Tôi vừa tìm được lời giải rất gọn. Cho n là một số nguyên lẻ lớn hơn 2. Mỗi cạnh của complete graph K_n được gán một cân nặng khác nhau. Chứng minh rằng có một walk chiều dài n trên graph K_n này với các [...]
