partha@ihuxq.UUCP (07/15/83)
I came across a problem while trying to prove fault coverage of
algorithms for semiconductor RAM testing. The following is the problem:
Given a nonempty set T where |T|=N, form any q (q less than N) nonempty
subsets t1,t2,.....,tq of T where none of the subsets is disjoint with any
other (i.e., ti intersection tj is not null for any i,j in 1 to q) and
t1 U t2 U .... U tq = T. Does there exist a nonempty set R less than or equal
to T such that |R intersection ti| = 0 or an even number for every ti in 1 to
q?
Two examples to illustrate the problem:
a) Consider T={a,b,c}. Here |T|=3. For this case q could be 1 or 2.
case q=1:
Obviously t1={a,b,c}. There are three choices for R:
R={a,b} or R={b,c} or R={c,a}.
case q=2:
There are several choices for t1,t2 and R here.
Choice1: t1={a,b}, t2={b,c}, R={a,b,c}.
Choice2: t1={a,c}, t2={b,c}, R={a,b,c}.
Choice3: t1={b,c}, t2={a,b}, R={a,b,c}.
Choice4: t1={a}, t2={a,b,c}, R={b,c}.
... etc ...
b) Consider T={a,b,c,d}. Here |T|=4. q could be 1,2 or 3.
case q=1:
Again t1={a,b,c,d}.
R={a,b,c,d} or R={a,b} or R={b,c} or R={c,d} or
R={d,a} or R={a,c} or R={b,d}.
case q=2:
Choice1: t1={a,b}, t2={b,c,d}, R={c,d}.
Choice2: t1={a,b,c}, t2={b,c,d}, R={b,c}.
Choice3: t1={a}, t2={a,b,c,d}, R={b,c} or R={c,d} or R={b,d}.
... etc ...
case q=3:
Choice1: t1={a,b}, t2={b,c}, t3={a,b,d}, R={a,b,c}.
Choice2: t1={a,b,c}, t2={c,d}, t3={a,b,c,d}, R={a,b}.
Choice3: t1={a,b,c}, t2={b,c,d}, t3={c,d,a}, R={a,b,d}.
... etc ...
My conjecture is that for any N, one can always find R satisfying the
above conditions. Obviously enumeration is not the answer to prove this.
I need an existence proof for this problem. Any help in this direction will be
greatly appreciated.
Thanks!
P.S.: I was able to think of this problem in set theoretic notation. It
may be easier to attack this problem if formulated otherwise (for instance,
as a graph theory problem).
Partha Raghavachari
Bell Telephone Labs.
Naperville, Ill.
ihuxq!partha