## An Alternator Coin Puzzle

I run a program at MIT called PRIMES STEP, where we conduct mathematical research with children in grades 6 through 9. Our first research project was about a funny coin called an alternator. This coin exists only in a mathematician’s mind as it can change weight according to its own will. When you put the alternator on the scale, it can either weigh the same as a real coin or a fake coin (the fake coins are lighter than real ones). The coin strictly alternates how much it weighs each time it is put on the scale. My colleague, Konstantin Knop, recently sent me a fresh alternator puzzle.

Puzzle. There are four identical-looking coins: two real, one fake, and one alternator. How do you find the alternator using a balance scale at most three times?

Share:

1. #### Lazar Ilic:

First note that there are 24 possible starting positions and only 3 queries to differentiate between at most ~ 3^3 = 27 [~ due to potential convenient merging over alternating coin state switching criterion] so we will need to be somewhat careful. Let the coins be numbered #0, #1, #2, and #3 and weigh either 0 or 1 where a state of 2 represents an alternating coin with a weight of 0 if it is now placed on a scale and a state of 3 represents an alternating coin with a weight of 1 if it is now placed on a scale. Then we have the following algorithm for resolving the final state [often in its entirety rather than merely identifying the alternating coin] generated by manually manipulating an automatable Python code:

Weigh #0 with #1 against #2 with #3:
If #0 with #1 > #2 with #3:
Weigh #2 against #3:
If #2 > #3:
Weigh #0 against #1:
If #0 > #1:
Solved [[1, 3, 1, 0]]
Elif #0 == #1:
Solved [[1, 1, 2, 0]]
Else:
Solved [[3, 1, 1, 0]]
Elif #2 == #3:
Weigh #0 against #2:
If #0 > #2:
Solved [[1, 1, 0, 3]]
Else:
Solved [[1, 1, 2, 0]]
Else:
Weigh #0 against #1:
If #0 > #1:
Solved [[1, 3, 0, 1]]
Elif #0 == #1:
Solved [[1, 1, 0, 2]]
Else:
Solved [[3, 1, 0, 1]]
Elif #0 with #1 == #2 with #3:
Weigh #0 with #1 against #2 with #3:
If #0 with #1 > #2 with #3:
Weigh #0 against #1:
If #0 > #1:
Solved [[1, 3, 0, 1], [1, 3, 1, 0]]
Else:
Solved [[3, 1, 0, 1], [3, 1, 1, 0]]
Else:
Weigh #2 against #3:
If #2 > #3:
Solved [[0, 1, 1, 3], [1, 0, 1, 3]]
Else:
Solved [[0, 1, 3, 1], [1, 0, 3, 1]]
Else:
Weigh #0 against #1:
If #0 > #1:
Weigh #0 against #2:
If #0 > #2:
Solved [[1, 0, 3, 1]]
Elif #0 == #2:
Solved [[1, 0, 1, 2]]
Else:
Solved [[3, 0, 1, 1]]
Elif #0 == #1:
Weigh #0 against #1:
If #0 > #1:
Solved [[2, 0, 1, 1]]
Else:
Solved [[0, 2, 1, 1]]
Else:
Weigh #1 against #2:
If #1 > #2:
Solved [[0, 1, 3, 1]]
Elif #1 == #2:
Solved [[0, 1, 1, 2]]
Else:
Solved [[0, 3, 1, 1]]

———-

