Category Archives: Combinatorics

Toán Tổ Hợp.

Một bài toán thú vị

Con trai của một người bạn gửi một bài toán rất thú vị: Có 2013 con bài. Trên mỗi con bài người ta viết 1 số bất kỳ. Tất cả 2013 số này khác nhau. Người ta úp các con bài xuống. 1 bước đi cho phép người chơi chỉ ra 10 quân bài và […]

Chủ đề Combinatorics | Tagged , | 6 phản hồi »

Định lý Gale-Ryser

1. Định lý Gale-Ryser Định lý Gale-Ryser là một trong những định lý cổ điển của toán Tổ Hợp. Định lý này trả lời câu hỏi sau đây: Cho trước hai vectors và gồm các số nguyên dương. Có tồn tại một ma trận nhị phân gồm hàng và cột, sao cho tổng hàng thứ […]

Cũng thuộc về chủ đề Python, Thuật Toán | Tagged , | 6 phản hồi »

Định lý Brégman và entropy

1. Permanents Gọi là một ma trận vuông , là tập các hoán vị của , và là dấu của một hoán vị . Ta có thể tính định thức của bằng biểu thức Cũng công thức trên, nếu ta bỏ phần dấu của hoán vị đi thì ta có cái gọi là permanent của […]

Cũng thuộc về chủ đề Xác suất & thống kê | Tagged , , | 2 phản hồi »

Cây nhị phân và cây tìm kiếm nhị phân

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++. Bài trước: Danh sách liên kết và danh sách nhảy cóc Bài sau: Các cây tìm kiếm cân bằng: AVL, đỏ đen, (2,4), và cây loe 1. Binary trees 1.1. Terminologies A binary tree is […]

Cũng thuộc về chủ đề C++, Cấu trúc dữ liệu, Thuật Toán | Tagged , , | 4 phản hồi »

Một chứng minh khác cho bất đẳng thức Loomis-Whitney

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à […]

Chủ đề Combinatorics | Tagged , | 4 phản hồi »

Phần thuật toán của bài lính bắn laser

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 […]

Cũng thuộc về chủ đề Thuật Toán | Tagged , , | 22 phản hồi »

Lính bắn tia laser

Đô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 […]

Cũng thuộc về chủ đề Dành cho du học sinh | Tagged | 14 phản hồi »

Công thức

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.

Chủ đề Combinatorics | Tagged | Phản hồi »

Đếm xu

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 […]

Chủ đề Combinatorics | Tagged , , , , | 18 phản hồi »

Nghịch đảo Möbius và các viên bi mà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ố […]

Chủ đề Combinatorics | Tagged , , , , , | 28 phản hồi »

Cân xu

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 […]

Cũng thuộc về chủ đề Thuật Toán | Tagged , , | 6 phản hồi »

GT 6: Thử nhóm bất ứng biến giải mã nhanh

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 […]

Cũng thuộc về chủ đề Lý thuyết mã hóa, Thuật Toán | Tagged , , , | 3 phản hồi »

GT 5: Sơ lược lý thuyết mã hóa

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 […]

Cũng thuộc về chủ đề Lý thuyết mã hóa, Thuật Toán | Tagged , , , | 3 phản hồi »

GT 4: Bassalygo, Erdős, và Sperner

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í […]

Cũng thuộc về chủ đề Thuật Toán | 1 phản hồi »

GT 2: Phân Ly và Phân Cách

( 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 […]

Cũng thuộc về chủ đề Thuật Toán, Xác suất & thống kê | 31 phản hồi »