Grinch's Toy Store

[bonanova]

After disappointing Black Friday sales, management at Grinch's Toy Store found a way to boot profits.

Following an approach used in some amusement parks, GTS now sells coupons, which customers then use for payment at checkout.

The store's inventory comprises 22 toy models, each clearly marked with a unique, whole-dollar price.

Coupons are available in $6, $9 and $20 denominations.

Grinch's strategy is threefold.

[1] At checkout, extra coupon value is forfeit; no change is given.

Example: your total at checkout is $5. You pay with a $6 coupon. Grinch's keeps the $1 change.

[2] Prices have been set to ensure there is extra coupon value when toys are bought singly.

[3] Each toy model is limited one to a customer.

Your task is to visit Grinch's, browse the shelves, and find the minimum number of toys which, when bought together, using coupons, will ensure a fair purchase at checkout.

That is, there will be no change for Grinch's to keep.

This just in - Grinch's heard you were coming.

Fearing your intellectual prowess, they have replaced all price tags with UPC stickers, which only the checkout register can read.

[Guest]

So, there can be no toys at the $6, $9, $12, $15, $18, $20, $26, $29, $32, $35, or $38 price point (even cupon totals).

If the toys are priced starting at $1, then we have prices of

1,2,3,4,5,7,8,10,11,13,14,16,17,19,21,22,23,24,25,27,28,30.

I'm not sure I understand totally the task, but you could easily buy 2 toys to equal an even cupon value. 2+4, 4+5, 10+2, 10+5, 19+1, etc.

[bonanova]

You're on the right track.

If you select just one toy, you know Grinch will keep some of your money. He's priced them to ensure that.

If you select two toys they might turn out to be say a $2 toy and a $4 toy, and you could buy them exactly with a $6 coupon.

But since the prices have been removed, you don't know this until you get to checkout and then it's too late.

If you're going to select just two toys, you'd have to know that every combination of two prices can be paid exactly.

So that's what has to be found: if you bring N toys to checkout, there definitely won't be any change for Grinch to keep.

What is the smallest value of N?

[Guest]

I think this is it

It should be 8. that way, if you pick all the lowest number of toys, you still have more than any of the coupons.

[Guest]

So the average price is $15 and the lowest cupon is $6. I'd venture that the lowest number N could be would be the lowest common multiple, which is 30 toys.

[Guest]

I think this is it

It should be 8. that way, if you pick all the lowest number of toys, you still have more than any of the coupons.

Won't work. Let's say the 8 items you choose to purchase cost $1, $2, $3, $4, $5, $7, $8 and $13.

That's a total of $43. Every combo of $6, $9 and $20 coupons will result in there being extra coupon value.

Nice riddle, bonanova!

[Guest]

So the average price is $15

How'd ya come up with that?

[Guest]

After disappointing Black Friday sales, management at Grinch's Toy Store found a way to boot profits.

Following an approach used in some amusement parks, GTS now sells coupons, which customers then use for payment at checkout.

The store's inventory comprises 22 toy models, each clearly marked with a unique, whole-dollar price.

So based on this and condition #3 below, we will buy at most 22 toys.

Coupons are available in $6, $9 and $20 denominations.

Grinch's strategy is threefold.

[1] At checkout, extra coupon value is forfeit; no change is given.

Example: your total at checkout is $5. You pay with a $6 coupon. Grinch's keeps the $1 change.

[2] Prices have been set to ensure there is extra coupon value when toys are bought singly.

Therefore, possible toy prices are:

$1

$2

$3

$4

$5

$7

$8

All other odd (positive integer) numbers not divisible by 9, e.g. $11, $13, $15, $17, $19, $21, $23, $25, $29...

All other even (positive integer) numbers not divisible by 3 or 20, e.g. $10, $14, $16, $22, $26, $28, $32...

[3] Each toy model is limited one to a customer.

Your task is to visit Grinch's, browse the shelves, and find the minimum number of toys which, when bought together, using coupons, will ensure a fair purchase at checkout.

That is, there will be no change for Grinch's to keep.

