The coffee machine

Number Theory Level 3

A University department, with ten professors, is considering buying a coffee machine to put in the professors' room. The machine costs 1000$. The professors are asked, in a private email, how much they are willing to spend, at most, to participate in the purchase and gain the right to use the machine. Each one answers with an amount. What is the minimal sum, in dollars, of these amounts that ensures the formation of a group of participants, of any size, among the professors, able to buy the machine, every participant paying the same amount and spending no more than what they wanted to?

The answer is 2922.

1 solution

Marcus Barão Camarão
Jun 10, 2016

If we label as $x_1$ through $x_{10}$ , in decreasing order, the amounts the professors are willing to spend, it is clear that the purchase will take place if there is an integer $n$ between $1$ and $10$ and at least $n$ professors willing to spend $\frac{1000}{n}$ dollars. The worst possible situation, then, corresponding with the highest sum of the $x_i$ that does not allow the purchase, happens when the "most willing" professor is willing to spend 999, the second one 499, etc. giving a sum

$999+499+333+249+199+166+142+124+111+99=2921$

and a situation in which the purchase is not guaranteed. Clearly, any sum higher than $2921$ ensures that for some index $n$ , $x_n$ is greater than $\frac{1000}{n}$ and thus, because of the decreasing order,

$x_1+\ldots +x_n \geq nx_n\geq 1000$ .

The coffee machine

The answer is 2922.

1 solution

0 pending reports