KURSCHAK 2016

Let $1\le k\le n$ be integers. At most how many $k$ -element subsets can we select from $\{1,2,\dots,n\}$ such that for any two selected subsets, one of the subsets consists of the $k$ smallest elements of their union?

Prove that for any finite set $A$ of positive integers, there exists a subset $B$ of $A$ satisfying the following conditions:

• if $b_1,b_2\in B$ are distinct, then neither $b_1$ and $b_2$ nor $b_1+1$ and $b_2+1$ are multiples of each other, and
• for any $a\in A$ , we can find a $b\in B$ such that $a$ divides $b$ or $b+1$ divides $a+1$ .

If $p,q\in\mathbb{R}[x]$ satisfy $p(p(x))=q(x)^2$ , does it follow that $p(x)=r(x)^2$ for some $r\in\mathbb{R}[x]$ ?