Strange bills
I have 7 distinct dollar bills, each of which is a distinct integer denomination of $50 or less. Using these bills, I can buy anything that costs an integer amount between $1 and $60 (inclusive) in exact change.
What is the least possible value of the largest denomination of these 7 bills (in dollars)?
The answer is 16.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
5 solutions
How do you do that
Log in to reply
Basically, having bills 8, 4, 2, 1 means we can get any integer from 1 to 10 by summing some combination of them. Therefore, if we add larger bills, we don't need to worry about what exactly they are, as long as they are smaller or equal to the sum 1+2+4+8 i.e. if the next larger bill is not bigger than 16, we can still cover every integer on the way to the total sum. If it was 17, then we can't pay 16... as we only would have 15 or 17.
So let's say we add 16 bill. Now we have 1+2+4+8+16=31. We're not quite at 60, need 29$. Luckily we still have room to add 2 more bills, and it would make no sense to choose anything larger than 16, so it becomes obvious quickly that only two numbers less than 16 that add up to 29 are 15 and 14.
And since we still have bills 1,2,4,8, this ensures that the amount we can pay can end in any digit. Therefore it can be anything up to and including the sum of all bills.
If this makes little sense, I apologize. I'm not an expert.
Log in to reply
@anton dubovik In the first line, did you mean 15 instead of 9?
Log in to reply
@Arjen Vreugdenhil – No I was just trying to explain that by having bills 8,4,2,1 ensures that the last decimal place is 'taken care of'. That you're not going to miss any consecutive integer up to their total sum. Then adding 16 means you're not going to miss any integer up to the total sum of 31. Then adding 32, you're good until 63 etc.
The proof of : B n ≤ 2 n . If not, then some number in the set 1 . . 2 n is unreachable by a counting argument. (That's the justification for the 'it's not difficult to see that..' part of your argument.) Basically if there are at most (n-1) potential summands less than 2 n then there at most 2 n − 1 different sums reached. And that's not enough.
Wrote a short Python script to show same
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
|
Log in to reply
Nice job! But the real question is how does one come up with the list?
why do use python to list？ I am afraid if only write it on paper then you reach the conclusion
The set $$ 1 , 2 , 4 , 8 , 1 4 , 1 5 , 1 6 shows that $ 1 6 is a possible maximum. Let us shown that no smaller maximum is possible.
We have to have $$ 1 , 2 in our set (so that we can buy $ 1 and $ 2 dollar items. To be able to buy $ 4 dollar items, we have to have $ 3 or $ 4 as well. Since 1 + 2 + 4 + 1 1 + 1 2 + 1 3 + 1 4 = 5 7 < 6 0 , it is certainly not possible to have a largest denomination less than $ 1 5 .
- If we have $$ 1 , 2 , 3 , the only way we can buy a $ 6 0 item is if our denominations are $$ 1 , 2 , 3 , 1 2 , 1 3 , 1 4 , 1 5 . With this combination we cannot buy a $ 7 item.
- If we have $$ 1 , 2 , 4 , we can only buy a $ 6 0 item if our denominations are $$ 1 , 2 , 4 , 1 1 , 1 3 , 1 4 , 1 5 . With this combination we cannot buy a $ 8 item.
Thus a maximum denomination of less than $ 1 6 is impossible.
Though I cannot approve of his choice of language I agree with Stephen Garramone's assessment of this problem - it is complete nonsense.
Log in to reply
Another currency purist. Would you prefer a set of ounce weights that can weigh any amount from 1 to 6 0 ounces?
There is some research that says that the USA should introduce a 1 8 cent coin. Doing so would minimise the average number of coins change given back in a transaction.
Log in to reply
I would have preferred it had this question been set with ounce weights. I accept you argument for an 18 cent coin, but such a thing does not yet exist.
Log in to reply
@Thomas Sutcliffe – Because "such a thing does not yet exist", so it's complete nonsense?
That's a bullshit problem and solution. Get serious.
Relevant wiki: Mean (Average)
Here's an intuitive way to solve the problem.
Because at least some of the bills must tally to 60, the average value of the bills must be at least 7 6 0 , or approximately 8.6.
It's useful to see which values below this average are forced and then assess the possible values for the denominations greater than 8.6.
One dollar and $2 bills are clearly necessary. Continuing, $4 and $8 bills are also essential, making a binary pattern obvious.*
Consequently, the average value for the denominations greater than 8.6 must be no less than 3 6 0 − ( 1 + 2 + 4 + 8 ) =15. Since each bill must be unique, the greatest denomination must be no less than 16 and the three final denominations may be 14, 15 and 16.
To quickly verify that the set of denominations 1, 2, 4, 8, 14, 15 and 16 provide a solution, realize that due to their binary nature the first four bills cover the integer values 1 through 15. Because a $15 bill is available, the integers from 1 to 30 can be covered. Because $14+$16=$30, we can use the first four bills and $15 to achieve the integers 1 through 60.
*- Other sets for the denominations less than 8.6 such as {1, 2, 3, 7}, {1, 2, 4, 6}, etc., raise the average value of the denominations greater than 8.6.
Binary base is the best starting point. We can represent any decimal value from 0 until 63 with only 6 diferent values (power of 2). Larger value is 32, but we can stil add a new value. We can get a total sum of 60 using a higer bill of 29. As we can use a new bill, we can divide the 29$ bill in two bills: 14$ and 15$. So, larger bill value is 16$ (2^4).
This can be achieved with the bills:
1 , 2 , 4 , 8 , 1 4 , 1 5 , 1 6
To get the values 1-31, simply sum powers of 2 as if you were writing the number in binary. For example,
2 9 = 1 6 + 8 + 4 + 1
To get the values 32-46, start with 1 6 + 1 5 , then add to it powers of 2 as before. For example,
3 6 = 1 6 + 1 5 + 4 + 1
To get the values 47-60, start with 1 6 + 1 5 + 1 4 , then add to it powers of 2 as before. For example,
5 8 = 1 6 + 1 5 + 1 4 + 8 + 4 + 1
Note that this solution does not prove that 16 is the minimum of the highest denomination. A (not very rigorous) justification is provided here.
The ability to write numbers like this depends upon summing powers of 2. You could also try summing different powers (like powers of 3). However, you'd quickly find that none are as efficient as powers of 2. Then, you could try powers of 2 less than 16. However, it won't be possible to find a combination of distinct denominations that sums to 60 with 7 bills without including 16.
what about 1,2,3,7,11,12,13? First 4 cover 1-15, add the 11 covers 12-26, add 12 to that covers 24-38, add 13 to that covers 37-51, so you even get a bonus total!
Log in to reply
The question was to cover 1-60 not 1-50. And your numbers only cover from 1-49, did you mean 1,2,4,8,11,12,13?
The problem is poorly worded. It did not say that solver could make up denominations of bills and it did not say that no bill could be repeated. My solution was 50 +5 +1 +1 +1 +1 +1 = 60.
The question does not tell distinct amount of denominations. What about replacing those 1 4 , 1 5 , 1 6 with 1 5 , 1 5 , 1 5 .
Log in to reply
The question does specify that the denominations are distinct.
Log in to reply
Ah! sorry I didn't see although I checked it twice. Myopia at extreme ;)
Log in to reply
@Vishwash Kumar Γξω – The wording was a little unclear, so it's understandable. I've clarified the distinctness of the denomination amounts in the problem.
I approached the solution using a somewhat intuitive method. If the logic I present, is flawed, I welcome others to point it out. This is not a very mathematical solution. I will be very happy if somebody puts the logic in a more mathematical way(assuming the logic is right).
Let B1-B7 be the bill values in ascending order. We see that B1=1 and B2=2 need to be present
To have lowest possible value of maximum value bill, we need a more uniform distribution while covering every value and having a sum of 60.
As a starting point, I tried to get B4 close to 60/7 as this would ensure a uniform distribution. This comes to 8.57 So, B4 would be 8 or 9.
We need to choose a B3 such that sum of B1, B2, B3 can be used to get any values from 1 to B4-1.
For B4=9, no such value is possible.
For B4=8, B3 can be 4.
B1-B4 can produce maximum of 15. To get 60, we need 45 from B5, B6 and B7.
Choosing 14, 15 and 16 gives the minimum value of B7 as 16 with values being distinct. These values also cover all numbers up to 60.
If we reduce B4 less than 8, (B5+B6+B7) will go high ultimately pushing B7 higher.
To try to reduce B7 lesser than 16, we will need to increase value of B3 or B4. But we saw that B3=4 and B4=8 are maximum values possible values while covering all numbers below B4.
Hence, 16 is the lowest possible value of B7.
Number the bills from small to large as B 1 , … , B 7 .
Clearly, B 1 = 1 and B 2 = 2 ; it is not difficult to see that for n ≥ 3 , B n ≤ 2 n − 1 .
Now suppose B 7 = 1 5 . Then B 6 ≤ 1 4 and B 5 ≤ 1 3 . But then the sum is ∑ B n ≤ 1 5 + 1 4 + 1 3 + 8 + 4 + 2 + 1 = 5 7 , so obviously we cannot pay $60 with this set.
On the other hand, if B 7 = 1 6 , then we can have B 6 = 1 5 , B 5 = 1 4 , and B n = 2 n − 1 for the smaller bills; then ∑ B n = 1 6 + 1 5 + 1 4 + 8 + 4 + 2 + 1 = 6 0 .
Therefore the answer is B 7 = 1 6 .