a) Ostap could not take the last, 2002nd place in the first round, as otherwise he would have been immediately eliminated from the candidates. Therefore, $k \leq 2001$.

Suppose all candidates in the first round received almost the same number of votes, Ostap took the second-to-last place, and in each subsequent round, he received all the votes of the eliminated candidate. Then Ostap will win when the number of eliminated candidates reaches half. This will happen precisely in the 1002nd round.

Let's perform an exact calculation in the case where the candidates in the first round received $10^{6}, 10^{6}+1, \ldots, 10^{6}+2001$ votes. Then in the 1001st round, Ostap still has less than half of the votes, specifically: the votes of all candidates who took the last 1001 places in the first round. However, in the 1002nd round, he already has more than half of all the votes.

Indeed, Ostap has

$10^{6}+\left(10^{6}+1\right)+\ldots+\left(10^{6}+1001\right)=$

$=1002 \times 10^{6} + (1001 \times 1002) / 2=$

$=1002 \times 10^{6} + 1001 \times 501 = 1002501501$

votes, while the total number of voters is

$10^{6}+\left(10^{6}+1\right)+\ldots+\left(10^{6}+2001\right)=$

$=2002 \times 10^{6} + (2001 \times 2002) / 2=$

$=2002 \times 10^{6} + 2001 \times 1001 = 2004003001$.

It is easy to verify that this is less than twice the number of votes Ostap has.

b) Suppose $k>1$. The candidate who took first place in the first round will be called the favorite. Those who were eliminated in the first thousand rounds will be called underdogs, and all other candidates, except for Ostap, will be called leaders. Since the number of underdogs is 1000 and the number of leaders is 1001, one of the leaders did not receive votes from the underdogs. In the first round (and later), he had more votes than any underdog (since in the end, the underdog was eliminated, not this leader). Therefore, the favorite, who received the most votes in the first round, is not among the underdogs.

The maximum number of votes Ostap could have gathered by the 1001st round is all the votes of the underdogs at the time of their elimination and the votes of his initial supporters. Any leader in any of the first thousand rounds (and especially in the 1001st) has more votes than the underdog of that round. The favorite definitely has more votes than Ostap had in the first round. Therefore, the leaders collectively have more votes than Ostap in the 1001st round, and he cannot become the winner.

## Answer

$k=2001;$

b) $k=1$.

Submit a comment
![](https://cdn.mathpix.com/cropped/2024_05_06_caf98da37e6d9925b347g-49.jpg?height=40&width=249&top_left_y=732&top_left_x=13)

In the city of Udoyev, mayoral elections proceed as follows. If in a given round of voting no candidate receives more than half of the votes, a subsequent round is held with all candidates except the one with the fewest votes. (No two candidates ever receive the same number of votes; if a candidate receives more than half of the votes, they become mayor and the election ends.) Each voter votes for one candidate in each round. If the candidate advances to the next round, the voter votes for them again. If the candidate is eliminated, all their voters vote for the same remaining candidate.

In the upcoming election, 2002 candidates ran. Ostap Bender became mayor, finishing in $k$-th place in the first round. Determine the maximum possible value of $k$ if Ostap Bender was elected

a) in the 1002nd round;

b) in the 1001st round.