| If you look at this in matrix terms, you are trying to solve the
system APx = b, where A is represents the possible n(n-1)/2 possible
ways to add two weights together, P is a permutation matrix that
matches each equation with its result, x is the unknown, and b
is the vector of results. To illustrate with a simpler example,
start with the vector of objects [1 2 3]. A is the same for every
system with three objects:
1 0 1
1 1 0
0 1 1
P and x are unknowns (but we know what we should get for x).
b is [3 4 5].
The inverse of A is 1 1 -1
-1 1 1 * 1/2
1 -1 1
Multiplying A inverse by both sides of APx = b gives
Px = [1 3 2]. Since the problem doesn't call for the weights in any
particular order, P is irrelevant, and we can consider Px to be the
desired solution.
In general, there are n unknowns and n(n-1)/2 equations. For n < 3,
this is underspecified and there are no unique solutions, for n = 3,
it is exactly specified and there is always a unique solution, and
for n > 3, it is overspecified and there may not be a unique solution.
The problem becomes one of extracting an A and a b from the data such
that A is non-singular and b somehow matches A.
Jeff
|
| >For n=1,2 & 4, the recovery of the individual bale-weights
>is not possible, but for n=0,3,5 & 6 it can always be done.
Either I don't understand the problem, or something is wrong here. I don't
see any problem with n=1, and n=4 at least can be solved for some sets of
weights, e.g. 3,5,6,7,8,10, or whenever the largest weight is >= sum of 2nd
and 3rd.
One way of solving the problem by induction for all weights is to add a
null bale (weight =0) and pair it off with the others! :-)
Lynn
|
| > -< why not remove redundant weighings, then find null space? >-
The whole point is that it is difficult to identify all the
redundant weighings. This is a very different problem to 7.
Andrew
P.S.: If n is odd (> 1), I can prove I think that a set of pair-weighings
determines a set of bales uniquely. If n is even (>4) then there remains
one exotic special case for me to explore. This may be easy to eliminate,
hard to eliminate, or reveal some pretty special case. I hope it is the
first or the last.
However, my proof is not short. I'll post the work so far in the next reply.
If someone has any good insights, here's the place for them...
|