1
$\begingroup$

A salesman carries $3$ bags with $30$ balls in each of them. A bag can carry maximum of $30$ balls. He goes to the city to sell the ball but before entering the city he has to cross 30 tax stations, where he has to pay one ball from each bag as "tax". How many balls will he have at the end?

Best I could come up with was $25$. Is there any better answer? Is $25$ mathematically best possible?

Does this question even belong here? Or should I move it to puzzling?

$\endgroup$
2
$\begingroup$

Yes, 25 is the best solution mathematically possible. This is provable using the pigeon hole principle.

  1. For the first 10 tax stations, we have more than 60 balls, thus the pigeon hole principle, only piossible to keep these in 3 bags. Thus taking away 3 at a time.
  2. After 10 tax stations we have 60 (or less), and thus able to place these in 2 bags.
  3. Now After 10 tax stations we remove 2 at a time untill we reach 30 (or less ) balls, since before this it is not possible to place the balls in less than 2 bags, by the pigeon hole principle. This happens when we have ghone through 15 more stations, thus a total of 25.
  4. Now we can place all 30 balls in one bag, and have 5 stations left.

Thus we reach 25. In each tax stations it is not possible to loose less balls, and thus it is optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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