# OK to post homework
# Michael Saunders, 9/20/2020, Homework 4
#

# load packages
#
with(combinat):

# include Maple procedures from M4.txt
#
#CP(A,B): The Cartesian product of finite sets A and B
CP:=proc(A,B) local a,b:
    {seq(seq([a,b],a in A),b in B)}:
end:

#CheckMult(A,B): Empirically checks the trivial but EXTREMELY important fact 
#(see http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enu.pdf, p.2, bottom of column 1)
#that |AxB|=|A|*|B|
#Try:CheckMult({1,2,3},{a,b})
CheckMult:=proc(A,B)
    evalb(Mynops(CP(A,B))=Mynops(A)*Mynops(B)):
end:

#CheckAdd(A,B): Empirically checks the trivial but EXTREMELY important fact 
#(see http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enu.pdf, p.2, bottom of column 1)
#that |A union B|=|A|+|B| (assuming A and B are disjoint sets, I believe).
CheckAdd:=proc(A,B):
    if not type(A,set) then
        print(A, `is not a set `):
        RETURN(FAIL):
    fi:
    if not type(B,set) then
        print(B, `is not a set `):
        RETURN(FAIL):
    fi:
    if A intersect B<>{} then
        print(A,B, `have the following common elements `, A intersect B):
        RETURN(FAIL):
    fi:
    #This checks that if A and B are disjoint finite sets, then
    #|A U B|= |A| + |B|
    evalb(Mynops(A union B)=Mynops(A) + Mynops(B)):
end:




# 1.
#    Carefully study M4.txt and find:
#
#    CP({a,b,c},{b,c,d});
#    CheckMult({1,2},{3,4});
#    CheckAdd({1,2,3},{3,4,5});
#    member([d,o,r,o,n],Words({d,o,n,r},5));

print("1."):
CP({a,b,c},{b,c,d});
CheckMult({1,2},{3,4});
CheckAdd({1,2,3},{3,4,5});
member([d,o,r,o,n],Words({d,o,n,r},5));

#    {[a, b], [a, c], [a, d], [b, b], [b, c], [b, d], [c, b], [c, c], [c, d]}
#    false
#    {1, 2, 3}, {3, 4, 5}, `have the following common elements `, {3}
#    FAIL
#    false



# 2.
#    Find the smallest positive integer n such that
#    1, 2, 3, ....., n (in Maple: seq(i,i=1..n) ) only returns ONE hit, namely A27, from the OEIS.
#
#    Side note - this would be a good exercise for learning TCP/IP scripting.
#    Actually, I spent some time manually iterating this search (from 1..n) using the web form,
#    and I can no longer continue. This is a job for a computer. Perhaps I will come back to it later.



# 3.
#    The Principle of Inclusion-Exclusion for TWO sets says, that given a UNIVERSAL set U and subsets A1, A2
#    defining the COMPLIMENT of a subset A of U by Comp(U,A), 
#    
#    |Comp(U,A1) intersect Comp(U,A2)| = |U| - |A1| - |A2| + |A1 intersect A2|
#
#    Check the above Inclusion-Exclusion formula by hand for:
#    U = {1,2,3,...,15},
#    A1 = {x member U : x is multiple of 3},
#    A2 = {y member U : y is multiple of 5}.
#
#    Write out A1 and A2 in full:
#    A1 = {3,6,9,12,15}
#    A2 = {5, 10, 15}
#
#    Comp(U,A1) = {1,2,4,5,7,8,10,11,13,14};
#    Comp(U,A2) = {1,2,3,4,6,7,8,9,11,12,13,14};
#
#    Comp(U,A1) intersect Comp(U,A2) = {1,2,4,7,8,11,13,14};
#
#    A1 interset A2 = {15};
#
#    |Comp(U,A1) intersect Comp(U,A2)| = 8; |U| = 15; |A1| = 5; |A2| = 3; |A1 intersect A2| = 1;
#
#    8 ?= 15 - 5 - 3 + 1
#    8 ?= 8
#    TRUE.
#
#    Write a Maple procedure PIE2(U,A1,A2) that inputs three sets U,A1,A2. 
#    After checking that U,A1,A2 are indeed sets (RETURN FAIL if not) AND that A1 and A2 are NOT
#    subsets of U (RETURN FAIL they are subsets), compute |Comp(U,A1) intersect Comp(U,A2)| in
#    two ways...
#    First, directly find the size of the resultant set.
#    Second, use the above formula to compute the size.

PIE2 := proc(U,A1,A2) local R1, R2:
    # check args are sets and A1 and A2 are subsets of U
    if not (type(U,set) and type(A1,set) and type(A2,set)) then
        RETURN(FAIL);
    fi:
    if not (verify(A1, U, `subset`) or verify(A2, U, `subset`)) then
        RETURN(FAIL);
    fi:
    # direct method
    R1 := nops((U minus A1) intersect (U minus A2)):
    # using the formula given above
    R2 := nops(U) - nops(A1) - nops(A2) + nops(A1 intersect A2):
    RETURN([R1,R2]):
end proc:

#   Test PIE2(U,A1,A2)
print("2."):
U := {seq(i,i=1..15)}:
A1 := {3,6,9,12,15}:
A2 := {5,10,15}:
PIE2(U,A1,A2);

#    [8, 8]