Phone Company#13012

Phone Company (Editorial)

Author:

Adrian Miclaus

Solved by:

First to solve:

darkprinceee

There are \frac{n(n-1)}{2} pairs of students. Each individual selection (choosing one number) can cover at most one pair. Since each of the students makes selections, the total number of selections is , so necessarily nK \geq \frac{n(n-1)}{2}. We can divide by to get K \geq \frac{n-1}{2} \iff n \leq 2K+1. So no construction can work for n > 2K+1. Construction achieving n = 2K+1: Arrange students on a circle in the order 1,2,\dots,n. For each student , select the next students: i+1, i+2, \dots, i+K \pmod n.