66 replies to this topic

[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.

[Writersblock]

Spoiler for solution

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?

[bociniki]

I think this is it

Spoiler for solution

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

[Writersblock]

Spoiler for solution

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.

[Martini]

I think this is it

Spoiler for solution

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

Spoiler for solution

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!

[Martini]

Spoiler for solution

So the average price is $15

Spoiler for solution

How'd ya come up with that?

[spoxjox]

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.

Spoiler for solution

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.

Spoiler for solution

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.

Spoiler for solution

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.

Spoiler for solution

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.

[Writersblock]

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...

[Martini]

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.