Túi Tiền Bí Ẩn: Làm Sao Chia $100$ Đồng Vàng Để Thanh Toán Mọi Số Tiền?

Chào mừng bạn đến với thử thách toán học đầy trí tuệ và ứng dụng thực tế!

Đề bài

Một thợ mỏ vừa tìm thấy một kho báu gồm $100$ đồng vàng quý giá. Anh ta muốn chia số vàng này vào ít nhất các túi tiền có thể, sao cho bằng cách đưa ra các túi tiền (mà không cần mở chúng), anh ta có thể thanh toán bất kỳ số tiền nào từ $1$ đồng đến $100$ đồng cho người gác cổng.

Hỏi người thợ mỏ cần tối thiểu bao nhiêu túi tiền?
Và mỗi túi tiền phải chứa bao nhiêu đồng vàng?

Bạn có thể giúp anh ta không?

Gợi ý

Bài toán này liên quan đến cách biểu diễn số trong một hệ thống đặc biệt. Hãy nghĩ về cách mà hệ nhị phân (cơ số $2$ ) hoạt động, nhưng với một chút điều chỉnh ở túi cuối cùng để phù hợp với tổng số đồng vàng và giới hạn trên là $100$ .

Hãy bắt đầu với túi tiền nhỏ nhất có thể.
Mỗi túi tiền tiếp theo nên có số lượng đồng vàng đủ để “lấp đầy” các khoảng trống chưa thể tạo ra bằng các túi trước đó, hoặc mở rộng phạm vi thanh toán lên gấp đôi.
Tổng số đồng vàng trong tất cả các túi phải chính xác bằng $100$ .

Lời giải chi tiết

Để có thể thanh toán bất kỳ số tiền nào từ $1$ đến $100$ đồng mà không cần mở túi, chúng ta cần chia số vàng theo một quy tắc đặc biệt. Phương pháp hiệu quả nhất là sử dụng lũy thừa của $2$ , nhưng có một điều chỉnh cho túi cuối cùng.

Chúng ta hãy bắt đầu với số đồng vàng trong các túi:

Túi 1: Để có thể trả $1$ đồng, túi đầu tiên phải chứa $1$ đồng vàng. (Hiện tại có thể trả từ $1$ đồng).
Túi 2: Với túi $1$ đồng, chúng ta chỉ có thể trả $1$ đồng. Để có thể trả $2$ đồng và $3$ đồng ( $1+2$ ), túi thứ hai nên chứa $2$ đồng vàng. (Hiện tại có thể trả từ $1$ đến $3$ đồng: $1, 2, 1+2=3$ ).
Túi 3: Tiếp tục quy luật, túi thứ ba nên chứa $4$ đồng vàng. (Hiện tại có thể trả từ $1$ đến $1+2+4=7$ đồng).
Túi 4: Túi thứ tư chứa $8$ đồng vàng. (Hiện tại có thể trả từ $1$ đến $1+2+4+8=15$ đồng).
Túi 5: Túi thứ năm chứa $16$ đồng vàng. (Hiện tại có thể trả từ $1$ đến $1+2+4+8+16=31$ đồng).
Túi 6: Túi thứ sáu chứa $32$ đồng vàng. (Hiện tại có thể trả từ $1$ đến $1+2+4+8+16+32=63$ đồng).

Đến đây, chúng ta đã sử dụng $6$ túi và có thể thanh toán bất kỳ số tiền nào từ $1$ đến $63$ đồng. Tổng số đồng vàng trong $6$ túi này là $1+2+4+8+16+32=63$ đồng.

Chúng ta cần thanh toán đến $100$ đồng. Tổng số vàng còn lại là $100 - 63 = 37$ đồng. Chúng ta sẽ đưa tất cả số vàng còn lại này vào túi cuối cùng.

Túi 7: Chứa $37$ đồng vàng.

Vậy, người thợ mỏ cần $7$ túi tiền với số đồng vàng trong mỗi túi lần lượt là:

Kiểm tra lại:

Tổng số vàng: $1+2+4+8+16+32+37 = 100$ đồng. Chính xác!
Khả năng thanh toán:

Từ $1$ đến $63$ đồng: Có thể thanh toán bằng cách kết hợp các túi $1, 2, 4, 8, 16, 32$ .
Từ $64$ đến $100$ đồng: Để thanh toán một số tiền $N$ bất kỳ trong khoảng này, chúng ta sẽ dùng túi $37$ đồng, và cần thêm $N - 37$ đồng.
Giá trị $N - 37$ sẽ nằm trong khoảng từ $64-37 = 27$ đồng đến $100-37 = 63$ đồng.
Vì chúng ta có thể tạo ra bất kỳ số tiền nào từ $1$ đến $63$ đồng bằng $6$ túi đầu tiên, chúng ta chắc chắn có thể tạo ra bất kỳ số tiền nào từ $27$ đến $63$ đồng.
Do đó, bằng cách kết hợp túi $37$ đồng với các túi nhỏ hơn, chúng ta có thể tạo ra mọi số tiền từ $64$ đến $100$ đồng.