[superprismatic]

As the setup for this problem is the same as for my earlier

post, Shyster Al's Furniture Emporium, I'll repeat the

setup:

Shyster Al owns a furniture store. He's always looking for

a way to lure customers away from his competitors. But, in

the cut-throat furniture business, the best deal a dealer can

give to a customer is a 25% discount below the MSRP (Manufacturer's

Suggested Retail Price) and still make the necessary profit

to keep the store viable. One fine day, Al hit on a beautiful

scheme for his SAFE (Shyster Al's Furniture Emporium) store

which makes it seem as though his customers can get something

close to a 33.333...% discount. His scheme is this: If a

customer buys several items, he pays full MSRP price for the

first item. For subsequent items, he pays full price minus

1/3 of what he had to pay after the discount due on the previous

item. For example, if a customer is buying 4 items with these

MSRPs, in order, $600, $650, $900, and $300. He pays full price

for the first item but gets a discount of $200 on the second

item (1/3 of $600) for which he pays $450. This gives him a $150

discount on the third item (1/3 of $450) which costs him $750.

So, 1/3 of his net cost of the third item ($250) will be his

discount on the fourth, which will now only cost him another $50.

So, he pays $1850 ($600+$450+750+$50) for $2450 MSRP of furniture.

Each discount is limited by the price of the item being bought,

so, e.g., a discount of $100 on something costing $50 will revert

to a $50 discount.

What is the largest percentage discount which can be realized on

10 items, each having a positive MSRP, bought from Shyster Al?

For simplicity, assume that MSRP prices can be any positive real

numbers and that all calculations are done with infinite precision.

In other words, assume an ideal world where currency is concerned.

The answer to my first Shyster Al post was close to 25%. Is this

the largest possible for any set of 10 real MSRPs in any order?

[Guest]

Is 25%. It can be achieved in this manner:

Purchase the most expensive item you will buy.

Then purchase an item that is 1/3 the cost of that item. With discount it is free. Total spent is just the cost of the original item, while total msrp is original item times 4/3. Total discount so far is 1/4 or 25%.

Repeat this for the next 8 items, discount will remain 25% as all odd number purchases recieve 0 discount and give 1/3 disount while all even purchases are free after 1/3 discount and give no discount to the next item.

This all assumes that you are able to find items to buy where 1 item is 3 times the cost of the other. No larger discount is possible, if the 2nd item costs less than 1/3 than some discount is lost. If it costs more than 1/3, then the amount spent goes up and the overall discount will be lower.

Edited May 14, 2011 by Nana7

[superprismatic]

Is 25%. It can be achieved in this manner:

Purchase the most expensive item you will buy.

Then purchase an item that is 1/3 the cost of that item. With discount it is free. Total spent is just the cost of the original item, while total msrp is original item times 4/3. Total discount so far is 1/4 or 25%.

Repeat this for the next 8 items, discount will remain 25% as all odd number purchases recieve 0 discount and give 1/3 disount while all even purchases are free after 1/3 discount and give no discount to the next item.

This all assumes that you are able to find items to buy where 1 item is 3 times the cost of the other. No larger discount is possible, if the 2nd item costs less than 1/3 than some discount is lost. If it costs more than 1/3, then the amount spent goes up and the overall discount will be lower.

Yes, you've shown that you can get a discount of 25%. But you haven't shown that something larger is not possible.

By the way, you are allowed to assume that Shyster Al will always have 10 items for sale at whatever 10 MSRPs you desire.

[Guest]

Math proof that 1/4 is largest possible discount.

Denote msrp price for first item as 3x and price for second item as x. Total msrp is 4x and total spent is 3x, for discount of 1/4.

Test for other prices of second item by adding or subtracting n from its price.

For subtracting n:

First item is 3x, second is x-n. Mrsp is 4x-n, total spent is still 3x since item can not be discounted more than its own price. Discount is 1-3x/(4x-n). Compare this to max discount which is 1-3x/4x. Since 4x-n is less than 4x, then its reciprocal is greater, and the discount is smaller since discount is 1-reciprocal times 3x in both cases so a larger reciprocal means a smaller discount. This is true for all x and n.

For adding n, effect on first two items

First item is 3x, second is x+n, total msrp is 4x+n, total spent is 3x+n. Discount is 1-(3x+n)/(4x+n). As n is added to both the numerator and denominator, the fraction approachs 1 for increasing n values. So the discount approaches 0. The largest discount is for n=0, which is the original case. Positive n means some money will be spent on item 2, n dollars will be spent. This will give a discount of n/3 to the next item, but that still leaves 2/3 of n added to the overall amount spent, and is still a discount smaller than 1/4 overall. That is true for all x and n.

That covers all possible prices.

[superprismatic]

Math proof that 1/4 is largest possible discount.

Denote msrp price for first item as 3x and price for second item as x. Total msrp is 4x and total spent is 3x, for discount of 1/4.

Test for other prices of second item by adding or subtracting n from its price.

For subtracting n:

First item is 3x, second is x-n. Mrsp is 4x-n, total spent is still 3x since item can not be discounted more than its own price. Discount is 1-3x/(4x-n). Compare this to max discount which is 1-3x/4x. Since 4x-n is less than 4x, then its reciprocal is greater, and the discount is smaller since discount is 1-reciprocal times 3x in both cases so a larger reciprocal means a smaller discount. This is true for all x and n.

For adding n, effect on first two items

First item is 3x, second is x+n, total msrp is 4x+n, total spent is 3x+n. Discount is 1-(3x+n)/(4x+n). As n is added to both the numerator and denominator, the fraction approachs 1 for increasing n values. So the discount approaches 0. The largest discount is for n=0, which is the original case. Positive n means some money will be spent on item 2, n dollars will be spent. This will give a discount of n/3 to the next item, but that still leaves 2/3 of n added to the overall amount spent, and is still a discount smaller than 1/4 overall. That is true for all x and n.

That covers all possible prices.

Now you have to show that this extends to the best possible for 10 items. Your first post showed that

you can get to 10 without changing the discount that you got from the first 2. Somehow you must show that

the best for 10 is one that starts with the best for 2. Perhaps an inductive argument will work?

[Guest]

Any case from the first two which results in a discount flowing to the 3rd will be an overall discount below 25%. Therefore all odd items can be considered to be the same case as the first item, since none of them begin with a discount already. So what applies for a case of 2 will apply for all cases of even number items whether it is 2, 10, or a million, the best discount will always be 25%.

[superprismatic]

Any case from the first two which results in a discount flowing to the 3rd will be an overall discount below 25%. Therefore all odd items can be considered to be the same case as the first item, since none of them begin with a discount already. So what applies for a case of 2 will apply for all cases of even number items whether it is 2, 10, or a million, the best discount will always be 25%.

You say, "Any case from the first two which results in a discount flowing to the 3rd will be an overall discount below 25%."

But the sequence 600, 650, 300, 50, 3, 1, 3, 1, 3, 1 has a discount flowing to the 3rd and enjoys a discount that is not below 25%.

[Guest]

I stopped short with the 3rd item. I failed to notice that the next item, getting a 1/3 discount, can bring the average back to 25%. And even if it does not get it all the way back to 25, more items still have that potential. So the proof needs another step to show that, or maybe a proof that takes a different approach.

Edited May 14, 2011 by Nana7

[superprismatic]

I stopped short with the 3rd item. I failed to notice that the next item, getting a 1/3 discount, can bring the average back to 25%. And even if it does not get it all the way back to 25, more items still have that potential. So the proof needs another step to show that, or maybe a proof that takes a different approach.

At first blush, it seems easy to show that 25% is the best that can be done. I've tried, but I still can't come up with a proof of that fact.

On the other hand, I can't seem to come up with anything better than that. There's something going on here that I can't grasp. I hope others

work on this and come to some conclusion. Anyway, thank you for your valliant attempt. Please keep working on it, as I will. Welcome to the club!

[Guest]

I tried some other scenarios and 25% is simple to achieve with almost any set of numbers in practically any order with only the following rules, 1) do not lose any discount dollars by buying an item cheaper than 1/3 the price paid for the prior item. For item 10, buy an item that is exactly 1/3 the price that was paid for item 9. I think that will always be 25%. Maybe proving that case will prove that it can never be more than 25%