import copy
avv=[]
for a in range(0,4):
for b in range(0,4):
for c in range(2,4):
if a!=b:
av=[1 for d in range(4)]
av[a]=0
av[b]=c
avv.append(av)
avv=[[0, 2, 1, 1], [0, 1, 2, 1], [0, 1, 1, 2]]
for a in range(0,4):
for b in range(a+1,4):
bvv=[] # >
cvv=[] # =
dvv=[] # dude[0]%2+dude[1]%2+dude[2]%2+dude[3]%2:
dudec=copy.deepcopy(dude)
for d in range(4):
if dudec[d]>=2:
dudec[d]=5-dudec[d]
bvv.append(dudec)
elif 2*(dude[a]%2+dude[b]%2)==dude[0]%2+dude[1]%2+dude[2]%2+dude[3]%2:
dudec=copy.deepcopy(dude)
for d in range(4):
if dudec[d]>=2:
dudec[d]=5-dudec[d]
cvv.append(dudec)
else:
dudec=copy.deepcopy(dude)
for d in range(4):
if dudec[d]>=2:
dudec[d]=5-dudec[d]
dvv.append(dudec)
print(len(bvv),len(cvv),len(dvv))
if 1:
print(bvv) # [[2, 1, 0, 1], [1, 2, 0, 1], [1, 1, 0, 3], [1, 1, 0, 2], [2, 1, 1, 0], [1, 2, 1, 0], [1, 1, 3, 0], [1, 1, 2, 0]]
print(cvv) # [[0, 1, 3, 1], [0, 1, 1, 3], [1, 0, 3, 1], [1, 0, 1, 3], [3, 1, 0, 1], [1, 3, 0, 1], [3, 1, 1, 0], [1, 3, 1, 0]]
print(dvv) # [[0, 3, 1, 1], [0, 2, 1, 1], [0, 1, 2, 1], [0, 1, 1, 2], [3, 0, 1, 1], [2, 0, 1, 1], [1, 0, 2, 1], [1, 0, 1, 2]]
for a in range(0,4):
for b in range(a+1,4):
bvv=[] # >
cvv=[] # =
dvv=[] # dude[b]%2:
dudec=copy.deepcopy(dude)
if dudec[a]>=2:
dudec[a]=5-dudec[a]
elif dudec[b]>=2:
dudec[b]=5-dudec[b]
bvv.append(dudec)
elif dude[a]%2==dude[b]%2:
dudec=copy.deepcopy(dude)
if dudec[a]>=2:
dudec[a]=5-dudec[a]
elif dudec[b]>=2:
dudec[b]=5-dudec[b]
cvv.append(dudec)
else:
dudec=copy.deepcopy(dude)
if dudec[a]>=2:
dudec[a]=5-dudec[a]
elif dudec[b]>=2:
dudec[b]=5-dudec[b]
dvv.append(dudec)
#print(len(bvv),len(cvv),len(dvv))
print(a,b)
print(bvv) #
print(cvv) #
print(dvv) #
if len(bvv)<=3 and len(cvv)<=3 and len(dvv)<=3:
print(a,b)
print(bvv) # [[2, 1, 1, 0], [1, 2, 1, 0], [1, 1, 2, 0]]
print(cvv) # [[1, 1, 0, 3], [1, 1, 3, 0]]
print(dvv) # [[2, 1, 0, 1], [1, 2, 0, 1], [1, 1, 0, 2]]

2. #### Sanandan Swaminathan:

Interesting puzzle. Here is one way to determine the alternator coin and also whether it will be in heavy or light state the next time we decide to use it in the future. By backtracking, we also know the state the alternator was in before we started our weighings.

Let H = heavy (real) coin, L = light (fake) coin, Ah = alternator in heavy state, Al = alternator in light state. We don’t know whether the alternator is in Ah or Al state initially, and all coins look identical.

1st weighing: Put two coins in each pan. If the pans balance, the first weighing involved one of the following possibilities:
H, L versus H, Al
H, L versus Al, H
L, H versus H, Al
L, H versus Al, H
H, Al versus H, L
Al, H versus H, L
H, Al versus L, H
Al, H versus L, H

2nd weighing: If the pans BALANCED in the 1st weighing, simply repeat the 1st weighing (without moving any coins). The possibilities shown above for the 1st weighing would transform in the 2nd weighing to:
H, L versus H, Ah
H, L versus Ah, H
L, H versus H, Ah
L, H versus Ah, H
H, Ah versus H, L
Ah, H versus H, L
H, Ah versus L, H
Ah, H versus L, H

In the first 4 cases above, the right pan would be heavier. In the last 4 cases, the left pan would be heavier. The alternator is in the heavier pan, and it will weigh light if we use it again. For the 3rd weighing, compare the two coins in the 2nd weighing’s heavier pan against each other, for example H versus Al (which was Ah during the 2nd weighing) in the first case above. The alternator is the coin on the lighter pan in the 3rd weighing, and it will be in heavy state the next time we use it in the future.

On the other hand, consider the scenario where the 1st weighing showed an imbalance. WLOG, assume that the left pan was heavier. This means that the 1st weighing involved one of the following possibilities:
H, H versus L, Ah
H, H versus L, Al
H, H versus Ah, L
H, H versus Al, L
H, Ah versus H, L
H, Ah versus L, H
Ah, H versus H, L
Ah, H versus L, H

For the 2nd weighing, compare the two coins on the 1st weighing’s LIGHTER pan against each other, for example L versus Al (which was Ah in the 1st weighing) in the first case above. This 2nd weighing would have the following possibilities corresponding to the cases above:
L = Al
L L
H > L
L L
L < H

If the 2nd weighing shows equality, it must have involved L = Al or Al = L above. In this case, for the 3rd weighing, simply repeat the 2nd weighing. So, we would now be comparing L versus Ah, or Ah versus L. The heavier pan contains the alternator, and it will be in light state the next time we use it in the future.