In other words, you have to have equal to or more than the coupon value.

This just in - Grinch's heard you were coming.

Fearing your intellectual prowess, they have replaced all price tags with UPC stickers, which only the checkout register can read.

So the problem is to get the minimum number of toys guaranteed to equal or exceed the coupon value. Since we are not told how many coupons of which denominations we have, this is not solvable as given. If we assume one $6 (minimum value) coupon, then clearly getting any three toys is sufficient to guarantee no overcharge. If we assume one coupon of each denomination, we have $35 in spending power. In that case, buying any eight toys is enough to guarantee no leftover money.

There is no way in the given problem to maximize your coupon use to the nearest dollar or anything like that.

[Guest]

I got the $15 average by averaging the prices in my first post.

[3] Each toy model is limited one to a customer.

I missed that, so my guess of 30 is wrong.

Since we are not told how many coupons of which denominations we have

I assumed as many cupons of each denomination as necessary were available, so long as we didn't let grinch keep any money. So 4 $6's and a $20 would be fine (just as a random example).

buying any eight toys is enough to guarantee no leftover money

I think you are missing the point. The point is to not let grinch have any money, not to max out the total amount of one cupon of each denomination. Martini debunked 8 as the number.

Still working on it...

[Guest]

I got the $15 average by averaging the prices in my first post.

Ahh, I see. But I there's no requirement that the toys must start as inexpensive as $1.

[Guest]

True, but I thought it a logical assumption.

First, each toy has a unique whole dollar price. Second, prices have been set to ensure there is extra coupon value when toys are bought singly.

If I were Grinch I'd definatly start with $1 in case someone wanted to buy that, I'd make $5 extra! That is the highest price point gap and my opportunity to make the most off 1 transaction.

[Guest]

True, but I thought it a logical assumption.

First, each toy has a unique whole dollar price. Second, prices have been set to ensure there is extra coupon value when toys are bought singly.

If I were Grinch I'd definatly start with $1 in case someone wanted to buy that, I'd make $5 extra! That is the highest price point gap and my opportunity to make the most off 1 transaction.

Yes, but you can't make that assumption so you can come up with an average that you'd use in a formula to determine an answer. Calculating the answer would have zero to do with what a toy store would do to maximize profits and is based purely on the least possible amount of toys that must be purchased.

[Guest]

If you're going to select just two toys, you'd have to know that every combination of two prices can be paid exactly.

Why? That wasn't the problem.

So that's what has to be found: if you bring N toys to checkout, there definitely won't be any change for Grinch to keep.

What is the smallest value of N?

Three. With three toys, you guarantee that the price will not be less than $6, so you can pay with a $6 coupon without leftover. If you have one coupon of each denomination, then eight is the smallest value of N that guarantees no leftover coupon money.

[Guest]

Won't work. Let's say the 8 items you choose to purchase cost $1, $2, $3, $4, $5, $7, $8 and $13.

That's a total of $43. Every combo of $6, $9 and $20 coupons will result in there being extra coupon value.

Nope. For example, two $20 coupons results in zero extra coupon value.

[Guest]

I assumed as many cupons of each denomination as necessary were available, so long as we didn't let grinch keep any money. So 4 $6's and a $20 would be fine (just as a random example).

That would make sense if the condition were to find the minimum number of toys that must be purchased in order to assure that any possible price resulting can be fully paid by coupons alone, without any excess payment with the coupons. But this is not what the problem requested.

[Guest]

If you're going to select just two toys, you'd have to know that every combination of two prices can be paid exactly.

Why? That wasn't the problem.

Yes, that is the problem.

Three. With three toys, you guarantee that the price will not be less than $6, so you can pay with a $6 coupon without leftover. If you have one coupon of each denomination, then eight is the smallest value of N that guarantees no leftover coupon money.

You're misunderstanding the problem. See my first post in this thread for why 8 toys isn't the answer.

Nope. For example, two $20 coupons results in zero extra coupon value.

It's irrelevant that two $20 coupons would result in extra coupon value. What's relevant is that no combination of $6, $9 and $20 coupons can result in not having extra coupon value.