Edited May 15, 2011 by Nana7

[Guest]

I can not find a simple or elegant proof. There is a way to prove it though, but it is very ugly and drawn out. Start by noting that the final item purchased must have msrp equal to 1/3 the amount paid for the previous item, otherwise we will not have the best possible discount. Next rule is that no discount may be wasted, no msrp may be less than the amount paid for the prior item. Next, calculate the overall discount for n items for case where only n items are purchased, for all n from 3 to 10. I already did the case for n=2, that is why only 3 through 10 are left to do. The reason for not just doing 10 is because the proof involves a chain of discount effects from prior items and the chain is broken and reset whenever a set of items leaves no discount. But since it works for n = 2 and n = 3 (shown below), it is ok to break the chain along the way to 10 items since we just finish buying the remaining items using cases of n=2 and/or n=3.

Case for n = 3. Other n will be similar. Msrp will be indicated by letters a,b,etc

Total the msrp, a+b+c. Note that c must equal 1/3 price paid for b. Price paid for b is (b-a/3). Total msrp is now a+b+(b-a/3)/3=8/9a+4/3b=(8a+12b)/9=4/9(2a+3b)

Total the amounts paid, note item 3 is free so total is a+b-a/3 = (2a+3b)/3

Dividing amount paid by msrp and simplifying yields 3/4. Overall discount is then 1/4 for all cases that follow the rules above. This same method can be used for other cases of n but it really gets drawn out with lots of letters and also with increasing powers of 3 for each new n.

