Bài 5

Với mỗi số nguyên dương

n

, Ngân hàng Cape Town phát hành đồng xu mệnh giá

\tfrac{1}{n}

. Cho một tập hợp hữu hạn các đồng xu như vậy (mệnh giá không nhất thiết khác nhau) với tổng giá trị không vượt quá

99+\tfrac12

, chứng minh rằng có thể chia tập hợp này thành

100

nhóm trở xuống sao cho mỗi nhóm có tổng giá trị không vượt quá

1

Bước 1 trên 6: Hai phép ghép không mất giá trị

Bước trước Bước tiếp

\underbrace{\tfrac{1}{2m}+\tfrac{1}{2m}}_{2} = \tfrac{1}{m}, \qquad \underbrace{\tfrac{1}{2m+1}+\cdots+\tfrac{1}{2m+1}}_{2m+1} = 1

Phân tích chi tiết

Lặp lại hai phép sau khi còn có thể, không làm đổi tổng giá trị: nếu một đồng mệnh giá $\tfrac{1}{2m}$ xuất hiện hai lần, thay cặp đó bằng một đồng mệnh giá $\tfrac{1}{m}$ ; nếu một đồng mệnh giá $\tfrac{1}{2m+1}$ xuất hiện $2m+1$ lần, tách cả $2m+1$ đồng đó ra thành một nhóm hoàn chỉnh riêng (tổng giá trị đúng bằng $1$ ). Mỗi phép làm giảm ngặt số đồng xu, nên quá trình này dừng lại.