That would make sense if the condition were to find the minimum number of toys that must be purchased in order to assure that any possible price resulting can be fully paid by coupons alone, without any excess payment with the coupons. But this is not what the problem requested.

Yes, it is.

[Guest]

Let's assume for the moment that the problem is to find the minimum number of toys that must be purchased in order to assure that any possible price resulting can be fully paid by coupons alone, without any excess payment with the coupons.

I believe the solution to the above problem is nine items.

We can safely assume that we might potentially choose gifts that give any value between zero and infinity. The only constraint is that the individual prices not be evenly divisible by 6, 9, or 20.

The question then becomes: First, is it the case that for some minimum value N, any number at or above N can be reached by summing 6x + 9y + 20z for nonnegative integer values of x, y, and z; and second, if it is the case, then what is N?

Clearly, any multiple of 6 can be reached, which includes all even numbers evenly divisible by 3. We can extend this to all odd numbers divisible by 3 by noting that any odd number divisible by 3 is equal to the sum of 9 plus an even number evenly divisible by 3. Thus, to create the sum for 3M, where M is an odd, positive integer greater than or equal to 3, we can recast 3M as 9 + 3(M - 3). But since M is odd, M - 3 will be even, and therefore 3(M - 3) will be evenly divisible by 6, and 3M = 9 + 6K where K = M - 3.

Since 20 is not evenly divisible by 3, we can see that all even integers above some certain value are also reachable. We can quickly determine that 34 is the largest even number that is not a sum of some integer amount of 20s and 6s. To wit, solving through 100 and noting the pattern that develops:

36 = 0(20) + 6(6)

38 = 1(20) + 3(6)

40 = 2(20) + 0(6)

42 = 0(20) + 7(6)

44 = 1(20) + 4(6)

46 = 2(20) + 1(6)

48 = 0(20) + 8(6)

50 = 1(20) + 5(6)

52 = 2(20) + 2(6)

54 = 0(20) + 9(6)

56 = 1(20) + 6(6)

58 = 2(20) + 3(6)

60 = 3(20) + 0(6)

62 = 1(20) + 7(6)

64 = 2(20) + 4(6)

66 = 3(20) + 1(6)

68 = 1(20) + 8(6)

70 = 2(20) + 5(6)

72 = 3(20) + 2(6)

74 = 1(20) + 9(6)

76 = 2(20) + 6(6)

78 = 3(20) + 3(6)

80 = 4(20) + 0(6)

82 = 2(20) + 7(6)

84 = 3(20) + 2(6)

86 = 4(20) + 1(6)

88 = 2(20) + 8(6)

90 = 3(20) + 5(6)

92 = 4(20) + 2(6)

94 = 2(20) + 9(6)

96 = 3(20) + 6(6)

98 = 4(20) + 3(6)

100 = 5(20) + 0(6)

etc.

Now we only have left the odd positive integers not divisible by 3. This is easy; simply subtract 9 from each odd number, and you get an even number that has already been solved above. Turns out that 43 is the lowest positive integer that cannot be made with the sums of integer multiples of 20, 9, and 6. (This can easily be seen by noting that 43 is 9 + 34, and we already determined that 34 is not reachable by the sums of integer multiples of 6, 9, and 20.) To wit:

45 = 9 + 36, or simply 5(9)

47 = 9 + 38

49 = 9 + 40

etc.

So our problem is to find the minimum number of toys that will sum to a value greater than $43. If we assume that no toy will be priced at $0, the possible prices (with running totals of the sum of all previous prices) are:

1. $ 1 ($ 1)

2. $ 2 ($ 3)

3. $ 3 ($ 6)

4. $ 4 ($10)

5. $ 5 ($15)

6. $ 7 ($22)

7. $ 8 ($30)

8. $10 ($40)

9. $11 ($51)

Therefore, the solution is nine items.

[Guest]

That would make sense if the condition were to find the minimum number of toys that must be purchased in order to assure that any possible price resulting can be fully paid by coupons alone, without any excess payment with the coupons. But this is not what the problem requested.

