# General solution to a weighing puzzle

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

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.$$
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. 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$$.