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

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.

Đố 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?

Cơ hội làm 'tổng thống' không thể bỏ qua trong tuần lễ vàng Vinpearl Kỳ nghỉ Tổng thống 3 ngày 2 đêm tại Vinpearl Phú Quốc trị giá 200 triệu đồng cùng hàng nghìn voucher nghỉ dưỡng Vinpearl với ...

Bên trong khách sạn xa xỉ giam giữ hoàng thân Ả-rập suốt 2 tháng Hoàng thân Alwaleed bin Talal nằm trong số hàng chục nhân vật có máu mặt của Saudia Arabia bị giam giữ tại khách sạn 5 ...

TS Trần Nam DũngĐại học Khoa học Tự nhiên (Đại học Quốc gia TP HCM)