MathDB

An infinite number of participants gathered for the Olympiad, who were registered under the numbers

1, 2,\ldots

. It turns out that for every

n = 1, 2,\ldots

a participant with number

n{}

has at least

n{}

friends among the remaining participants (note: friendship is mutual). There is a hotel with an infinite number of double rooms. Prove that the participants can be accommodated in double rooms so that there is a couple of friends in each room.
Proposed by V. Bragin, P. Kozhevnikov

Problem Statement