Puzzle Corner

[Laird]

An old favourite puzzle. Some if not all of you are probably familiar with it already:

You are given 9 balls and a pair of balancing scales. All of the balls are of equal weight except for one of them, but you are not told which one this is, nor whether it is heavier or lighter than the rest. Your task is to discover which ball is a different weight and whether it is heavier or lighter. You may use the scales three times to weigh any combination of balls against any other combination. You may of course base your choice of balls for a weighing on the results of a previous weighing. The solution is a description of the process of weighing that you would go about to find the odd ball and whether it's heavier or lighter than the rest.

Okay, I think I've got this.

Show contentSpoiler:

Divide the balls into 3 equal groups (A, B, C). 

Weigh A against B. 
     If they are equal, then weigh 2 balls from A against 2 balls from C. 
          If they are equal then weigh the remaining C ball against one of the A balls and determine if it is heavy or light.
          If they are unequal (heavy or light), then split the 2 balls from C and weigh one against the other to find the corresponding heavy or light ball.
 
     If they are unequal, then weigh 2 balls from the heavier group, and 1 ball from the lighter group against the 3 balls from C.
          If they are equal, weigh the remaining ball from the heavier group and 1 of the remaining 2 balls from the lighter group against 2 balls from C. If they are equal, the last ball in the lighter group (the one not on the scale) is lighter than the rest. If they are heavier, then the ball on the scale from the heavier group is heavier than the rest. If they are lighter, then the ball on the scale from the lighter group is lighter than the rest.
          If C is heavier, then the ball on the scale from the lighter group is lighter than the rest. If C is lighter, then one of the 2 heavy balls on the scale is heavier than the rest. Weigh them against each other to tell which it is.

Linda

An old favourite puzzle. Some if not all of you are probably familiar with it already:

You are given 9 balls and a pair of balancing scales. All of the balls are of equal weight except for one of them, but you are not told which one this is, nor whether it is heavier or lighter than the rest. Your task is to discover which ball is a different weight and whether it is heavier or lighter. You may use the scales three times to weigh any combination of balls against any other combination. You may of course base your choice of balls for a weighing on the results of a previous weighing. The solution is a description of the process of weighing that you would go about to find the odd ball and whether it's heavier or lighter than the rest.

I'm afraid that one was beyond me. I had to look the answer up.

The pirate game:

Five pirates, in order of seniority (A, B, C, D, E) find 100 gold coins and must figure out how to split them up. The most senior pirate (A) makes a proposal which the pirates vote on. If the proposal is accepted by the majority, fine. But if it isn't, the senior pirate is thrown overboard into shark-infested waters to die. Then the next most senior pirate (B) makes a proposal which is voted upon. Now that there are only 4 pirates, a tie is possible, in which case the vote of the most senior pirate (who is also the one making the proposal) stands. However, if there isn't a tie and the proposal isn't accepted, then this most senior pirate is also thrown overboard. And on it goes until there is potentially only one pirate remaining (E), who takes all the loot.

These are the conditions upon which the votes are based:
Each pirate is rational and can follow the game through to its logical conclusion.
Each pirate wants to survive.
Each pirate wants to get as much money as possible.
Each pirate is bloodthirsty, and all else being equal, would like to see a more senior pirate thrown overboard.
No pirate trusts another pirate enough to make a private deal with them.

How should the first, most senior pirate propose to split up the gold coins?

I arrived at this thread late, after the 'sisters' problem had already been discussed at length.

Rather than read all the relies, I set about writing a program to generate a set of families of a given size (example five siblings) and supplied the values using a pseudo-random number generator. This isn't strictly necessary, but it avoids the necessity to analyse the data by hand.

By the time I'd written the following two functions:

Code:

int Family::boySisters() const
{
    return ngirls * nboys;
}

int Family::girlSisters() const
{
    return ngirls * (ngirls - 1);
}

an imbalance was clearly evident.

I then ran the program for 10 million families. For each run I chose the number of siblings at the start - anything from one child to 98 children (an arbitrary selection).

The results echoed Linda's.

(This doesn't mean my program is correct. To be thorough I'd still need to produce a set of expected results by hand, as well as have the code thoroughly reviewed for errors).

For each run I chose the number of siblings at the start - anything from one child to 98 children (an arbitrary selection).

Yikes. That poor woman!

Linda

Yikes. That poor woman!

Linda

Quite.

Still, for problems in general, looking at larger numbers may reveal a pattern not apparent in smaller numbers.

[Laird]

Okay, I think I've got this.

Nice!

My own solution which I have reconstructed from rough memory from years back:

Show contentSpoiler:

Labelling the 9 balls from A to I.

Step 1 (first weighing). ABC vs DEF
Result 1a. The scales balance. The odd ball out is one of GHI => goto 2.
Result 1b. The scales are unbalanced => goto 4.

Step 2 (second weighing, from 1a). G vs H.
Result 2a. The scales balance. I is the odd ball out. Weigh it against any other to determine whether it is heavier or lighter.
Result 2b. The scales are unbalanced => goto 3.

Step 3 (third weighing, from 2b). G vs A.
Result 3a. The scales balance. H is the odd ball out and we know whether heavier or lighter from the direction of the scales at step 2.
Result 3b. The scales are unbalanced. G is the odd ball out and we know whether heavier or lighter from the direction of the scales at this step.

