Weighing in 2015 different ways

Question

This question was inspired by something I realized while thinking about @Gamow's Weighing in 89 different ways.

You have a two-pan balance and $2015$ weights, with masses $1,2,4,\ldots, 2^{2014}$. You also have one coin with a mass that is at least $1$ and at most $2^{2014}$.

There are exactly $2015$ ways to place the coin in the left pan of the balance, and some number of weights in either pan of the balance, such that both sides of the balance have the same total mass. How many possibilities are there for the mass of the coin?

Hint 1:

How many ways are there to make $2^n$? What about $3\times2^n$, $5\times2^n$, $7\times2^n$?

Hint 2a:

The 99th-smallest possibility is $1476395007\times2^{1970}$.

Hint 2b:

If we pad out the binary representation of $1476395007\times2^{1970}$ to $2015$ digits, the result is 14 zeroes, 1 one, 1 zero, 1 one, 1 zero, 27 ones, and 1970 zeros. The continued fraction $[14;1,1,1,1,27]$ is equal to $\frac{2015}{138}$. The appearance of $2015$ in the numerator is not a coincidence!

Hint 3:

$1476395006\times2^{1970}\rightarrow[14;1,1,1,1,26]=\frac{1942}{133}\\1476395007\times2^{1970}\rightarrow[14;1,1,1,1,27]=\frac{2015}{138}\\1476395008\times2^{1970}\rightarrow[14;1,1,2]=\frac{73}{5}$

Hint 4:

https://electronics.stackexchange.com/a/202024

Answer 1

We will prove something slightly stronger that implies 2012rcampion's solution is corrrect.

