Another Ebbozonian coin weighing puzzle

Question

This puzzles continues "The Ebbozonian coin weighing puzzle" from last week.

---

In the country of Ebbozonia, there are only two type of coins: light coins and heavy coins. The weights of these coins satisfy the following properties:

• All light coins have the same weight $L$.
• All heavy coins have the same weight $H$.
• Heavy coins are heavier than light coins: $H>L$

The precise values of $L$ and $H$ are not known to the public. The difference between $L$ and $H$ should be fairly small, as there is no way of distinguishing the two coin types without a balance. His Highness, the Honourable Minister of Treasury, has recently announced the following important property of the Ebbozonian coin system:

• If a balance is in perfect equilibrium with $h_1$ heavy and $\ell_1$ light coins on the right pan and with $h_2$ heavy and $\ell_2$ light coins on the left pan, then $h_1=h_2$ and $\ell_1=\ell_2$ must necessarily hold true.

Cosmo puts 30 Ebbozonian coins on the table and asks Fredo to determine quickly whether these 30 coins all have the same weight. On the table, there is a balance with two pans (but there are no weights).

Question: Can Fredo solve Cosmo's problem by using the balance at most four times?

Answer 1

I hypothesize that 22 is the maximum, and the maximum follows this oeis.org sequence

So I've had a little progress without a computer. I want briefly to return to @Joel's solution to the 10 coin, 3 weighing puzzle and the reason why it works. To start we'll say heavy coins weigh 1 and light weigh 0. Also we're assuming that all weighing are balanced (since otherwise we're done), have the same number of coins on each side and we want to show that with a certain configuration we can prove that all the coins weigh the same.

1 In my first weighing I'm going to take a group of coins that I'll call $A$ with an as yet unknown size and with weight $a$. They will be on one side, and I'll get to the other side later.

2 In my second weighing, I'll take $A$ and another coin $B$ which I'll say weighs $b$ on one side, and other coins of equal number on the other side, which I'll call group $C$. Obviously $C$ weighs $a+b$.

3 Now for my third weighing, I'll take $C$ and $B$ and weigh it against $A$ and two as yet untested coins ($D$). Then the two untested coins must weigh $2b$ (since $C+B-A$ weighs $(a+b) +b-a$). Therefore the two untested coins must each weigh $b$. So now I have three coins that all weigh $b$ and that aren't in $A$. Suppose I had those three on the other side of weighing 1. Then $A$ had three coins in it, and it must consist of three coins each weighing $b$, and so $C$ must have four coins each weighing $b$, and so all 10 coins must be the same. This is a proof that Joel's previous solution works as intended.

However, one could also instead have simply continued with a fourth weighing following a similar strategy:

4 Weigh $C$, $B$ and $D$ against $A$ and four as yet untested coins ($E$). Once again it is easy to show that the 4 new coins ($E$) weigh $4b$, and so each one weighs $b$. In this case when you go back to the first weighing you weigh $A$ against 7 coins ($B$, $D$ and $E$), which weigh $7b$, and so once again it follows that all 22 coins weigh $b$.

However, 22 coins is not 30 coins, so I suspect that my generalization may not be the best one available. It does show that for $n>1$ weighings there is a strategy to get $3.2^{n-1}-2$ coins sorted out.

To summarize this answer for 4 weighings:

1. $1,\ldots,7$ v $8,9,10,11,12,13,14$
2. $1 ,\ldots, 7,8$ v $15,\ldots,22$
3. $1,\ldots,7,9,10$ v $8,15,\ldots,22$
4. $1,\ldots,7,11,12,13,14$ v $8,9,10,15,\ldots,22$

Answer 2

As I mentioned in a previous comment, checking all weighings can take more than an hour on a fast machine. So I stopped trying to solve it that way, and only used it to check possible answers.

Weighing #1:

1-15 v 16-30

Excluding duplicates, this gives me the following ordered groups and possible weighings, where the number listed is the number of fewer coins (light or heavy):

15 15
 ------
  1   1
  2   2
  3   3
  4   4
  5   5
  6   6
  7   7

Now, the next part was to find a suitable second weighing. I tried following the first puzzle's weighing strategy and that led to problems. I could solve everything except for 20 light / 10 heavy. So I abandoned that.

I tried many different weighings, and decided what I really needed to do was avoid multiples of 3 and 5. This brings me to weighing 2:

1-11 v 12-22

This gives me the following known group sizes in order and possible weighings for them:

11 4 7 8
 ----------
  1 0 1 0
  2 0 2 0
  1 1 0 2
  3 0 3 0
  2 1 1 2
  4 0 4 0
  3 1 2 2
  2 2 0 4
  5 0 5 0
  4 1 3 2
  3 2 1 4
  6 0 6 0
  5 1 4 2
  4 2 2 4
  3 3 0 6

Given the general large difference between the first and third and second and fourth groups, I want to combine them for my third weighing. I tried a few different ways and came up with the following:

7-11,16-22 v 12-15,23-30

This weighing made it impossible to have many of the second group of weighings be equal, leaving me with the known group sizes and weighings of:

6 5 4 7 8
-----------
0 2 1 1 2
2 1 1 2 2
4 0 1 3 2
0 4 2 2 4
2 3 2 3 4

Now I have one weighing left, and it is:

1-6,15-22 v 7-11,23-30

This makes all the remaining weighings invalid leaving the only possibilities as 30 light/0 heavy or 0 light/30 heavy.

TL;DR

1-15 v 16-30
1-11 v 12-22
7-11,16-22 v 12-15,23-30
1-6,16-22 v 7-11,23-30

Answer 3

Here is another solution for 30 coins. Split the 30 coins into sets a,b,c,d,e containing 2,5,6,8,9 coins respectively. Then compare these combinations of sets:

d : a+c
a+e : b+c
b+e : c+d
c+e : a+b+d

In answer to Joel Rondeau's comment about 60 coins, there are numerous solutions using the balance five times.

For example, split the 60 coins into sets a,b,c,d,e,f,g containing 5,6,7,9,10,11,12 coins respectively. Then compare these combinations of sets:

a+e : b+d
e+f : a+c+d
e+g : a+b+f
f+g : b+c+e
d+e+f : a+b+c+g

And a solution for 90 coins in five weighings:

Split the 90 coins into sets a,b,c,d,e,f containing 10, 12, 15, 16, 18, 19 coins. Then compare:

a+e : b+d
b+f : c+d
c+f : d+e
e+f : a+b+c
a+d+f : b+c+e