Proving by weighting

Question

Here is the puzzle:

Alice and Bob leave in a world where all diamonds are divided into 2 types: Light and Heavy. All diamonds look exactly the same. All light diamonds weight exactly the same, all heavy also weight exactly the same but a bit more than the light (by an unknown, infinitely small amount more).
Now, Bob wants to sell Alice N light and N heavy diamonds. Before he does it he has to prove that those are exactly N light and N heavy, not like 2N light or any other combination of light and heavy. And he must do it using infinitely precise scales, which can only compare two weights (i.e. they don't show the weight difference, only which one is heavier). He must do it in 4 weightings.
What is the maximum N, which Bob can sell?

For example, it's easy to solve the puzzle for N = 15.
Name all diamonds according to their weight. Light: L1, L2, ...; heavy: H1, H2, ...

Weighting 1: compare L1 vs H1. Alice sees that the first is lighter and believes that L1 is a light diamond and H1 is a heavy diamond.
Weighting 2: compare L2+L3+H1 vs H2+H3+L1. Alice sees that the first set of diamonds is lighter and concludes that L2,L3 is light diamond and H2,H3 is heavy, since this is the only way for Weighting1 and Weighting2 to be as they are.
Weighting 3: compare L4L5L6L7H1H2H3 vs H4H5H6H7L1L2L3.
Weighting 4: compare L8..L15H1..H7 vs H8..L15L1..L7.

And I know, in fact, there is a solution for $N=27$.

What I need to know is a maximum $N_{max}$, a weighting procedure for $N_{max}$ diamonds, and proof that there is no possible procedure for $N_{max}+1$ diamonds.

Answer 1

Note, if you are having a hard time relating the solution below to the question. That is because of OP's extensive changes to the question. Originally, heavy diamonds were 101g and light ones 100g.

There is no maximum, in fact, any N>100 can be verified in 2 weighings.

Indeed, let M be the largest multiple of 101 not larger than N. Place M light diamonds against 100xM/101 heavy diamonds. The balance will show they are equal which proves their identities. Now swap all the not yet weighed diamonds in like-for-like and weigh again. This is always possible with the sole exception of N=201. where we have 101 heavies left over and only 100 spots to swap them in. But this can be solved by adding one of the already confirmed heavies to the light side and balancing it by the 101st new heavy.

Answer 2

No proof of optimality, but for the record, I have a solution for

$N=27$

Comparisons: $r_1 \dots r_8s_1 \dots s_8a_1 \dots a_3 < x_1 \dots x_{16}b_1 \dots b_3 < y_1 \dots y_{16}a_1 \dots a_3<r_1 \dots r_8s_1 \dots s_8b_1 \dots b_3;r_1 \dots r_8b_1 \dots b_3y_1 \dots y_{16}<s_1 \dots s_8a_1 \dots a_3x_1 \dots x_{16}$

Because they are separated by 3 $<$ signs, there are at least three more heavy diamonds in $r_1 \dots r_8s_1 \dots s_8a_1 \dots a_3$ versus $r_1 \dots r_8s_1 \dots s_8b_1 \dots b_3$. As the only differences are $a_i$ and $b_i$, it must be that all of $a_i$ are light and all of $b_i$ are heavy, and the difference (in number of heavy diamonds) across each of these 3 $<$ signs is exactly one.

Then, consider the inner comparison $x_1 \dots x_{16}b_1 \dots b_3 < y_1 \dots y_{16}a_1 \dots a_3$. There must be exactly four more heavy diamonds among the $y_i$ versus the $x_i$.

Now, consider the last comparison. The heavy diamonds in $b_i$ and $y_i$ outnumber $a_i$ and $x_i$ by 7, so in order to satisfy the comparison, it must be that all of $r_i$ are light and all of $s_i$ are heavy.

Then we can see from the 3 $<$ chain that the total number of light and heavy diamonds are the same (e.g. we know there are exactly $8$ heavy diamonds on the left and $11$ on the right which tells us the exact numbers among $x_i$ and $y_i$). This is true even though we don't know which of $x_i$ or $y_i$ are heavy or light.

Answer 3

The answer is in fact simple:

Nmax=15, and the procedure in question is in fact optimal

Why? First, let's introduce some abbreviations for the sake of simplicity:

KL and KH for "known-light" and "known-heavy", i.e. diamonds which already have their weight proven by us. Similarly, PL and PH for "presumed-light" and "presumed-heavy", i.e. diamonds which are labeled as such but still unproven.

Now, notice that

when weighing, we cannot mix PL and PH diamonds on one side of the scales, since, for example, one of the PL diamonds could be in fact heavy, and a PH diamond cold be light, and so, this could go undetected. For similar reasons, we cannot distribute same "P" diamonds (i.e. PL or PH) between different sides of the scales (since,for example, one of the PL diamonds on each side could be heavy, and this will go undetected because the weight difference remain the same).

So,

the only sound arrangement is to put PL+some "K" diamonds on the one side of the scales, and PH+some "K" on the other.

But

to prove or disprove the weights of multiple diamonds at once, we need to have a set of known diamonds that can be separated in two parts (having the same number of diamonds) with large weight difference. If $d$ is the difference between light and heavy, and we have $2k$ known diamonds, the largest difference we can create is $kd$ ($k$ heavy minus $k$ light ones). Such difference cannot positively identify a set of "P" diamonds of size more than $2(k+1)$ at once (because we won't know the difference between weights upon weighing, only which part is heavier). If we put $k+2$ "P" diamonds on each side, the difference between "P" weights will be $(k+2)d$, and we cannot detect by placing additional "K" diamonds if this difference is in fact $(k+2)d$ or $(k+1)d$ which can happen if only one of the "P" diamonds on the scales is labeled wrong.

That means that

having $k$ KL and $k$ KH diamonds, we cannot identify more than $k+1$ PL and $k+1$ PH diamonds in one weighing.

Before the 1st weighing, we have

$k(0)=0$

Since

$k(i)=2k(i-1)+1$ (we know how to identify exactly $k+1$ pairs of diamonds, since this is the procedure described in the question itself),

we have that

$k(i)=2^i-1$. Putting $i=4$ gives $k(4)=15$.

P.S. Sorry for such a lengthy and complicated proof, I wrote this from my phone at 0:48 (12:48 AM) local time.