2
$\begingroup$

Two perfect logicians (A and B) each have a bag of gold coins. A has more coins than B and each bag contains an amount of coins which is some multiple of 6. All coins are identical in appearance and mass. Their task is to split their combined coins equally between 2 crates (1 and 2) which initially have the same mass. They take turns to add coins to the crates - distributing 3 coins between the crates on each turn. Before each and every turn they are allowed to know which crate is heavier or if both crates have the same mass. A takes the first turn. As soon as B has 3 coins remaining he must leave them between the 2 crates for A to use. A and B cannot contact each other or communicate in any way - either before or during the task.

Both A and B know all the above information and they are told whether they are A or B.

How do A and B complete the task?

$\endgroup$
  • $\begingroup$ When does the game end? $\endgroup$ – Bridgeburners Jan 2 at 20:07
1
$\begingroup$

Let's start by assuming, from player A's point of view, that player B will always place more coins in the lighter box than the heavier one. Later I will show that this assumption is not necessary.

A can always make sure she gives player B either an excess of 3 coins, or an excess of 1 coin in the first box. In both cases, B will either place 0,3, or 1,2. However, A will know what the disparity is in each case.

If A leaves B with 3 excess coins in box 1, B will respond by either placing 0,3, or 1,2. If B does 0,3, the boxes will be even. If he does 1,2, then box 1 will have an excess of 2 coins. Thus, if A sees box 1 heavier in response, she'll know that its excess is 2 coins.

If A leaves B with 1 excess coin in box 1, B will either do 0,3, or 1,2. If he does 0,3, that leaves box 2 with 2 excess coins. If he does 1,2, that leaves them even. Thus A knows that after B's play the boxes will either be even, or have 2 excess coins in box 2.

If A sees even boxes, she can drop 3,0 and leave B with 3 excess in box 1. If A sees box 1 with 2 excess coins, she can drop 1,2, and leave box 1 with one excess coin. If she sees box 2 with 2 excess coins, she can drop 3,0 and leave box 1 with one excess coin.

To summarize the above, if player A leaves player B with 3 or 1 excess coins in box 1, she will only ever see either even boxes, or a disparity of 2. If she sees even boxes or a disparity of 2 in either box, she can always leave box 1 with an excess of 3 or 1 coins. Because she can start the game by leaving B with a 1 or 3 excess, she can always keep track of how big the disparity is, regardless of what B plays.

When player B is on his last 3 coins, A is either leaving him with 1 or 3 excess coins in box 1. Since she's keeping track, when she sees that he left her his last coins between the crates, she'll know how to distribute them to even them out.

Now, the entire above answer assumes that player B will always put more coins in the lighter box than the heavier one, even if he chooses, at random, whether to play 0,3 or 1,2. But suppose, instead, that he just distributes it however he wants, even possibly placing more coins in the heavier box. Then it's easy to show that player A has no way of tracking the coin disparity. You can show this by showing that, for any given disparity that A leaves for B, there are multiple ways for B to create a disparity in either box. However, if he always places more coins in the lighter box, then as I showed above, there exists a strategy for A to keep track of the disparity. (There may be other strategies, but all I had to show is that there exists at least one, and that no strategy exists if he doesn't follow this rule.) Thus, as a perfect logician, player B knows that he must always place more coins in the lighter box for player A to possibly keep track of the disparity. Since player A is a perfect logician, she also knows that he must do this for her to keep track of the coin count. Also, since she knows that he's a perfect logician, she knows that he knows that this is the only thing he can do to win, and thus she knows he will do it. And because he knows that she's a perfect logician, he knows that she will use a strategy to keep track of the coins as long as he does this, and he knows that she knows he will do this based on the above logic. Thus they both know they will win, without having to make any assumption about what the other will do.

