Мандарины в ящике (модификация задачи К. А. Кнопа)

[Ktina]

В ящике лежат 20 мандаринов. Известно, что любые 11 из них весят в сумме больше одного килограмма, а любые 10 весят в сумме меньше одного килограмма. Каково наименьшее возможное число мандаринов, весящих от 90 до 100 г?

[Cash]

Пусть $x_1 \ge x_2 \ge x_3 \ge \cdots \ge \x_{20}$ веса наших мандаринов в граммах.
Тогда не более, чем 9 из них весят более 100 г. То есть $x_{10} < 100$
Если $x_{11} < 90$, то $x_{10}+x_{11}+ \cdots + x_{20}<90 \cdot 10+100 = 1000$ - противоречие.
Значит, 2 мандарина должны быть.
Набор
$x_1= \cdots = x_9 = 100.5$,
$x_{10}=x_{11}=96$,
$x_{12} = \cdots = x_{20}=89.9$
удовлетворяет условию.

[Sender]

Не годится, первые 10 весят больше килограмма.

[Ktina]

Sender в сообщении #615100 писал(а):

Не годится, первые 10 весят больше килограмма.

Это - всего лишь несущественная деталь.
Вместо 100,5 можно взять $100+\epsilon$

-- 05.09.2012, 15:08 --

У меня решение было более длинное и менее умное, чем у Cash:

Очевидно, мандаринов, весящих больше 100 г, не более 9, а весящих менее 90 г - не более 10. Таким образом, мандаринов, не весящих от 90 до 100 г - не более 19. Следовательно, один искомый мандарин должен быть.
Пусть он ровно один. Тогда лёгких (тех, что меньше 90) будет ровно 10, а тяжёлых (больше 100) - ровно 9.
Расположим все 20 в порядке неубывания. Тогда вес 11-ти наилегчайших будет меньше килограмма.
Таким образом, искомых мандаринов не менее двух. Ситуация, когда их ровно два, возможна. В моём примере я тоже использовала число 96:

$$90-\epsilon,\quad 90-\epsilon,\quad 90-\epsilon,\quad \dots , \quad 90-\epsilon,\quad 96,\quad 96,\quad 100+\epsilon,\quad 100+\epsilon ,\quad 100+\epsilon, \dots , 100+\epsilon$$

(лёгких - 9 штук, искомых - 2, тяжёлых - 9)

[Cash]

Sender в сообщении #615100 писал(а):

Не годится, первые 10 весят больше килограмма.

Это описка. Веса первых девяти мандаринов я считал по $100.1$.

Интересно также посмотреть модификацию задачи, потребовав целочисленные значения. Например, вместо мандаринов у нас будут коробки со спичками. В любых 10 коробках менее 1000 спичек, в любых 11 - более 1000.

Пример с 5-ю строится легко, а вот доказать, что четырьмя обойтись нельзя?

-- Ср сен 05, 2012 16:54:09 --

Хотя тоже, наверное, не слишком сложно.
Доказываем, что $x_{12} \ge 90$, далее, что $x_9 \le 100$, или для случая 4 коробка "средних" размеров ими могут быть с 9-го по 12-й.
$3x_{10} \ge x_{10}+x_{11}+x_{12} > 1000 - 8 \cdot 89 =288$, откуда
$x_{10} >96$
$x_1+ \cdots+x_8+x_9+x_{10} > 101 \cdot 8 + 96 \cdot 2 =1000$

[vitalykurin]

Не очень четкая формулировка задачи, на самом деле. Вес мандаринов может быть любой? Минимальное количество ведь может зависеть от веса "неправильных" мандаринов. Если они весят по 101 г, то это одно дело. А если больше, то уже другие будут параметры.