| Re .1:
>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.
Nearly. It should be PAx = b. But note that not all b are achievable,
so a better equation to work with might be PAx = Ax', where x' is another
unknown vector of dimension n.
>Multiplying A inverse by both sides of APx = b gives
A is singular for all n *except* n=3.
>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.
By *defining* b = Ax', we ensure that there is always at least one solution.
Thus the problem reduces to determining uniqueness.
>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.
I agree with what I think you are trying to say, and I think that my
suggested approach addresses it.
Re .2:
>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.
I am only allowed to weigh *two* bales at a time, so if I've only one bale I
can never do any weighings at all! For n=4, the weighings you quote admit
either {1,2,4,6} or {�,2�,4�,5�}.
>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! :-)
I am explicitly prohibited from doing this.
Andrew
|
| We have n bales to weigh. We weigh them 2 at a time giving us
m = n*(n-1)/2 results. I will attempt to find those n for which is it
*always* possible to determine the list of weights of each bale, based on
the list of pair-weights. Say that such an n is *preserving*. If n is
not preserving, say it is *destructive*.
A quick exploration suggests that 1,2 & 4 are destructive, 0,3,5 & 6
are preserving. But now let's take a more systematic approach. Say n >= 3.
Let �_i be the row vector (of length n) which takes the value 1 exactly
in the ith place, otherwise is 0. Let t(i) = i*(i-1)/2. Define the
(m+1)x(n) matrix C as follows: let C(i) denote the ith row of C.
C(1) = sum(i=1,...,n) (�_i)
for 1 =< i < j =< n:
C(t(n-1)-t(n-i)+j) = �_i + �_j
For instance, for n=5, C should look like this:
(11111)
(11000)
(10100)
(10010)
(10001)
(01100)
(01010)
(01001)
(00110)
(00101)
(00011)
Next, let P be an (m+1)x(m+1) permutation matrix which fixes the first
entry. ie: Each entry is equal to 0 or 1. Each row and column contains
exactly one entry equal to 1. P(1,1)=1.
Let x be any column vector of dimension. Suppose that there exists
another such vector,x', such that:
PCx = Cx' (*)
n is preserving IFF
for all P, x and x' satisfying (*), we can find some (n)x(n)
permutation matrix, Q, such that:
x' = Qx
Right, the first thing to do is to find an explicit representation for
x'. Ie, we need to find a left inverse for C. There exist many candidates
for D, the (n)x(m+1) matrix such that DC = I_n, where I_n is the (n)x(n)
identity matrix. Caveat: I shall henceforth use I for all identities of
whatever dimension, and O for all empty matrices of whatever dimensions even
if non-square. Pick one such D (later to be made more precise), then:
x' = DPCx
Incidentally, we can show that x' is a function of x, C and P, but not of D.
(Effectively, we have many more equations than we need to compute x', the
choice of D just represents the selection of those we arbitrarily choose to
solve the problem). Note also that DPC is independent of x.
x' may be determined by just a few of the pair-weights. But what is
much more constraining is that *all* the pair-weights exhibited by x' match
those exhibited by x. Ie, we substitute for x' in (*):
(CD-I)PCx = O
Since this is to be true for all x, it is equivalent to:
(CD-I)PC = O
So we can redefine 'preserving' independently of x:
n is preserving IFF
for all P, (CD-I)PC = O => DPC is a permutation matrix. (**)
For instance, suppose that P is the identity. Then (CD-I)PC = CDC-C
= CI-C = O, whilst DPC = DC = I. So we could rewrite the lhs of (**) as:
(CD-I)(P-I)C = 0
The next thing to do is to define D more precisely. Just as we
chose C without loss of generality, so we can pick D to suit ourselves.
Breaking C and D into submatrices:
E
C = - where E is square and by our construction symmetric
F
& we'll choose D so that:
D = G | O where G = E^(-1), since E is invertible.
It's clear that DC = I.
Then CD is an (m+1) x (m+1) matrix, which can be subdivided into four
submatrices, with the top left matrix (n)x(n).
I | O
CD = --+--
FG | O
O | O
CD-I = --+--
FG |-I
Now what is G?
Let b = 1/(n-2), a = 1-b.
Then G(1,1) = -b
G(1,i) = G(i,1) = b (i=2,...,n)
G(i,i) = a (i=2,...,n)
else, G(i,j) = - b.
Check, [EG](1,1) = -b +(n-1)b = 1
[EG](1,i) = a + b -(n-2)b = 0 (for i>1)
[EG](i,i) = b + a = 1 (for i>1)
[EG](i,j) = b - b = 0 (for i,j > 1, i<>j)
So, for instance for n=5,
G =
(-b b b b b)
( b a -b -b -b)
( b -b a -b -b)
( b -b -b a -b)
( b -b -b -b a)
where in this case b = 1/3, a = 2/3.
So, what will FG look like? Well any row of FG is a row of F acted
upon by G. The (t(n-1)-t(n-i)+j-n)th row of F is simply �_i + �_j, 1<i<j.
So the corresponding row of FG is G(i)+G(j). Let u = the uniform row vector,
with each entry 1. Then:
[FG](t(n-1)-t(n-1)+j-n) = �_i + �_j - 2b*u + 4b*�_1
The -I component of CD-I gives us -�_(t(n-1)-t(n-i)+j).
OK so much for CD-I. Now we examine columns of PC. P
(multiplying C on the left) acts by permuting the rows of C. So each column
of PC will contain n 1's. Say that f(i) of them in the ith column occur
in the 2nd->nth entries. The first entry will always be a 1.
So, the row of FG|-I times the column of PC, taken mod 1, yields:
2b*[1-f(i)]
For this to be 0, we need that (n-2) | 2*(f(i)-1) for all columns i.
Now, f=f(i) is drawn from {0,...,n-1}, so:
k(n-2) = 2(f-1)
Now, first cases where f-2 is negative or zero.
f=0 => n-2 | 2, n =< 4
f=1 always possible.
Otherwise, we know (n-2) >= (f-1), so 2 >= k > 0
n-2 = f-1 => f = n-1.
n-2 = 2(f-1) => f = �n, and n is even.
We assume henceforward that n >= 5. So EITHER n is odd, and f = 1,
or n-1, OR n is even, and f = 1, �n or n-1.
So we have found a major constraint on P. P permutes the rows of
C, and selects n-1 of them for appearance in rows 2->n. This will cause
2(n-1) 1's to appear in the (n-1)x(n) matrix which consists of the 2->n rows
of PC. Since sum(f(i)) = 2(n-1) then for some i, f(i) > 1.
CASE 1: there is i with f(i) = n-1. Then f(j) = 1 for all j <> i.
CASE 2: there are i, i' with f(i)=f(i')=�n. Then f(j) = 1 for all j <> i,i'.
Now, one point is that the constraint we have found for P is
specific to D. If we chose some other D, we would expect a similar constraint
to hold. In particular, to compute x', we chose to use exactly all the
equations which mentioned x'(1), the first element of x. We could have
equally chosen any x'(i) to address.
If CASE 1 applied to *each* of these n versions of D, then we could
say that P has the following property: in moving from C to PC, the set of
(n-1) rows containing a 1 in the ith column is replaced by (n-1) rows
containing a 1 in the q(i)th column. Then view the function q as defining
a permutation matrix, Q, on the elements {1,...,n}, such that PC = CQ.
Then DPC = DCQ = Q, and we have proved the required statement.
So, we need to focus on the possibility that P acts on C in the
more complicated manner suggested by CASE 2. We also know that n is even.
We know there is one row with i & i', (�n-1) rows with i & something else
and (�n-1) rows with i' & something else again. These are the rows which
occupy rows 2->n of PC.
|