Let $[x_n,y_n,x_{n-1},y_{n-1}, \dots, x_1,y_1,x_0]$ be the binary number $p$ given by $$\text{$x_n$ 0's , $y_n$ 1's , $x_{n-1}$ 0's , $y_{n-1}$ 1's , $\dots$ , $x_1$ 0's , $y_1$ 1's , $x_0$ 0's}$$

Then the numerator of the simplified fraction that is equal to the continued fraction$$[x_n;y_n,x_{n-1},y_{n-1}, \dots ,x_1,y_1]$$is precisely the number of distinct ways of writing an equality $p +q = r$, where $q$ and $r$ are never $1$ in the same binary digit and are always $0$ on every binary digit beyond $x_n$.

It should be clear how every solution as in the statement corresponds to a solution on the scale: $p$ is the weight of the coin, and $q, r$ provide the choice of weights on each pan of the balance.

Moreover, we assume without loss of generality that $x_n, y_n \geq 1$, except $x_0$ may be $0$. It can be easily seen the coin may not weigh $2^{2014}$, so the assumption is justified (its last bit must be $0$, and its first bit need not be $0$), and the weight of the coin can always be written as some $p$ in the statement. This also shows why we must consider, as 2012rcampion did, only fractions with $2015$ in the numerator that are greater than one.

The proof will be by induction.

• Base case: $n=1$.

In this case, $p$ is of the form$$\underbrace{00\dots 0}_{x_1}\underbrace{11\dots 1}_{y_1}\underbrace{00\dots 0}_{x_0}$$

Our reasoning will go as follows: we will analyze how the conditions on $q$ and $r$ shape a solution, going from the rightmost digit of $q$ and proceeding to the left. We will consider possibilities for $q$ that will automatically ensure the conditions on $q$ and $r=p+q$ are satisfied.

For any solution $(p,q,r)$, the fist $x_0$ digits of $q$ must be $0$, for otherwise condition that $q$ and $r$ not be $1$ in the same digit would be violated.

Now, we may choose any of the next $y_1$ digits of $q$ to be $1$, and this will create a domino effect of carry-overs, imposing that all other of these $y_1$ digits be $0$ (so as not to violate the digit condition). Of course, we may also choose to have all of these $y_1$ digits be $0$, and as in the preceding paragraph this will make it so that all of the next $x_1$ digits also be $0$.

We have thus found one solution (all zeroes) and $y_1$ 'partial' solutions, with a $1$ in one of the digits corresponding to $y_1$ and $0$ at the other digits. We need only find the possibilities for the last $x_1$ digits of the partial solutions. These last digits of the sum $p+q$ currently look like this:$$\underbrace{00\dots 0}_{x_1-1}1$$

We may choose to have the corresponding rightmost digit in $q$ be $0$, and this will impose that all other digits be also $0$; or we may choose it be $1$, and this will create a carry over. In this latter case, the new last digits of the sum have a very similar form:$$\underbrace{00\dots 0}_{x_1-2}1$$

Continuing in this fashion, we find there are $x_1$ fits to the $y_1$ partial solutions we initially encountered. These fits correspond to choosing one of the last $x_1$ digits and assigning $1$ to all digits that (strictly) precede it in the segment, and $0$ to all others. Notice in particular that the last digit will always be $0$, even when all others that precede it are $1$, because of the condition that binary digits beyond $x_n$ be $0$.

There are thus $x_1y_1 +1$ solutions. Now, consider the continued fraction of the statement. We have$$[x_1;y_1]=x_1+\frac{1}{y_1}=\frac{x_1y_1+1}{y_1},$$so the numerator of the corresponding simplified fraction is in agreement, as claimed.

• Inductive step: suppose the claim holds for all $m$ with $1 \leq m \leq n-1$ and let $p$ be given by $[x_n,y_n, \dots, x_1,y_1,x_0]$.

We will analyze the shape of the initial digits of $q$, like we did in the previous case. Its first $x_0$ digits need once again be $0$.

If we choose the next $y_1$ of its digits to be $0$, then the next $x_1$ of its digits will also have to be $0$, and we will have found one partial solution, complete until the digits that correspond to $y_2$.

Like before, we may also choose one of the $y_1$ digits to be $1$, and this will create a domino carry-over effect. Any of these $y_1$ choices will result in a sum that looks like this:$$\dots \underbrace{00\dots 0}_{x_2} \underbrace{11\dots 1}_{y_2}\underbrace{00\dots 0}_{x_1-1}1$$

As in the previous case, we may choose the rightmost digit in the segment to be $0$ or $1$, where choosing $0$ implies that all the next digits (until the $y_2$ segment) also be $0$, and choosing $1$ implies a new choice must be made for the next rightmost digit (with similar implications).

This results in $x_1-1$ fits that end in $0$ (so the next segment of $1$'s in $p+q$ has length $y_2$) and a single fit that ends in $1$ (so the next segment of $1$'s in $p+1$ has length $y_2+1$). We may group the former with our lone previous partial solution, for a total $y_1(x_1-1)+1$ partial solutions that need a fit for the binary number $[x_n,y_n, \dots, x_2,y_2]$, and $y_1$ partial solutions that need a fit for the binary number $[x_n,y_n, \dots, x_2,y_2+1]$.

We may apply the inductive hypothesis to these fits, but we will use some results on continued fractions. Consider the sequence of positive integers $(a_j)$ given by the $x_i$'s and $y_i$'s: \begin{array}{ccccccccc} x_n&y_n&x_{n-1}&y_n{-1}&\dots &x_2&y_2&x_1&y_1\\ a_0&a_1&a_2&a_3& \dots &a_{l}&a_{l+1}&a_{l+2}&a_{l+3} \end{array}

Let $h_j$ and $k_j$ be the corresponding recursive sequences (see the link). Then we have that$$[x_n;y_n, \dots, x_2,y_2]=[a_0;a_1, \dots, a_l,a_{l+1}]\\ [x_n;y_n, \dots, x_2,y_2+1]=[a_0;a_1, \dots, a_l,a_{l+1}+1]=[a_0;a_1, \dots, a_l,a_{l+1},1]$$

Hence, by Theorems 1 and 2:$$[x_n;y_n, \dots, x_2,y_2]=\frac{h_{l+1}}{k_{l+1}}\\ [x_n;y_n, \dots, x_2,y_2+1]=\frac{h_{l+1}+h_l}{k_{l+1}+k_l}$$

By Corollary 1 and the Lemma at the end, these fractions are irreducible so we may apply the inductive hypothesis to the (binary) numbers $[x_n,y_n, \dots, x_2,y_2]$ and $[x_n,y_n, \dots, x_2,y_2+1]$, obtaining that the total number of solutions is: \begin{align}&(x_1y_1-y_1+1)\cdot h_{l+1} + y_1 \cdot (h_{l+1}+h_l)\\ = \text{ } &(a_{l+2}a_{l+3}-a_{l+3}+1)\cdot h_{l+1} + a_{l+3} \cdot (h_{l+1}+h_l)\\ = \text{ } &(a_{l+2}a_{l+3}+1)\cdot h_{l+1} + a_{l+3} \cdot h_l\\ = \text{ } &a_{l+3}(a_{l+2}\cdot h_{l+1}+h_l)+h_{l+1}\\ = \text{ } &a_{l+3}\cdot h_{l+2} + h_{l+1}=h_{l+3} \end{align}

On the other hand, $h_{l+3}$ is the numerator of the simplified fraction given by$$[x_n;y_n, \dots, x_1,y_1]=[a_0;a_1, \dots, a_{l+2},a_{l+3}]=\frac{h_{l+3}}{k_{l+3}},$$which completes the induction.

Lemma: The fraction $\frac{a \cdot h_{l+1}+h_l}{a \cdot k_{l+1}+k_l}$ is irreducible for all integers $a$ with $0 \leq a \leq a_{l+2}$.

Indeed, when $a=0$ we have $\frac{h_l}{k_l}$ and when $a=a_{l+2}$ we have $\frac{h_{l+2}}{k_{l+2}}$.

When $a$ is in between, it suffices to note that by construction of the sequences $(h_j)$ and $(k_j)$, $a \cdot h_{l+1}+h_l$ is precisely the numerator in the simplification of the continued fraction $[a_0;a_1, \dots, a_l,a_{l+1},a]$, and $a \cdot k_{l+1}+k_l$ is its denominator. Then, when $a\geq 2$ irreducibility follows from the fact that $\frac{1}{a}$ is irreducible, and when $a=1$ it follows from the fact that $[a_0;a_1, \dots, a_l,a_{l+1},a]=[a_0;a_1, \dots, a_l,a_{l+1}+1]$ (and in this case, $a_{l+1}+1\geq 2$, so $\frac{1}{a_{l+1}+1}$ is irreducible).

Notice the $a_j$ involved are all positive (only $a_{l+4}$ may be zero), so that none of the assumptions of the lemma lead to contradictions.

When I decided to try and tackle this problem, I had no idea it would be as hard and take as long as it did. I have no idea how you could see this relation between combinatorics of weightings and continued fractions, but I'm glad you did, because my other attempts were not at all feasible, involving recursion that was not very realistic to compute. Your hints were invaluable.

Still, I am very glad to have been shown this. It's one of those mathematical truths that bewilders me by how it unexpectedly relates two things that seem to have nothing at all in common, shedding light on some intricate underlying structure that has always been there, unmindful of whether or not we grasp it.

Answer 2

Update

Going back to my original post

...we are looking for the cardinality of the set $\{f(q) = 2015\}$ for all $q$ in the allowed range,

where $f$ is defined as

$f(n) =\begin{cases}f(\frac{n}2) & \quad \text{if } n \text{ is even},\\ f(\frac{n+1}2) + f(\frac{n-1}2) & \quad \text{if } n \text{ is odd}\end{cases}$ and $f(0) = 1$ and $n>0$.

This is explained as follows:

Let $*****,y_1,y_2$ be an arbitrary number.

• If $y_2$ is 0, this cannot be further expanded. So we have to look at $y_1$.
• If $y_2$ is 1, we can leave it fixed as $1$ (hence, we can forget about it), or...
• we may expand it to $1,-1$. Now, the $1$ will interfere with $y_1$, so we have $*****,(y_1+1),-1$. We have fixed $y_2 = -1$, so we can further ignore it.

Again, if $y_1 = 0$, the expansion will stop here. For the starting conditions, the number of representations of $0$ is $1$.

One problem remains, $f(1) = f(1)+f(0)$. This is because, given an infinite series of weights $(2^i)_{i>0}$ there are infinitely many representations of $1$. In the question, $i$ cannot be larger than $2^{2014}$, which gives a max recursion depth.

The sequence that arises is closely related to the Stern-Brocot sequence, but I haven't found a good way to compute the cardinality of the set $\{f(q) = 2015\}$.

End of update

So...

...the weight can be $1$ since then we have $[1]$, $[2-1]$, $[4-2-1]$,...,$[2^{2014}-2^{2013}-...-1]$ which are the only ways to get $1$ (I guess no proof is needed for this). There are exactly $2015$ such sums. Also, the weight may be $2^{2014}-1$ (and, of course, this is the maximum weight) since we have $[2^{2014}-1]$, $[2^{2014}-2+1]$, $[2^{2014}-4+2+1]$,...,$[2^{2014}-2^{2013}+...+1]$. There is obviously some symmetry here.

This gives us a rough lower bound of $2$ :-)

