Ta gọi voucher mệnh giá 16 SAR là voucher loại 1, mệnh giá 23 SAR là voucher loại 2. Ý tưởng cơ bản là nếu N chia hết cho 16 thì ta dùng loại 1 là được. Nhưng nếu N chia 16 có dư thì làm sao?
Dùng tiền mặt ta xử lý được tình huống số dư là 1, 2. Nhưng nếu số dư là 3 thì sao? Lúc này ta sẽ dùng 5 voucher loại 2 để được 115 SAR, phần còn lại chia hết cho 16 ta trả bằng voucher loại 1.
Chẳng hạn 131 = 5 x 23 + 1 x 16. Tất nhiên điều này chỉ thực hiện được nếu N ≥ 115. Dùng thêm 2 SAR tiền mặt, ta có thể sử lý được tình huống N chia 16 dư 4, 5. Bằng cách này, nếu ta xử lý được hết tất cả các số dư là xong.
Ta thấy:
23 chia 16 dư 7. Vậy ta xử lý được các số dư 7, 8, 9 với N ≥ 23.
2 x 23 chia 16 dư 14. Vậy ta xử lý được các số dư 14, 15 với N ≥ 46.
3 x 23 chia 16 dư 5. Vậy ta xử lý được các số dư 5, 6, 7 với N ≥ 69.
4 x 23 chia 16 dư 12. Vậy ta xử lý được các số dư 12, 13, 14 với N ≥ 92.
5 x 23 chia 16 dư 3. Vậy ta xử lý được các số dư 3, 4, 5 với N ≥ 115.
6 x 23 chia 16 dư 10. Vậy ta xử lý được các số dư 10, 11, 12 với N ≥ 138.
Như vậy thì mọi số N ≥ 138 đều chắc chắn sẽ trả đúng được. Tuy nhiên ngay cả những số < 138 cũng vẫn có thể trả đúng được.
Nhìn vào phân tích ở trên, ta thấy rằng nếu N chia 16 có số dư không phải là 10, 11 thì chỉ cần N ≥ 115 là trả đúng được. Từ đây ta tìm được số 123 là số lớn nhất không trả đúng được. Suy ra N = 124 là giá trị cần tìm.
Từ đây ta thấy chỉ cần đi khoảng 4 người là gần như sẽ không gặp vấn đề. Còn nếu đi 5 người trở lên thì chắc chắn sẽ không gặp vấn đề.
TS Trần Nam Dũng
Đại học Khoa học Tự nhiên (Đại học Quốc gia TP HCM)