At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid?
Solution
To determine the maximum total amount the university could have paid, we can model the problem using graph theory. Consider a graph with 2017 edges, where each edge represents a pair of distinct entrées ordered by a mathematician. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée.
We seek to maximize the sum
where denotes the degree of vertex .
The optimal configuration is achieved by the graph , which consists of a clique on 64 vertices plus an additional vertex connected to one vertex of the clique. This graph has vertices and edges. The sum is given by:
Calculating this, we find:
Thus, the maximum total amount the university could have paid is: