Taylor Series Problem

by Kingofmath101, Aug 4, 2017, 10:37 PM

This problem is courtesy of Steven Miller's "The Probability Lifesaver," Chapter 11.

Problem: Without explicitly finding the Taylor Series, use the properties of $e^x$ to show that the Taylor series for $e^x$ is $\sum^{\infty}_{n = 0}\frac{x^n}{n!}$ .

Solution: Let the $n$ th coefficient of the Taylor Series for $e^x$ be $a_n$ (starting at $n = 0$ ). That is, we have

$e^x = \sum^{\infty}_{n = 0}a_nx^n$
We know that the exponential is its own derivative. That is, we know that

$\sum^{\infty}_{n = 0}a_nx^n = \sum^{\infty}_{n = 0}na_nx^{n - 1}$
for all $x \in \mathbb{R}$ . Due to the uniqueness of the Taylor expansion, we have the recurrence relation

$a_n = na_{n - 1}$
This holds for $n \geq 1$ . For $n = 0$ we can see that $a_0 = 1$ , and then $a_n = n!$ for all larger $n$ . This is the desired result. $\square$

calculus

differentiating identities

CMIMC Proposed Problems-Algebra

by Kingofmath101, Jul 27, 2017, 4:40 AM

1. Compute $\sum^{\infty}_{x = 1}\frac{1}{x^2(x + 1)}$ .

2. Let $P(x)$ be a $2016$ degree polynomial. One incomplete factorization of $P(x)$ is $P(x) = (x^3 - 11x^2 + 34x - 24)(x^3 - 10x^2 + 31x - 30)Q(x)$ for some $2010$ degree polynomial $Q(x)$ . Let $R_t(x)$ be the remainder when $P(x)$ is divided by $x - t$ . Compute $\sum^{6}_{t = 1}R_t(x)$ .

3. Compute $\prod^{2016}_{j = 1}je^{\prod^{2016}_{i = 1}e^{((-1)^i)}}$ .

4. Compute $\sum^{98}_{j = 0}\frac{100}{9900 - 199j + j^2}$ .

5. Let $f(x) = \frac{1}{1 - \frac{1}{1 - x}}$ . Compute $f^{2016}(2016)$ , where $f$ is composed upon itself $2016$ times.

6. Let $a_k$ and $b_k$ be sequences defined where $a_0 = 1$ , $a_1 = \frac{7}{2}$ , $b_0 = 1$ , $b_1 = \frac{9}{2}$ , and the following recurrence relations hold for all integers $k \geq 2$ :

$a_k = 8a_{k - 1} - 15a_{k - 2}$
$b_k = 8b_{k - 1} - 15b_{k - 2}$

The value of $a_{2017} + b_{2017}$ can be written as $2^r \cdot s$ , where $r$ is a positive integer and $s$ is a positive odd integer. Compute $r$ .

7. The value of

$\sum^{\infty}_{j = 3}\frac{j}{\lfloor{\frac{j}{2}\rfloor}!}$
is equivalent to $\frac{ae}{2} + \frac{b}{2}$ , where $a$ and $b$ are integers. Compute $a + b$ .

8. The value of the sum

$\sum^{\infty}_{j = 0}\sum^{\infty}_{i = 1}\frac{i}{3^{j + i}}$
can be written as $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Compute $a + b$ .

9. Let $f(x) = a_{2017}x^{2017} + a_{2016}x^{2016} + ... + a_1x + a_0$ be a $2017$ -degree odd polynomial that has $2017$ real and distinct, roots. Let these roots be $r_1, r_2, ..., r_{2017}$ . Moreover, $a_0, a_1, ..., a_{2017} \in \mathbb{R}$ . Let the sequence $\{\sigma_k\}^{2017}_{k = 1}$ be defined so that

$\sigma_1 = r_1 + r_2 + ... + r_{2017}$ $\sigma_2 = r_1r_2 + r_2r_3 + ... + r_{2017}r_1$ $\cdots$ $\sigma_{2017} = r_1r_2...r_{2017}.$
Compute $\sum^{2017}_{k = 1}\sigma_k$ .

10. Let $f$ be a function $f: \mathbb{R} \rightarrow \mathbb{R}$ such that $f(53) = 12$ , $f(x) > 1$ for all $x \in \mathbb{R}$ , and the following hold:

