Maths Olympiad Prep

Library / /7 of 37

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine the maximum total amount the university could have paid, we can model the problem using graph theory. Consider a graph G G 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
S(G)=e=vwmin(deg(v),deg(w)), S(G) = \sum_{e = vw} \min(\deg(v), \deg(w)),
where deg(v) \deg(v) denotes the degree of vertex v v .

The optimal configuration is achieved by the graph L64 L_{64} , which consists of a clique on 64 vertices plus an additional vertex connected to one vertex of the clique. This graph has 64 64 vertices and (642)+1=2017 \binom{64}{2} + 1 = 2017 edges. The sum S(L64) S(L_{64}) is given by:
S(L64)=(k1)(k2)+1=63(642)+1. S(L_{64}) = (k-1) \binom{k}{2} + 1 = 63 \cdot \binom{64}{2} + 1.

Calculating this, we find:
S(L64)=6364632+1=632016+1=127008+1=127009. S(L_{64}) = 63 \cdot \frac{64 \cdot 63}{2} + 1 = 63 \cdot 2016 + 1 = 127008 + 1 = 127009.

Thus, the maximum total amount the university could have paid is:
127009. \boxed{127009}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.