HMMT 十一月 2019 · 团队赛 · 第 2 题
HMMT November 2019 — Team Round — Problem 2
题目详情
英文原题
- [20] 2019 students are voting on the distribution of N items. For each item, each student submits a voteon who should receive that item, and the person with the most votes receives the item (in case of a tie,
no one gets the item). Suppose that no student votes for the same person twice. Compute the maximumpossible number of items one student can receive, over all possible values of N and all possible ways ofvoting.
解析
英文解析
- [20] 2019 students are voting on the distribution of N items. For each item, each student submits a voteon who should receive that item, and the person with the most votes receives the item (in case of a tie,
no one gets the item). Suppose that no student votes for the same person twice. Compute the maximumpossible number of items one student can receive, over all possible values of N and all possible ways ofvoting.
Proposed by: Milan Haiman
Answer: 1009
To get an item, a student must receive at least 2 votes on that item. Since each student receives at most
2019
2019 votes, the number of items one student can receive does not exceed = 1009 . 5. So, the answer isat most 1009. This occurs when N = 2018 and item i was voted to student 1 , 1 , 2 , 3 , . . . , 2018 by student 2
2 i − 1 , 2 i − 2 , . . . , 2019 , 1 , . . . , 2 i − 2 respectively for i = 1 , 2 , . . . , 2018. Thus, the maximum possible numberof items one student can receive is 1009.