212 weights of 1 gram

Question

Fredo owns a balance with two pans and 212 weights, each of 1 gram. Fredo proudly announces to Cosmo that his weight system has the following stunning property:

For every integer weight $W$ with $1\le W\le212$, there is a unique way of getting a perfect equilibrium with $W$ in the left pan and some of the weights in the right pan.

Cosmo is not impressed: "What do you mean by a unique way of getting a perfect equilibrium?"
To which Fredo answers: "It is unique, if we ignore the ordering of the weights and if we do not distinguish between weights of equal value."
Cosmo is still not impressed: "But there must be dozens of weight systems with that property!"

Question: Is Cosmo right? How many other weight systems are there whose weights are integers that add up to $212$ and that have Fredo's special property?

Answer 1

There are 3 weight systems with these properties.

Let's try looking at it from the biggest weights first.

Let $w$ be the biggest weight of one such system, and let $n$ be the number of $w$-weights in the system. Let the remainder $r = 212 - n \times w$. Then $n$ is maximal (subject to $n \times w \leq 212$) and $r = w-1$.

Indeed, if $n$ were not maximal, then $r \geq w$. We can do division with remainder to find $p\geq 1$ and $0\leq q < w$ with $r = p \times w + q$. There is a unique combination of weights that add up to $q$, and none of these weights are $w$-weights (because $q < w$). We can use this to derive a contradiction of the uniqueness of an $r$-weighting:

• Take $p\times$ $w$-weights and the unique $q$-weighting (or nothing, if $q = 0$).
• Take all weights except $w$-weights; by hypothesis they add up to $r$.

It follows that $n$ is maximal and $r < w$. Now, if $r < w-1$, no weighting would be able to produce a $(w-1)$-weighting, so it must be $r = w-1$.

With this in mind, our formula then becomes:

$$\begin{equation}n \times w +r = 212\end{equation}$$

$$\Leftrightarrow n \times w + (w-1) = 212$$

$$\Leftrightarrow (n+1) \times w = 213$$

In other words our biggest weights in a system must be integer divisors of $212 + 1$

The only numbers this is true for are the following:

$$\begin{array}{lll} w=1& n=212& r=0\\ w=3& n=70& r=2\\ w=71& n=2& r=70 \end{array}$$

Of course, 213 would also fit, but we wouldn't get a single weight of that size and the remainder would still be 212, so nothing would be gained.

As for how we can fill in the remainder with weights, the next biggest weigth in the remainder must fulfill the same properties as the original biggest weigth. Therefore, we can use the same rules as we first used (except for $w=1$, because in that case $r=0$).

Since $r+1$ is a prime number in both cases, the complete remainder must be made out of $1$-weigths.

Finally, our systems are the following:

• $212\times$ $1$-weights;
• $70\times$ $3$-weights and $2\times$ $1$-weights;
• $2\times$ $71$-weights and $70\times$ $1$-weights.

Answer 2

Let's supose there is an alternative weight system other than all weights being one. How should it look like?

Let's suppose we have n integer weights w1,...,wn such that

w1 + w2 + ... + wn = 212, n <= 212 and let's see if we can construct a different system.

We can arrange our weights without losing generality: w1 <= w2 <= ... <= wn.

We know that w1 = 1, because we need to express 1.

Then, let k be the lowest integer weight we have above one. Then we have, sorted, this weights: 1, 1, 1, 1,..., 1, k,...

Then wi = k: If i < k, k-1 is not expressible as the sum of 1's (there are not enough ones). If i > k, k is expressible both as k and as a sum of ones.

This leaves us with a structure like this:

1, 1, 1, ..., 1, k1, k1, k1, ..., k1, k2, ..., ks.

where k1 appears at position k1. What numbers can we express so far? Only with ones: 1, 2, ..., k1-1 With k1: k1, k1+1,..., 2*k1-1

This means we need a new weight k2 to be 2*k1. What numbers can we express? Only with ones: 1, 2, ..., k1-1 With k1: k1, k1+1,..., 2*k1-1 With k2: k2, k2+1,..., k2 + k1 + (k1-1) = 4*k1 - 1

This means we need a new k3 to be 4*k1, and k4 to be 8*k1, etc. So we have a base-2 system of weights:

