AoPS - Problem

Source: Iran National Olympiad - 2014 Second Round - D2P3

Tags: floor function, function, combinatorics unsolved, combinatorics

Amir Hossein

08.05.2014 09:08

Members of "Professionous Riddlous" society have been divided into some groups, and groups are changed in a special way each weekend: In each group, one of the members is specified as the best member, and the best members of all groups separate from their previous group and form a new group. If a group has only one member, that member joins the new group and the previous group will be removed. Suppose that the society has $n$ members at first, and all the members are in one group. Prove that a week will come, after which number of members of each group will be at most $1+\sqrt{2n}$.

By analyzing small values, it appears that for $T_k \leq n < T_{k+1}$ (where $T_k = \dfrac {k(k+1)}{2}$ for $0\leq k$ is the $k$-th triangular number), for example \[ 5\to(4,1)\to(3,2)\to(2,2,1)\to(3,1,1)\to(3,2)\to \cdots\] \[ 6\to(5,1)\to(4,2)\to(3,2,1)\to(3,2,1)\to \cdots\] \[ 7\to(6,1)\to(5,2)\to(4,2,1)\to(3,3,1)\to(3,2,2)\to(3,2,1,1)\to(4,2,1)\to \cdots\] the least maximal size $f(n)$ of groups in a configuration is $f(n) = k = \left \lfloor -\dfrac {1}{2} + \sqrt{2n + \dfrac {1}{4}}\right \rfloor < \sqrt{2n}$. The function $f(n)$ is non-decreasing, increasing by $1$ precisely when $n$ is a triangular number. The sequence of configurations becomes periodical, with period of length $1$ when $n$ is a triangular number, and of length $f(n)+1$ when $n$ is not a triangular number (starting with the $(n-f(n)+1)$-th term when $n$ is a triangular number, and with the $(n-f(n))$-th term when $n$ is not a triangular number). The first term containing a group with $f(n)$ members is the $(n-f(n)+1)$-th. Of course, all these are for the moment just conjectures, waiting to be proved.