$\endgroup$
  • $\begingroup$ To insert a paragraph break in a spoiler block, add a line between your paragraphs with ">!<space><space>". To add a blank line between paragraphs, add two lines like that :) $\endgroup$ – hdsdv Jan 2 at 21:53
  • $\begingroup$ Very thorough solution Bridgeburner. Congrats. $\endgroup$ – ThoughtBox Jan 2 at 23:02
  • $\begingroup$ Only last thing to prove is that after B's final move, A can always finish the task. $\endgroup$ – ThoughtBox Jan 2 at 23:12
8
$\begingroup$

Here is a new approach. The old solution was not perfect.

Logician A can force the crates to balance.

As long as B has coins, A puts 3 coins in the lightest crate. Except if the crates balance, then A puts 2 coins in one crate and 1 in the other. This guarantees that after A's turns the imbalance is always of 1 coin. If B tries to increase the imbalance by adding to the heavier crate, then A will add 3 coins to the other crate and get the imbalance back to 1.

When B runs out of coins and offers his last 3 coins to A, the imbalance can be up to 4. At that point A must play his 3 coins and B's 3 coins. In the next turn A adds 3 coins to the lighter crate as before. This reduces the imbalance to 1. Then A adds 2 coins to the lighter crate and 1 to the heavier one. This balances the crates.

A still has extra coins left, a multiple of 6. A distributes these coins evenly between the 2 crates, 3 coins in each crate every 2 turns. This keeps the crates balanced.

So A can guarantee the crates balance without relying on B or even wondering what B is trying to do.

$\endgroup$
  • $\begingroup$ Remember that there is no criteria saying that A and B must both do the same thing. Does this affect things at all? As a side point, the problem can be logically solved. $\endgroup$ – ThoughtBox Jan 1 at 22:06
  • $\begingroup$ No. A and B can make different choices regarding what strategy they follow. I clarified the solution. $\endgroup$ – Florian F Jan 1 at 22:10
  • $\begingroup$ Your two behaviors are: 1) Both put more into the lighter crate 2) distribute 6 coins equally every two turns. Can A and B trust the other person do follow behavior 2) when behavior 1) appears to work? $\endgroup$ – ThoughtBox Jan 1 at 22:20
  • $\begingroup$ A and B can't know for sure what the other will do. And they don't need to. If B follows just one of these behaviors, and A trusts he does, then A can make it work. $\endgroup$ – Florian F Jan 1 at 23:08
  • $\begingroup$ "A and B can't know for sure what the other will do". This is incorrect. They both realize there is a strategy which always works and that it is the only working strategy. "And they don't need to". This is incorrect. They do need a strategy for the task and not knowing the other persons move will cause them to fail. $\endgroup$ – ThoughtBox Jan 1 at 23:34
4
$\begingroup$

On each turn, each of A and B check to see which crate is heavier, and thus which is lighter. If one is lighter, put 3 coins in it. If they are both the same, pick one and put 3 coins in it.

When B is down to three coins left, they are left between the crates. This will happen before A runs out of coins.

So the final steps are up to A to carry out.
A will use the 3 coins left by B in the same way as A's own coins. Following exactly the same method as before, ensuring both crates have equal coins is simple.

The only possible objection here is that A and B don't communicate in advance. But it wouldn't be particularly logical to follow a radically different strategy here; unless one or both of them are, quite illogically, acting pathologically against the objective, it really only takes one of the two of them to follow this strategy for it to succeed. And indeed, at the end, A really must do this anyway (since B runs out of coins early), so to accomplish the objective, this ultimately needs to be A's strategy.

No matter what B does, A can always counter it by adding their coins to the lighter crate, especially since B must cede their last 3 coins to A - which ensures no matter what B's strategy is, A can always counterbalance it and keep the crates within 3 coins of each other. So really, only A needs to be following this strategy anyway.

As for being able to pick different numbers of coins to put in each crate, perfect logicians should understand that, with coin numbers evenly divisible by 6, the simplest course of action is to always put 3 coins in one crate, so I argue this is what they'd do in any case.

However, A will know on their second turn if B is not using the same strategy because if B is, the crates will be evenly weighted at the start of A's second turn. If B is not doing the same strategy then

