archive

Start with any positive integer $n$. If $n$ is even, replace it by $n/2$, and if $n$ is odd, replace it by $3n+1$. Repeat this forever. Prove or disprove that every starting value eventually reaches 1.

Let $x_1$ and $x_2$ be the roots of $x^2+px+q=0$. Express $x_1^3+x_2^3$ in terms of $p$ and $q$ without solving the equation.

P is the class of decision problems that can be solved in polynomial time, and NP is the class of decision problems whose yes answers can be checked in polynomial time given a suitable certificate. Is P equal to NP? Equivalently, does some NP-complete problem, such as Boolean satisfiability, have a…

Twin primes are pairs of primes that differ by 2, such as $11,13$ or $41,43$. Prove that there are infinitely many twin prime pairs.

Given two graphs on $n$ vertices, decide whether they are isomorphic, that is, whether some relabeling of the vertices of one turns it into the other. Is there an algorithm that does this in time polynomial in $n$?

Prove that every even integer greater than 2 is the sum of two primes. For example $28=5+23$ and $100=3+97$.

Find all polynomials $P$ with real coefficients such that $P(x^2)=P(x{)}^2$ for every real $x$.

Let $\omega$ be the infimum of all real $c$ such that two $n\times n$ matrices can be multiplied using $\mathcal{O}(n^c)$ arithmetic operations. The schoolbook method shows $\omega \le 3$, and $\omega \ge 2$ because the output has $n^2$ entries. Is $\omega =2$?

Find the value of $\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots }}}}$ and explain in what sense the infinite expression has a value.

Prove that for every positive integer $n$ $1^3+2^3+\cdots +n^3=(1+2+\cdots +n{)}^2.$

Color every point of the plane so that any two points at distance exactly 1 receive different colors. What is the smallest number of colors for which this is possible? It is known that the answer is 5, 6 or 7. Determine it.

Prove that for positive real numbers $x_1,\dots ,x_n$ $\frac{x_1+\cdots +x_n}{n}\ge \sqrt[n]{x_1{x}_2\cdots x_n},$ with equality only when all the $x_i$ are equal.