PUMaC 2017 · 团队赛 · 第 7 题

PUMaC 2017 — Team Round — Problem 7

(5) 2017 voters vote by submitting a ranking of the integers { 1 , 2 , . . . , 38 } from favorite (a vote for that value in 1st place) to least favorite (a vote for that value in 38th/last place). Let a be the integer that received the most k th place votes (the smallest such integer if there is k 38 ∑ a tie). Find the maximum possible value of a . k k =1

解析

Each number receives, on average, ≈ 53 . 1 votes in a given spot. Clearly 38 cannot be 38 every entry on the composite ranking, because it can only be voted for 2017 times and by the pidgeonhole principle it would have to get voted for at least 54 times each time it wins. However, it can win 36 times; that would account for 1944 votes. (It can’t win 37 times because while that would account for only 1998 votes, if it receives exactly 54 votes each time it wins and an extra votes 19 of those times there would be issues with the other numbers receiving exactly 53 votes, since 53 · 37 + 54 = 2015, so there would be two leftover votes each of those times. Allocating the extra 54 votes on top of the 18 would enable us to instead accomplish this, since a tie goes to the lower number.) We see that we now have ample room to awards the two remaining spots in the composite ranking to 37, making our total 38 · 36 + 37 · 2 = 1442 . Problem written by Zack Stier 2