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]

I'm certain this was not the best way to figure this out, but here was my system.

I entered numbers 1-60 in Excel, and simply went through the list ticking off all of the total purchase prices that could be paid for evenly by coupons. For example assuming my toys totaled $15, I could pay for them with no loss, by using a $6 and $9 coupon without a loss. Once I got to $44, I got to a string of six sequential totals which could be paid for without a dollar loss, which meant all subsequent totals would require no loss (as I could just add $6 coupons to each of these numbers).

I then assumed the best case scenario, where I was able to find the cheapest toys totaling this amount, and I deduced that they would be: 1,2,3,4,5,7,8,10,11.

So nine items is the minimum????

[Guest]

7

[bonanova]

I'm certain this was not the best way to figure this out, but here was my system.

I entered numbers 1-60 in Excel, and simply went through the list ticking off all of the total purchase prices that could be paid for evenly by coupons. For example assuming my toys totaled $15, I could pay for them with no loss, by using a $6 and $9 coupon without a loss. Once I got to $44, I got to a string of six sequential totals which could be paid for without a dollar loss, which meant all subsequent totals would require no loss (as I could just add $6 coupons to each of these numbers).

I then assumed the best case scenario, where I was able to find the cheapest toys totaling this amount, and I deduced that they would be: 1,2,3,4,5,7,8,10,11.

So nine items is the minimum????

Yes ... great job. You're exactly right ...

[Guest]

my least prices which directly do not add up to any combination of coupons were 1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37 and 43.

pick any seven and u can pay with a combination of coupons!

correct me if i am wrong.

[bonanova]

my least prices which directly do not add up to any combination of coupons were 1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37 and 43.

pick any seven and u can pay with a combination of coupons!

correct me if i am wrong.

Sure.

The amounts you've given are the prices of the 22 different toys.

They are the only amounts that cannot be made exactly with a combination of $6, $9 and $20 coupons.

So we know that 1 toy is not enough to have a fair price at checkout. When bought singly, all toys ensure that Grinch gets some of your money.

Neither is 2 toys enough: $1 and $2 total $3.

Neither is 3 toys enough: $1, $2 and $7 total $10

Neither is 4 toys enough: $1, $2, $3 and $4 total $10

Neither is 5 toys enough: $1, $2, $3, $4 and $7 total $17

Neither is 6 toys enough: $1, $2, $3, $4, $5 and $7 total $22

Neither is 7 toys enough: $1, $2, $3, $4, $5, $8 and $11 total $34

Neither is 8 toys enough: $1, $2, $3, $4, $5, $7, $8 and $13 total $43

None of these totals can be made exactly with coupons.

But 9 toys is enough:

The 9 cheapest toys are $1, $2, $3, $4, $5, $7, $8, $10 and $11, which total $51 = $6 + $9 + $9 + $9 + $9 +$9.

Any amount greater than $43 can be made exactly with a combination of coupons, and the combination of any 9 different toys totals more than $43.

So 9 toys ensures a fair price at checkout, and it's the minimum number that does so.

[Guest]

Why not 3 toys?

A $1, $2, and $3 toy paid for with a $6 coupon?

Or am I thinking to simple on this?

Edited April 10, 2008 by DarkChild of Mercury

[bonanova]

Why not 3 toys?

$1, $2, and $3 toys paid for with a $6 coupon?

Or am I thinking to simple on this?

Yes, kind of.

You could buy two toys - $2 and $4 = $6 and pay a fair price.

But the puzzle asks for the minimum number of toys that will

[no matter which toys they are] ensure a fair price at checkout.

As noted, [see post 56] there are combinations of up to 8 toys that add up to an unfair price.

But if you get 9 toys, whatever they are, it's guaranteed to have a fair price.

[Guest]

Given the wording of the problem, particularly that it doesn't specify our number of coupons or their denominations, and the conclusion another poster drew that we have to get AT LEAST enough toys to have their prices meet or EXCEED or coupon amount, the minimum is 1 toy, because you could easily go in with no coupons and a pocket full of cash. That would show Old Grinchy.

[bonanova]

Given the wording of the problem, particularly that it doesn't specify our number of coupons or their denominations, and the conclusion another poster drew that we have to get AT LEAST enough toys to have their prices meet or EXCEED or coupon amount, the minimum is 1 toy, because you could easily go in with no coupons and a pocket full of cash. That would show Old Grinchy.

Following an approach used in some amusement parks, GTS now sells coupons, which customers then use for payment at checkout. Coupons are available in $6, $9 and $20 denominations. The only thing in Grinch's store that cash will buy is coupons.

1 toy is the wrong answer because any of the toys bought singly will lose you money at checkout. [Another provision of the OP, q.v.]

[Guest]

