Problems by archive

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$. Prove that $\frac{a^2+b^2}{ab+1}$ is the square of an integer.

Show that there is no formula, built from the coefficients with addition, subtraction, multiplication, division and radicals, that gives the roots of every polynomial equation of degree five.

In a unique game, variables take labels from a set of size $k$, and each constraint on a pair of variables $(u,v)$ says that the label of $v$ is a fixed permutation of the label of $u$. Prove or refute that for every $\epsilon >0$ there is a $k$ such that it is NP-hard to distinguish instances…

$n$ runners start together on a circular track of length 1 and run forever, each at its own constant speed, with all speeds different. Prove that for each runner there is a moment when every other runner is at distance at least $1/n$ along the track. The speeds $0,1,\dots ,n-1$ show that $1/n$…

Find all functions $f:\mathbb{Q}\to \mathbb{Q}$ such that $f(x+y)=f(x)+f(y)$ for all rational $x$ and $y$.

A one-way function is a function $f$ that can be computed in polynomial time, but such that every probabilistic polynomial-time algorithm, given $f(x)$ for a uniformly random $x$, finds some preimage of $f(x)$ only with negligible probability. Prove or disprove that one-way functions exist.

Prove that for all positive real numbers $a$, $b$ and $c$ $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\ge \frac{3}{2}.$ When does equality hold?

A finite family of finite sets is union-closed if the union of any two members is again a member. Prove that every finite union-closed family that contains at least one nonempty set has an element lying in at least half of the sets of the family.

BPP is the class of decision problems solvable by a polynomial-time randomized algorithm that answers correctly with probability at least 2/3 on every input. Is every problem in BPP solvable by a deterministic polynomial-time algorithm, that is, is P = BPP?

Solve the system $x+y+z=6,xy+yz+zx=11,xyz=6.$

Let $C$ be any simple closed curve in the plane. Prove or disprove that $C$ always contains four points that are the vertices of a square.

Given an integer $N$ with $b$ bits, find its prime factorization. Is there a classical (non-quantum) algorithm that does this in time polynomial in $b$?

Find a rectangular box whose three edges, three face diagonals and space diagonal all have integer lengths, or prove that none exists. In other words, find positive integers $a,b,c$ such that $a^2+b^2$, $b^2+c^2$, $a^2+c^2$ and $a^2+b^2+c^2$ are all perfect squares.