1
$\begingroup$

A specific form of this puzzle looks like this:

There are $N$ piles of stones. Each pile contains stones that weigh the same. The possible weights are $1$ or $2$. The task is to determine the weight of the stones in each pile. You have access to a weighing scale, but you can only use it once. You can choose any amount of stones from one or more piles to weigh together to get their total weight.

The solution to this is to take $1$ from pile $1$, then $2,4,8,$ from pile $2,3,4$ respectively, i.e. $p(n) = 2^{n-1}.$ Then it's possible to work out the weight of each pile from the measured weight.

If in the question the "Weight space" is changed to $1,2,4$ instead of $1,2,$ then the solution $p(n)$ would be $4^{n-1}$.

My question is if the "space" of possible weights are $W_1$, $W_2$, $W_3$, $W_4$ $\dots$ , what would be the "general formula" for the function $p(n)$ in terms of "$W$"s?

edit: sorry forgot to mention that the number of stones used should be minimized

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Fact: For any integers $p,w>1$, each $n\in \{0,1,\ldots, w^p-1\}$, there are unique coefficients $(d_i)_{i=0}^{p-1}$ such that $$n=\sum_{i=0}^{p-1}d_iw^i.$$

It seems obvious from the problem, but I'll state it just to be safe:

  1. We know beforehand the set of possible weights.
  2. The scale is infinitely accurate.

Let's assume we have $p$ piles numbered $0$ through $p-1$. Assume that the weight of pile $i$ is $c_i\in \{1,\ldots, w\}$, $w$ a known integer. Choose $w^i$ coins from pile $i$ and weigh them to get $$W:=\sum_{i=0}^{p-1}c_iw^i.$$ We calculate $$\hat{W}:=W-\sum_{i=0}^{p-1}w^i=\sum_{i=0}^{p-1}(c_i-1)w^i.$$ Since $c_i-1\in \{0,\ldots, w-1\}$, the values of $c_i-1$, and therefore of $c_i$, are uniquely determined by this number.

What if the weights are not integers? Consider the $\mathbb{Q}$-vector space $(\mathbb{R},\mathbb{Q},+,\cdot)$, and then the induced quotient space $V=(\mathbb{R},\mathbb{Q},+,\cdot)$. Let $W\subset (0,\infty)$ be the set of possible weights and let $B$ be a basis for $W$ over $\mathbb{Q}$. We can find such a basis by enumerating the set of weights $W$ as $c_0,\ldots, c_{p-1}$, iterating through the list, and omitting any $c_i$ which is in $\text{span}_\mathbb{Q}\{c_0,\ldots, c_{i-1}\}$.

Each weight $c_i$ can be uniquely written as $$c_i=\sum_{v\in B}\frac{a_{i,v}}{b_{i,v}}v$$ where $a_{i,v}$ are integers, $b_{i,v}$ are positive integers, and $\text{gcd}(a_{i,v},b_{i,v})=1$. Let $$b=\text{lcm}\{b_{i,v}v\in B, 0\leqslant i < p\}.$$ Define $$u_i=bc_i=\sum_{v\in B}a_{i,v} v.$$ Let $a=\max\{a_{i,v}:v\in B, 0\leqslant i<p\}$. As above, choose $a^i$ rocks from pile $i$. Then we can calculate $$\sum_{i=0}^{p-1}\sum_{v\in B}a_{i,v} a^i v.$$ Because $v$ is a basis, the coefficients $\sum_{i=0}^{p-1}a_{i,v}a^i$ can be calculated for each $i$. We can also calculate $\sum_{i=0}^{p-1}(a_{i,v}-1)a^i$, and, as above, the $a_{i,v}$ are unique. So we can work backward to find $a_{i,v}$, $a_{i,v}/b_{i,v}$,$u_i$, $c_i$.

$\endgroup$

You must log in to answer this question.

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