MathLabs

Bài 4

Cho n>0n>0 là một số nguyên. Ta có một chiếc cân và nn vật nặng có khối lượng 20,21,…,2n−12^0,2^1,\dots,2^{n-1}. Ta lần lượt đặt từng vật trong nn vật lên cân, sao cho đĩa cân bên phải không bao giờ nặng hơn đĩa cân bên trái. Ở mỗi bước, ta chọn một vật chưa được đặt lên cân và đặt nó lên đĩa trái hoặc đĩa phải, cho đến khi tất cả các vật đã được đặt. Hãy xác định số cách để thực hiện việc này.
Bước 1 trên 5: Thiết lập một ánh xạ quên giữa hai kích cỡ liên tiếp
Bước trướcBước tiếp
Hiểu nôm na

Vật nặng 1 không nhất thiết được đặt đầu tiên. Bỏ bước đặt nó; nếu nó ở bên phải thì độ lệch trước đó là số dương chẵn, nên chia đôi các vật còn lại vẫn giữ đĩa trái không nhẹ hơn.

20,21,…,2n−1 → 20,21,…,2n−22^0,2^1,\dots,2^{n-1}\ \to\ 2^0,2^1,\dots,2^{n-2}
Phân tích chi tiết

Gọi f(n)f(n) là số cách sắp xếp hợp lệ cho nn vật nặng 20,21,…,2n−12^0,2^1,\dots,2^{n-1}; ta muốn chứng minh f(n)=1⋅3⋅5⋯(2n−1)=(2n−1)!!f(n)=1\cdot3\cdot5\cdots(2n-1)=(2n-1)!!. Trường hợp cơ sở f(1)=1f(1)=1 là hiển nhiên: chỉ có vật nặng 11, đặt nó bên phải sẽ làm phải nặng hơn ngay, nên nó phải đặt bên trái, cho đúng một cách hợp lệ. Với một cách sắp xếp hợp lệ bất kỳ cho nn vật, bỏ đi bước đặt vật 202^0 rồi chia đôi mọi vật còn lại; kiểm tra ngắn gọn cho thấy phải vẫn không bao giờ nặng hơn trái ở bất kỳ giai đoạn nào, nên ta được một cách sắp xếp hợp lệ cho n−1n-1 vật 20,…,2n−22^0,\dots,2^{n-2}.