PUMaC 2016 · 组合（A 组） · 第 8 题
PUMaC 2016 — Combinatorics (Division A) — Problem 8
题目详情
- Katie Ledecky and Michael Phelps each participate in 7 swimming events in the Olympics (and there is no event that they both participate in). Ledecky receives g gold, s silver, and b L L L bronze medals, and Phelps receives g gold, s silver, and b bronze medals. Ledecky notices P P P that she performed objectively better than Phelps: for all positive real numbers w < w < w , b s g we have w g + w s + w b > w g + w s + w b . g L s L b L g P s P b P Compute the number of possible 6-tuples ( g , s , b , g , s , b ). L L L P P P 1
解析
- We claim that Ledecky performs objectively better than Phelps if and only if g ≥ g , g + s ≥ L P L L g + s , and g + s + b ≥ g + s + b , but it is not the case that g = g , s = s , and P P L L L P P P L P L P b = b . First, assume that all these conditions are satisfied. Let 0 < w < w < w be the L P b s g weights and let m = w , m = w − w , and m = w − w (all positive values). Note that b b s s b g g s w g + w s + w b = m ( b + s + g ) + m ( s + g ) + m g g L s L b L b L L L s L L g L and similarly for Phelps. Thus, w g + w s + w b > w g + w s + w b . g L s L b L g P s P b P Now assume that at least one of these conditions fails. If g < g then letting w = 1, L P g w = . 02, and w = . 01 makes Ledecky’s score lower than Phelps’s. If g + s ≥ g + s s b L L P P then letting w = 1, w = . 99, and w = . 01 makes Ledecky’s score lower than Phelps’s. If g 2 b g + s + b ≥ g + s + b then letting w = 1, w = . 99, and w = . 98 makes Ledecky’s L L L P P P g 2 b score lower than Phelps’s. Finally, if g = g , s = s , and b = b , then Ledecky’s score L P L P L P equals Phelps’s regardless of the weights. Now for the computation. Give Ledecky and Phelps each an extra silver and bronze medal; this doesn’t change the calculus. Note that ( g , s , b ) can now be represented by placing L L L three bars in different places among twelve stars representing the events. For example, the configuration ∗∗ | ∗ | ∗∗∗∗∗ | ∗ represents that Ledecky got 2 gold, 1 silver, and 5 bronze medals, and did not receive a medal in one event. We can represent ( g , s , b ) and ( g , s , b ) in L L L P P P 2 this manner and then smoosh the two representations together, removing duplicate bars (ones that are in the same place). The resulting figure has at least 3 and at most 6 bars among 9 stars. To do our counting, be go in the other direction: for every smooshed representation we find the number of representations for Ledecky and Phelps whose smooshing gives the desired smooshed representation, where Ledecky objectively outperforms Phelps. We do this using casework based on the number of bars in the smooshed representation. Case 1: 3 bars. Then Ledecky and Phelps got the same number of gold, silver, and bronze medals, so Ledecky could not have objectively outperformed Phelps. Case 2: 4 bars. Then Ledecky and Phelps have two bars in common and each have one bar that the other doesn’t. For each configuration, this gives 12 possibilities, and the ones in which Ledecky objectively outperforms Phelps are the ones in which her bar comes first. So there ( ) 10 are 6 possibilities. There are ways to place four bars among nine stars so that none of the 4 bars are next to each other. Case 3: 5 bars. There are 5 ways to choose the bar in common. Among the other four bars, ( ) 10 the order must be LLPP or LPLP, so there are 10 possibilities. There are ways to place 5 five bars among nine stars so that none of the bars are next to each other. Case 4: 6 bars. The order must be LLLPPP, LLPPLP, LPLLPP, LPLPLP, or LLPLPP, so ( ) 10 there are 5 possibilities. There are ways to place six bars among nine stars so that none 6 of the bars are next to each other. ( ) ( ) ( ) 10 10 10 Thus, the answer is 6 + 10 + 5 = 4830 . 4 5 6 Problem written by Eric Neyman. If you believe that any of these answers is incorrect, or that a problem had multiple reason- able interpretations or was incorrectly stated, you may appeal at tinyurl.com/pumacappeals . All appeals must be in by 1 PM to be considered. 3