Problems by archive

Given $n$ integers, decide whether some three of them sum to zero. A simple algorithm takes $\mathcal{O}(n^2)$ time. Is there an algorithm that runs in time $\mathcal{O}(n^{2-\epsilon })$ for some fixed $\epsilon >0$?

Prove that for every integer $n\ge 2$ there are positive integers $x,y,z$ with $\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}.$

For a sequence $S$ of accesses to keys in a binary search tree with $n$ keys, let $\mathrm{OPT}(S)$ be the minimum total cost of serving $S$ by any binary search tree algorithm that may rotate the tree, even one that knows $S$ in advance. Prove or disprove that splay trees serve every access…

A positive integer is perfect if it equals the sum of its proper divisors, like $6=1+2+3$ and $28=1+2+4+7+14$. Every known perfect number is even. Is there an odd perfect number?

A sorting network on $n$ wires is a fixed sequence of comparators, each of which swaps the values on two wires if they are out of order, such that every possible input comes out sorted. What is the minimum number of comparators in a sorting network for $n=13$ inputs?

Let $f(N)$ be the smallest number such that any $f(N)$ points in the plane, no three on a line, include $N$ points that are the vertices of a convex polygon. Prove or disprove that $f(N)=2^{N-2}+1$ for every $N\ge 3$.

Given a real $m\times n$ matrix $A$ and a vector $b\in {\mathbb{R}}^m$, decide whether there is $x\in {\mathbb{R}}^n$ with $Ax\ge b$. Is there an algorithm whose number of arithmetic operations is bounded by a polynomial in $m$ and $n$ alone, independent of the size of the numbers in $A$ and $b$?

Euler's totient $\phi (n)$ counts the integers in $1,\dots ,n$ that are coprime to $n$. When $n$ is prime, $\phi (n)=n-1$, which certainly divides $n-1$. Is there a composite number $n$ for which $\phi (n)$ divides $n-1$?

Prove that every set of more than $2^{n-1}$ vertices of the $n$-dimensional hypercube induces a subgraph with a vertex of degree at least $\sqrt{n}$. Gotsman and Linial showed that this implies the sensitivity conjecture, that the degree and block sensitivity of a Boolean function are bounded by a…

The Riemann zeta function is defined by $\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$ for $\mathrm{Re}(s)>1$ and extended by analytic continuation to all complex $s\ne 1$. It vanishes at $s=-2,-4,-6,\dots$. Prove that every other zero of $\zeta$ has real part exactly $1/2$.