Examples

Let us first study a couple of examples (msb is the left-most bit).

• If we take a number $n=\underbrace{0\cdots0}_{m}1$, there are $m+1$ different representations.
• For $n=\underbrace{0\cdots0}_{m}11$, there are $2m+1$ different representations.
• More generally, for $n=\underbrace{0\cdots0}_{m_1}\underbrace{1\cdots1}_{m_2}$, there are $m_1m_2+1$ different representations.
• For $n=\underbrace{0\cdots0}_{m_1}\underbrace{1\cdots1}_{m_2}\underbrace{0\cdots0}_{m_3}$, there are $m_1m_2+1$ different representations, regardless of $m_3$ since there is no $1$ to expand.
• We omitt $n=\underbrace{1\cdots1}_{m_1}\underbrace{0\cdots0}_{m_2}\underbrace{1\cdots1}_{m_3}$, as this is larger than the allowed solution.
• For $n=\underbrace{0\cdots0}_{m_1}\underbrace{1\cdots1}_{m_2}\underbrace{0\cdots0}_{m_3}\underbrace{1\cdots1}_{m_4}$ we rewrite the expression. Let underline denote negative bits and denote an expandable set of bits with overline. We have the following:
  1. $0\cdots00,11\cdots11,0\cdots00,11\cdots11$ - $1$
  2. $ \overline{0\cdots01},\overline{00\cdots0\underline{1}},1\cdots11,00\cdots00$ - third and fourth field does not change, so $m_1m_2$ possible representations.
  3. $ 0\cdots00,11\cdots11,\overline{0\cdots01},\overline{00\cdots0\underline{1}}$ - first and second field does not change, so $m_3m_4$ possible representations.
  4. $\overline{0\cdots01}, 00\cdots00 ,\underline{1}\underline{1}\cdots\underline{1},\overline{00\cdots0\underline{1}}$ - $m_1m_4$ representations.
  5. $\overline{0\cdots01}, \overline{00\cdots0\underline{1}} ,\overline{0\cdots01},\overline{00\cdots0\underline{1}}$ - $m_1m_2m_3m_4$ possible representations. All these sets are disjoint and give in total $m_1m_2m_3m_4+m_1m_2+m_3m_4+m_1m_4+1 = $$m_3 m_4+m_1 (m_4+m_2 (m_3 m_4+1))+1$ representations, which corresponds to the numerator of $[m_1;m_2,m_3,m_4]$.

