喝汽水問題

                                                  by flyinghearts

有1000瓶汽水，喝完后每3個空瓶能換1瓶汽水，問最后最多可以喝幾瓶汽水，此時剩余幾個空瓶？

不妨假設，共有n瓶汽水，每a個空瓶能換b瓶汽水（a > b）。剛開始有n瓶汽水，喝完后就有n個空瓶，多喝的汽水是靠空瓶換來的，每進行一次空瓶換汽水，就能多喝b瓶汽水、空瓶數目就減少了a-b個（a個空瓶換了b瓶汽水，喝完后得到b個空瓶）。

(下面用 [x] 表示x的整數部分)

1 如果允許從別處（老板或其他顧客處）借空瓶（當然，有借有還）

空瓶換汽水次數：   [n / (a - b)]

最后剩余空瓶：     n % (a - b)

總共可以喝到汽水： n + [n / (a - b)] * b

2 不允許借空瓶

 空瓶換汽水過程中，一但空瓶數小于a，則停止交換。

 對 n < a，顯然，空瓶換汽水次數為0，總共可以喝到汽水n瓶，最后剩余空瓶n個

 對 n >= a：（下面提供三種解法）

  解法一    空瓶換汽水次數k等于滿足n – (a-b)*t < a的最小非負整數t:

              t > (n-a)/(a-b)，最小的t為 [(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]

              剩余的空瓶數：n – (a-b)*t

= n – (a-b)*([(n-b)/(a-b)])

                           = b + (n-b) - (a-b)*([(n-b)/(a-b)])

= b + (n-b)%(a-b)

解法二   先預留a個空瓶，將剩余的n-a個空瓶進行換汽水，換的過程中，若空瓶不夠a個，則從預留的a個空瓶中“借”，因而，

空瓶換汽水次數：[(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]（預留的a個空瓶也能換一次）

最后剩余空瓶： (n-b) % (a-b) + b（預留的a個空瓶換得b瓶汽水）

解法三   最后一次空瓶換汽水得到的b瓶汽水，喝完后得到b個空瓶，因而最后剩余空瓶數必然大于b個，先預留b個空瓶，將剩余的n-b個空瓶進行換汽水，若空瓶不夠a個，則從預留的b個空瓶中“借”（由于能進行空瓶換汽水，空瓶數>= a – b，因而“借”完后，可以保證空瓶數大等于a），

           空瓶換汽水次數：[(n-b)/(a-b)]，

最終剩余空瓶數：b + (n-b) % (a-b)

（對解法三，n>=b時結論成立，對解法一、二，可以驗證n >=b時，結論也成立）

因而，對 n >= b

空瓶換汽水次數：   [(n-b)/(a-b)]

最后剩余空瓶：     b + (n-b) % (a-b)

總共可以喝到汽水： n + [(n-b)/(a-b)] * b

對原題：

 n = 1000，a = 3, b = 1， a – b = 2

 若允許借空瓶    

可以喝到汽水： 1000 + 1000 / 2 = 1500

剩余空瓶：1000 % 2 = 0

若不允許借空瓶

可以喝到汽水： 1000 + (1000 - 1) / 2 = 1499，

剩余空瓶：     1 + (1000 - 1) % 2 = 2