1. Let A and B be finite sets and f : A --> B. If the number of elements in A is
ID: 2965972 • Letter: 1
Question
1. Let A and B be finite sets and f : A --> B. If the number of elements in A is greater than the number of elements of B, then f is not one-to-one.
After we have covered induction, we will be able to prove this theorem. Until then, we must be content to use it without proof. Now solve the following problem.
Let A be a set consisting of exactly ten distinct integers between 1 and 100. Also let B be the set of all positive integers between 0 and 1000. Consider the function f : P(A) --> B defined by the rule that for all X belongs to P(A),
f(X) = sum of the elements of X.
(a) Prove that f is not one-to-one.
(b) Using (a), prove that there exist subsets C,D of A with C not equals to D such that the sum of the elements in C is equal to the sum of the elements in D
(c) Using (b), prove that there exist disjoint non-empty subsets C', D' of A with the sum of the elements in C' equal to the sum of the elements in D'
2.You find a beat-up old chess board that is missing the A1 and H8 squares (they have been torn off, but all other squares are present). As a super-fancy art project, you decide to glue dominoes to the surface of the board. Assuming each domino takes up exactly two adjacent squares, is it possible to cover the entire chess board with dominoes? (Hint: think about white vs. black squares)
Explanation / Answer
1. a) The first condition for being a one to one is that the number of elements in both the sets should be equal which is not happening here. A contains ten integers whereas B has a 999. Next point is that we know that we can have different combinations such that the sum in each combination is the same. But the sum of two or more integers cannot vary each time. Hence it is a function and not one-one but rather many-one.
b) Now since it is a many to one (which also follows from the basic definition of a function), it means, there are combinations or subsets, the sum of which may be the same. For example, 2+4=6,1+5=6, 4+2=6, 5+1=6, 1+2+3=6 and so on.
c)The proof is almost same only that teh sets need to be disjoint. Hence, we will remove combinations which have the same numbers. Still such combinations exist such as, 2+4=6 and 1+5=6
2. Not possible!. A domino placed on the chessboard will always cover one white square and one black square. Therefore a collection of dominoes placed on the board will cover an equal numbers of squares of each colour. If the two white corners are removed from the board then 30 white squares and 32 black squares remain to be covered by dominoes, so this is impossible. If the two black corners are removed instead, then 32 white squares and 30 black squares remain, so it is again impossible.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.