0
$\begingroup$

30 buses are used to transport 2000 passengers. Each bus has 80 seats and each passenger will occupy exactly one seat.

Consider the following statement: At least X buses will carry at least 67 passengers and at least Y buses will have at least 14 vacant seats.

Assuming that this statement is always true irrespective of the way passengers are assigned to buses, what are the maximum possible values of X and Y?

$\endgroup$
1
  • $\begingroup$ Use the extended pigeonhole principle $\endgroup$
    – nir shahar
    Aug 13, 2021 at 16:28

1 Answer 1

1
$\begingroup$

Let's try to find a feasible allocation of passengers to buses that minimizes $X$. Let's consider the ideal situation in which all non-empty buses, except possibly one, are filled with one less than $67$ passengers (i.e., with $66$ passengers).

In this setting the number of buses needed to transport $2000$ people is $\left\lceil \frac{2000}{66} \right\rceil = 31$, which is not feasible. Therefore we need at least one bus with at least $67$ people. Unfortunately using exactly one bus with at least $67$ people is also not feasible since we would be able to carry at most $29 \cdot 66 + 80 = 1994$ people. We can however allocate $66$ people per bus to $28$ buses and the remaining $152$ people to the remaining two buses. This shows that $X=2$.

Let's now try to find an allocation that minimizes $Y$. We want as few buses as possible to have at least $14$ vacant seats, i.e., we want as many buses as possible to have at least $80-14 + 1 =67$ passengers. The maximum number of buses with at least $67$ passengers is $ \left\lfloor \frac{2000}{67} \right\rfloor = 29$. This shows that $Y = 1$ (we can allocate $67$ people per bus to $29$ buses, and the remaining $57$ people to the final bus).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.