Problem 1450

### Part (a)
1. Graph Representation: Represent the problem using graph theory. Let each student be a vertex in a graph $G$ with $n$ vertices. Each student can choose $k$ other students with whom calls are free. This can be represented as a directed graph where each vertex has an outdegree of at most $k$.

2. Contradiction Approach: Assume that all calls between any two students are free. This implies that the underlying undirected graph is a complete graph $K_n$.

3. Degree Condition: In a complete graph $K_n$, each vertex has a degree of $n-1$. However, in our directed graph, each vertex has an outdegree of at most $k$. Therefore, the total number of directed edges is at most $nk$.

4. Edge Counting: In a complete graph $K_n$, the total number of edges is $\frac{n(n-1)}{2}$. For $n \geq 2k+2$, we have:
$$\frac{n(n-1)}{2} > nk$$
Simplifying this inequality:
$$\frac{n(n-1)}{2} > nk \implies n(n-1) > 2nk \implies n-1 > 2k \implies n > 2k + 1$$
This contradicts our assumption that $n \geq 2k+2$.

5. Conclusion: Therefore, there must exist at least one pair of students who will be charged when speaking.

$\blacksquare$

### Part (b)
1. Graph Representation: Again, represent the problem using graph theory. Let each student be a vertex in a graph $G$ with $n = 2k+1$ vertices. Each student can choose $k$ other students with whom calls are free.

2. Construction of Free Call Arrangement: We need to show that there exists a way to arrange the free calls such that everybody can speak free to anybody else in the group.

3. Perfect Matching in Bipartite Graph: Consider a bipartite graph $B$ with two sets of vertices $A$ and $B$, each containing $k+1$ vertices. Each vertex in $A$ is connected to exactly $k$ vertices in $B$, and vice versa. This ensures that each student can choose $k$ other students for free calls.

4. Hall's Marriage Theorem: By Hall's Marriage Theorem, if every subset of vertices in $A$ is connected to at least as many vertices in $B$, then there exists a perfect matching. Since $|A| = |B| = k+1$ and each vertex has $k$ connections, the conditions of Hall's Marriage Theorem are satisfied.

5. Conclusion: Therefore, there exists a way to arrange the free calls such that everybody can speak free to anybody else in the group.

$\blacksquare$