A chicken farmer can make 6kg, 9kg and 20kg bags of chicken. However he can't make anything else, so for example if you asked him for 7kg of chicken he couldn't do it. On the other hand if you asked him for 15kg he would be able to do that by selling you both a 6kg bag and a 9 kg bag.

A natural question to ask is which amounts can he make and which amounts can he not make, a sub-question here is to ask what the largest integer amount he cannot make is. It should be noted that he can make as many bags of each weight as he wants.

The solution (stop here if you want to play with it yourself for a few minutes, because spoilers ahead) is to notice that if you don't use any 20 kg bags you can make a lot of multiples of 3. In particular one can make 0,6,9,12,15,18 and so on bags every non-negative multiple of 3 except 3 itself.

The next thing to notice is that if you don't use a 20kg bag that that's all you can do! Adding 6s and 9s isn't ever going to give you something which isn't a multiple of 3.

Now if we use just one 20kg bag? Well then we can make 20,26,29 32,35,... . In other words we can make most positive integers which leave a remainder of 2 when divided by 3 (in a more formal phrasing numbers which are 2 mod 3) and nothing else. The exceptions being things less than 20 and 23.

That only leaves those weights which are 1 mod 3. We need at least two 20kg bags to get anything which is 1 mod 3, but using exactly two 20s we can make 40,46,49 and so on. This means the largest integer weight we can't make is 43kg.

Now the trick here was to notice that 6 and 9 share a common factor of 3. That's all well and good but what if the farmer can make lots of 3 arbitrary positive integers a,b and c? It turns out that this is an open problem but I'll leave it for another post.

## No comments:

## Post a Comment