[In 1991, I posted an article to rec.puzzles asking for a solution to
a special case of the Dinitz conjecture.  To describe this special case,
let A_{i,j} denote the set in the ith row and jth column.  The special
case in question is: A_{i,j} = A_{k,l} whenever i = k.  Below are two
of the responses I got.  The latter is cited in my paper on the Dinitz
conjecture.   ---TYC, 3/22/97]



From @mail.uunet.ca:Software.Mitel.COM!Tom.Gray@mitel Wed Nov 27 11:23:18 1991
Return-Path: <@mail.uunet.ca:Software.Mitel.COM!Tom.Gray@mitel>
Received: from bourbaki (BOURBAKI.MIT.EDU) by math.mit.edu (4.1/Math-2.0) 
	id AA10234; Wed, 27 Nov 91 11:22:08 EST
Received: from mail.uunet.ca ([142.77.1.1]) by bourbaki; Wed, 27 Nov 91 11:25:24 EST
Received: from mitel by mail.uunet.ca with UUCP id <53343>; Wed, 27 Nov 1991 11:24:39 -0500
Received: from Software.Mitel.COM (spock) by Mitel.COM (4.1/SMI-4.1)
	id AA17992; Wed, 27 Nov 91 10:24:00 EST
Received: from msn244 by Software.Mitel.COM (4.0/SMI-4.0)
	id AA23689; Wed, 27 Nov 91 10:27:10 EST
Date: 	Wed, 27 Nov 1991 10:27:10 -0500
From: Tom.Gray@software.mitel.com (Tom Gray)
Message-Id: <9111271527.AA23689@Software.Mitel.COM>
To: grayt@software.mitel.com, tycchow@math.mit.edu
Subject: Re: Trivial or non-trivial?
Status: RO

Here are some refernces .

You want to see i an analysis of multistage swtching
networks which are represented by Paull's matrix
(the matrix you gave in the puzzle).

Your puzzle is really asking how such a network
can be configured to give valid connections
betwen an arbitrary set of inputs and outputs.

See chapter 3 of
Switching and Traffic Theorey 
for Integrated Broadband Networks
Joeseph Y Hui
Kluwer Academic Publishers
ISBN 0-7923-9061-X

The theorems of Paull and Slepian-Duguid on rearranagble
networks are what you want. these show how an arbitrary set
of interconnections can be rearranged to create the valid
set of connections described in your puzzle. The reference
has elementary demonstrations of bot theorems.

                    Tom Gray

From galois!snorkelwacker.mit.edu!spool.mu.edu!uunet!mcsun!sun4nl!dutrun!dutrun2!dutiba.tudelft.nl!dekker Wed Nov 27 13:09:35 EST 1991
Article: 4206 of rec.puzzles
Path: galois!snorkelwacker.mit.edu!spool.mu.edu!uunet!mcsun!sun4nl!dutrun!dutrun2!dutiba.tudelft.nl!dekker
From: dekker@dutiba.tudelft.nl (Rene Dekker)
Newsgroups: rec.puzzles
Subject: Re: Trivial or non-trivial?
Message-ID: <6301@dutrun2.tudelft.nl>
Date: 27 Nov 91 12:19:06 GMT
Article-I.D.: dutrun2.6301
Sender: news@dutrun2.tudelft.nl
Reply-To: dekker@dutiba.tudelft.nl (Rene Dekker)
Organization: Delft University of Technology (TWI)
Lines: 108
Originator: dekker@dutiaa

> Fix an integer n > 0.  Let S_1, ..., S_n be n sets, each with n
> elements.  (The n elements in a given set must be all distinct, but the
> sets need not be pairwise disjoint; in fact, they could be all equal.)
> Show that there is an n x n matrix such that
> 
> 1. the elements in the ith row are precisely the elements of S_i; and
> 2. for each j, the elements in the jth column are all distinct.
> 
> In fact, I know of no elementary solution to the problem, ...

A sulotion follows, which I have devised together with Arlet Ottens. It
is a fairly intuistic solution, not a mathematical proof, but it could
turn into one when a math guru would take a look at it.



Assume that you can fill a k * n matrix with k sets (k < n). Then we
show that you can also fill a (k+1) * n matrix with (k+1) sets.

First, note that for all numbers there is a column in a proper k * n
matrix (k < n) that does not contain that number. Otherwise it would
appear twice in one row.
Suppose this is our k * n matrix:

    .....
    .....
    .....
    .....

The dots represent numbers in the matrix.  We have to add the set
{a,b,c,..,e} as the (k+1)th row, the a..e representing n distinct
numbers. We start by trying to add the first element: a. It can always
be placed in one column, because there is always a column not
containing a. So we add:

    .....
    .....
    .....
    .....
       a

Then we try to add b,c,etc. One number might cause trouble because all
the previous numbers occupy the columns it could be placed in.  Suppose
that is c:

    .....
    ..c..
    ....c
    c..p.
     b a

There is always a column where c could be placed, though this may be
occupied by an other number, say a. We now try to move a c from an
empty column, say the first one in our example, to the column occupied
by a, in the following manner:

We exchange the c in the first column with the number in the same row
in a's column. Say that number is p:

    .....
    p.cq.
    ....c
    p..c.
     b a
     
Now we have a's column containing a c but no p and the first column
containing a p and no c. The first column can now possibly contain two
p's, which must be dealt with. We exchange the other p with its mate in
a's column, say q:

    .....
    q.cp.
    ....c
    p..c.
     b a

Note that a's column cannot contain two p's, because we just removed
the single p in that column. The first can possibly contain two q's
now, but we deal with that in the same manner as the p's. When we
continue to do that we eventually end up with the first column
contaning no c's and the whole matrix in order. The we can place the c
in the first column:

    .....
    q.cp.
    ....c
    p..c.
    cb a

We proceed in this manner until all the elements of the extra set are
added.  In this way we have showed that a correct (k+1) * n matrix can
be formed from a correct k * n matrix, and by the induction principle
we can form a correct n * n matrix.

The only thing that has to be showed yet, is that the exchanging
process between two columns will eventually end.  At one point we have
a set of pairs that are already exchanged and a set of pairs that are
not yet exchanged.  Within each set there is no conflict between the
pairs. There can only exist a conflict between a pair in one set and a
pair in the other.  When that is so, we take the pair in the
not-yet-exchanged set, flip it and put it in the yet-exchanged set.
This newly added pair cannot create a conflict, because otherwise it
would have conflicted also before the exchange process started.

-- 
-------------------------------------------------------------------------------
Rene Dekker      Delft University of Technology        dekker@dutiba.tudelft.nl
Signature under construction. (|:-)