Step 4 (second weighing, from 1b). ADG vs BEI.
Result 4a. The scales balance. The odd ball out is C or F => goto 5.
Result 4b. The scales are unbalanced in the same direction as step 1. The odd ball out is A or E => goto 6.
Result 4c. The scales are unbalanced in the opposite direction as step 1. The odd ball out is either B or D => goto 7.

Step 5 (third weighing, from 4a). F vs A.
Result 5a. The scales are balanced. The odd ball out is C, and we know whether heavier or lighter from the direction of the scales at step 1.
Result 5b. The scales are unbalanced. The odd ball out is F, and we know whether heavier or lighter from the direction of the scales at this step and step 1.

Step 6 (third weighing, from 4b). A vs B.
Result 6a. The scales balance. E is the odd ball out and we know whether heavier or lighter from the direction of the scales at steps 1 and 2.
Result 6b. The scales are unbalanced. A is the odd ball out and we know whether heavier or lighter from the direction of the scales at all steps (1, 4, and 6).

Step 7 (third weighing, from 4c). B vs A.
Result 7a. The scales balance. D is the odd ball out and we know whether heavier or lighter from the direction of the scales at steps 1 and 4.
Result 7b. The scales are unbalanced. B is the odd ball out and we know whether heavier or lighter from the direction of the scales at all steps (1, 4, and 7).

My friend's solution - unconditional weighings! So simple!

Show contentSpoiler:

ABC vs DEF
ABC vs GHI
ADG vs BFH

The outcomes are as follows, where, e.g., "Bh" means "Ball B is the odd one out, and heavier", and "1<" means, "The scales on the 1st weighing tip to the left":

Ah: 1< 2< 3<
Bh: 1< 2< 3>
Ch: 1< 2< 3=
Dh: 1> 2= 3<
Eh: 1> 2= 3=
Fh: 1> 2= 3>
Gh: 1= 2> 3<
Hh: 1= 2> 3>
Ih: 1= 2> 3=

Al: 1> 2> 3>
Bl: 1> 2> 3<
Cl: 1> 2> 3=
Dl: 1< 2= 3>
El: 1< 2= 3=
Fl: 1< 2= 3<
Gl: 1= 2< 3>
Hl: 1= 2< 3<
Gl: 1= 2< 3=

Other solutions are probably possible.

Here's another from the Skeptical Intelligencer:

‘You know’, said the historian, ‘it never ceases to amaze me that of the first five presidents of the USA, three died on the fourth of July’. ‘Really?’ exclaimed both the psychologist and the mathematician. ‘Yes’, the historian continued, ‘and what are the odds of your correctly guessing which three they are?’ After a short pause the psychologist answered, ‘One in six’. ‘Hang on’, said the mathematician as he jotted down his calculations on a scrap of paper. ‘It’s actually one in ten’. Who is right?

[Laird]

The pirate game:

Five pirates, in order of seniority (A, B, C, D, E) find 100 gold coins and must figure out how to split them up. The most senior pirate (A) makes a proposal which the pirates vote on. If the proposal is accepted by the majority, fine. But if it isn't, the senior pirate is thrown overboard into shark-infested waters to die. Then the next most senior pirate (B) makes a proposal which is voted upon. Now that there are only 4 pirates, a tie is possible, in which case the vote of the most senior pirate (who is also the one making the proposal) stands. However, if there isn't a tie and the proposal isn't accepted, then this most senior pirate is also thrown overboard. And on it goes until there is potentially only one pirate remaining (E), who takes all the loot.

These are the conditions upon which the votes are based:
Each pirate is rational and can follow the game through to its logical conclusion.
Each pirate wants to survive.
Each pirate wants to get as much money as possible.
Each pirate is bloodthirsty, and all else being equal, would like to see a more senior pirate thrown overboard.
No pirate trusts another pirate enough to make a private deal with them.

How should the first, most senior pirate propose to split up the gold coins?

My solution:

Show contentSpoiler:

A: 98 coins.
B:  0 coins.
C: 1 coin.
D: 0 coins.
E:  1 coin.

My reasoning:

I worked backwards from the point at which it gets down to D and E with D most senior pirate. Since D's vote breaks the tie, she can win no matter what, so she will split the coins 100-0 in her favour, and E gets nothing.

Therefore, at the next highest level (where C is most senior), E will vote for anything that gives him at least one coin. So, if C gives E one coin, he can count on E's vote, and thus has two votes (his own and E's), and D's vote is irrelevant, so he (C) does not need to give D anything. So, if it comes down to CDE, then C can split the coins 99-0-1 and win the proposal.

At the next highest level (where B is most senior), B's vote breaks any tie, so she needs only one vote other than her own. She can best gain that by giving D one coin, since D will get nothing at the next proposal if this one fails to pass. Then, since C's and E's votes are irrelevant, she doesn't need to give them anything. So, if it comes down to BCDE, then B can split the coins 99-0-1-0 and win the proposal.

At the highest level (where A is most senior), he (A) needs two votes other than his own. Since if this proposal fails, C and E get nothing at the next proposal, then the cheapest way to get the two necessary votes is to offer C and E a single coin each. He can then give himself the remainder (98 coins) and deny B and D (whose votes are irrelevant) any coinage.