B must be putting 1 coin in one crate and 2 in the other. It wouldn't be reasonable for B to put 2 into the heavier crate, increasing the imbalance between the crates, so A can assume B has put 1 in the heavier crate and 2 in the lighter, as B perhaps wasn't sure if maybe A was doing this same split. In this case, A can still ... do the exact same strategy, add 3 coins to the lighter crate. This leaves, after A's second turn, 3+1 in one crate and 2+3 in the other. B will then go again and follow B's strategy, bringing the totals to 3+1+2 and 2+3+1, and now they're even again. A also now knows which strategy B is following and can thus counterbalance it at the end of the process if needed.

$\endgroup$
  • 1
    $\begingroup$ Yes, your strategy of doing 3 0 then 0 3 is valid. But doing 2 1 then 1 2 is just as valid and cannot be ruled out by either A or B. Therefore, since there are two working strategies how can each player know which of the two strategies the other will follow? $\endgroup$ – ThoughtBox Jan 1 at 20:43
  • 1
    $\begingroup$ Oh. I actually understood the problem statement to be that they must add three coins to one crate, not that they can distribute them between crates as they see fit. @ThoughtBox perhaps you may want to make that more explicit. $\endgroup$ – Rubio Jan 1 at 20:46
  • $\begingroup$ B doesn't need to know what A is doing. A needs to know what B is doing, as A is the one who has to make the last choices of where to put coins at the end. I've addressed this now. $\endgroup$ – Rubio Jan 1 at 21:09
  • 1
    $\begingroup$ Ooh ooh, I know the answer to the last question: it's "not what a perfect logician would do, as it denies A the ability to learn how B is playing to ensure A can get the crates equal at the end". A will logically assume that B doesn't add coins to the heavier crate. That's reason enough. +1 from me. $\endgroup$ – CG. Jan 1 at 21:44
  • 1
    $\begingroup$ Yeah I already noted that in my answer. Perfect logicians won't use a strategy that is going to deny the other the ability to achieve the objective, unless they're playing the game pathologically. So they won't use a random strategy, and they won't take an action that increases the imbalance between crates needlessly. As it turns out, even if two-in-the-heavier-crate is B's strategy, A can learn that and counter it in the end. However, I don't want to expand this answer by covering every possible action B might do, sane or not, as for the stated "perfect logicians", many make zero sense. $\endgroup$ – Rubio Jan 1 at 21:49
3
$\begingroup$

A and B have two logical choices.

