The King's New Accountant

Question

The king of Ebonchester has just returned from his recent conquests of Baronshire and with him he brought four cart loads of plunder. However Baronshire is known for its lacklustre fiscal regulation, so the king would like to test the authenticity of every coin. The problem is his old accountant died at his side in battle (a good king never goes anywhere without his accountant). Thus he wants to recruit the most meticulous counters in the land.

Having placed posters on every street corner offering the handsomely paid job he was soon inundated with applications. Each applicant had to prove their worth by determining the forged coin from a stack of 12 (which could either by lighter or heavier) in just 3 weighings.

Ah!

Since the great infrastructure drive of a few years prior everyon in the kingdom has internet access, and it turns out that everyone and their mother had rushed to Stack Exchange in preparation for their interview and every single one of them knew the answer.

So the king went back to the drawing board and devised three new and more fiendish tests:

General Rules
- There are 12 coins, of equal size and shape, and exactly 1 is slightly lighter or heavier
- There is a scale available that can tell you whether one side is heavier than another when coins are weighed against each other
- Each weighing may consist as many or as few coins on either side as possible
- The coins can not otherwise be determined apart
- The coins are labelled 1-12
- Any relabelling is done without you knowing which coins have had the label change

Test 1
In the first test once the scale has fallen to the left or right during a weighing, it must fall the same way, or balance equally, in all future weighings.

Test 2
After each weighing the number of the counterfeit coin is swapped with:
- The coin labelled one higher than its current number if it is lighter than the other coins
- The coin labelled one lower than its current number if it is heavier than the other coins
If the coin is light and numbered 12 it would swap with 1 and if it is 1 and heavy it would swap with 12. That is the number on a light coin increases by 1 each weighing (mod 12) and decreases on a heavy coin by 1 each weighing (mod 12)

Test 3
As per test 2 but now a coin increases or decreases (mod 12), when light or heavy respectively, by the current number on the coin itself. For example if coin 7 was light, after the next weighing it would have its label switched with coin 2, and if it were heavy it would switch with 12.

Question: What is the minimum number of weighings required (if possible) to be certain of which coin is the counterfeit and whether it is light or heavy in each case?

Disclaimer: These are original variations, and while I have solutions of my own, I am not certain they are optimal for tests 2 or 3

Answer 1

Here's the solution to part 3:

The relabelings double the number of a light coin, and set the number of a heavy coin to 12. In particular, because 12 is divisible by 4, the odd coin must have an even number after one weighing and must be divisible by 4 after two.

Therefore, after two weighings, there are only four possible situations due to relabeling: either 4 is light, 8 is light, 12 is light, or 12 is heavy. Distinguishing them in one weighing is not possible, but we can do it with two weighings.

First weighing: 1,4,7,10 against 2,5,8,11. Second weighing: 3,9 against 6,12.

If the first weighing balances, then the odd coin is now labeled either 6 or 12. If these two together are lighter than 3 and 9 (which must be two regular coins after relabeling), the odd coin is lighter, otherwise it is heavier. After the second weighing, the odd coin is labeled 12 and we are done.

If the first weighing does not balance, suppose 1,4,7,10 was lighter. Then either the odd coin was light and is now labeled 2 or 8, or the odd coin was heavy and is now labeled 12. If the second weighing balances, the odd coin is light. After the second weighing, it is now labeled 4. Otherwise, the odd coin is heavy and is labeled 12.

The case where 2,5,8,11 is lighter is similar: if the second weighing balances, the odd coin is light and is now labeled 8; otherwise, it is heavy and labeled 12.

Answer 2

Test 1

This solution doesn't require case analysis. Make the following weighings:

5,8,11,12 vs 6,7,9,10
1,2,11,12 vs 3,4,9,10
8,11,12 vs 3,4,7
2,8,12 vs 4,6,10

Based on when the scale tips, you should be able to determine which is the fake. This is optimal because, as Mike said before me,

You can't distinguish 24 possibilities of (forged coin, heavier or lighter) with only 15 possible weighing results.

Test 2

There's a high possibility I messed up somewhere, but if I didn't, make the following weighings:

1,3,10,12 vs 2,4,9,11
4,9,10,12 vs 1,5,8,11
2,3,5,7,9 vs 1,4,6,8,10

Then look at the table (L means left pan is lighter) to determine which coin was originally fake:

Fake   Light   Heavy

 1      L0L     RR0
 2      R0R     LL0
 3      LLL     R0L
 4      RRR     L0R
 
 5      00L     0RR
 6      00R     0LL
 7      0RL     00R
 8      0LR     00L 

 9      RL0     LLR
 10     LR0     RRL
 11     RLR     LRR
 12     LRL     RLL

If you know which coin was originally fake, you can also determine its current label if required.

This solution is optimal because

again, you can't distinguish the 24 possibilities with only 2 weighings, as those can only give 9 distinct results.

Test 3

The following weighings work (taken from f''s answer):

1,4,7,10 vs 2,5,8,11
3,9 vs 6,12

Read his answer to know why this works.

Answer 3

This is a partial answer.
For Test 1, the minimum number of weighings is

4.

Here is a procedure which succeeds in that many weighings. Start by weighing

1,2,3 vs 4,5,6

The result is either Right Heavy, Left Heavy, or Balanced.

1. Right heavy: 1,2 vs 4,7. [We now know 7 is genuine]
   • Right heavy: There are three possibilities now. Either 1 is light, 2 is light, or 4 is heavy. Weigh 1 against 7, then 2 against 7 to find out which, being careful to put 7 on the right.
   • Balance: There are three possibilities now. Either 3 is light, 5 is heavy or 6 is heavy. Weigh 7 against 5, then 7 against 6, to find out which, being careful to put 7 on the left.
2. Left heavy: this is symmetric to the right heavy case.
3. Balance: 7,8 vs 9,10. [We now know 1 and 2 are genuine]
   • Right heavy: 7,8 vs 1,2.
     • If the scale tips right, then one of 7 or 8 is light. Weigh 7 vs 1 to check which.
     • If the scale balances, then one of 9 or 10 is heavy. Weigh 1 vs 9 to check which.
   • Left Heavy: this is symmetric to the right heavy case.
   • Balance: The counterfeit coin is either 11 or 12. Weight 1 vs 11, then 1 vs 12 to find out.

Here's why this many weighings are necessary. After three weighings, there are only 15 possible results. To see this: every result looks like UUU, UUB, UBU, UBB, BUU, BUB, BBU, or BBB, where B = balanced, U = unbalanced. For the first seven of these, U can be either Left or Right, leading to $2\times 7+1=15$ possible results. Since there are 24 > 15 possibilities to distinguish between, three weighings is insufficient.