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)
Private Sub Form_Load()
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 |
computer attempt
