All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 6 coins (Posted on 2016-01-13)
There are 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The labels are supposed to display the weights of the coins.

How can you determine whether all the labels are correct,
using the balance scale only twice?

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer attempt | Comment 4 of 10 |
First off, we recognize that any weighing result that differs from what would be expected based on true markings would be enough to declare there's a mislabeling somewhere, and so if this were the first weighing, the second need not take place.

That being the case, determination of what to weigh in the second weighing can't be determined by the result of the first, as the second weighing doesn't take place if the expected result of the first weighing does not happen.

Next, determine what ways there are for a given pan to weigh a given amount. The total pan weight is shown on the left below, with the right hand column showing ways of getting that pan total, with each digit representing a coin assuming proper label:

1  1

2  2

3  3
3  12

4  4
4  13

5  5
5  23
5  14

6  6
6  24
6  15
6  123

7  34
7  25
7  16
7  124

8  35
8  26
8  134
8  125

9  45
9  36
9  234
9  135
9  126

10  46
10  235
10  145
10  136
10  1234

11  56
11  245
11  236
11  146
11  1235

12  345
12  246
12  156
12  1245
12  1236

13  346
13  256
13  1345
13  1246

14  356
14  2345
14  1346
14  1256

15  456
15  2346
15  1356
15  12345

16  2356
16  1456
16  12346

17  2456
17  12356

18  3456
18  12456

19  13456

20  23456

21  123456

Then I made the assumption that the expected weighings should be expected to result in equalities, as inequalities would lead to too much ambiguity as to how given results were achieved.

The program looked through all possible pairs of expected-equality weighings, to see one where only one permutation (123456) of the weights, out of the 6!=720, of the labels in order would satisfy both equalities. However, none of the ways of selecting the pair of weighings satisfied this. At a minimum, 2 of the permutations fit, as summarized below.

The way to understand the entries below is exemplified by the first one:

2 3 12 46 235
123456
123654

The first line states that there are 2 permutations of the weights with the respective labels that would satisfy the sets of weighings where the first weighing was 3 vs 1 and 2, and the second weighting was 4 and 6 vs 2, 3 and 5.

The next line shows that, of course, if the labels are correct, then you'd get equality in both weighing.  But the next line after that shows the other permutation that would have the same two results: the 4 and the 6 weights have their labels interchanged.

The remaining sets are interpreted similarly.

2 3 12 46 235
123456
123654

2 5 14 6 123
123456
132456

2 23 14 6 123
123456
132456

2 5 23 26 134
123456
423156

2 5 14 46 235
123456
132456

2 6 123 26 134
123456
321456

2 6 123 46 235
123456
132456

2 26 134 45 126
123456
163452

I then thought perhaps my thinking that there always must be equality in the expected results.  Allowing expected inequality would make exhaustive analysis more difficult, so I haven't done it, but starting with an obvious one, 1, 2, 3 and 4 vs 5 and 6, would cover a lot of territory as that would be the only case where two coins would be expected to be heavier than four.  But what would you do next if the set passes this test? The 5 and 6 labels could be interchanged, or there could be a mixup within the 1, 2, 3, 4 set.  Trying to mix these, such as making the second weighing 5 vs 2 and 3 or 6 vs 1, 2 and 3 would still allow, in the case of passing via equality, mismatches within or outside the sets of lower expected weights involved.

Even if the second weighing were to expect inequality, such as 6 vs 4 and 1, and it passed, that would still leave open the possibility that 2 and 3 had their labels interchanged.

DefDbl A-Z
Dim crlf\$, combs(21, 10) As String, ncombs(21), how\$(720)

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

For n1 = 0 To 1
For n2 = 0 To 1
For n3 = 0 To 1
For n4 = 0 To 1
For n5 = 0 To 1
For n6 = 0 To 1
tot = n1 + 2 * n2 + 3 * n3 + 4 * n4 + 5 * n5 + 6 * n6
cm\$ = ""
If n1 Then cm = cm + "1"
If n2 Then cm = cm + "2"
If n3 Then cm = cm + "3"
If n4 Then cm = cm + "4"
If n5 Then cm = cm + "5"
If n6 Then cm = cm + "6"
ncombs(tot) = ncombs(tot) + 1
combs(tot, ncombs(tot)) = cm
Next
Next
Next
Next
Next
Next

For tot = 1 To 21
For i = 1 To ncombs(tot)
Text1.Text = Text1.Text & mform(tot, "##0") & "  " & combs(tot, i) & crlf
Next
Text1.Text = Text1.Text & crlf
Next

minways = 9999

For t1 = 3 To 15
For t2 = t1 To 15
For w11 = 1 To ncombs(t1) - 1
For w12 = w11 + 1 To ncombs(t1)
lhs1\$ = combs(t1, w11)
rhs1\$ = combs(t1, w12)
If nodup(lhs1, rhs1) Then

For w21 = 1 To ncombs(t2) - 1
For w22 = w21 + 1 To ncombs(t2)
lhs2\$ = combs(t2, w21)
rhs2\$ = combs(t2, w22)
If nodup(lhs2, rhs2) Then
If ways(lhs1, rhs1, lhs2, rhs2) <= minways Then
minways = ways(lhs1, rhs1, lhs2, rhs2)
Text1.Text = Text1.Text & minways & " " & lhs1 & " " & rhs1 & " " & lhs2 & " " & rhs2 & crlf
If minways < 10 Then
For j = 1 To minways
Text1.Text = Text1.Text & how(j) & crlf
Next
Text1.Text = Text1.Text & crlf
End If
End If
If ways(lhs1, rhs1, lhs2, rhs2) = 1 Then
Text1.Text = Text1.Text & lhs1 & " " & rhs1 & " " & lhs2 & " " & rhs2 & crlf

End If
End If
Next
Next

End If
Next
Next
Next
Next

Text1.Text = Text1.Text & crlf & minways & " done"

End Sub

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

Function nodup(a\$, b\$)
good = 1
For i = 1 To Len(b\$)
If InStr(a\$, Mid(b\$, i, 1)) Then good = 0: Exit For
Next
nodup = good
End Function

Function ways(a\$, b\$, c\$, d\$)
w = 0
coins\$ = "123456": h\$ = coins
Do
DoEvents
lhst1 = 0
For i = 1 To Len(a)
lhst1 = lhst1 + Val(Mid(coins, Val(Mid(a, i, 1)), 1))
Next
rhst1 = 0
For i = 1 To Len(b)
rhst1 = rhst1 + Val(Mid(coins, Val(Mid(b, i, 1)), 1))
Next
lhst2 = 0
For i = 1 To Len(c)
lhst2 = lhst2 + Val(Mid(coins, Val(Mid(c, i, 1)), 1))
Next
rhst2 = 0
For i = 1 To Len(d)
rhst2 = rhst2 + Val(Mid(coins, Val(Mid(d, i, 1)), 1))
Next
If lhst1 = rhst1 And lhst2 = rhst2 Then
w = w + 1
how\$(w) = coins\$
End If
permute coins
Loop Until coins = h
ways = w
End Function

 Posted by Charlie on 2016-01-13 13:42:02

 Search: Search body:
Forums (0)