# Identifying counterfeit coins

There are 5 bags with 100 coins in each bag. A coin can weigh 9, 10 or 11 grams. Each bag contains coins of equal weight, but we do not know what type of coins a bag contains. You have a digital scale (that tells the exact weight). How many times do you needd to use the scale to determine which type of coin each bag contains ?

Since there are 3 possible weights, upon centering we can work with $$-1,0$$ and $$1$$. It is possible to proceed in only one weighing by selecting $$\lambda_1, \ldots, \lambda_5\in \{1,\ldots, 100\}$$ such that the map

$$\{-1,0,1\}\to \{-\sum_{i=1}^5\lambda_i,\ldots, \sum_{i=1}^5\lambda_i\}$$
$$(w_1,\ldots, w_5) \mapsto \sum_{i=1}^5 \lambda_i w_i$$

is injective.

This can be accomplished by letting $$\lambda_i = 3^{i-1}$$. I don't understand the rationale behind this choice. Can someone provide some intuition ? Is there a simple mathematical reason as to why choosing powers of $$3$$ makes the map injective ?

• Because you have three possible values -1, 0 and 1.
– Stef
Commented Nov 29, 2023 at 9:10
• Just like when mapping digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} to number, you want powers of 10 because you have ten distinct digits, and when mapping bits to numbers in binary you want powers of 2, here you have three different "digits" so you want powers of 3. Maybe it helps more to recentre them as 0, 1 and 2 rather than -1, 0 and 1.
– Stef
Commented Nov 29, 2023 at 9:11
• @Stef Thank you. Centering to $0$, $1$, $2$ makes total sense. Now I recognize a basic property of base-3 expansion. Please post this as an answer. Commented Nov 29, 2023 at 9:27