| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 7.1 | | GALLO::JMUNZER | | Tue Jul 22 1986 17:51 | 3 |
| Does anyone know of any progress on this problem?
John
|
| 7.2 | I doubt it. | MODEL::YARBROUGH | | Wed Jul 23 1986 10: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 10: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 11: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 11: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 13: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 14:11 | 34 |
| If we weigh ABC, AD, BD (as in 7.4), and also D, we can determine the
weights of A, B, and C:
(A) = (AD)-(D)
(B) = (BD)-(D)
(C) = (ABC)+(D)+(D)-(BD)-(AD)
We still aren't ahead of the game; taking 4 weighings to get 4 weights.
However, I expect that with a few more weights and weighings, we will be.
Consider how much info we have after weighing just ABC, AD, and BD.
There are 8 possibilities (we assume w.l.g. that A=x).
A B C D ABC AD BD
x x x x 3x 2x 2x
x x x y 3x x+y x+y
x x y x 2x+y 2x 2x
x x y y 2x+y x+y x+y
x y x x 2x+y 2x x+y
x y x y 2x+y x+y 2y
x y y x x+2y 2x x+y
x y y y x+2y x+y 2y
Now x x x x can be recognized because (AD)=(BD) and (ABC)=3(BD)/2.
But x x x y ,
x x y x ,
and x x y y seem to be indistinguishable.
Now x y x x has (BD) = (ABC) - �(AD),
x y x y has (BD) = -2(ABC) + 4(AD),
x y y x has (BD) = �(ABC) + �(AD),
and x y y y has (BD) = 2(ABC) - 2(AD),
and so these are distinguishable in general (i.e., unless 2x=3y or 2x=y).
- Gilbert
|
| 7.8 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Thu Jul 24 1986 14: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 14: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 16: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 18: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 18:22 | 40 |
| There are (up to symmetry) two ways to solve 5 coins in four
weighings. In the following arrays, a 1 appears in the position (i,j)
iff coin j should appear in the ith weighing.
( 0 0 1 0 1 )
( 0 0 0 1 1 )
( 0 1 1 1 0 )
( 1 1 0 0 1 )
( 1 1 1 0 1 )
( 1 0 0 1 1 )
( 0 1 0 1 1 )
( 0 0 1 1 0 )
To see that these work, use the following theorem:
c coins can be solved in w weighings if:
there exists a w*c matrix, A, such that no element, �, of the nullspace of A
satisfies:
(i) � =/= 0
(ii) each component, �_i, of � = p or q or r or s.
(iii) p + q = r + s
[The nullspace of a matrix M is the set of vectors, V, such that
M.v = 0 for all v in V.]
For the two examples given above, the null-spaces are respectively
{ ( 3a, -2a, a, a, -a) | a is real }
{ ( -2a, -2a, a, -a, 3a) | a is real }
p+q+r+s = a in each case, so p+q = r+s only if a=0, in which case �=0.
Trivially, therefore, 6 coins can be solved with 5 weighings, which
leaves the coast clear for investigating 7 coins with 5 weighings.
Andrew.
|
| 7.13 | | KOBAL::GILBERT | Ownership Obligates | Wed Dec 28 1988 08:09 | 4 |
| The theorem is interesting. Could you give some clues about its derivation?
Also, the condition (ii) isn't clear. Does it mean that if |{�_i}| > 4,
then element � does not satisfy the conditions? Is |{�_i}| = 3 okay?
|
| 7.14 | � = c-c' | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Wed Dec 28 1988 08:59 | 67 |
| Assume that we've got a matrix, A, representing the weighing strategy.
We have the coins' weights in a vector, c, and the results of the weighings are
a vector w.
w = A.c
What does it mean for that strategy to fail? Well, it means that there are
two different sets of coins' weights, c and c' such that
A.c = w = A.c'
i.e.: A.(c-c') = 0.
Now clearly � are going to exist, such that A.� = 0.
(Assuming that none of the weighings are redundant, then the dimension of the
nullspace will be the number of coins minus the number of weighings).
The question is, when do � exist that correspond to c-c'?
If c is composed of elements x and y, whilst y is composed of elements x'
and y', then c-c' will be composed of elements
p = x-x'
q = y-y'
r = x-y'
s = y-x'
such that p+q = r+s.
And contrariwise, if I have � with components drawn from a set {p,q,r,s}
with p+q=r+s, then let me define:
x = p + f
y = p+q-r + f
x'= f = p+q-r-s + f
y'= p-r + f
where f is a fudge factor that I can freely define to be anything I want
to make all the weights come out positive. Then I've identified two
sets of coins which are going to behave the same under the given weighing
strategy. If no such � exists, then my strategy must be a good one.
Unfortunately, that doesn't solve the problem of *finding* good
A. We can now constrain the search massively: particularly the set
{2,-1,1,0} is one which is extremely common. This implies (among other
things) that no set of columns can add to the same as another set of columns.
Together with the wlog restriction that no weighing should use a superset of
the coins that another weighing uses, we can proceed.
But I haven't managed to find a 5*7 A. I am reasonably confident
that there I have exhausted 4*5, and that there is no 4*6. If a 5*7 exists,
then:
(1) No coin is weighed by itself.
(2) A coin which only appears in one weighing is a *singleton*.
There is at most one singleton.
Perhaps some one feels like knocking up a program to search for
answers.
A final area that I haven't explored is whether we can do better by
having a flexible strategy: i.e. we don't decide all the weighings right at
the beginning, but look at the earlier results. The lack of knowledge
here means I cannot say whether my theorem is an 'if' theorem or an 'iff'
one.
Andrew.
|
| 7.15 | | 4GL::GILBERT | Ownership Obligates | Fri Dec 30 1988 16:39 | 58 |
| Andrew (or somebody) -
Could you verify the following two solutions? For convenience, I've
included the null-space after each solution.
**********************
0 1 1 0 1 0 0
1 1 0 1 1 1 0
1 1 0 0 0 0 1
0 0 1 1 0 1 1
0 0 0 0 1 1 1
---------------------
-2 0 -2 4 2 -4 2
0 -2 -1 4 3 -5 2
**********************
0 1 1 0 1 0 0
1 1 0 1 1 0 0
1 1 1 1 0 0 1
1 1 0 0 1 1 1
0 0 1 1 1 1 1
---------------------
-2 0 -2 0 2 -4 4
0 -2 -1 -1 3 -5 4
**********************
How'd I do that? I guessed at an element in the null space (ex:
(5, -4, 3, -2, 1, 0, -1)), then found from the 2^7 possibilities
all of the weighings for which w.� = 0. There were about 17 of these.
Of these 17 weighings, I gathered subsets of 5 weighings which
passed a few simple tests that Andrew suggested -- each element
must be weighed at least once, no more than one singleton, no
linear dependencies, and row is a subset of another row. This
resulted in fewer than 200 plausible 5x7 weighing matrices A.
For each of these, I found the null space (which can be represented
by a 2x7 matrix, as above). For each null space, I found a set of
1x2 vectors [a b] such that [a b].� had at least two equal columns
(these were found by equating all pairs of columns and solving for
an [a b]), since if [a b].� must have at most 4 distinct values
(Andrew's p,q,r, and s), then at least two columns must be equal.
This was a shortcut to the alternative of varying a (or b) continuously
-- I was working with integers.
For each [a b] vector (there could never be more than 42 of them)
[a b].� was computed. If the number of distinct values in this
product was < 4 (and the result wasn't all zeroes), then � was
discarded. If there were 4 distinct values, the p+q=r+s test was
applied, and � discarded if p+q=r+s. Note that this was efficiently
tested by 2*(p+Z) = (p+q+r+s), where Z = q, r, or s.
If none of the [a b] vectors caused � to be discarded, then � must
represent a solution; the ones I've found are shown above.
If these solutions stand, it seems worthwhile to try for 8 coins
in 5 weighings. However, this causes a null space with 3 free
variables, so a better approach to the p+q=r+s test may be needed.
|
| 7.16 | Gasp! | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Sat Dec 31 1988 07:42 | 39 |
| Congratulations, Peter! I'm impressed!
So far as I can tell from drawing the points in the Cartesian plane,
your two solutions work fine. Certainly, your method is sound. Any chance
of you posting me your software? I'd be very keen to play around with it.
I also really like your approach of 'guessing'. It just hadn't occured
to me to do it that way, although I had an idea there might be several answers.
Now as far as 8 coins with 5 is concerned, I agree that the pqrs
checking process would be time consuming, as you try all the projections of
the eight points in three-space onto the integers (via the trick of mapping
them onto one another as you did). But it's possible, and I believe
combinatorially feasible.
Where I think you would run into difficulties is in guessing a correct
�, if one exists. Prove me wrong.
However, if we can find *all* the answers to 7*5 then we automatically
know if there are any 8*5 answers. Pick any column from an 8*5 and delete it.
The 7*5 remaining must be one of the solutions. So, we should see a family of
eight 7*5 which are nearly similar to one another.
Frankly, my hunch is that none exists, ie no 8*5 exists.
Another approach would be similar to another coin problem. If we have
a balance, and want to find out in three weighing which one of fourteen coins is
a dud, being either lighter or heavier than all the others, then we know its
impossible. Because there are 28 different possibilities, and only 27
different outcomes from three weighings (where each either balances or left
heavier or right heavier). However, I can't transfer the argument to our
current problem. It may be that the pqrs result *is* the analogous result
for the current problem.
However I can't see how we can take your guessing approach, and
exhaustively guess all the solutions.
Sorry for the rambling nature of the reply. I just wanted to get down
all my thoughts.
|
| 7.17 | addendum | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Sat Dec 31 1988 07: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 15: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 11: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 16: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
****************************
|