$2f(x^2 - 1)^2 + 2f(x^2 + 1)^2 = f(x + 1)^4 + 3f(x + 1)^2 - 40$ $f(x^2 - 1)^2 - f(x^2 + 1)^2 = -f(x + 1)^3 - f(x + 1)^2 + 20.$
Compute $f(2603)$ . Note we use the convention that $f(x)^2 = f(x) \cdot f(x)$ , $f(x)^3 = f(x) \cdot f(x) \cdot f(x)$ , and so on.

This last problem has an interesting history behind it: when it was created and reviewed, everything seemed to be in order except it was unknown if such a function $f$ exists. The CMIMC staff were unable to determine the answer to this question, and consequently this problem was not used on the competition. I leave it as an open problem to determine if such a function exists, and one could always just assume that it exists for sake of solving this problem.

Mathematics Competitions

CMIMC

algebra

CMIMC Proposed Problems-Calculus

by Kingofmath101, Jul 27, 2017, 4:33 AM

1. Integrate $\int{\frac{e^{2x}(\sin x - \cos x)}{\sin^3 x}dx}$ .

Mathematics Competitions

CMIMC

calculus

integration

CMIMC Proposed Problems-Computer Science

by Kingofmath101, Jul 27, 2017, 4:32 AM

1. In computer science, \textit{concurrent processes} are processes that occur simultaneously with shared memory. The steps of the processes may be interwoven in some unknown order that can change. At time $t = 0$ , the value of some variable $x$ which is considered shared memory between Processes A and B is 6. Let the steps of Process A be

Step 1: $x = x - 4$

Step 2: $x = x * 3$

Similarly, let the steps of Process B be

Step 1: $x = x - 5$

Step 2: $x = x * 4$

Both processes A and B will run twice (with the steps interwoven in some order) and then stop. For some interweaving of the steps, what is the minimum possible value of $x$ ? (Note: the second run through of Process B may begin before the first run through of Process A finishes, or vice-versa. However, for a specific process, Step 1 occurs before Step 2.)

2. Consider a 2-dimensional array with a length of $2016$ and a width of $2016$ (entries, so we have a $2016 \times 2016$ grid of entries). We denote which row we are in with the index $i$ , and which column we are in with the index $j$ . The indices of each variable range from $0$ to $2015$ , inclusive (integers only, of course). Initially all of the entries in the array are set to False. Then a program iterates through all of the entries, by passing through them row by row. For each entry, the code determines the values of $i$ and $j$ , and turns the value of the entry to True if and only if the sum of $i$ and $j$ are a multiple of $6$ . When the program has terminated, how many entries are set to have a value of True (Sidenote: in Python, the condition that $i$ and $j$ sum to a multiple of $6$ is represented by the statement $i + j == 0 \% 6$ .)

3. A hash table contains eleven buckets, labeled with the numbers $0, 1, ..., 10$ . At this point in time, the ``0" bucket is empty. The remaining ten buckets each contain one element: a list of the positive integers up to $n$ , where $n$ is the label on the bucket (for instance the ``4" bucket contains the list $[1, 2, 3, 4]$ ). Then the following program is executed two times, where the program's process is described as follows: randomly generate a list of the subset of the first ten positive integers so that each list (including the empty list) is equally likely to occur. The program returns a tuple of the length of the generated list and the list itself. This list is then mapped to the bucket corresponding to its length (for instance, a list of length $4$ is mapped to the ``4" bucket, regardless of the contents of the list). After this program's two executions are complete, what is the probability that the ``7" bucket still contains $[1, 2, 3, 4, 5, 6, 7]$ ? You need not fully simplify your answer.

4. Consider the following algorithm, where the input is a positive integer $k$ at least $2$ . Identify the unique prime factorization of $k$ such that

$k := p_1^{a_1}...p_n^{a_n}$
where $a_1, a_2, ..., a_n$ are positive integers and $p_1, p_2, ..., p_n$ are distinct prime numbers. Let $\Omega$ denote the application of the algorithm described above to $k$ . Note that if $\Omega(k) = k,$ the algorithm does not terminate because it is caught inside an infinite loop. For the sake of this problem we say that $k$ fails to terminate with respect to $\Omega$ . Find the sum of all positive integers $k$ less than $60$ for which $k$ does fails to terminate with respect to $\Omega$ (note: if $\Omega(a) = k$ , $k$ fails to terminate with respect to $\Omega$ , and $a \neq k$ , we do not count $a$ in our total).

