MATH 145: Homework Solutions #6
1. Brualdi 6.2
Find the number of integers between 1 and 10,000 inclusive which are not
divisible by
4,6,7, or 10.
Answer:
Let 
be the set of integers between 1 and
10,000 that are divisible by 4, 
be the
set of integers between 1 and 10,000 that are divisible by 6,
be the set of integers
between 1 and 10,000 that are divisible by 7 and let
be the set of integers between
1 and 10,000 that are divisible by 10. Then by the inclusion-exclusion principle
the
number of integers between 1 and 10,000 inclusive which are not divisible by
4,6,7, or
10 is
because:
2. Brualdi 6.3
Find the number of integers between 1 and 10,000 which are neither perfect
squares
nor perfect cubes.
Answer:
Let S = {1, 2, ..., 10000} be the set of all integers between 1 and 10,000. Then
|S| =
10000. Let be the set of all perfect squares in S . Then
since
all integers less than 100 and their perfect squares are in S . Let be the set
of all
perfect cubes in S . Then 
since 9261 is the
largest number that
is a perfect cube in S . Now 
are integers in
S that are both perfect squares
and perfect cubes. Therefore if n is in , and
the prime factorization of n is
then each exponent 
is divisible by 6. That is are integers
in S that are 6 th powers of an integer . The largest integer which is 6th power
in S is
4096. so 
.
Therefore by the inclusion-exclusion principle we have the number of integers
between
1 and 10,000 which are neither perfect squares nor perfect cubes is
3. Brualdi 6.7
Determine the number of solutions of the equation
in
non-negative
integers 
and
not exceeding 8.
Answer:
Let S be the set of all non- negative integral solutions of the equation
.
Then, the number of non-negative integral solutions of the given equation
is ,
Let the set consist of solutions in S for which
We make a change of
variable ,
to get|| which is the same as the number of non-negative solutions
of
the equation 
. Therefore
Similarly, if we let
be the set of solutions in S for
which 
, be the set of
solutions in S for which 
and
be the set of solutions in S for which
,
we get
The set consists of solutions in S which have
and . Let
. Then, || is the same as the non-negative
integral
solutions of the equation
Thus, || = 0. Similarly, we can easily verify that
By inclusion-exclusion principle we get that the number of
solutions of the equation
in non-negative integers
and
not exceeding
8 is
(It is quite obvious that the sets
, . . . , are
disjoint because if two numbers are
greater than 8, then the sum of them together with other non-negative integers
exceeds
14. Thus 680 − 4 × 56 = 456.)
| Prev | Next |