6
$\begingroup$

I have one Math puzzle to which I think I found the solution but wanted to check your opinion on it. The puzzle is the following:

George has 1 banknote of 100 (the currency does not matter. Lets name it "currency" just for convinience). Valid banknotes in the currency are: 100, 50, 20, 10, 5, 2 and 1.

So he decided to spent some of the money in the shopping mall (he did not take any other banknotes with him. Just the one banknote of 100). At the end of the shopping it turns out that:

  1. In each and every shop he bought just one item and therefore just one payment was made.

  2. The price of the item was a whole integer (no decimal points are allowed)

  3. For each item he never had the exact sum that's why he always gives the nearest higher sum banknotes (of which he had at the moment).

  4. The sellers on the other hand always have enough money in different banknotes that's why they return the change with as less banknotes as possible. However, at the end it turns out that each seller aways return at least two banknotes to George.

The question is:

What is the maximum number of items that George can buy with these restrictions?

I have bolded the important parts in my opinion, so they pop out.

The approach that I took was the following:

1. In each shop the way I tried to figure out the price of the item is to have a change with as less as possible banknotes of 1 and 2 as change and with as much as higher value of the banknotes in the change
2. And as less as the price can be.

Improve this question
$\endgroup$
9
  • $\begingroup$ Two banknotes. It does not matter if they are different or not. Eg. if, George has 20 and buy something for 10 the seller should return 10, not 5 and 5 because the rule that he should follow to return as less as possible banknotes. And this is not a valid buying. But if George has 50 and the buying is 10 the seller can and should return 20 20. Also if George has 50 and 10 if the item is 9 or 8 he could not use 50 because there is a rule to use the nearest banknote (10). The change in both cases cannot be valid, so this buying is also not valid. $\endgroup$
    – Take a chance
    May 16, 2020 at 8:25
  • 2
    $\begingroup$ Welcome to PSE! I have a question: what do you mean by "always gives the nearest banknote"? Does it mean George will give some banknotes such that the sum is as minimum as possible greater than the price? $\endgroup$
    – athin
    May 16, 2020 at 11:39
  • 1
    $\begingroup$ I think @athin was asking whether he can pay with more than one banknote or only with one banknote. $\endgroup$
    – Jens
    May 16, 2020 at 12:18
  • 1
    $\begingroup$ You might want to update your question so it says "always gives the nearest higher sum of banknotes" or similar. $\endgroup$
    – Jens
    May 16, 2020 at 12:39
  • 2
    $\begingroup$ I have modified it. Thanks $\endgroup$
    – Take a chance
    May 16, 2020 at 12:48

2 Answers 2

Reset to default
1
$\begingroup$

Here are all possible outcomes if someone is trying to figure this out without a computer:

https://pastebin.com/X9GBuvut

it seems there are

186 possible outcomes for 8 items.

I have some observations:

9,10 or 20 has to be the value of the first item. Other than these values, it is impossible to get 8 items. The reason is probably getting more small banknotes such as 1,2,5. The least number of 1,2,5 seems the best way to get the maximum amount of items.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This is the outcome I also get + some other observations. You can also get 8 items if the first one costs 5, second one 2, third one 9, fourth one 7, then 17, 10 17 and 17. Yes, we strive to get as less as possible 1 and 2. And we can spend 5 if we do not have yet 1 or 2. If we have, then we do not need a change of 5, because this limit our options for the next buying. It seems that you can get to the answer only by trying or coding and there is no mathematical prove of this. $\endgroup$
    – Take a chance
    May 18, 2020 at 12:04
  • $\begingroup$ Also when you have a banknote of 5 you should buy something for 2, so you will get change of 1 and 2. When you have a banknote of 10 you should buy something for 7, so you will get again 1 and 2. When you have a banknote of 20, you should buy something for 9 and get a change of 10 and 1. (if possible, if not you can maximize the spending with 17. It turns out that if you cannot spend 9 you are almost at the end and it does not matter how much of this 20 you will spend because the rest most probably you cannot spend). When you have 50 $\endgroup$
    – Take a chance
    May 18, 2020 at 12:09
  • $\begingroup$ @Takeachance no this is not possible, 5,2,9,7,17 then 10 is not possible. because it will be the sum of small banknotes you have. (50 2 2 2 1 1 1 1) you cannot buy 10 with these banknotes because 2+2+2+1+1+1+1=10. I am pretty sure my code is right :) well if you did not change a rule though... ("For each item he never had the exact sum") $\endgroup$
    – Oray
    May 18, 2020 at 12:28
  • 1
    $\begingroup$ Oh, yep, I saw that when I tried to buy the item for 10 with 50 I already have 10 from 1 and 2. Yes, it seems impossible to solve for 8 if the first item is different than 9 and 10. $\endgroup$
    – Take a chance
    May 18, 2020 at 13:07
-1
$\begingroup$

8 items is the maximum he can buy, and still follow the rule enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ This does not provide any proof of the maximum. The solution isn't even valid, because the final purchase does not meet the required conditions. $\endgroup$
    – Daniel Mathias
    May 17, 2020 at 9:12
  • $\begingroup$ Yes, in your table the last purchase is not valid because he cannot give the exact sum. So from it 7 looks like the answer. However, I managed to make more purchases following all rules. Just want to check if there is some prove or just trying all the possibilities $\endgroup$
    – Take a chance
    May 17, 2020 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.