Solutions of moed B, 2003 (briefly)


1. (a) The symetric numbers C(n,i) and C(n,n-i) are equal
and have the same sign. Let us balance their coefficients
i and n-i to n/2 both. We get

    Our sum = n/2 * (the sum that is known to be 0) = 0.

   (b) Via derivative, analogously to what was given in
the class.


2. a) 45~4, since there are 45 possible independent grades.

b) The sum of the numbers is 312, while each one is at most 100.
The method is standart, using D(n,r) and Inclusion-Exclusion.

Another way is to study the numbers (100-grade). Their sum is 88,
while each one is at most 100. No Inclusion-Exclusion is needed.

c) Similar to (b), but we decrease each grade by 56 before
the computing. The sum of the numbers is 88, while each one
is at most 44.

d) Permutations: 45*44*43*42.


3. From the course exactly.


4. (a) 0 0 0 0 1 0 1 infinity

   (b) 2 4 4 2 4 2 2 2

   (c) n=2~k (the symbol "~" denotes degree)

       n n~2 n~2 (between n and n~2) 2~n (between 1 and n) n! k+1

   n~2 =< 2~n; 2~n < n!; k+1 < n; (between 1 and n) is incomparable with k+1.


   (d) The formula is on the number of possible equivalence
relations in A. ...


5. There are two ways:

(1) To convert all psukim, except for (p V q) to the -> form,
to get p->s and q->r, and to use the inference law 11.

(2) To suppose (s or r) to be false, thus s=0, r=0. The values
of the other psukim are forced: u=1, p=0, q=1, r=1. The latter
value is a contradiction.


6. There are two ways:

(1) We insert notB into the parenthesis, and after that notA
into the result. By the way, (B and notB) disappears, and
after that (A or notA) disappears. The result coincides with
the right hand part.

(2) Via the Wenn diagramm, this is easy.


7. (a) F = { ( a, F(a) ) }, F~2 = { ( a, F(F(a)) ) }.

   (b) In the composition of two F relations,

 - there is a unique value - F(a) - of the second partner of a;

 - F(a) is in A, hence there is a unique value - F(F(a)) - of
   the second partner of F(a);

 - hence, the partner of a in the composition relation exists
   and is unique.

  (c) |F|=5, |F~2|=5, |F V F~2|=10, |F*|=25.

  (d) (1) |F V F~2|=<2n, since F V F~2 is the union of two sets
of size n each.

      (2) For each a in A, let us consider two pairs: (a,F(a))
and (a,F(F(a))). If they are distinct for all a, then there
are 2n pairs totally. This is not the case only if for some a,
(a,F(a))=(a,F(F(a))). But this shows that F(a)=F(F(a)), that
is the element b=F(a) is as required.


8. (a)
   {(a,c), (b,d)}; 
   {(a,c), (a,d), (b,d)}; 
   {(a,c), (a,d), (b,c), (b,d)}.

   (b) The constraints require that there are two minimal elements
and two maximal elements. There may be two, three, or four pairs,
in the relation. For each case, there is only one possible form,
given that each element must be connected with at least one other
element.