2
$\begingroup$

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 ?

$\endgroup$
3
  • $\begingroup$ Because you have three possible values -1, 0 and 1. $\endgroup$
    – Stef
    Commented Nov 29, 2023 at 9:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Stef
    Commented Nov 29, 2023 at 9:11
  • $\begingroup$ @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. $\endgroup$ Commented Nov 29, 2023 at 9:27

1 Answer 1

1
$\begingroup$

The reason why choosing powers of 3 makes the map bijective is that you have 3 distinct possible weights.

If you had 10 possible distinct digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, then you'd use powers of 10 to have a bijection between lists of digits and numbers. If you had 2 possible distinct bits 0 and 1, then you'd use powers of 2 to write numbers in binary.

Here you have three possible weights; originally 9, 10 and 11. You already saw that it was easy to "recentre" them to -1, 0 and 1; you might as easily recentre them to 0, 1 and 2 if it makes the analogy with a number-writing system more obvious.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .