Bài toán về cách xài voucher tiết kiệm nhất ở Saudia Arabia

aA

Các bài toán thực tế luôn hấp dẫn học sinh, sử dụng dạng bài này là cách rất tốt để mở đầu cho một chủ đề toán học nghiêm túc.

Trong một chuyến đi Saudia Arabia, ông Nam chuẩn bị hai loại voucher có mệnh giá 16 riyal (SAR) và 23 riyal, mỗi loại đều có đủ nhiều. Khi mua đồ ăn ở nhà ăn, quầy tính tiền sẽ không trả lại tiền thừa nếu khách đưa thừa, nhưng sẽ không đồng ý nếu khách đưa thiếu dù chỉ một riyal.

Chẳng hạn nếu khách mua đồ ăn giá 18 SAR vẫn phải trả một voucher 23 SAR (thiệt mất 5 SAR). Còn nếu mua 30 SAR thì cách tối ưu là dùng 2 voucher loại 16 SAR (thiệt mất 2 SAR).

Để khắc phục tình trạng này, ông Nam có dự trữ thêm 2 SAR tiền mặt, như vậy gặp tình huống bữa ăn giá 18 SAR có thể trả một voucher 16 SAR và 2 SAR tiền mặt, tương tự với bữa ăn giá 25 SAR (23 + 2) hay 40 SAR (16+23+1).

Tuy nhiên, vẫn còn có những tình huống khiến ông bị thiệt, ví như với bữa ăn giá 35 SAR thì ông đành phải trả 16+23 = 39, thiệt 4 SAR. Du khách này trao đổi với một số người bạn thì nhận được lời khuyên rằng nếu khách hàng đi đông người và tính tiền chung thì hầu như vấn đề này sẽ không xảy ra.

bai toan ve cach xai voucher tiet kiem nhat o saudia arabia

Đố bạn tìm số nguyên dương N nhỏ nhất sao cho nếu tổng số tiền không nhỏ hơn N thì ta luôn trả đúng được bằng hai loại voucher ở trên và 2 SAR tiền mặt. Ngoài ra, ông Nam cần đi chung với mấy người bạn nữa để có thể luôn trả đúng,biết rằng giá một bữa ăn trưa dao động từ 30 SAR đến 50 SAR?