| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 7.1 | | GALLO::JMUNZER | | Tue Jul 22 1986 20:51 | 3 |
| Does anyone know of any progress on this problem?
John
|
| 7.2 | I doubt it. | MODEL::YARBROUGH | | Wed Jul 23 1986 13:16 | 22 |
| I don't think there is a solution. The reason is that you don't
gain enough information by weighing multiple coins. Look at the
simpler cases:
coins weighings
1 1
2 2 (both coins must be weighed, and you can't distinguish
between 2w1 and w1+w2)
3 3 (weighing one coin gives w1, but the 2nd w'ing still
cannot distinguish between 2w2 and w1+w2; even if
it were known to be w1+w2 another weighing would be
needed to tell which is w1.)
Notice that even at n=3 we are losing ground when weighing multiple
coins: not only can we not discriminate at one level, but EVEN IF
WE COULD there are additional cases to sort out. In general, weighing
N coins as a group implies N+1 possible outcomes, so there is no
gain in weighing many coins over a sequence of single weighings.
The addition of another coin multiplies the number of cases to be
discriminated, so there still is no more efficient method than weighing
each coin independently. Now if the number of w1's were limited,
or some other additional restriction made, we might have enough
leverage to do it in fewer weighings.
|
| 7.3 | More ammunition. | MODEL::YARBROUGH | | Wed Jul 23 1986 13:27 | 11 |
| Let me amplify that argument.
Suppose that we start by weighing individual coins, and we get lucky:
we are able to know w1 and w2 after two weighings. Using this
information, we start weighing groups of coins. However, each time
we weigh two or more coins it is possible that the two we weigh
are w1+w2, so we STILL have to make another weighing to distinguish
them. Even with larger groups of coins, any sort of an even mix
leaves us in the same state of ignorance. It is not difficult to
count the number of w1's and w2's, but knowing which is which still
is most efficiently done one coin at a time.
|
| 7.4 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Wed Jul 23 1986 14:31 | 8 |
| Re .3:
If we know x and y, we can determine the weights of at least four
coins in only three weighings: Weigh ABC, AD, and BD (where each
letter is a coin).
-- edp
|
| 7.5 | | MODEL::YARBROUGH | | Wed Jul 23 1986 14:48 | 2 |
| Right. Of course, it takes at least two weighings to determine x
and y in the problem as stated. That's five for four coins.
|
| 7.6 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Wed Jul 23 1986 16:25 | 13 |
| Re .5:
I wouldn't include the two coins I've used to determine x and y among
the four I determine later! That's six coins in five weighings.
Actually, the increase from two coins to four in two weighings to
three holds promise of larger increases with more weighings. And
perhaps only one weighing would be needed to determine x, with y
coming from observations of the other four weighings, or possibly
x and y could both come from combined weighings.
-- edp
|
| 7.7 | | CLT::GILBERT | It's a Dusey | Wed Jul 23 1986 17:11 | 34 |
| 7.8 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Thu Jul 24 1986 17:21 | 8 |
| A program reports there is no single way to determine the weights of
six weights using four weighings even if x and y are known. However,
this does not rule out a method that decides what to weigh next based
on previous results. Also, I need to check the program to be sure
there are no bugs.
-- edp
|
| 7.9 | | CLT::GILBERT | It's a Dusey | Thu Jul 24 1986 17:23 | 3 |
| re .8
Would this (no way to determine 6 in 4, given x and y) imply
that there's (no way to determine 7 in 5, not given x and y)?
|
| 7.10 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Thu Jul 24 1986 19:41 | 9 |
| Re .9:
Well, we jumped from 2 in 2 to 4 in 3, so maybe we could jump from 5 in
4 to 7 in 5. But don't count on it. That wouldn't leave us much room
to squeeze in a determination of x and y. I think we'd better look
for variable methods.
-- edp
|
| 7.11 | how about this approach? | CLT::GILBERT | It's a Dusey | Thu Jul 24 1986 21:20 | 18 |
| I was thinking of automating the approach in .7. That is, choose 5
plausible subsets (SS1 through SS5) to weigh, and generate the table:
A B C D E F G SS1 SS2 SS3 SS4 SS5
x x x x x x x 3x 2x 2x 4x 3x
x x x x x x y 3x x+y x+y 3x+y 3x
...
x y y y y y y x+2y x+y 2y x+3y 3y
Now whenever SS3 is linearly dependent on SS1 and SS2, we can divide
the 2^6 combinations into equivalence classes based on that dependence.
We can further subdivide them based on the linear dependence of SS4
on S1 and S2. And so on. I suspect that this approach will divide
the 2^6 combinations down to uniqueness, except for boundary cases,
which can probably be resolved by a little non-computerized thinking.
Which subsets to use (since 2^7 choose 5 is quite large)? Well, just
pick some (by hand) that look reasonable.
|
| 7.12 | 5 coins, 4 weighings | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Tue Dec 27 1988 21:22 | 40 |
| 7.13 | | KOBAL::GILBERT | Ownership Obligates | Wed Dec 28 1988 11:09 | 4 |
| 7.14 | | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Wed Dec 28 1988 11:59 | 67 |
| 7.15 | | 4GL::GILBERT | Ownership Obligates | Fri Dec 30 1988 19:39 | 58 |
| 7.16 | Gasp! | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Sat Dec 31 1988 10:42 | 39 |
| 7.17 | addendum | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Sat Dec 31 1988 10:47 | 8 |
| Oh, yes, one another thing. I've got all the 7*5 which contain
exactly one singleton, and which pass various other simple tests. If you
send me your s/w, Peter, I can use the last part to check for solutions.
So that means if we do decide to look for 7*5 exhaustively, we can
assume there are *no* singletons. A minor thing but it might help.
Andrew.
|
| 7.18 | | KOBAL::GILBERT | Ownership Obligates | Sat Dec 31 1988 18:25 | 12 |
| I sent the Pascal program (400 lines) to Andrew.
I tried 8 coins in 5 weighings, but with no success. I'm going to
start an exhaustive search.
At first, it appears that there are 2^(8*5) possible weighings, but
that's not quite true. Note that we can limit the first weighing to
one of eight possibilities (based on the number of coins weighed).
The number of combinations for the first *two* weighings can also be
reduced by various symmetries and constraints to just 29 possibilities.
This reduces the search space to at most 29*2^24 weighings.
|
| 7.19 | 27 solutions for (7 coins, 5 weighings) | KOBAL::GILBERT | Ownership Obligates | Sun Jan 01 1989 14:59 | 85 |
| There are 27 unique solutions to the (7 coins, 5 weighings) problem. These
are described below by their null spaces.
---------------------
5 -4 -3 -2 1 2 0
4 -4 -2 -2 2 0 2
---------------------
5 -4 -3 -2 2 0 1
4 -4 -2 -2 0 2 0
---------------------
5 -4 -3 1 0 2 1
4 -4 -2 2 2 0 0
---------------------
5 -4 -2 1 2 0 1
4 -4 -2 2 0 2 0
---------------------
5 -4 3 -2 -1 1 0
3 -2 2 -2 -1 0 1
---------------------
5 -4 3 -2 -2 0 -1
2 -2 1 -1 0 -1 0
---------------------
5 -4 -2 -2 -1 1 0
3 -2 -2 -1 -1 0 1
---------------------
5 -4 -2 -2 1 -1 0
2 -2 -1 0 1 0 -1
---------------------
5 -4 2 -3 1 -2 0
1 0 2 -1 1 0 -2
---------------------
5 -4 2 -2 1 0 1
1 0 2 0 1 -2 -1
---------------------
5 -4 2 0 -2 1 1
1 0 2 -2 0 1 -1
---------------------
4 -4 -2 -2 2 0 2
4 -3 -3 -2 1 2 0
---------------------
4 -4 -2 2 2 0 -2
4 -3 -3 2 1 -2 0
---------------------
4 -4 -2 2 0 2 0
4 -3 -3 1 2 0 1
---------------------
4 -4 2 2 0 -2 0
4 -3 2 1 -2 0 1
---------------------
4 -4 -2 -2 2 0 2
3 -2 -3 -2 1 2 0
---------------------
4 -4 -2 -2 2 0 0
3 -2 -3 -2 0 2 1
---------------------
4 -4 -2 2 2 0 0
3 -2 -2 -1 0 2 1
---------------------
4 -4 -2 -2 2 0 2
2 -1 -3 -2 1 2 0
---------------------
4 -4 -2 -2 2 0 0
2 -1 -3 -2 0 2 1
---------------------
4 3 -3 -2 -1 1 0
2 2 -1 -2 -1 0 1
---------------------
4 -2 0 -4 2 2 0
2 3 -4 0 -1 1 2
---------------------
4 -3 -2 -2 -1 1 0
2 -1 -2 -1 -1 0 1
---------------------
3 -2 -1 2 -1 1 0
2 -2 1 0 -1 0 1
---------------------
3 -2 2 -3 0 -2 1
1 -2 -2 1 2 0 -1
---------------------
3 -2 2 -1 0 1 -2
1 -2 -2 3 2 -1 0
---------------------
2 1 -2 1 0 -1 0
1 -2 0 -1 2 0 1
---------------------
|
| 7.20 | some solutions to (9,6) | 4GL::GILBERT | Ownership Obligates | Tue Jan 03 1989 19:34 | 96 |
| Well, I've been working on the program. There were some errors in it,
so the list in 7.19 (for 7 coins, 5 weighings) may be incomplete. It
had also given indications that there are no solutions for (8,5), but
that may also be in doubt.
Here are eight solutions for (9,6). This search is still incomplete.
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 1 0 0 0 1 1 1 1
1 0 1 1 0 1 0 1 0
0 0 1 1 0 0 1 0 1
0 0 1 0 1 1 0 0 1
---------------------------
2 0 0 0 -1 0 -1 -2 1
0 2 0 1 -2 1 -2 -2 1
0 0 2 -2 0 -1 1 1 -1
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 0
1 1 1 0 0 1 1 1 0
1 1 0 1 0 1 0 0 1
1 0 1 0 1 0 1 0 1
0 0 0 1 0 0 1 1 1
---------------------------
2 0 0 1 -2 -2 1 -1 -1
0 2 0 0 -1 -2 1 -1 0
0 0 2 1 -2 -1 0 -1 0
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 0 0 0 0 1 0 1 0
0 1 1 0 0 1 1 1 1
0 1 0 1 0 1 0 0 1
0 0 0 1 0 0 1 1 0
---------------------------
2 0 0 0 -2 -1 1 -1 1
0 4 0 0 -2 -1 -1 1 -3
0 0 2 1 -2 0 -1 0 -1
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 1 1 0 0 1 0 1 0
1 0 0 1 0 1 1 1 1
0 1 1 0 0 0 1 0 1
0 1 0 0 1 1 0 0 1
---------------------------
2 0 0 0 -1 0 -1 -2 1
0 2 0 4 -4 1 -3 -3 1
0 0 1 2 -2 1 -2 -2 1
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 1 0 0 0 1 0 1 1
1 0 1 0 0 0 1 1 0
0 1 0 1 0 0 1 1 1
0 0 0 1 1 1 0 1 0
---------------------------
1 0 0 2 -2 0 -1 0 -1
0 4 0 1 -2 -1 -2 2 -5
0 0 2 3 -4 1 -2 0 -1
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 1 0 0 0 1 0 1 0
1 0 1 1 0 1 0 0 1
1 0 1 0 0 0 1 1 0
0 0 0 1 1 1 1 1 1
---------------------------
2 0 0 -8 4 1 1 -3 5
0 1 0 -2 0 0 1 -1 2
0 0 1 -4 2 1 0 -1 2
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 1 0 0 0 1 0 1 0
1 0 0 0 0 0 1 0 1
0 0 1 1 0 0 1 1 0
0 0 1 0 0 1 0 0 1
---------------------------
1 0 0 2 -2 0 -1 -1 0
0 4 0 4 -6 -1 -1 -3 1
0 0 2 -4 2 -1 1 1 -1
****************************
1 1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 1 1
1 1 0 0 0 1 1 1 0
1 0 1 0 0 1 1 0 1
0 1 0 1 0 1 0 0 1
0 0 1 0 1 1 0 1 0
---------------------------
-6 0 0 1 1 -3 7 2 2
0 -3 0 4 -2 0 1 2 -1
0 0 -3 -2 4 0 1 -1 2
****************************
|