6
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ With a quad core i7, I'm sitting at about an hour to run through all the combinations. If the next one has 60 coins, someone else can answer it. $\endgroup$ – Joel Rondeau Oct 19 '15 at 17:27
  • 3
    $\begingroup$ So for the next one, we also want to know what kind of computing hardware Fredo has available. $\endgroup$ – DrunkWolf Oct 20 '15 at 17:09
  • $\begingroup$ I'm not sure the last condition is needed. We only ever will perform a weighing with with same number of coins on both sides, so if they balance it has to be the case that $h_1=h_2$ and $l_1=l_2$ $\endgroup$ – Dr Xorile Oct 21 '15 at 11:41
  • $\begingroup$ @Gamow, do you know the answer too this? Are you waiting for a proof that it's impossible? $\endgroup$ – Dr Xorile Nov 9 '15 at 18:24
  • $\begingroup$ @DrXorile: Yes, I know the answer. $\endgroup$ – Gamow Nov 9 '15 at 18:27
4
$\begingroup$

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$
$\endgroup$
  • $\begingroup$ The question is whether it's possible to do more than 22. $\endgroup$ – Dr Xorile Oct 23 '15 at 1:19
  • $\begingroup$ What if $b$ were 2 coins, not 1? $\endgroup$ – Charles Koppelman Oct 23 '15 at 17:49
  • $\begingroup$ @CharlesKoppelman, I did my analysis assuming some number of coins in $B$, but it turns out that if it's more than 1 then there's a way of pairing the coins with light/heavy, in $B$ and all the things you weigh $B$ against. Basically, the above hinges on the idea that if you can show that $n$ coins weigh $nb$, then all $n$ coins weigh $b$ where $b$ is 0 or 1. But if you have $2n$ coins weighing $nb$, where $b$ is 0,1 or 2, then it falls apart. $\endgroup$ – Dr Xorile Oct 23 '15 at 21:10
  • $\begingroup$ But I wonder if there can be a way to make it make sense again. $\endgroup$ – Charles Koppelman Oct 26 '15 at 18:43
  • $\begingroup$ I tried various options, and couldn't get better than 22. I'd like to figure out what the maximum no of coins is for a given number of weighings. I think that more than 22 may not be possible... $\endgroup$ – Dr Xorile Oct 26 '15 at 19:11
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is an extremely clever solution! Congrats $\endgroup$ – Dr Xorile Dec 4 '15 at 1:03
  • $\begingroup$ That was my 4th solution. I "solved" it 3 other times, then ran it through my original program to check it, and discovered an error each time. I was actually expecting that this time and was surprised when it didn't happen. $\endgroup$ – Joel Rondeau Dec 4 '15 at 1:10
1
$\begingroup$

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
$\endgroup$

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.