Yes, it is.

At the risk of being petulant: No, it is not. Reread the initial post. There is absolutely no mention made of paying exact amounts with the coupons. The only stipulation is that there be no excess amounts on the coupons.

[Guest]

Let's assume for the moment that the problem is to find the minimum number of toys that must be purchased in order to assure that any possible price resulting can be fully paid by coupons alone, without any excess payment with the coupons.

I believe the solution to the above problem is nine items.

That won't work either. If the nine toys you choose to purchase end up costing $1, $2, $3, $4, $5, $7, $8 $10 and $14, your choices would total $54. Every combo of $6, $9 and $20 coupons will result in there being extra coupon value.

At the risk of being petulant: No, it is not. Reread the initial post. There is absolutely no mention made of paying exact amounts with the coupons. The only stipulation is that there be no excess amounts on the coupons.

Paying the exact amount = no excess amounts on the coupons.

[Guest]

Let's assume for the moment that the problem is to find the minimum number of toys that must be purchased in order to assure that any possible price resulting can be fully paid by coupons alone, without any excess payment with the coupons.

I believe the solution to the above problem is nine items.

That won't work either. If the nine toys you choose to purchase end up costing $1, $2, $3, $4, $5, $7, $8 $10 and $14, your choices would total $54. Every combo of $6, $9 and $20 coupons will result in there being extra coupon value.

6($9) = $54

9($6) = $54

2($9) + 6($6) = $54

4($9) + 3($6) = $54

At the risk of being petulant: No, it is not. Reread the initial post. There is absolutely no mention made of paying exact amounts with the coupons. The only stipulation is that there be no excess amounts on the coupons.

Paying the exact amount = no excess amounts on the coupons.

Yes, but "no excess on coupons" != "paying the exact amount".

[Guest]

6($9) = $54

Ahh, then that may be the answer.

Yes, but "no excess on coupons" != "paying the exact amount".

Care to explain that one?

[Guest]

Yes, but "no excess on coupons" != "paying the exact amount".

Care to explain that one?

Sure. If I'm told not to leave any excess value on the coupon (because it will not be reimbursed to me but instead taken by Grinch's), that means that I don't want to pay for a $5 purchase with a $6 coupon -- that would leave "excess on coupons", or what bonanova called "extra value" (I think he called it that). However, if I pay for a $7 purchase with a $6 coupon,that leaves no "extra value" or "excess on coupons" -- the entire $6 value of the coupon is used.

[Guest]

However, if I pay for a $7 purchase with a $6 coupon,that leaves no "extra value" or "excess on coupons" -- the entire $6 value of the coupon is used.

The riddle states that toys are paid by using coupons; it never mentions that cash can be used along side them. For this riddle to be any kind of a challenge, "paying the exact amount = no excess amounts on the coupons".

[Guest]

The riddle wouldn't be much of a riddle if cash could be used along with coupons.

True enough. But as you said to Writersblock, you can't make that assumption. The riddle as written does not prohibit use of cash.

By the way, I'm not merely being pedantic or anal-retentive. I was genuinely confused about the point of the riddle. Looking through the thread, it appears I was not the only one.

[Guest]

True enough. But as you said to Writersblock, you can't make that assumption.

I didn't make any assumptions- you did. The riddle states that purchases are made using coupons. You assumed that cash could also be used.

"Following an approach used in some amusement parks" is a mention of the tickets only that are used to get on rides.

Anyway, I'm betting you're the first to answer the riddle correctly.

[Guest]

Ok, I agree that the amounts of each item could be any whole number not $6, $9, $20, or any sum or multiple thereof.

I read this the entire time as suggesting that you had to pay cash for cupons and ONLY CUPONS could be used to buy merchandise. Otherwise the riddle is amazingly easy if you can combine cash and cupons.

As for 9 items --- Without the costs of the items we cannot solve this problem. That's why I assumed that the items started at $1 and increased in "allowable" dollar increments.

Maybe the OP can give some guidance.