MAT3500 - Counting Assignment - Part 1
01/11/2024
6
Min.
Counting - Hoang Anh Duc - MIM - HUS - VNU
Work 4.
How many binary strings are there with 7 digits,
start with 00 or end with 111?
Solution:
Let A be the set of all 7-digits binary strings
that start with 00
Let B be the set of all 7-digits binary strings
that end with 111
We count |A| = 2^5 = 32
We count |B| = 2^4 = 16
We count |A intersect B| = 2^2 = 4
By the inclusion-exclusion rule, we have
|A union B| = |A| + |B| - |A intersect B| = 44
So there are 44 7-digits binary strings that start
with 00 or end with 111
Work 6.
How many positive integers are there that are less
or equal to 1000 which satisfies:
(a) Is a multiple of 7
(b) Is a multiple of 7 and 11
(c) Is a multiple of 7 but not 11
(d) Is a multiple of 7 or 11
(e) Not a multiple of 7 and 11
- (a) Is a multiple of 7
We need to find positive integers that is less or equal
to 1000 and satisfies the form 7k with k in Z^+ such that
7k <= 1000 -> k <= 1000/7 ~ 142.857
So there are 142 positive integers less or equal to 1000
that is a multiple of 7
- (b) Is a multiple of 7 and 11
A number that is a multiple of both 7 and 11 must be
a multiple of 7 x 11 = 77, we need to find positive
integers that is less or equal to 1000 and satisfies
the form 77k with k in Z^+ such that
77k <= 1000 -> k <= 1000/77 ~ 12.987
So there are 12 positive integers less or equal to 1000
that is a multiple of 7 and 11
- (c) Is a multiple of 7 but not 11
From let A and B be the set of integers that are less
or equal to 1000 and is a multiple of 7 and 11, respectively
|A| - |A intersect B| = 142 - 12 = 130
So there are 130 positive integers less or equal to 1000
that is a multiple of 7 and 11
- (d) Is a multiple of 7 or 11
From let A and B be the set of integers that are less
or equal to 1000 and is a multiple of 7 and 11, respectively
|A union B| = |A| + |B| - |A intersect B|
= 142 - floor(1000/11) - 12
= 142 + 90 - 12 = 220
So there are 220 positive integers less or equal to 1000
that is a multiple of 7 or 11
- (e) Not a multiple of 7 and 11
From let A and B be the set of integers that are less
or equal to 1000 and is a multiple of 7 and 11, respectively
1000 - |A union B| = 1000 - 220 = 780
So there are 780 positive integers less or equal to 1000
that is not multiple of 7 and 11
Work 11.
Suppose a drawer contains only two types of socks:
black and white, with 12 of each color. A person takes
socks from the drawer randomly in the dark.
(a) How many socks must be taken to ensure that
there are two of the same color? Four of the same color?
(b) How many socks must be taken to ensure there is
one pair of black socks?
(c) If there are 12 more brown socks added to the drawer,
how many socks must be taken to ensure that there are
two of the same color?
-
We make use of the pigeonhole principle
-
(a) How many socks must be taken to ensure that there are two of the same color? Four of the same color?
To ensure that two socks are of the same color, we can
consider the worst-case scenario where we pick one black
sock and one white sock (one of each color). In this case,
taking a third sock would guarantee that it matches one
of the previous two socks, since there are only two
colors available.
So, to ensure that there are two socks of the same color,
the answer is: 3
For four socks of the same color, consider the worst-case
scenario where we have taken three socks of each color (three
black and three white), totaling six socks. Taking an
additional (seventh) sock will guarantee that we have
four of one color.
Thus, to ensure there are four socks of the same color,
the answer is: 7
- (b) How many socks must be taken to ensure there is one pair of black socks?
To ensure we get at least one pair of black socks,
consider the worst-case scenario where we have picked
all 12 white socks before picking a black sock.
In this case, taking two more socks would ensure
we have two black socks.
Therefore, the answer is: 12 + 2 = 14
- (c) If there are 12 more brown socks added to the drawer, how many socks must be taken to ensure that there are two of the same color?
Now, there are three colors: black, white, and brown, with
12 socks of each color. To ensure two socks of the same color,
we consider the worst-case scenario where we pick one sock of
each color (one black, one white, and one brown). In this case,
taking a fourth sock guarantees that it will match one of
the previously drawn colors.
Thus, to ensure there are two socks of the same color,
the answer is: 4
Work 12.
Prove that in any group of n integers, there are two
integers that have the same remainder when divided by n-1.
-
Solution:
-
We make use of the pigeonhole principle
When an integer is divided by n - 1, the possible remainders
are 0, 1, 2, ... , n - 2
So there are n - 1 total possible remainders
Pigeonhole Principle:
Pigeons -> n integers
Pigeonholes -> n - 1 possible remainders possible when each
integer is divided by n - 1
So there are more integers than possible remainders, by the
pigeonhole principle, at least 2 integers must have the same
remainder when divided by n - 1
Work 17.
- Prove the theorem below:
\[\begin{gather*} \text{For all integers } n, r \text{ that satisfies } 0 \leq r \leq n \quad \\[5pt] C_n^r = C_n^{n-r} \quad \end{gather*}\]
- Solution:
\[\begin{gather*} \text{LHS = } C_n^r = \frac{n!}{r!(n-r)!} \quad \\[8pt] \text{RHS = } C_n^{n-r} = \frac{n!}{(n-r)!r!} = \text{ LHS} \quad \end{gather*}\]
Work 18.
- Prove the theorem below:
\[\begin{gather*} \text{Let } n > k \geq 1 \text{, we have} \quad \\[5pt] C_n^k = C_{n-1}^k + C_{n-1}^{k-1} \quad \end{gather*}\]
- Solution:
\[\begin{align*} \text{RHS } &= C_{n-1}^k + C_{n-1}^{k-1} \quad \\[8pt] &= \frac{(n-1)!}{((n-1) - (k-1))!(k-1)!} + \frac{(n-1)!}{((n-1)-k)!k!} \quad \\[8pt] &= \frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-1-k)!k!} \quad \\[8pt] &= \frac{(n-1)!k}{(n-1)!k!} + \frac{(n-1)!(n-k)}{(n-k)!k!} \quad \\[8pt] &= \frac{(n-1)!k+(n-1)!(n-k)}{(n-k)!k!} \quad \\[8pt] &= \frac{(n-1)!(k+(n-k))}{(n-k)!k!} \quad \\[8pt] &= \frac{(n-1)!n}{(n-k)!k!} = \frac{n!}{(n-k)!k!} = C_n^k = \text{ LHS} \quad \end{align*}\]
Work 19.
- Use the theorem in work 18, prove the following identity:
\[\begin{gather*} C_n^k - C_{n-2}^{k-2} = 2C_{n-2}^{k-1} + C_{n-2}^k \quad \end{gather*}\]
- References: