Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-09-13 05:33:13

vagelis
Member
Registered: 2007-09-13
Posts: 4

set theory?

I have a prodlem that seems like it needs set theory consepts for solving it.
I would like to have a roadmap from where to start looking since set theory is a large field.
My problem is :

I have 3 sets

A:{1,2,3,4,5}
B:{1,2,3}
C:{1,5}

and i want to count all possible sets D {x,y,z} that x belongs to A, y belongs to B, z belongs to C (similar to the cardinality of AxBxC)  BUT there souldn't be any number more than one time (i.e. (1,2,1) should not be counted)

I know the answer for this problem is 15 but i need a formula for solving such problems without having to enumerate each solution (since the numbers of each set can be really high)

Thank you in advance.

Offline

#2 2007-09-13 06:10:57

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: set theory?

For two sets, A and B, we remove one every time it is in the intersection of A and B.  To see this, try your example:

(1, 1)
(1, 2)
(1, 3)

(2, 1)
(2, 2)
(2, 3)

(3, 1)
(3, 2)
(3, 3)

(4, 1)
(4, 2)
(4, 3)

(5, 1)
(5, 2)
(5, 3)

Since 1 is in the intersection, we remove (1,1).  Since 2 is, we remove (2, 2) and since 3 is, we remove (3, 3).  The result is that the answer will be:

|A x B| - |A n B|

Try to see if you can generalize this result to 3 sets.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#3 2007-09-13 07:22:21

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: set theory?

Ok, so I came back to this an it's a bit more complicated than I had first thought for 3 sets.  The final answer is:

|A x B x C| - |C|*|A n B| - |B|*|A n C| - |A|*|B n C| + 2*|A n B n C|

Here is the reasoning:

We take all 3-tuples (a, b, c) and we want to eliminate some because there are places where a = b, a = c, or b = c.  We need to eliminate all pair where a = b.  So we take out A n B.  But for each element in A n B, it is paired with |C| element from C.  So we need to remove |C|*|A n B|.  The same logic applies to the other subtractions.

But wait, what if we have (1, 1, 1)?  By the logic above, we would be removing this 3 times.  But we can only remove it once.  So we add it back in there twice with 2*|A n B n C|, as for this to happen, the element must be in all three sets.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#4 2007-09-13 19:33:50

vagelis
Member
Registered: 2007-09-13
Posts: 4

Re: set theory?

Thank you for your responce .

I will try to see if the same logic can be applied to 4 sets since in my problem the number of sets can varry!

Offline

#5 2007-09-13 21:31:41

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: set theory?

It can, but the formula will be very complicated.
With 2 sets, only 2 terms are required but 3 sets need 5. Jumping from 3 to 4 will need even more terms, and it would be easy to go wrong somewhere whilst counting those.

I'm not sure whether this is better or worse, but I'd do it by a kind of 'induction'. I'll use your example to demonstrate.

First we look for all single-element sets that can be made from A.
Obviously, these are:

{1}
{2}
{3}
{4}
{5}

Now we take every set in that list and add every element we can from B on to them.

{1,2} {1,3}
{2,1} {2,3}
{3,1} {3,2}
{4,1} {4,2} {4,3}
{5,1} {5,2} {5,3}

Now we take every set in that list and add elements from C.

{1,2,5}
{1,3,5}
{2,1,5}
{2,3,1} {2,3,5}
{3,1,5}
{3,2,1} {3,2,5}
{4,1,5}
{4,2,1} {4,2,5}
{4,3,1} {4,3,5}

{5,2,1}
{5,3,1}

I know that that's just listing the solutions, but it's a well-defined method for doing so and so you could probably get a computer to do all the work for you.


Why did the vector cross the road?
It wanted to be normal.

Offline

#6 2007-09-14 03:56:43

vagelis
Member
Registered: 2007-09-13
Posts: 4

Re: set theory?

ok for anyone interested here is a java code that calculates such solutions ...

        Vector<Integer> vr1 = new Vector<Integer>();
        vr1.add(new Integer(1));
        vr1.add(new Integer(2));
        vr1.add(new Integer(3));
        vr1.add(new Integer(4));
        vr1.add(new Integer(5));
       
        Vector<Integer> vr2 = new Vector<Integer>();
        vr2.add(new Integer(1));
        vr2.add(new Integer(2));
        vr2.add(new Integer(3));
       
        Vector<Integer> vr3 = new Vector<Integer>();
        vr3.add(new Integer(1));
        vr3.add(new Integer(5));

        Vector<Vector<Integer>> vr = new Vector<Vector<Integer>>();
       
        vr.add(vr1);
        vr.add(vr2);
        vr.add(vr3);

        Vector<Integer[]> row = new Vector<Integer[]>();
        for (int i = 0; i < vr.size(); i++)
        {
            if(i+1==vr.size())
                break;
            Vector<Integer> row1 = vr.get(i);
            if(i==0)
            {
                // copy to row vector
                for (int j = 0; j < row1.size(); j++)
                {
                    Integer[] integer = new Integer[]{row1.get(j)};
                    row.add(integer);
                }
            }
            Vector<Integer[]> newRow = new Vector<Integer[]>();
            Vector<Integer> row2 = vr.get(i+1);
            for (int j = 0; j < row.size(); j++)
            {
                Integer[] previousResult = row.get(j);
                int resultSize = previousResult.length;
                for (int j2 = 0; j2 < row2.size(); j2++)
                {
                    Integer currentValue = row2.get(j2);
                    Integer[] tmpPreviousResults = new Integer[previousResult.length];
                    System.arraycopy(previousResult, 0, tmpPreviousResults, 0, previousResult.length);
                    Arrays.sort(tmpPreviousResults);
                    if(Arrays.binarySearch(tmpPreviousResults, currentValue)>=0)
                    {
                        // Already exist so skip
                        continue;
                    }
                    Integer[] newResult = new Integer[resultSize+1];
                    for (int k = 0; k < previousResult.length; k++)
                    {
                        newResult[k] = previousResult[k];
                    }
                   
                    newResult[resultSize] = currentValue;
                    newRow.add(newResult);
                }
            }
            row = newRow;
        }

thank you very much for your effort.

Offline

#7 2007-09-14 03:58:17

vagelis
Member
Registered: 2007-09-13
Posts: 4

Re: set theory?

Oh ... forgot ... for printing the result ( THE "row" Vector) :

    private static void print(Vector<Integer[]> holder)
    {
        for (int i = 0; i < holder.size(); i++)
        {
            Integer[] v = holder.get(i);
            for (int j = 0; j < v.length; j++)
            {
                System.out.print("\t"+v[j]);
            }
            System.out.print("\n");
        }
    }

Offline

Board footer

Powered by FluxBB