Amazon 4-for-3 deals

Amazon 4-for-3 deal:
Buy 4 item and have the one with the least price free. 4-for-3 items are under $10.
I believe if I buy 4n books, then it will be made into a 4n-for-3n deal that's not in writing, where n items with the least price is free. I did not test it yet, hope someone try that for me. Maxium saving is 25%, not bad.

How to maximize the amount of saving, suppose there is no such thing as shipping fee(If you are in your Amazon prime trial period).

1. Assume one have to buy n items.
2. If n is divisible by 4, the best strategy is to sort the items by price, forms a series of prices a_i, where a_i\le a_{i+1}. This also forms set B.(uhh.. this set allows repetition of elements...)
3. Buy a vector of them each time <a_{4i+1}, a_{4i+2}, a_{4i+3}, a_{4i+4}> for 0\le i\le \frac{n}{4}-1, which will maximize saving.
Proof: The total amount of money paid for this method is
\sum _{i=1}^{n} a_i - \sum _{i=0}^{\frac{n}{4}-1} a_{4i+1}
Make each of the number removed into a set, S
Each time find one element for S, the 4 element of B is removed.
A non-rigorous proof
Create n blocks out of 4n elements in B, name it b_1,b_2,b_3.....b_n
S is set containing the minimal for each b_n.
we can see a_1 has to be part of S, and b_1.
suppose a_2 is not in b_1, but in b_k,
and a_i is the smallest number in b_1 other than a_i.
If one switch a_2 with a_i, we can find all the smallest number in b_k is larger than a_2. All the rest blocks doesn't change at all.
Which shows that a_2 must be in the same block with a_1 to allow the sum of S be maximized.
use the same reasoning for a_3 and a_4.
and use the same reasoning for all blocks.
we get the original way have to be the best way.
If the count of elements in B is not divisible by 4, the best way is still the same, group items of 4 from most expensive to least expensive, remain a few least expensive ones in one group, buy each group separately.

This can be extended to any n-for-n-1 deals and should be able to extend to any n-for-k deals, where k lesser than n.

Post new comment

The content of this field is kept private and will not be shown publicly.
If you have a Gravatar account, used to display your avatar. If you have a Gravatar account, used to display your avatar.
  • Allowed HTML tags: <img> <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <span> <fn>
  • Lines and paragraphs break automatically.
  • Textual smileys will be replaced with graphical ones.
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>. Beside the tag style "<foo>" it is also possible to use "[foo]".
  • Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.

More information about formatting options

What is 32 + 31?
To combat spam, please solve the math question above.
Honey Pot that kill bots