Edited May 15, 2011 by Nana7

[Guest]

I can not find a simple or elegant proof. There is a way to prove it though, but it is very ugly and drawn out. Start by noting that the final item purchased must have msrp equal to 1/3 the amount paid for the previous item, otherwise we will not have the best possible discount. Next rule is that no discount may be wasted, no msrp may be less than the amount paid for the prior item. Next, calculate the overall discount for n items for case where only n items are purchased, for all n from 3 to 10. I already did the case for n=2, that is why only 3 through 10 are left to do. The reason for not just doing 10 is because the proof involves a chain of discount effects from prior items and the chain is broken and reset whenever a set of items leaves no discount. But since it works for n = 2 and n = 3 (shown below), it is ok to break the chain along the way to 10 items since we just finish buying the remaining items using cases of n=2 and/or n=3.

Case for n = 3. Other n will be similar. Msrp will be indicated by letters a,b,etc

Total the msrp, a+b+c. Note that c must equal 1/3 price paid for b. Price paid for b is (b-a/3). Total msrp is now a+b+(b-a/3)/3=8/9a+4/3b=(8a+12b)/9=4/9(2a+3b)

Total the amounts paid, note item 3 is free so total is a+b-a/3 = (2a+3b)/3

Dividing amount paid by msrp and simplifying yields 3/4. Overall discount is then 1/4 for all cases that follow the rules above. This same method can be used for other cases of n but it really gets drawn out with lots of letters and also with increasing powers of 3 for each new n.

Nice work nana, I'm writing out the general solution, I wish there was a handy way to sum powers of 3!

[Guest]

Hm, I think this is correct, but I don't have the time right now to analyze it. I grouped terms up, the MSRPs are a through j, a>b>c>d....>j. Here is the first few terms, a + b - a/3 + c - b/3 - a/9 + d - c/3 - b/9 - a/27, and so on, and the last price looks like this j - i/3 - h/9 - g/27 - f/81 - e/243 - d/729 - c/287 - b/6561 - a/19683. not very elegant right?

Here's the final price all tidied up, on first glance it seems like its a bigger discount than i imagined so i think its wrong, but i think i am on the right track: a*9842/19683 + b*3281/6561 + c*1094/2187 + d*365/729 + e*122/243 + f*41/81 + g*14/27 + h*5/9 + i*2/3 + j. Nana7 maybe you can finish it up? Did I make any glaring errors?

[Guest]

I think I have a general solution for n terms. It works thusly: for any n number of items, total the price paid in the numerator and simplify to place all values for a in one term, for b in one term, etc. Do the same in the denominator with the msrp. For the final item n, it will equal 0 in the numerator and the msrp will be 1/3 the price paid for item n-1. To make the numbers much easier to deal with, multiply everything in the numerator and denominator by 3 to the power of n-1. This should get rid of all fractions. Note that item n will be written in terms of a,b,etc. I worked this out for n=10 and saw that the value for a in the numerator was .75 the value of a in the denominator, and this was true for the other items b through i as well. So the numerator can be rewritten as .75 times the denominator, which reduces to .75, giving a discount of 25%. So case for n is proven. The numbers are as follows, multiplying all by 3^9 or 19683 to be rid of all fractions.

numerator terms for a,b,c,d,e,f,g,h,i

14763, 14760, 14769, 14742, 14823, 14580, 15309, 13122, 19683

denominator terms for a,b,c,d,e,f,g,h,i

19684, 19680, 19692, 19656, 19764, 19440, 20412, 17496, 26244

I will try to post the general solution for all n in another post

[Guest]

Hm, I think this is correct, but I don't have the time right now to analyze it. I grouped terms up, the MSRPs are a through j, a>b>c>d....>j. Here is the first few terms, a + b - a/3 + c - b/3 - a/9 + d - c/3 - b/9 - a/27, and so on, and the last price looks like this j - i/3 - h/9 - g/27 - f/81 - e/243 - d/729 - c/287 - b/6561 - a/19683. not very elegant right?

