Problems by archive

Give a deterministic algorithm that decides whether an integer $n$ is prime in time polynomial in the number of digits of $n$, without relying on any unproved conjecture.

Prove that for every positive integer $n$ there is a prime number strictly between $n^2$ and $(n+1{)}^2$.

Is there an algorithm that, given the code of any program and an input, correctly decides whether the program eventually halts on that input? Prove your answer.

A Hadamard matrix of order $n$ is an $n\times n$ matrix $H$ with entries $\pm 1$ whose rows are mutually orthogonal, so that $H{H}^T=nI$. Such a matrix can exist only if $n$ is 1, 2 or a multiple of 4. Prove that a Hadamard matrix exists for every multiple of 4.

Is there an algorithm that takes any polynomial equation with integer coefficients, in any number of unknowns, and decides whether it has a solution in integers?

Let $N(a)$ be the number of times the integer $a>1$ appears in Pascal's triangle. For example, $N(3003)=8$. Is there a constant $M$ with $N(a)\le M$ for every $a>1$?

Can the integers $1,2,\dots ,N$ be colored red and blue so that no Pythagorean triple $a^2+b^2=c^2$ has $a$, $b$ and $c$ all the same color? Find the largest $N$ for which this is possible, or show that it is possible for every $N$.

Prove that the regions of any map drawn in the plane can be colored with at most four colors so that any two regions sharing a border of positive length get different colors. Equivalently, prove that every planar graph is 4-colorable.

Among all Turing machines with 5 states and 2 symbols that halt when started on a blank tape, what is the largest number of steps $S(5)$ taken before halting? Determine $S(5)$ and prove that every 5-state machine that runs longer never halts.

Prove that the equation $a^n+b^n=c^n$ has no solution in positive integers $a,b,c$ when $n$ is an integer greater than 2.