5. Consider the following list of positive integers:

$251, 269, 112, 122, 150, 213, 242, 269, 210.$
For reference, three-way merge sort works according to the following algorithm: if your list is one element, return that list (the base case). Otherwise, split the list into thirds based on the original order (e.g. in the above example the list is partitioned into $\{251, 269, 112\}$ , $\{122, 150, 213\}$ , and $\{242, 269, 210\}$ ), and assume they are sorted. Then return the three-way merge sort of the three sublists appended together (i.e. the recursive call). In this example every list and sublist has a length that is an integer power of $3$ (don't worry about the resulting sublists being uneven in size). Let $a$ be the number of steps to sort the above list using three-way merge sort (where for this problem we define a step as a partitioning of a list into thirds, and the sorting of any three already sorted sublists counts as two steps). Let $b$ be the number of steps to sort the above list using insertion sort. Compute $|a - b|$ .

6. Consider the set $S = \{1, 2, ..., 15\}$ . We wish to make a set cover of $S$ . A set cover is a collection of sets $S_1, S_2, ..., S_k \subseteq S$ such that $\cup^{k}_{i = 1}S_i = S$ . However, the sets you have to choose from to make the set cover are predetermined. In this case you have a ``wild card" set $S_1 \subseteq S$ . It can be any subset of $S$ that you please. Moreover, you also have these other subsets of $S$ to consider:
$S_2 = \{1, 2, 3, 5, 6, 7, 8, 10, 11, 13, 15\}$ $S_3 = \{1, 4\}$ $S_4 = \{8, 9\}$ $S_5 = \{2, 7\}$ $S_6 = \{12, 13, 15\}$ $S_7 = \{2, 3, 5, 8, 14\}$ You wish to make a set cover using $S_1$ and exactly three of the other sets $S_2, S_3, S_4, S_5, S_6,$ and $S_7$ . What is the smallest possible cardinality of $S_1$ ?

This post has been edited 2 times. Last edited by Kingofmath101, Aug 4, 2017, 10:23 PM

Mathematics Competitions

CMIMC

computer science

algorithms

CMIMC Proposed Problems- Number Theory

by Kingofmath101, Jul 27, 2017, 4:29 AM

1. Let $F_n$ denote the Fibonacci numbers where $F_1 = 1$ , $F_2 = 1$ , $F_3 = 2$ , and so on. Let $G_n$ denote another sequence called the Gigafibonacci numbers where $\forall n \in \mathbb{N}^+$ , we have $G_n = F_n + F_{n + 1} + F_{n + 2}$ . Compute $G_{2016} \mod 2016$ .

2. How many positive perfect squares strictly less than $7056^3$ exist?

3. Let $k_1$ , $k_2$ , ..., $k_{2016}$ be consecutive positive integer solutions to the linear congruence $4x + 5 \equiv 1 \mod 8$ . Compute $\frac{k_1 + k_2 + ... + k_{2016}}{2}\mod 2016$ .

Mathematics Competitions

CMIMC

number theory

CMIMC Proposed Problems- Combinatorics

by Kingofmath101, Jul 27, 2017, 4:26 AM

1. Consider this 1-player version of Whack-a-mole, where the board has 10 holes labelled $1, 2, ..., 10$ . At the start of the game, all of the holes are empty except for hole 1, out of which a single mole rises. A turn consists of the player randomly hitting exactly one mole. At the end of each turn each hole has an independent $\frac{1}{8}$ probability of a mole popping out. If at the beginning of a turn there are no moles to whack, the turn immediately ends. If a mole is not whacked, it stays put; if it is whacked, it crawls back into the hole. What is the expected number of turns that must pass before the player is faced with a mole in every hole?

2. How many ways are there to arrange the phrase "COLORFUL TARTAN" into an eight-word block and a six-word block where neither block of letters has two of the same letter? (specifically, the two Es in the phrase must be in different blocks of letters, among others).

3. Find the sum of all positive integers between $1$ and $2016$ (inclusive) that are not multiples of $2$ or $7$ (or both $2$ and $7$ ). (this could also be viewed as an algebra problem in some respect)

4. Find the number of $12$ -bit binary strings that possess at least one of the following properties:
-There are exactly $4$ ones in the string
-Both the first and the last bit are $1$ s (there may be more $1$ s than these two)\end{enumerate}

5. Andrew and Bert are playing Tic-Tac-Toe on a standard 3-by-3 Tic-Tac-Toe game board with the usual game rules. Andrew uses "X"s and moves first, while Bert uses "O"s and moves second. Andrew makes his first move in the center square of the board. From there, Bert and Andrew move in succession, twice for each player, picking a random unoccupied square in which to make a move. At this point there are three "X"s and two "O"s on the board. Assuming Andrew has not yet won (i.e. placed "X"s in three squares in a row), what is the probability that Bert will win on his next move?

6. You roll a pair of standard six-sided die fifteen times. Define a \textit{consecutive nine} to be the event where not only one rolling of the pair of dice gives two faces which sum to $9$ , but either the previous rolling or the next rolling also summed to $9$ (or both). The expected number of consecutive nines can be written in the form $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Compute $a + b$ .

7. We have a collection of fair six-sided dice, which we label $1$ through $n$ for some positive integer $n \geq 2$ . For each $i \in \{1, 2, 3, ..., n\}$ , the sides of the $i$ th die are labelled as $i$ , $i + 1$ , $i + 2$ , $i + 3$ , $i + 4$ , and $i + 5$ . Moreover, let $X_i$ be the random variable denoting the value that die $i$ shows if it is rolled once.

Abhl plays the following game. He rolls the $n$ dice in order. For the second die onward, he looks at what number the previous die landed on. If that number is on the die he is about to roll, he paints over that number and replaces it with a $0$ --unless he did this to the previous die--and then he rolls the next die. Abhl's score is the sum of what all $n$ die land on. If his expected score where $n = 2017$ is computed, it can be written as the form $\frac{a}{2} + b \cdot 2017$ , where $a$ and $b$ are positive integers. Compute $(a + b) \mod 1000$ .

8. Find the sum of the digits of the value of

$\sum^{12}_{b = 0}\sum^{b}_{c = 0}\dbinom{6}{b - c}\dbinom{6}{c}.$
9. We denote $K_6$ to be the complete graph in six vertices. Its vertex set is $[6]$ , or equivalently, $\{1, 2, 3, 4, 5, 6\}$ . Moreover, its edge set is $\dbinom{[6]}{2}$ . Now, let $e$ be an arbitrary edge in $\dbinom{[6]}{2}$ . Consider the graph $G$ with the same vertex set as $K_6$ and edge set $\dbinom{[6]}{2}\setminus \{e\}.$ Let us pick five edges at random from $G$ 's edge set. Upon finding the probability that this selection of edges forms a three-clique (three vertices that connect to each other to form a triangle), you realize it will be of the form $\frac{a}{b},$ where $a$ and $b$ are relatively prime positive integers. Compute $a + b$ .

10. Twenty people are sitting around a circular table, each with a plate of lasagna in front of them. The people are numbered $1$ through $20$ in a counterclockwise fashion. Between each adjacent pair of people is a single fork. However, five of the forks were randomly contaminated, and the diners knowing which ones they were, threw them away. Then, in the order in which the people were numbered, they randomly pick up one fork next to them and eat (if both of a person's adjacent forks were thrown away, they do not eat). A fork is called sauce-covered if at least one person uses it to eat. After every person has picked up a fork (or been deemed unable to do so), what is the expected number of sauce-covered forks?

Mathematics Competitions

CMIMC

combinatorics

CMIMC Proposed Problems-Geometry

by Kingofmath101, Jul 27, 2017, 4:18 AM

1. How many isosceles triangles with side lengths $6$ , $6$ , and $a$ have an integer area, where $a$ is an integer?

geometry

Mathematics Competitions

CMIMC

CMIMC Proposed Problems

by Kingofmath101, Jul 27, 2017, 4:17 AM

I have spent two years contributing to the advent of the Carnegie Mellon Informatics and Mathematics Competition (see http://cmimc.org). This has caused me to write a number of problems specifically for this cause, although not all problems were used for the competition itself. I am going to share these problems over a series of posts (without solutions) organized by category for your solving pleasure. Enjoy!

Mathematics Competitions

CMIMC

Unique Proof of Trigonometric Inequality

by Kingofmath101, Jul 19, 2017, 9:34 PM

We present a new proof to the inequality $t - 1 + \cos t \geq 0$ on the nonnegative reals. Equivalently, we will show that $t \geq 1 - \cos t$ . Let $x(t) = e^t$ and $\alpha(t) = \sin t$ . Let $t \geq 0$ be arbitrary. Also note that $\alpha(t)$ is bounded above by the constant $1$ on all real numbers and that $e^t > 0$ for all $t \in \mathbb{R}$ , so it follows that

$e^t\sin t \leq e^t$
In other words, $x(t)\alpha(t) \leq \frac{dx}{dt}$ . Since $\alpha(t)$ is continuous (namely on the nonnegative numbers), we can apply Gronwall's Inequality to obtain the bound

$x(t) \geq x(0)e^{\int^{t}_{0}\alpha(s)ds} \Rightarrow$ $e^t \geq 1 \cdot e^{\int^{t}_{0}\sin s ds} \Rightarrow$ $e^t \geq e^{1 - \cos t}$
Taking the natural logarithm of both sides produces the desired result. $\square$

Counting in Two Ways

by Kingofmath101, Jun 8, 2017, 4:55 AM

We prove the following result from Stasys Jukna's book Extremal Combinatorics, which the author posed as an exercise. Let $0 \leq k \leq n$ , and we prove

$\dbinom{n}{2} = \dbinom{k}{2} + k(n - k) + \dbinom{n - k}{2}$
Combinatorial Proof: We will use a counting-in-two-ways argument. Let's say we are enumerating the edges of a complete graph on $n$ edges. The LHS represents the trivial quantity of edges in the complete graph $K_n$ . However, we can count said edges in another manner. Partition the vertex set of $K_n$ into two sets of vertices, with $k$ and $n - k$ vertices, respectively. Call these vertex subsets Group A and Group B respectively. We can partition the edge set of $K_n$ as follows: edges between two vertices from Group A, edges between a vertex from Group A and a vertex from Group B, and edges between two vertices from Group B. The number of such edges in each category is $\dbinom{k}{2}$ , $k(n - k)$ , and $\dbinom{n - k}{2}$ respectively, and the desired result holds. $\square$

Algebraic Proof: We also provide the binomial coefficient expansion proof:

$\dbinom{n}{2} = \dbinom{k}{2} + k(n - k) + \dbinom{n - k}{2} \Leftrightarrow$ $\frac{n!}{2!(n - 2)!} = \frac{k!}{2!(k - 2)!} + kn - k^2 + \frac{(n - k)!}{2!(n - k - 2)!} \Leftrightarrow$ $\frac{n!}{(n - 2)!} = \frac{k!}{(k - 2)!} + 2kn - 2k^2 + \frac{(n - k)!}{(n - k - 2)!} \Leftrightarrow$ $n(n - 1) = k(k - 1) + 2kn - 2k^2 + (n - k)(n - k - 1) \Leftrightarrow$ $n^2 - n = k^2 - k + 2kn - 2k^2 + n^2 - kn - n - kn + k^2 + k \Leftrightarrow$ $-n = k^2 - k + 2kn - 2k^2 - 2kn - n + k^2 + k \Leftrightarrow$ $0 = -k^2 - k + k^2 + k \Leftrightarrow$ $0 = 0,$
as desired. $\square$

combinatorics

graph theory

binomial coefficients

algebra

Kingofmath101's Math Blog 2.0

by Kingofmath101, Aug 4, 2017, 10:37 PM

by Kingofmath101, Jul 27, 2017, 4:40 AM

by Kingofmath101, Jul 27, 2017, 4:33 AM

by Kingofmath101, Jul 27, 2017, 4:32 AM

by Kingofmath101, Jul 27, 2017, 4:29 AM

by Kingofmath101, Jul 27, 2017, 4:26 AM

by Kingofmath101, Jul 27, 2017, 4:18 AM

by Kingofmath101, Jul 27, 2017, 4:17 AM

by Kingofmath101, Jul 19, 2017, 9:34 PM

by Kingofmath101, Jun 8, 2017, 4:55 AM