As a generalization of the size of the reprsentation sets, we have the recursion $S_i = m_iS_{i-1} + S_{i-2}$, $S_0 = 1$, $S_{-1}=0$. Of course this generalization is non-trivial, but for now I will treat it handwavingly.

We see that it fits the continued fraction (from the hint).

The weights

The maximum weight is obtained by $[1;1,1,1,1,1,1,1...]$, which corresponds to the Fibonacci sequence: in this case $2015 < F_{18}$. This is a bit too much to simply perform brute force search over (since all lengths up to 18 must be checked and with the first $0 \leq m_1 \leq 14$).

I suspect that, to find the solutions, we should be able solve the non-linear equations modular

$\begin{bmatrix}m_1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}m_2 & 1 \\ 1 & 0\end{bmatrix}\cdots\begin{bmatrix}m_k & 1 \\ 1 & 0\end{bmatrix} \equiv \begin{bmatrix}0 & * \\*&*\end{bmatrix} \bmod \{5,13,31\}$

and reconstruct using Chinese remainder theorem, but it still requires a lot of work. I guess there is a smart way to exploit the structure or maybe a theorem regarding continued fractions that may be usable.

Answer 3

(Please tell me why this works, I have no idea!)

Hint 2b suggests that there is a relationship between binary representations of coin weights and continued fractions. I assumed that this relationship is a one-to-one mapping, so we can count all possible weights by enumerating the continued fractions.

Basically, we want all fractions with $2015$ in the numerator, whose continued fractions represent binary numbers less than $2^{2015-1}$. Those numbers have a leading zero in their binary expansion, so we want fractions whose continued fraction expansion begins with a nonzero number: that is, fractions greater than one. This means that the denominator must be less than $2015$, and coprime to $2015$. There are $\phi(2015)$ numbers matching those criteria, so the number of possible denominators/possible fractions/possible continued fractions/possible binary numbers/possible weights is just:

$1440$

Answer 4

Here is my intended solution:

Consider the number of ways to weigh $(2k+1)\times2^n$. Any weighing must involve the weight $2^n$ and no smaller weights. If $2^n$ is on the left, the remaining weights form a weighing of $(2k+2)\times2^n$. If $2^n$ is on the right, the remaining weights form a weighing of $2k\times2^n$. Therefore, the number of ways to weigh $(2k+1)\times2^n$ is equal to the number of ways to weigh $2k\times2^n$, plus the number of ways to weigh $(2k+2)\times2^n$.

If we start with $0$ having 1 weighing and $2^{2015}$ having 0 weighings, we can generate the number of weighings for every integer in between by adding neighboring terms. This corresponds exactly to the way the Stern-Brocot tree is generated. Therefore the number of ways to weigh $x$ is precisely the denominator of the $x$th (zero-indexed) term in the Stern-Brocot tree with depth $2015$.

The weight $2^{2014}$ corresponds to the fraction $\frac{1}{1}$, so we want to count the number of fractions in the Stern-Brocot tree that are less than $1$ and have a denominator of $2015$. There are $\phi(2015)$ such fractions, one for each possible numerator coprime to $2015$ (the tree is deep enough to contain them all), so the answer is $1440$.

---

The hints about the continued fractions were detailing a way to calculate the specified term in the Stern-Brocot tree, although the fractions were reversed for simplicity.