Maths Olympiad Prep

Library / /19 of 26

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Russia

In a canteen, there are 100100 apples of total weight 1010 kg, each apple weighs not less than 2525 g. The barman has to cut them into some pieces and distribute these pieces among 100100 students so that each student receives exactly 100100 g. Prove that the barman can attain this aim in such a way that the weight of each piece is at least 2525 g.

В буфете лежат 100100 яблок суммарного веса 1010 кг, каждое весит не меньше 2525 г. Буфетчице нужно разрезать их на части и раздать 100100 детям, каждому по 100100 г. Докажите, что она может это сделать так, чтобы любой кусок яблока весил не меньше 2525 г.

Solution

Все веса в решении будут измеряться в граммах. Назовём кусок яблока (или само яблоко) большим, если его вес не меньше 2525.

Докажем индукцией по nn, что nn больших яблок суммарного веса 100n100n можно разрезать на большие куски и раздать nn детям поровну.

База при n=1n = 1 очевидна.

Пусть n>1n > 1. Рассмотрим два самых тяжёлых яблока; пусть их веса aba \ge b. Заметим, что a+b200a + b \ge 200 (иначе средний вес одного яблока будет меньше, чем 200/2=100200/2 = 100).

Выкинем эти два яблока из набора и добавим в него яблоко веса c=a+b100100c = a + b - 100 \ge 100. По предположению индукции, полученный набор можно разрезать на большие куски и раздать n1n-1 детям поровну.

Если при этом какой-то кусок нового яблока оказался больше 5050, разрежем его на два больших куска. Через несколько таких разрезаний мы придём к ситуации, когда новое яблоко разделено на куски весов c1,c2,,ckc_1, c_2, \dots, c_k, не превосходящих 5050. Обозначим sd=c1++cds_d = c_1 + \dots + c_d при d=1,2,,kd = 1, 2, \dots, k и положим s0=0s_0 = 0.

Покажем теперь, как разрезать исходный набор. Все яблоки, кроме aa и bb, разрежем так же, как и в новом наборе. Заметим, что a200/2=100a \ge 200/2 = 100. Обозначим через tt минимальный индекс такой, что ast75a - s_t \le 75 и отрежем от aa куски c1,,ctc_1, \dots, c_t, а от bb — куски ct+1,,ckc_{t+1}, \dots, c_k. Заметим, что ast1>75a - s_{t-1} > 75, поэтому от aa остался кусок a=ast=(ast1)cta' = a - s_t = (a - s_{t-1}) - c_t такой, что 75a>75ct2575 \ge a' > 75 - c_t \ge 25. От bb же остался кусок bb' такой, что a+b=a+bc=100a' + b' = a + b - c = 100, поэтому 25b7525 \le b' \le 75.

Итак, можно aa' и bb' отдать одному ребёнку, а остальные куски распределить между остальными детьми так же, как это делалось в новом наборе. Утверждение доказано.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.