10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Cosmo never claims the weights have to add up to 212, or that they have to be integer multiples of a gram, so his statement is perfectly correct. $\endgroup$ – user2357112 Nov 30 '15 at 18:04
  • $\begingroup$ @user2357112 each of 1 gram: doesn't this mean that they are integer multiples of a gram? In fact because there are 212 of them, they add up to 212 grams. $\endgroup$ – user2023861 Nov 30 '15 at 18:18
  • $\begingroup$ @user2023861: This particular weight system happens to be made of integer multiples of a gram, but that's not part of "that property" that Cosmo claims plenty of weight systems share. $\endgroup$ – user2357112 Nov 30 '15 at 18:20
  • $\begingroup$ Can you explain this part a little more? "For every integer weight W with 1≤W≤212, 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." Pick W = 212. If there are 212 weights, each of 1 gram, then to put 212 in the left pan, you have to use all your weights, and then there are none left for the right pan. This would seem to be in violation of "W in the left pan" and some ... in the right pan." $\endgroup$ – Joshua Taylor Nov 30 '15 at 20:37
  • $\begingroup$ Oh, I think I get it. Fredo actually has owns two sets of weights: a set of 212 1 gram weights, and then some other set that we don't know about (except for its special property). $\endgroup$ – Joshua Taylor Nov 30 '15 at 20:48
12
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ why would there be more than 1 w? this question is confusing me $\endgroup$ – njzk2 Nov 30 '15 at 22:39
  • $\begingroup$ I like that your solution also points to how one can solve general problems of this kind. Nice job! $\endgroup$ – Fimpellizieri Nov 30 '15 at 23:29
  • $\begingroup$ @Fimpellizieri: I would like to thank you for making my solution look so nice. $\endgroup$ – The Dark Truth Dec 1 '15 at 7:54
  • $\begingroup$ @TheDarkTruth you're welcome. The credit goes to you though; the reasoning was yours! $\endgroup$ – Fimpellizieri Dec 1 '15 at 20:48
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Ivo Beckers: that System wouldn't have the property of all numbers adding up to exactly 212. The answer is still incorrect. I'm working on another answer. $\endgroup$ – The Dark Truth Nov 30 '15 at 14:15
  • $\begingroup$ 70x1 and 2x71 is a system with the same property, so is 2x1 and 70x3. They are the only ones I think, due to 211 being a prime $\endgroup$ – DrunkWolf Nov 30 '15 at 14:39
  • $\begingroup$ Good point DarkTruth! $\endgroup$ – Edgar G. Nov 30 '15 at 15:25
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You're right. I withdraw this answer and will delete it shortly. $\endgroup$ – Lawrence Dec 2 '15 at 1:31
  • $\begingroup$ @f'' I managed to amend the solution to address the missing condition, so I'll leave it up for now. However, I'm not particularly happy with my solution as it stands and will remove it if it proves unpopular. $\endgroup$ – Lawrence Dec 2 '15 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.