Solution

Todo

Solution

The statement is false. There are three cases:
case #1: $a>1$, when $b=1$, $b^2 \ges a$ is false.
case #2: $a=1$, when $b=0.5$, $b^2 \ges a$ is false.
case #3: $0<a<1$, when $b=a$, $b^2 \ges a$ is false.
No matter what value we choose for $a$ in its domain, there is alwasy some value for $b$, that $b^2 \ges a$ is false.

Solution

Let $p$ be the statement $\exists a \forall b (b^2 \ges a)$ and $s$ be the statement $\neg p$.

$\begin{aligned} s &\equiv \neg(\exists a \forall b (b^2 \ges a))\\ &\equiv \forall a \exists b (b^2 < a)\\ \end{aligned}$

For every $a$, let $b=\frac{\sqrt a}{2}$, we have

$\begin{aligned} b^2 &= (\frac{\sqrt a}{2})^2\\ b^2 &= \frac{a}{4} < a \end{aligned}$

Thus the statement $s$ is true, and the original statement $p$ is false.

Solution

Todo

Solution

To prove the statment, we first need to prove that if $k^3$ is odd, then $k$ is odd.
(1) By contrapositive, the contraposition is: if $k$ is even, then $k^3$ is even.
Let $k=$, where $n$ is an integer. We have

$\begin{aligned} k^3 &=(2n)^3 \\ &=8n^3 = 2 \cdot (4n^3) \end{aligned}$

The contraposition is true. Thus the statement that if $k^3$ is odd, then $k$ is odd, is proved.
(2) From (1), we know that $k$ is odd. Let $k=2m+1$,

$\begin{aligned} k^2 + 1 &= (2m+1)^2 + 1\\ &= 2(2m^2+2m+1) \end{aligned}$

$k^2 + 1$ is even.Thus the original statment is proved.

Solution

Let $y \in h(A) \cup h(B)$,
case #1: $y \in h(A)$, by defintion, $\exists (a_1\in A) h(a_1) = y$

$\begin{aligned} y \in h(A) &\To a_1 \in A\\ &\To a_1 \in A \cup B\\ &\To h(a_1) \in h(A \cup B)\\ &\To y \in h(A \cup B) \end{aligned}$

case #2: $y \in h(B)$, by defintion, $\exists (a_2\in B) h(a_2) = y$

$\begin{aligned} y \in h(A) &\To a_2 \in B\\ &\To a_2 \in A \cup B\\ &\To h(a_2) \in h(A \cup B)\\ &\To y \in h(A \cup B) \end{aligned}$

In both cases, we proved if $y \in h(A) \cup h(B)$, then $y \in h(A\cup B)$. Thus. the original statement is proved.

Solution

Strings start with 00: $2^{10}$.
Strings end with 1111: $2^{8}$.
Strings start with 00 and end with 1111: $2^{6}$
Because of double counting, by inclusion/exclusion principle, the number of strings either start with 00 or end with 1111 is $2^{10} + 2^8 - 2^6$.

Solution

Let the set of $p$ elements be $P$, and the set of $s$ elements be $S$
case #1: when $p>s$, there is no one-to-one function.
case #2: when $p \les s$, there are $s$ ways to map $p_1$ to $S$, there are $(s-1)$ ways to map $p_2$ to $S$, so on so forth, there are $(s-p+1)$ ways to map $p_p$ to $S$. By product rule, the total of one-to-one functions is $s(s-1)(s-2) \cdots (s-p+1)$.

Solution

Todo

Solution

By contradiction, the contradiction is: $16^n$ is $O(15^n)$.
(1) By definition of $O$, $\exists c,k (16^n \les C\cdot 15^n) \forall n>k$, then we have

$\begin{aligned} 16^n \les C\cdot 15^n\\ C \ges (\frac{16}{15})^n \end{aligned}$

(2) Because $\dfrac{16}{15} \ges 1$ and $n$ can be arbitraily large, $\dlim_{n \to \infty}(\frac{16}{15})^n = \infty$.
(3) There is no such constant $C$, which statisfies $C \ges (\frac{16}{15})^n$.
(4) Thus the contradiction is false.
The original statment is true.

Solution

The possible reminders of a number divided by $x$ are $0, 1, 2, \cdots, x-1$. The total of the reminders is $x$.
Objects: $nx+1$ integers
Boxes: $x$ reminders
By the Piegeon Hole Principle, the number of integers with same reminders is at least

$\lceil \frac{nx+1}{x} \rceil = \lceil n+ \frac{1}{x} \rceil = n+1$

Solution

1. The number of subsets with $n$ elements is $C(m, n)$ (combination), where $0 \les n \les m$.
2. The number of all subsets is

$C(m, 0) + C(m, 1) + \cdots + C(m, m) = \sum_{n=0}^m C(m, n)$

3. Let $x=1, y=1$

$\begin{aligned} 2^m = (x+y)^m &= \sum_{n=0}^m C(m, n) x^{n-k} y^k\\ & = \sum_{n=0}^m C(m, n) 1^{n-k} 1^k\\ &= \sum_{n=0}^m C(m, n) \end{aligned}$

According to (2) and (3), the statement is proved.

Solution

$\begin{aligned} C_{total} &= 61^{11}+ 61^{10} + 61^{9} + 61^{8} + 61^{7}\\ C_{nospecial} &= 54^{11}+ 54^{10} + 54^{9} + 54^{8} + 54^{7}\\ C_{special} &= C_{total} - C_{special} \end{aligned}$

Solution

We can treat AB and FGH as two individual elements, then the answer can be given by the number of 5-permutations of a set of 5 elements. That is $P(5, 5)$.

Solution

1. Let the set be $A$ and $A=\emptyset$.
2. Let the relation be $R$ and $R \subseteq A \times A = \emptyset$.
Because the assumption that there are elements in $A$ is false, the conclusion $R$ is symmetric and anti-symmetric is true.

Solution