k1-1 ones: 1, 1, 1, ... k1, 2*k1 4*k1, ... 2^r*k1, for some integer r.

This adds to k1-1 + k1*(1+2+..+2^r) for some r, so we have this equation:

212 = k - 1 + k*(1+2+..+2^r), or

k * (1 + 1+ 2 +4 + ... + 2^r) = 213 = 3*71. Let's be q = 1 + 1+ 2 +...+2^r,

k * q = 3*71, all being integers and 3 and 71 being prime numbers, there are only two possibilities:

If k = 3, then q = 71 for some r. And if k = 71, q = 3 for some r. If you calculate q, q = 1 + (sum of powers of 2 until r) = 1 + 2^(r+1)-1 = 2^(r+1). So q is a power of two, and none of 3 and 71 are powers of two.

This leaves us with an impossible system other than all weights being one.

Answer 3

To be able to weigh objects of integer weight, including those of weight 1, the weights must form a set which in ascending order has the property that the first has weight 1 and each subsequent one has either the same weight as the preceding one, or the sum of all preceding weights plus 1. Weights of any other value, if included in the set, would allow the weight of some objects to be expressed with at least two different combinations of weights.

This means that if there are n1 weights of weight 1, the next weight must be of weight n1+1 and if there are n2 of these, the next heaviest must be of weight n2(n1+1)+n1+1 which factorises as (n2+1)(n1+1). The weight of the ith heaviest of the set will thus be (n(i-1)+1)(n(i-2)+1)...(n1+1) and the heaviest object that can be weighed will be (n(i)+1)(n(i-1)+1)(n(i-2)+1)...(n1+1)-1.

A set of weights capable of weighing an object of maximum weight 212 must thus consist of n(i)+n(i-1)+n(i-2)...+n1 weights of which

(n(i)+1)(n(i-1)+1)(n(i-2)+1)...(n1+1)-1=212

Adding 1 to each side, the task is thus to factorise 213, the prime factors of which are 1, 3, 71 and 213.

There are only three sets which satisfy this, Fredo's set where (212+1)-1=212 and the sets (70+1)(2+1)-1=212 and (2+1)(70+1)-1=212. These correspond to a set containing 2 weights of weight 1 and 70 weights of weight 3 (2x1+1) and one containg 70 weights of weight 1 and 2 weights of weight 71 (70x1+1).

Answer 4

Fredo's system represents a unary numeral system (i.e. base-1). We can change the base and still have Fredo's uniqueness property.

For a number system in base $n$, select weight values $n^k$ for all non-negative integers $k$ such that $n^k$ is at least 212. Then for each weight value, acquire $n-1$ weights.

Write the weight $W$ in base-n notation (e.g. in base-2 for W=5, write "101"). This representation is unique for each given (positive) $n$. The place value of each digit corresponds to a unique weight value. For each digit, its numeric value corresponds to the number of weights of the corresponding weight value to select. Since the representation is unique, the selection of weights is also unique, provided we have fewer than $n$ of each weight value.

Now, Frodo requires the weights to add up to 212. Define $s(p)$ as the sum of all weights in the system up to weight value $n^p$. That is, $$s(p) = \sum_{k=0}^{p} (n-1)n^k$$

Given $n$, we need to find place value $k$ such that 212 is between $s(p-1)$ and $s(p)$ for some $p$, and the remaining weight is a multiple of $n^p$, where that multiple is less than $n$ (i.e. the last place value may have less than the maximum number of weights).

It can be shown that none of the systems for $1 < n < 15$ work. From $n=15$, we have $n^ > 212$, so we can just solve $212 - (n-1) = kn$, which reduces to $213 = (k+1)n$. Since $212 = 3 * 71$, both of which are prime, the only remaining solution is $n=71, k=2$. That is, 70 sets of 1-weights, and 2 sets of 71-weights. This matches one of the systems others have derived.

If we now relax the system and allow more than $(n-1)$ of the largest weights, we still have a unique numbering system, but can now admit the other solution involving $3 * 71$, namely, $n=3, k=70$. That is, 2 sets of 1-weights and 70 sets of 3-weights. This matches the other system others have derived.

[Note: I much prefer the solution by @TheDarkTruth for this problem, but will leave this solution up for now as it offers an alternate formulation of the puzzle.]