Here's the final price all tidied up, on first glance it seems like its a bigger discount than i imagined so i think its wrong, but i think i am on the right track: a*9842/19683 + b*3281/6561 + c*1094/2187 + d*365/729 + e*122/243 + f*41/81 + g*14/27 + h*5/9 + i*2/3 + j. Nana7 maybe you can finish it up? Did I make any glaring errors?

I am not so good at following works in progress. Your first terms look correct. For last item j though, I believe the signs should flip for each term. And I would not use a "j" at all but write the final item as one third of i * discount given to i. For your final price tidied up, you have taken a slightly different approach and have a j term so I can not compare it well to my work. It looks impressive though.

Edited May 15, 2011 by Nana7

[Guest]

I realized that the proof for n = 10 contains the proof for all n less than 10 within itself. To prove for smaller n, shift all items to the left. ie for n = 9, take the n=10 proof and drop the a item, make item b the new item a, item c the new item b, and so forth. We keep the multiplier at 3^9 so that none of the numbers change from the last proof, and done. Since the items in the numerator are all still 3/4 of the denominator items, nothing else changes. Removing the orginal item "a" does not alter anything, and it is proven for n=9. All the other items can be removed as well to take it down from n=10 all the way to n=2.

As for what is going on here, (3^n + 3^(n-1) )*3/4 = 3^n

That has a lot to do with why the price is 3/4, I think.

Edited May 15, 2011 by Nana7

[Guest]

I realized that the proof for n = 10 contains the proof for all n less than 10 within itself. To prove for smaller n, shift all items to the left. ie for n = 9, take the n=10 proof and drop the a item, make item b the new item a, item c the new item b, and so forth. We keep the multiplier at 3^9 so that none of the numbers change from the last proof, and done. Since the items in the numerator are all still 3/4 of the denominator items, nothing else changes. Removing the orginal item "a" does not alter anything, and it is proven for n=9. All the other items can be removed as well to take it down from n=10 all the way to n=2.

As for what is going on here, (3^n + 3^(n-1) )*3/4 = 3^n

That has a lot to do with why the price is 3/4, I think.

Nana your work is very impressive, that last equation is wonderful, that's the sort of mathematical relationship that I always enjoy thinking about. Did you notice how it has multiplication, addition, and exponentiation all in one? Random fact but Richard P. Feynman said that he thought the most elegant equation was e^(i*pi) + 1 = 0 for similar reasons.

[Guest]

Thanks. It was an interesting problem.

[Guest]

a,b,c the payment is

a,b-a/3,c-1/3(b-a/3)=c-b/3+a/9

Nice work nana, I'm writing out the general solution, I wish there was a handy way to sum powers of 3!

[k-man]

For a simple proof let's work backwards starting from the last item.

Let's call the amount PAID for the last item X. Let's call the discount received on the last item D₁.

So, MSRP for the last item is x+D₁.

For the previous item (second to last) we paid 3D₁ and received a discount D₂. Thus MSRP for the previous item is 3D₁+D₂.

The same goes for third to last item. Paid: 3D₂, Discount: D₃, MSRP: 3D₂+D₃

Second item: Paid: 3D_n-2, Discount: D_n-1, MSRP: 3D_n-2+D_n-1

First item: Paid: 3D_n-1, Discount: 0, MSRP: 3D_n-1

The total discount we receive is sum(D_i) for i in [1,n-1]

The sum of all MSRPs is 4(sum(D_i))+X

So, it's clear that if X=0 we get 25% discount. If X>0, then the discount is less than 25%.

[Guest]

That is very elegant!

[k-man]

Thanks, Nana.

is that in this proof I assumed that there are no lost discounts. In other words, all discounts are fully realized and therefore D_i ≥ 0. After all, we're trying to find the maximum possible overall discount, so it's fair to assume that the maximum cannot be reached by losing a portion of a discount on a single purchase.

[Guest]

For a simple proof let's work backwards starting from the last item.

Let's call the amount PAID for the last item X. Let's call the discount received on the last item D₁.

So, MSRP for the last item is x+D₁.

For the previous item (second to last) we paid 3D₁ and received a discount D₂. Thus MSRP for the previous item is 3D₁+D₂.

The same goes for third to last item. Paid: 3D₂, Discount: D₃, MSRP: 3D₂+D₃

Second item: Paid: 3D_n-2, Discount: D_n-1, MSRP: 3D_n-2+D_n-1

First item: Paid: 3D_n-1, Discount: 0, MSRP: 3D_n-1

The total discount we receive is sum(D_i) for i in [1,n-1]

The sum of all MSRPs is 4(sum(D_i))+X

So, it's clear that if X=0 we get 25% discount. If X>0, then the discount is less than 25%.

very smart and easy solution.