Found problems: 373
Suppose that $X_1, X_2, \ldots$ are real numbers between 0 and 1 that are chosen independently and uniformly at random. Let $S=\sum_{i=1}^kX_i/2^i,$ where $k$ is the least positive integer such that $X_k<X_{k+1},$ or $k=\infty$ if there is no such integer. Find the expected value of $S.$
Let $A$ be the $n\times n$ matrix whose entry in the $i$-th row and $j$-th column is \[\frac1{\min(i,j)}\] for $1\le i,j\le n.$ Compute $\det(A).$
For each integer $n\ge 1,$ compute the smallest possible value of \[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\] over all permutations $(a_1,\dots,a_n)$ of $\{1,\dots,n\}.$
[i]Proposed by Shahjalal Shohag, Bangladesh[/i]
Find the sum of $1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdots+(n-1)(n-1)!+n\cdot n!$, where $n!=n(n-1)(n-2)\cdots2\cdot1$.
$a_{1}=5$ and $a_{n+1}=a_{n}^{3}-2a_{n}^{2}+2$ for all $n\geq1$. $p$ is a prime such that $p=3(mod 4)$ and $p|a_{2011}+1$. Show that $p=3$.
Let $N_{13}$ be the answer to problem 13, and let $k = \tfrac{1}{N_{13} + 6}$.
Compute the infinite product
\[ (1 - k + k^2)(1 - k^3 + k^6)(1 - k^9 + k^{18})(1 - k^{27} + k^{54})\cdots, \]
where the factors take the form $(1 - k^{3^a} + k^{2\cdot 3^a})$ for all nonnegative integers $a$.
Let $n \ge 2$ be a fixed integer. [list=a] [*]Determine the largest positive integer $m$ (in terms of $n$) such that there exist complex numbers $r_1$, $\dots$, $r_n$, not all zero, for which \[ \prod_{k=1}^n (r_k+1) = \prod_{k=1}^n (r_k^2+1) = \dots = \prod_{k=1}^n (r_k^m+1) = 1. \] [*]For this value of $m$, find all possible values of \[ \prod\limits_{k=1}^n (r_k^{m+1}+1). \] [/list]
[i]Kaixin Wang[/i]
Let $p=1601$. Prove that if
\[\dfrac {1} {0^2+1}+\dfrac{1}{1^2+1}+\cdots+\dfrac{1}{(p-1)^2+1}=\dfrac{m} {n},\]
where we only sum over terms with denominators not divisible by $p$ (and the fraction $\dfrac {m} {n}$ is in reduced terms) then $p \mid 2m+n$.
[i]Proposed by A. Golovanov[/i]
For an integer $ m$, denote by $ t(m)$ the unique number in $ \{1, 2, 3\}$ such that $ m \plus{} t(m)$ is a multiple of $ 3$. A function $ f: \mathbb{Z}\to\mathbb{Z}$ satisfies $ f( \minus{} 1) \equal{} 0$, $ f(0) \equal{} 1$, $ f(1) \equal{} \minus{} 1$ and $ f\left(2^{n} \plus{} m\right) \equal{} f\left(2^n \minus{} t(m)\right) \minus{} f(m)$ for all integers $ m$, $ n\ge 0$ with $ 2^n > m$. Prove that $ f(3p)\ge 0$ holds for all integers $ p\ge 0$.
[i]Proposed by Gerhard Woeginger, Austria[/i]
Suppose that a sequence $a_1,a_2,\ldots$ of positive real numbers satisfies \[a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}\] for every positive integer $k$. Prove that $a_1+a_2+\ldots+a_n\geq n$ for every $n\geq2$.
Let $n$ and $k$ be positive integers. Prove that for $a_1, \dots, a_n \in [1,2^k]$ one has
\[ \sum_{i = 1}^n \frac{a_i}{\sqrt{a_1^2 + \dots + a_i^2}} \le 4 \sqrt{kn}. \]
Alex calculated the value of function $f(n) = n^2 + n + 1$ for each integer from $1$ to $100$. Marina calculated the value of function $g(n) = n^2-n+1$ for the same numbers. Who of them has greater product of values and what is
their ratio?
Let the sum $\sum_{n=1}^{9} \frac{1}{n(n+1)(n+2)}$ written in its lowest terms be $\frac{p}{q}$ . Find the value of $q - p$.
Evaluate: $ \sum\limits_{k\equal{}1}^\infty \frac{1}{k\sqrt{k\plus{}2}\plus{}(k\plus{}2)\sqrt{k}}$
For all positive integers $k$, define $f(k)=k^2+k+1$. Compute the largest positive integer $n$ such that \[2015f(1^2)f(2^2)\cdots f(n^2)\geq \Big(f(1)f(2)\cdots f(n)\Big)^2.\][i]Proposed by David Altizio[/i]
Let $p$ be an odd prime, and put $N=\frac{1}{4} (p^3 -p) -1.$ The numbers $1,2, \dots, N$ are painted arbitrarily in two colors, red and blue. For any positive integer $n \leqslant N,$ denote $r(n)$ the fraction of integers $\{ 1,2, \dots, n \}$ that are red.
Prove that there exists a positive integer $a \in \{ 1,2, \dots, p-1\}$ such that $r(n) \neq a/p$ for all $n = 1,2, \dots , N.$
[I]Netherlands[/i]
Suppose that a sequence $a_1,a_2,\ldots$ of positive real numbers satisfies \[a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}\] for every positive integer $k$. Prove that $a_1+a_2+\ldots+a_n\geq n$ for every $n\geq2$.
Prove that for every real or complex $x$
$$\prod_{k=1}^{\infty} \frac{1+2\cos \frac{2x}{3^{k}}}{3} =\frac{\sin x}{x}.$$
For a permutation $\pi$ of the integers from 1 to 10, define
\[ S(\pi) = \sum_{i=1}^{9} (\pi(i) - \pi(i+1))\cdot (4 + \pi(i) + \pi(i+1)), \]
where $\pi (i)$ denotes the $i$th element of the permutation. Suppose that $M$ is the maximum possible value of $S(\pi)$ over all permutations $\pi$ of the integers from 1 to 10. Determine the number of permutations $\pi$ for which $S(\pi) = M$.
[i]Ray Li[/i]
In a dance party initially there are $20$ girls and $22$ boys in the pool and infinitely many more girls and boys waiting outside. In each round, a participant is picked uniformly at random; if a girl is picked, then she invites a boy from the pool to dance and then both of them elave the party after the dance; while if a boy is picked, then he invites a girl and a boy from the waiting line and dance together. The three of them all stay after the dance. The party is over when there are only (two) boys left in the pool.
(a) What is the probability that the party never ends?
(b) Now the organizer of this party decides to reverse the rule, namely that if a girl is picked, then she invites a boy and a girl from the waiting line to dance and the three stay after the dance; while if a boy is picked, he invites a girl from the pool to dance and both leave after the dance. Still the party is over when there are only (two) boys left in the pool. What is the expected number of rounds until the party ends?
Prove that if $N{}$ is a large enough positive integer, then for any permutation $\pi_1,\ldots,\pi_N$ of $1,\ldots, N$ at least $11\%$ of the pairs $(i,j)$ of indices from $1{}$ to $N{}$ satisfy $\gcd(i,j)=1=\gcd(\pi_i,\pi_j).$
[i]Proposed by Vlad Spătaru[/i]
The product of the $ 9$ factors $ \left (1\minus{}\frac{1}{2} \right ) \left (1\minus{}\frac{1}{3} \right ) \left (1\minus{}\frac{1}{4} \right ) \ldots \left (1\minus{}\frac{1}{10} \right )\equal{}$
\[ \textbf{(A)}\ \frac{1}{10} \qquad
\textbf{(B)}\ \frac{1}{9} \qquad
\textbf{(C)}\ \frac{1}{2} \qquad
\textbf{(D)}\ \frac{10}{11} \qquad
\textbf{(E)}\ \frac{11}{2}
\]
Two ducks, Wat and Q, are taking a math test with $1022$ other ducklings. The test has $30$ questions, and the $n$th question is worth $n$ points. The ducks work independently on the test. Wat gets the $n$th problem correct with probability $\frac{1}{n^2}$ while Q gets the $n$th problem correct with probability $\frac{1}{n+1}$. Unfortunately, the remaining ducklings each answer all $30$ questions incorrectly.
Just before turning in their test, the ducks and ducklings decide to share answers! On any question which Wat and Q have the same answer, the ducklings change their answers to agree with them. After this process, what is the expected value of the sum of all $1024$ scores?
[i]Proposed by Evan Chen[/i]
Let $f$ be a function from R to R. Suppose we have:
(1) $f(0)=0$
(2) For all $x, y \in (-\infty, -1) \cup (1, \infty)$, we have $f(\frac{1}{x})+f(\frac{1}{y})=f(\frac{x+y}{1+xy})$.
(3) If $x \in (-1,0)$, then $f(x) > 0$.
Prove: $\sum_{n=1}^{+\infty} f(\frac{1}{n^2+7n+11}) > f(\frac12)$ with $n \in N^+$.
Suppose that $a_1 = 2$ and the sequence $(a_n)$ satisfies the recurrence relation \[\frac{a_n -1}{n-1}=\frac{a_{n-1}+1}{(n-1)+1}\] for all $n \ge 2.$ What is the greatest integer less than or equal to \[\sum^{100}_{n=1} a_n^2?\]
$\textbf{(A) } 338{,}550 \qquad \textbf{(B) } 338{,}551 \qquad \textbf{(C) } 338{,}552 \qquad \textbf{(D) } 338{,}553 \qquad \textbf{(E) } 338{,}554$