How many binary strings are there with 7 digits,
start with 00 or end with 111?

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

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

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

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

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

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

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

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?

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

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

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

Prove that in any group of n integers, there are two
integers that have the same remainder when divided by n-1.

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