I used an excel sheet and used the sum functions to come up with an answer. I do believe it works.
This is not correct. It wants the MINIMUM number. For the first few bags, you only need to put 1 in the first pouch, 2 in the second pouch, 3 in the next pouch, then skip to 7 coins for the next pouch for example, because you can already make 4, 5, and 6 with the first three pouches.
I agree that I can do it with a number of bags that is a prime number whose digits sum to 4, as was suggested a couple of pages ago. However, I'm not necessarily convinced that is the minimum number of bags required.
My first thought is to go with powers of 2, so 1, 2, 4, 8, etc. That gives me 872 leftover coins in a last bag, I believe.
This would be following your logic of going 1, 2, but then skipping 3 because 3 = 2 + 1.
I do think you can do it with less... not sure I want to check my answer though Dx
Giving away the answer would take all the fun out of it.
Besides, I hear there are 10 types of people: Those who understand ______ and those who don't. (c;
I'd love to know if you have managed to come up with a smaller solution. I'm not having any luck reducing the number, but don't have a proof that it is the smallest set.
I was thinking that if you do the same thing up to 999 and then 2 pouches of 1000 and one of 2000
And then one for the leftover coins, gives me one more than my original solution.
Yeah. I used 1, 2, 4 as well but did not want to give out solution.
Sorry, that does make the solution pretty easy if it turns out to be the correct method, doesn't it? On the other hand, I do want to help people out with clues, just not give away the final answer.
geometric progession works up to a certain number, but after that would you turn to a different method or would you start at another geometric progreesion? i think my answer is an undersestimate, but oh wells, i've submitted already.
The geometric progression will work all the way up if you just toss the leftover coins into another pouch. What I'm not sure about is whether there is another method that can work with those leftover coins to make a smaller number of pouches.
Okay, I can satisfy the conditions of giving out exactly any total that is asked for by using pouches containing 1, 2, 4, ..., 2^n plus a pouch containing the leftover coins. This gives me n+2 pouches.
So the question is, can I find a set of values, a(1), a(2), ... a(n+1) such that
1. the sum of a(1) + a(2) + ... + a(n+1) = 4967, and
2. for any number from 1 to 4967, I can give you a set of pouches that totals that number.
The alternative would be to ask whether we can prove there is no such set. My number theory is too weak to come up with either answer immediately.
Okay...I feel like an idiot now. Thanks for the hints without answers. I've got what you guys are saying...and if it isn't the smallest answer possible, it's the closest I'm going to get!
I reckon just find out how many times the maximum can be divided by 2
Gonna do it later though. Got an exam in an hours time x_X
Why divide the maximum by 2?
It's the same geometric progression idea that we were looking at earlier. The idea is to divide the total by 2, then divide it by 2 again, and see how many times you can do that until you get to less than 1.