If the 2nd weighing shows imbalance, then for the 3rd weighing, compare the coins that were on the HEAVIER pan in the 1st weighing against each other. If this 3rd weighing shows equality, it means that we’ve just weighed H against H. In this scenario, the alternator is the coin that was on the heavier pan in the 2nd weighing, and it will be in light state the next time we use it in the future. On the other hand, if the 3rd weighing shows imbalance, we have just compared H versus Al, or Al versus H (the Al was Ah on the heavier pan in the 1st weighing). The alternator is the coin on the lighter pan of the 3rd weighing, and it will be in heavy state the next time we use it in the future.

3. #### Sanandan Swaminathan:

Looks like one of my paragraphs above is malformed, possibly due to “less than” and “greater than” symbols. I’m pasting the paragraph below using words rather than symbols:

For the 2nd weighing, compare the two coins on the 1st weighing’s LIGHTER pan against each other, for example L versus Al (which was Ah in the 1st weighing) in the first case above. This 2nd weighing would have the following possibilities corresponding to the cases above:
L equals Al
L less than Ah
Al equals L
Ah greater than L
H greater than L
L less than H
H greater than L
L less than H

4. #### Sanandan Swaminathan:

Properly formatted this time (please ignore previous posting which was malformed due to the symbols used)…

Here is one way to determine the alternator coin and also whether it will be in heavy or light state the next time we decide to use it in the future. By backtracking, we also know the state the alternator was in before we started our weighings.

Let H = heavy (real) coin, L = light (fake) coin, Ah = alternator in heavy state, Al = alternator in light state. We don’t know whether the alternator is in Ah or Al state initially, and all coins look identical.

1st weighing: Put two coins in each pan. If the pans balance, the first weighing involved one of the following possibilities:
H, L versus H, Al
H, L versus Al, H
L, H versus H, Al
L, H versus Al, H
H, Al versus H, L
Al, H versus H, L
H, Al versus L, H
Al, H versus L, H

2nd weighing: If the pans BALANCED in the 1st weighing, simply repeat the 1st weighing (without moving any coins). The possibilities shown above for the 1st weighing would transform in the 2nd weighing to:
H, L versus H, Ah
H, L versus Ah, H
L, H versus H, Ah
L, H versus Ah, H
H, Ah versus H, L
Ah, H versus H, L
H, Ah versus L, H
Ah, H versus L, H

In the first 4 cases above, the right pan would be heavier. In the last 4 cases, the left pan would be heavier. The alternator is in the heavier pan, and it will weigh light if we use it again. For the 3rd weighing, compare the two coins in the 2nd weighing’s heavier pan against each other, for example H versus Al (which was Ah during the 2nd weighing) in the first case above. The alternator is the coin on the lighter pan in the 3rd weighing, and it will be in heavy state the next time we use it in the future.

On the other hand, consider the scenario where the 1st weighing showed an imbalance. WLOG, assume that the left pan was heavier. This means that the 1st weighing involved one of the following possibilities:
H, H versus L, Ah
H, H versus L, Al
H, H versus Ah, L
H, H versus Al, L
H, Ah versus H, L
H, Ah versus L, H
Ah, H versus H, L
Ah, H versus L, H

For the 2nd weighing, compare the two coins on the 1st weighing’s LIGHTER pan against each other, for example L versus Al (which was Ah in the 1st weighing) in the first case above. This 2nd weighing would have the following possibilities corresponding to the cases above:
L equals Al
L less than Ah
Al equals L
Ah greater than L
H greater than L
L less than H
H greater than L
L less than H

If the 2nd weighing shows equality, it must have involved “L equals Al” or “Al equals L” above. In this case, for the 3rd weighing, simply repeat the 2nd weighing. So, we would now be comparing L versus Ah, or Ah versus L. The heavier pan contains the alternator, and it will be in light state the next time we use it in the future.

If the 2nd weighing shows imbalance, then for the 3rd weighing, compare the coins that were on the HEAVIER pan in the 1st weighing against each other. If this 3rd weighing shows equality, it means that we’ve just weighed H against H. In this scenario, the alternator is the coin that was on the heavier pan in the 2nd weighing, and it will be in light state the next time we use it in the future. On the other hand, if the 3rd weighing shows imbalance, we have just compared H versus Al, or Al versus H (the Al was Ah on the heavier pan in the 1st weighing). The alternator is the coin on the lighter pan of the 3rd weighing, and it will be in heavy state the next time we use it in the future.