Kvant Math Problem 970

Let the 32 stops lie on a line in increasing order of distance from the initial point, labeled $1,2,\dots,32$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 10m54s
Source on kvant.digital

Problem

At the initial stop, 32 passengers boarded a bus, each of whom needs to travel to 32 different stops located 1 km apart from each other. The driver decided to hold a vote on which stops to cancel and which to keep. He announces the stops in some order. A passenger votes for cancellation if they intend to travel further, votes against if they intend to get off at that stop, and abstains if they are supposed to get off earlier (not taking into account that, in later voting, their stop may also be cancelled). If there are more votes for cancellation than against, the stop is cancelled, and those who intended to get off there decide to travel to the nearest among the remaining non-cancelled stops (if there are two such stops, to the first of them).

What is

  1. the minimum,
  2. the maximum

number of stops that can remain depending on the order in which the driver announces them?

S. L. Eliseev

Exploration

Let the 32 stops lie on a line in increasing order of distance from the initial point, labeled $1,2,\dots,32$. Each passenger is assigned a distinct destination stop, so exactly one passenger has destination $k$ for each $k\in{1,\dots,32}$.

When stop $s$ is announced, passengers behave according to their fixed destination:

A passenger with destination $t>s$ votes for cancellation, since they still need to travel further along the route. A passenger with destination $t=s$ votes against cancellation, since they intend to get off there. A passenger with destination $t<s$ abstains.

Thus, at the moment stop $s$ is voted on, the number of “for” votes equals the number of destinations greater than $s$, while the number of “against” votes is always exactly $1$. This suggests that cancellation depends only on $s$, not on the order of announcement, but it is necessary to check carefully that no earlier cancellation or redirection changes voting behavior in a way that affects later outcomes.

The only potentially delicate point is whether reassigning passengers who were supposed to get off at cancelled stops could alter later vote counts; however, voting depends only on intended destinations relative to the announced stop, not on actual travel outcomes.

This indicates a strong rigidity in the system, suggesting that the number of remaining stops may be invariant.

Problem Understanding

This is a Type A problem. One must determine all possible numbers of stops that can remain after the cancellation process, depending on the order in which stops are announced.

The key difficulty is to determine whether the dynamic redistribution of passengers after cancellations can influence later votes, or whether the voting outcome at each stop is determined solely by the static configuration of destinations.

The analysis suggests that the process is rigid, and the final number of remaining stops is independent of the announcement order. The expected result is a single value.

Proof Architecture

The first lemma establishes the exact composition of votes at a stop $s$, showing that it depends only on the relative order of destinations.

The second lemma shows that cancellation of a stop does not change the voting behavior at any other stop.

The third lemma determines precisely for which values of $s$ cancellation occurs by comparing the number of “for” and “against” votes.

The fourth lemma concludes that exactly two stops are never cancelled.

The most delicate point is the second lemma, since it requires verifying that rerouting passengers after cancellations does not affect future vote counts.

Solution

Let the stops be labeled $1,2,\dots,32$ along the route in increasing order of distance from the initial point. For each $k\in{1,\dots,32}$, exactly one passenger has destination $k$.

Fix a stop $s$ at the moment it is announced. Consider the set of all passengers.

A passenger with destination $t>s$ has not yet reached their intended stop, so they vote for cancellation. The number of such passengers is $32-s$, since exactly the destinations $s+1,s+2,\dots,32$ lie above $s$.

A passenger with destination $t=s$ votes against cancellation, and this is exactly one passenger.

A passenger with destination $t<s$ abstains by the rules of the process.

Therefore, at the announcement of stop $s$, the number of votes for cancellation is $32-s$, and the number of votes against is $1$.

The rule states that the stop is cancelled if and only if the number of votes for cancellation is strictly greater than the number of votes against, which is equivalent to

$32-s>1,$

that is,

$s<31.$

Hence every stop $s\in{1,2,\dots,30}$ is cancelled whenever it is announced, while stops $31$ and $32$ are never cancelled.

The order of announcement does not affect this conclusion, since the quantities $32-s$ and $1$ depend only on the label $s$ and not on the sequence in which stops are processed. Cancellation of a stop does not remove passengers from the system; it only redirects those who intended to get off there, while voting behavior remains determined by original destinations. Thus no future vote is altered by previous cancellations.

Consequently, regardless of the announcement order, exactly two stops remain un-cancelled, namely stops $31$ and $32$.

Therefore both the minimum and the maximum possible number of remaining stops equal $2$, and the set of all possible values consists of the single number $2$.

$$\boxed{2}$$

Verification of Key Steps

The critical point is the computation of vote counts at a fixed stop $s$. The partition of passengers into those with destinations greater than, equal to, or less than $s$ is exhaustive and independent of any earlier cancellations, since every passenger retains their original destination throughout the process.

The second delicate point is the claim that rerouting passengers after a cancellation does not affect future voting. Voting at a later stop $t$ depends only on whether a passenger’s destination is greater than, equal to, or less than $t$, which is unaffected by any previous rerouting of intermediate stops.

The final inequality check $32-s>1$ is exact, and the threshold $s=30$ is the last value satisfying strict inequality, ensuring precisely two non-cancelled stops.

Alternative Approaches

One can view the process as assigning to each stop $s$ a fixed score $32-s-1$, independent of order. A stop is cancelled exactly when this score is positive, so the process reduces to a static threshold problem. This viewpoint removes any need to discuss dynamics and makes the invariance under announcement order immediate, but it is less directly tied to the voting interpretation than the main argument.