$120$ bags with $100$ coins are placed on the floor. One bag has coins that weigh $9$ grams, the other bags have coins that weigh $10$ grams. One may place some coins (not necessarily from the same bag) on a weighing scale, but it will only properly display the weight if it is less than $1000$ grams. Determine the minimum number of times that the weighing scale may be used in order to identify the bag that has the $9$-gram coins.
Problem
Source: Argentina Cono Sur TST 2014, Problem 6
Tags: combinatorics proposed, combinatorics
09.09.2014 15:52
It clearly cannot be done with one weighing for a group of $14$ or more bags, but it can be done for a group of $13$ or less bags (just take $1,2,\ldots,13$ coins from them, for a total weight of at most $910$). It clearly can be done with at most $4$ weighings for $120$ bags (from each of a group of $40$ bags we may take $13$ plus $13\cdot 2$ plus $13\cdot 3$ plus $4$, for a total weight of at most $820$). It remains to investigate if a cleverer method may reduce that.
09.09.2014 18:53
Method for $135$ bags with three weightings. Notice that from a group of $44$ bags we may take $13$ plus $13\cdot 2$ plus $13\cdot 3$ plus $5 \cdot 4$, for a total weight of at most $980$. If it is less than $980$ we may identify it with another weighting as mentioned before. If it is exactly $980$ for another $13$ bags we may identify it with another weighting as mentioned before. For a total of $57$ bags with two weightings. Similarly for a first weighting to identify those $57$ bags from a group of $78$ we may take $57$ plus $21\cdot 2$ for a total weight of at most $990$. If it is less than $990$ we may identify it with another two weightings as mentioned before. If it is exactly $990$ for another $57$ bags we may identify it with another two weightings as mentioned before. For a total of $135$ bags with three weightings.
09.09.2014 20:08
mavropnevma wrote: It clearly cannot be done with one weighing for a group of $14$ or more bags, but it can be done for a group of $13$ or less bags (just take $1,2,\ldots,13$ coins from them, for a total weight of at most $910$). Notice that if you know that exactly one bag has $9$ grams coins you can have $14$ bags and find the bag with one weighting. (leave the 14th bag out of the scale. Moreover for the $3$ weighting example. Notice that from a group of $46$ bags we may take $14 +14\cdot 2 +14\cdot 3 +4 \cdot 4$, for a total weight of at most $1000$. If it is less than $1000$ we may identify it with another weighting as mentioned before. If it is exactly $1000$ for another $14$ bags we may identify it with another weighting as mentioned before. For a total of $60$ bags with two weightings. Similarly for a first weighting to identify those $60$ bags from a group of $80$ we may take $60 +20\cdot 2$ for a total weight of at most $1000$. If it is less than $1000$ we may identify it with another two weightings as mentioned before. If it is exactly $1000$ for another $60$ bags we may identify it with another two weightings as mentioned before. For a total of $140$ bags with three weightings.