1. Place all three coins in the lightest crate (or always number 1 if they're equal).
2. Place two coins in the lightest crate (or always number 1 if they're equal), and one in the heaviest.
Note that it's only A that will encounter equal weighing crates, so A can always choose the same one (not that it matters).

Let's say A choose strategy 1. Then, when it's A's turn again, either the crates will be the same weight, in which case A and B chose the same strategy. If they're not the same weight, that means the B chose strategy 2.

If that happens, then

Crate 1 will contain 4 coins, and crate 2 will contain 2 coins. A will then place 1 coin in crate 1 and 2 coins in crate 2. That way, there will be 5 coins in crate 1 and 4 in crate 2.

A will now change their approach to strategy 2.

The crates will now always be equal after B's turn.

After that it's straight forward. A will know if crate 1 is one or three coins heavier than crate 2 when B is finished.

All B does is to choose one of the strategies and stick with it. A will adapt their strategy accordingly.

$\endgroup$
1
$\begingroup$

A can balance the crates with the following strategy, with or without B's cooperation.

While the two are alternating turns, A should:
1. If the boxes are balanced, put 1 coin in one box, 2 coin in the other.
2. If The boxes are imbalanced, put 3 coins in the lighter box.

Once B runs out of coins, A can balance the crates with the addition of B's 3 coins:
1. If the crates are balanced, alternate putting 3 coins in each crate.
2. If the crates are imbalanced, A can put B's 3 coins in the lighter crate.

2.1 Then put 2 coins into the lighter box, 1 coin into the heavier box, and use the remaining coins to once again alternate.

Proof:

Claim: When A and B are alternating turns, A can guarantee the difference between the crates to always be 1 after A's move. After B's move, the difference between the crates will not exceed 4.

Base case: starting with 0 coins in each in each case, A will split the coins 2/1 in each crate, which satisfies the claim above. B has four moves after: 3/0, 0/3, 2/1, 1/2. Each then results in: 5/1, 2/4, 4/2, 3/3. In all 4 cases, the difference is at most 4 apart.

Induction: At the beginning of A's turn, the two crates are at most 4 apart. Because the total number of coins is even, the difference can only be 0, 2, or 4.

Case 0: Same as base case.

Case 2: The crates must have a coin distribution of (3n+2/3n+4) before A's turn because the sum of coins has to be a multiple of 6. A will put 3 in the lighter crate (3n+5/3n+4), which makes the crates only one apart.

Case 4: The crates must have a coin distribution of (3n+1/3n+5) before A's turn because the sum of coins has to be a multiple of 6. A will put 3 in the lighter crate (3n+4/3n+5), which makes the crate only one apart.

At the beginning of B's turn the crates is always 1 apart. After B's turn, the difference in coins between the crates will not exceed 4. Say the crates are at (n/n+1) when B starts:

Case (3/0): B puts 3 coins into the lighter box resulting in (n+3/n+1). The difference is 2, less than 4.

Case (0/3): B puts 3 coins into the heavier box resulting in (n/n+4), the difference is 4.

Case (1/2): B puts 1 into the lighter box, 2 into the heavier one resulting in (n+1/n+3), difference is 2.

Case (2/1) B puts 2 into the lighter box, 1 into the heavier one resulting in (n+2/n+2), which makes the crates balanced.

After B runs out of coins A will have 6m+3 coins, and gain another 3 coins from B. As shown above after B's turn, the two crates are at most 4 apart and the difference can only be even: 0, 2, or 4.

Balanced case: A can balance the crates by alternating putting 3 coins in each crate.

Imbalanced case: A can determine the difference between the two crates by putting the 3 coins from B into the lighter crate. The crates are either in (3n+1/3n+5) or (3n+2/3n+4) and become (3n+4/3n+5) or (3n+5/3n+4). Following this, the crates can be balanced by putting 2 coins into the lighter crate and 1 coin into the heavier crate resulting in (3n+6/3n+6). A now has 6m coins left, which can be distributed evenly by alternating coin deposits in the crates.

Note that m can be 0 for the boxes to be balanced. A can balance the crates by having at least as many coins as B.

$\endgroup$
0
$\begingroup$

Didn't look at any answers:

A puts 3 coins in crate 1 followed by B putting 3 coins in crate 2 (A can put 2 coins in crate 1 and 1 coin in crate 2 followed by B putting 2 coins in crate 2 then 1 coin in crate 1 if they must use both crates).
This is repeated until B puts his last 3 coins in between the crates.
A distributes these last 3 coins of B as B would've played them above.
Both crate now have equal amount of coins.
A then splits his coins into the two crates and we're done.

Or am I missing something?

$\endgroup$
  • $\begingroup$ This requires that A and B coordinate their strategies beforehand, which is not allowed. When B gets their first turn, they have no way of knowing if A did (3, 0) or (2, 1), so they have no way of knowing how to distribute their coins to achieve balance at the end of their turn. B cannot determine what A's move was, so they cannot mirror it. $\endgroup$ – Nuclear Wang Jan 2 at 22:08
  • $\begingroup$ @NuclearWang Thanks much it makes sense now. And I'll have to think about it a bit more too! :-) $\endgroup$ – Paul Evans Jan 2 at 22:27
  • $\begingroup$ Nicely explained Nuclear Wang. $\endgroup$ – ThoughtBox Jan 2 at 23:03

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.