It seems to me that the real hurdle in this riddle (once you understand what it's asking, which is evidently an issue) is to determine that every integer over 43 can be expressed as a linear combination of 6, 9, and 20. Is there a general solution to this problem? By which I mean, for any n integers x1,...,xn is there a constructive way to find the least integer Y such that any integer greater than Y is a linear combination of the x's?

It also occurs to me that Y can't always exist, for instance if x1,...,xn are all even. It also won't work if n=1 and x1!=1. Are there any other conditions that must be met for Y to exist in general?

[Guest]

I post this under the impression that no solution has been confirmed yet...

[spoiler='Solution

']I believe the answer is 6 items.

Suppose the 6 items you choose are valued at 1,2,3,4,5,$6, this would total $21 which could be payed with a $20 coupon and $1 cash. Any prices for items above the fewest possible would result in a total greater than $21 in which case, any excess can be payed in cash.

Unless we can't use money in combination with the coupons...

[bonanova]

It seems to me that the real hurdle in this riddle (once you understand what it's asking, which is evidently an issue) is to determine that every integer over 43 can be expressed as a linear combination of 6, 9, and 20. Is there a general solution to this problem? By which I mean, for any n integers x1,...,xn is there a constructive way to find the least integer Y such that any integer greater than Y is a linear combination of the x's?

It also occurs to me that Y can't always exist, for instance if x1,...,xn are all even. It also won't work if n=1 and x1!=1. Are there any other conditions that must be met for Y to exist in general?

A sufficient condition is for x₁ consecutive numbers to exist. The first time that happens [the lowest x₁ consecutive numbers] determines the least Y.

In this case the lowest 6 numbers are 43 44 45 46 47 48 - any higher number is one of these plus a multiple of 6.

How you construct Y [not just find it] is an interesting question - depends at least on whether the x's have common factors.

[Prime]

A sufficient condition is for x₁ consecutive numbers to exist. The first time that happens [the lowest x₁ consecutive numbers] determines the least Y.

In this case the lowest 6 numbers are 43 44 45 46 47 48 - any higher number is one of these plus a multiple of 6.

How you construct Y [not just find it] is an interesting question - depends at least on whether the x's have common factors.

True, it does depend on common as well as uncommon factors. Here is how.

As it has been already posted, 9 is the minimum number of different toys that guarantees a total price that could be constructed with $6, $9, and $20 coupons. That is becuase:

1. Any whole amount of $44 and up can be constructed with $6, $9, and $20.

2. Any 9 toys would cost more than $44 ($51, or more).

3. It is possible for any number of toys less than 9 to add up to an amount "unconstructable" with 6, 9, and 20.

Why 44:

There are only 3 types of whole numbers:

1. Those that are wholy divisibly by 3;

2. Those that yield a remainder of 1 when divided by 3;

3. And those that yield a remainder of 2 when divided by 3.

We can see that with the $6 and $9 coupons we could construct any whole amount wholy divisible by 3, starting with $6.

20 gives a remainder of 2 from the division by 3. Therefore, starting with 26 and up, we can construct any amount that is gives remainder 2 from the division by 3. (Just add 20 and any amount divisible by 3 already available to us.)

40 gives a remainder of 1 from the division by 3. Thus, starting with 46 and up we can also have any total, which gives a remainder of 1 from the division by 3. Thus starting with $44, all totals are covered.

For understanding of a general formula, consider a case mutually prime numbers, unmared by a common factor (like 3 in the $6 and $9 coupouns). Let's take a $5 and a $7 coupon.

7 gives the remianer of 2 with 5; 14 -- remainder of 4; 21 -- rem. 1; and 28 -- rem. 3. Thus all remainders are covered. Because there are only 5 types of whole numbers...

Thus the minimum amount (inclusive) starting from which we can construct any whole amount with 5 and 7 is 28 - 5 + 1 = 24.

In general for two mutually prime numbers a and b, the formula is ab - a - b + 1.

For example, $2 and $3 coupons. Plugging those into the formula, we get: 2*3 - 2 - 3 + 1 = 2. So starting from $2 we could construct any whole-number amount with a combination of $2 and $3 coupons.

Now, back in the original problem we had $6 and $9 coupons. 6 is two 3-s; and 9 is 3 3-s. And, as mentioned above, with 2 and 3 we can construct any total from 2 and on. That's why with $6 and $9 coupons we could make any amount divisible by 3 starting from $6 (two 3-s).

[Prime]

Here are few corollaries and further conclusions on the subject.

As a corollary to my previous post:

I. If all coupon amounts have a common factor, they can only cover the amounts wholly divisible by that factor. For example, $6 and $9 coupons can only add up to the amounts divisible by 3 (and not all of them at that -- the $3 is not covered). If we added another coupon of $15, it would not help covering any additional amounts.

So, it was Grinch’s mistake to make a $20 coupon, which is mutually prime with 3.

II. The description of the general formula/algorithm for finding the break-even point may become confusing. It might be easier to show it by example.

Suppose, we have $15, $25, and $32 coupons.

1. The largest common factor of 15 and 25 is f=5. Then 15 = 3f and 25 = 5f. Let’s find the break-even point for 3 and 5: P = 5*3 - 5 - 3 + 1 = 8. (Using the ab-a-b+1 formula from my previous post.) That means that starting with 8f, we can have any amount divisible by f. Since f = 5 in our example, that means that starting with 40 we can have any amount divisible by 5 using $15 and $25 coupons.

2. Next, let’s find the break-even point between 5 (the common factor from the previous step) and 32. P = 5*32 - 32 - 5 + 1 = 124.

3. However, in the first step we found that every amount divisible by 5 is obtainable starting from 40. So we must add that offset here. Thus, the overall break-even point is 124 + 40 = 164.

That is with the coupons of $15, $25, and $32 we can obtain any whole-number amount starting from 164 and up. I am relying on my formula here and have not actually verified that result.

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

There can't be 21 cause that would be 9+6+6..

.

[Guest]

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.

I think the point is IF you were to only use coupons, as the question does ask how many toys must you purchase to ensure a fair price at checkout with coupons. What would be the point of the store hiding the actual prices (or even the point of the question itself) if you could also use your own cash? The coupons were designed so that the store would make a profit after poor Black Friday sales.

Edited May 7, 2011 by missepicfail