Previous: Euler LibraryUp: Maths

# Questions

## 1 Questions

### 1.1 Analysis

1. Find all (complex) solutions to the equation $$6z^5 + 15z^4 + 20z^3 + 15z^2 + 6z + 1= 0$$.
2. Consider the function $$f : \mathcal{P}(\mathbb{N}) \to \mathbb{N}$$ defined by:

let $$p_n$$ be the nth prime number, and let $$S = \{n_1, n_2, n_3, ...\}$$ then $$f$$ is given by:

$$f(S) = p_1^{n_1} * p_2^{n_2} * ...$$

We claim this implies there is a injection from the powerset of naturals to the naturals and so we provide a counterexample to Cantor's Theorem. Where is the mistake?

1. Find a closed form for $$\sum^n_{k=1} k \cos(kx)$$.
2. Prove or give a counterexample: if a function $$f: \mathbb{R} \to \mathbb{R}$$ is infinitely differentiable, and is nonzero somewhere on its domain, then it has countably many roots.
3. Show $$n!$$ is not elementary.

### 1.2 Algebra

1. Show that the Fundamental Theorem of Algebra and the statement that a polynomial of degree $$n$$ has exactly $$n$$ complex roots (including multiplicity), are equivalent.
2. Show that if $$G$$ and $$H$$ are groups of cardinality $$p$$ where $$p$$ is prime, then $$G$$ and $$H$$ are isomorphic.
3. Show that if $$R$$ is a finite integral domain, then it is also a field (Wedderburn's little theorem).
4. Given any prime $$p$$, show that $$\mathbb{F}_{p}$$ is not algebraically closed.
5. Do the 32 bit integers under two's complement form a group under addition? If not what structure do they form?
6. Show the algebraic numbers form a subring of $$\mathbb{C}$$. Do they form a field?

### 1.3 Linear Algebra

1. Show that a matrix is singular iff it has 0 as an eigenvalue.
2. Show that if $$M$$ is an invertible matrix in some field $$K$$, and has entries all in some subfield $$J \subseteq K$$, then $$M^{-1}$$ also has all of its entries in $$J$$. What if $$J$$ is not a field?
3. Let $$R$$ denote the set of rows of a matrix $$A$$, and $$C$$ the set of columns. Prove or find a counterexample to: if $$R = C$$ then $$A$$ is symmetric.

### 1.4 Number Theory

1. Show that there are no solutions to the diophantine equation $$a^2 + b^2 = c^2$$ if both $$a$$ and $$b$$ are odd.
2. Show that $$\liminf\limits_{n \to \infty} \frac{\phi(n)}{n} = 0$$
3. I choose a positive integer $$n \le 10000$$, your task is to determine whether or not this number is prime by "asking" a number $$k$$, to which I will say "yes" if $$k$$ is a divisor of $$n$$, or "no" if it is not. What is the fewest number of "asks" needed so that you are guarenteed to know whether or not $$n$$ is prime?
4. The powers of two $$\{ 2^0, 2^1, 2^2... \}$$ are a very special sequence, any positive integer can be written as a sum of unique powers of two in exactly one way. Prove the powers of two are the only strictly increasing positive integer sequence with this property.

### 1.5 Graph Theory

1. Show that $$\chi(C_{2n + 1}) = 3 \ \forall n \in \mathbb{Z}^+$$.
2. How many trees are there of size $$n$$ up to isomorphism?

### 1.6 Computation

1. Find the smallest integer $$n$$ such that $$n\ln{n} + n > 3^{197}$$
2. How many palindromes are there beneath $$10^{100}$$? What about $$100!$$ ?
3. Let $$P_n = \{ s \in "([|])\{2n\}" : \text{s is parenthetically closed} \}$$ show that $$P = \cup_{n \in \mathbb{N}} P_n$$ is not a regular language.
4. Describe a list implementation ($$\text{append}(e: E): \text{unit}, \ \text{get}(idx): E, \ \text{remove}(idx): \text{unit}$$) with $$O(1)$$ appends and removals.
5. What are the differences (if any) between the return values of these two functions:
def append1(x: List, y: List):
x = x + [y]
return x

def append2(x: List, y: List):
x.append(y)
return x


Created: 2023-10-23 Mon 18:48

Validate