KURSCHAK 2008

Denote by $d(n)$ the number of positive divisors of a positive integer $n$ . Find the smallest constant $c$ for which $d(n)\le c\sqrt n$ holds for all positive integers $n$ .

Let $n\ge 1$ and $a_1<a_2<\dots<a_n$ be integers. Let $S$ be the set of pairs $1\le i<j\le n$ for which $a_j-a_i$ is a power of $2$ , and $T$ be the set of pairs $1\le i<j\le n$ with $j-i$ a power of $2$ . (Here, the powers of $2$ are $1,2,4,\dots$ .) Prove that $|S|\le |T|$ .

In a far-away country, travel between cities is only possible by bus or by train. One can travel by train or by bus between only certain cities, and there are not necessarily rides in both directions. We know that for any two cities $A$ and $B$ , one can reach $B$ from $A$ , or $A$ from $B$ using only bus, or only train rides. Prove that there exists a city such that any other city can be reached using only one type of vehicle (but different cities may be reached with different vehicles).