Шары и коробки

Условие

На склад поступили 11 шаров разного диаметра: 12, 23, 12, 18, 27, 10, 12, 16, 27, 19, 16. А также 11 кубических коробок, у каждой задана длина ребра: 11, 26, 28, 15, 11, 13, 17, 14, 19, 28, 13. Упаковщик может положить шар только в такую коробку, длина ребра которой не меньше диаметра шара. Каждый шар можно упаковать только в одну коробку, и в каждую коробку можно положить не более одного шара. Какое наибольшее количество шаров удастся упаковать?

3 попытки

Если не получается
Как начисляется опыт
  • Разбор условия — +10
  • Мини-задача: сам — +20, с разбором — +5
  • Верный ответ — +30, пропущенные подсказки засчитываются
  • На ответ — 3 попытки, потом следующая подсказка и снова 3
  • В мини-задаче — 3 попытки, потом её разбор
  • «Проверь себя» — ★ и +30 за задачу

    Сначала попробуй решить сам

    Комбинаторика · пример и оценка

    Шары и коробки

    Условие

    На склад поступили 11 шаров разного диаметра: 12, 23, 12, 18, 27, 10, 12, 16, 27, 19, 16. А также 11 кубических коробок, у каждой задана длина ребра: 11, 26, 28, 15, 11, 13, 17, 14, 19, 28, 13. Упаковщик может положить шар только в такую коробку, длина ребра которой не меньше диаметра шара. Каждый шар можно упаковать только в одну коробку, и в каждую коробку можно положить не более одного шара. Какое наибольшее количество шаров удастся упаковать?

    Решаем за 6 коротких шагов. Ниже есть всё решение одним видео, а в каждом шаге свой короткий ролик: можно смотреть, можно читать. Шаги листай кнопкой «Дальше» внизу экрана. Ответ в самом конце. Не подглядывай, иди по порядку.

    Всё решение одним видео

    Шаг:
    9:57
    1

    Шаг 1 · разбираем условие

    Что дано и что нужно найти

    2:50

    Прочитаем условие по кусочкам и переведём каждый на простой язык. Здесь мы ещё ничего не решаем — только разбираемся, что к чему.

    • «На склад поступили 11 шаров разного диаметра: 12, 23, 12, 18, 27, 10, 12, 16, 27, 19, 16.»

      Есть 11 шаров. Диаметр — это ширина шара, если мерить насквозь, через центр.

      «Разного диаметра» значит, что шары не одинаковые. Но некоторые размеры повторяются: например, шаров диаметром 12 — три.

    • «А также 11 кубических коробок, у каждой задана длина ребра: 11, 26, 28, 15, 11, 13, 17, 14, 19, 28, 13.»

      Коробок тоже 11. Каждая коробка — куб: у неё длина, ширина и высота равны. Это и есть длина ребра.

      реброребро
    • «Упаковщик может положить шар только в такую коробку, длина ребра которой не меньше диаметра шара.»

      Шар влезает в коробку, если ребро ≥ диаметр. «Не меньше» значит «больше или равно».

      Шар 12 влезает в коробку с ребром 13 (13 > 12), но не влезает в коробку с ребром 11 (11 < 12). Шар 19 влезает в коробку 19: числа равны, а «равно» подходит.

      12ребро 1313 > 12✓ влезает12ребро 1111 < 12✗ не влезает19ребро 1919 = 19✓ влезает
      Коробку рисуем спереди — квадратом. Размеры в масштабе.
    • «Каждый шар можно упаковать только в одну коробку, и в каждую коробку можно положить не более одного шара.»

      Один шар — одна коробка. Получаются пары «шар — коробка». Два шара в одну коробку класть нельзя, даже если они там поместились бы.

    • «Какое наибольшее количество шаров удастся упаковать?»

      Нужно найти, сколько таких пар можно составить самое большее. Упаковывать все шары не обязательно: какие-то могут остаться без коробки.

    12231218271012162719161126281511131714192813 шарыкоробки12231218271012162719161126281511131714192813
    Все шары (оранжевые круги) и коробки (синие квадраты) в порядке из условия. Чем больше число, тем больше фигура.

    Задача: составить как можно больше пар «шар — коробка», где шар не больше коробки (диаметр ≤ ребро), и узнать, сколько получилось пар.

    2

    Шаг 2

    Расставим по порядку

    1:45

    Как будем решать. Ответ на вопрос «какое наибольшее количество» состоит из двух частей.

    • 1. Примерпоказать способ упаковать сколько-то шаров
    • 2. Оценкадоказать, что больше упаковать нельзя никаким способом

    Начнём с примера. Шары и коробки в условии перемешаны — подбирать пары неудобно. Расставим их по возрастанию: от маленьких к большим.

    • Шары10, 12, 12, 12, 16, 16, 18, 19, 23, 27, 27
    • Коробки11, 11, 13, 13, 14, 15, 17, 19, 26, 28, 28

    Проверка: в каждом ряду по-прежнему 11 чисел — никого не потеряли.

    10121212161618192327271111131314151719262828 шарыкоробки10121212161618192327271111131314151719262828
    Сверху — шары по возрастанию, снизу — коробки по возрастанию.

    Дальше говорим коротко: «шар 12» — шар диаметром 12, «коробка 13» — коробка с ребром 13.

    Самый большой шар — 27, самая большая коробка — 28. Значит, каждый шар по отдельности куда-то влезает. Но коробок 28 всего две — всем шарам сразу коробок может не хватить.

    Шары: 10, 12, 12, 12, 16, 16, 18, 19, 23, 27, 27. Коробки: 11, 11, 13, 13, 14, 15, 17, 19, 26, 28, 28.

    3

    Шаг 3

    Маленький шар — в маленькую коробку

    1:27

    Кладём шары по очереди: от самого маленького к самому большому.

    Правило: каждый шар кладём в самую маленькую свободную коробку, в которую он влезает.

    Почему в самую маленькую? Большие коробки сбережём для больших шаров. Маленький шар влезет и в маленькую коробку, а большому шару маленькая не подойдёт.

    • 10 → 11самая маленькая коробка 11; 11 > 10 — влезает
    • 12 → 11 ✗вторая коробка 11; 11 < 12 — не влезает, пропускаем
    • 12 → 13следующая коробка 13; 13 > 12 — влезает
    • 12 → 13второй шар 12 — в следующую коробку 13
    • 12 → 14третий шар 12 — в коробку 14
    10121212161618192327271111131314151719262828пусто шарыкоробки10121212161618192327271111131314151719262828пусто
    Зелёная стрелка — шар положили в коробку. Коробка 11 осталась пустой.

    Уложены 4 шара: 10 → 11, 12 → 13, 12 → 13, 12 → 14. Коробка 11 пустая: остальные шары — 16 и больше, в неё не влезут.

    4

    Шаг 4

    Укладываем все шары

    1:33

    Продолжаем по тому же правилу. Свободны коробки 15, 17, 19, 26, 28, 28 (и пустая 11).

    • 16 → 15 ✗15 < 16 — не влезает, пропускаем
    • 16 → 1717 > 16 — влезает
    • 16 → 19второй шар 16 — в следующую коробку 19
    • 18 → 26коробка 19 уже занята; следующая свободная — 26
    • 19 → 28следующая свободная — 28
    • 23 → 28вторая коробка 28
    • 27, 27 — нетсвободны только коробки 11 и 15, а 27 больше обеих
    10121212161618192327271111131314151719262828пустопусто шарыкоробки10121212161618192327271111131314151719262828пустопусто
    Уложены 9 шаров. Шары 27 и 27 (в красной рамке) остались без коробки, коробки 11 и 15 — пустые.

    А вдруг другим способом получится 10? Например, можно положить шар 27 в коробку 28 — но тогда шару 23 придётся искать другую коробку. Перебирать все способы долго. В следующем шаге докажем, что 10 не получится никак.

    Пример: 9 шаров упаковать можно (10 → 11, 12 → 13, 12 → 13, 12 → 14, 16 → 17, 16 → 19, 18 → 26, 19 → 28, 23 → 28).

    5

    Шаг 5

    Почему больше 9 нельзя

    1:29

    Подсказку даёт пример: коробка 15 осталась пустой, а все шары после неё — 16 и больше — в неё не влезают. Рассмотрим эти большие шары.

    • 7 шаровдиаметром 16 и больше: 16, 16, 18, 19, 23, 27, 27
    • ребро ≥ 16такой шар влезает, только если ребро ≥ диаметр, а диаметр ≥ 16
    • 5 коробокс ребром 16 и больше: 17, 19, 26, 28, 28 (коробка 15 не подходит: 15 < 16)
    • не больше 5в коробку — не больше одного шара, поэтому из 7 больших шаров упаковать можно не больше 5
    • 7 − 5 = 2хотя бы 2 больших шара останутся без коробки — при любом способе
    • 11 − 2 = 9значит, упаковано не больше 9 шаров
    16 и больше: 7 шаровребро не меньше 16: 5 коробок10121212161618192327271111131314151719262828 шарыкоробки7 шаров5 коробок10121212161618192327271111131314151719262828
    Большие шары (оранжевая рамка) помещаются только в коробки из синей рамки. Шаров 7, а коробок 5.

    Оценка: больше 9 шаров упаковать нельзя никаким способом.

    6

    Шаг 6

    Собираем ответ

    0:48

    Мы доказали две вещи.

    • 1. Пример9 шаров упаковать можно (шаг 4)
    • 2. Оценкабольше 9 нельзя: хотя бы 2 больших шара всегда без коробки (шаг 5)

    Значит, наибольшее количество — ровно 9.

    Почему нужны обе части? Только пример — вдруг найдётся способ лучше. Только оценка — вдруг и 9 не получится. Вместе они дают точный ответ.

    Ответ: удастся упаковать 9 шаров.

    !

    Где чаще всего ошибаются

    • 11

      Решили: самый большой шар 27 меньше самой большой коробки 28 — значит, влезут все. Но коробок 28 только две, а больших шаров больше.

    • 10

      Положили шар 16 в коробку 15 (или шар 12 в коробку 11). Шар влезает, только если ребро не меньше диаметра, а 15 < 16.

    • 5

      Клали шары в коробки по порядку списка из условия: первый шар — в первую коробку и так далее. Сначала нужно расставить оба ряда по возрастанию.

    • 9 без доказательства

      Нашли способ упаковать 9 шаров и остановились. Нужно ещё доказать, что 10 нельзя: 7 больших шаров и только 5 коробок для них.

    ✎

    Для тетради

    Как записать решение коротко

    Решение
    1. Упорядочим: шары 10, 12, 12, 12, 16, 16, 18, 19, 23, 27, 27; коробки 11, 11, 13, 13, 14, 15, 17, 19, 26, 28, 28.
    2. Пример на 9 шаров: 10 → 11, 12 → 13, 12 → 13, 12 → 14, 16 → 17, 16 → 19, 18 → 26, 19 → 28, 23 → 28.
    3. Оценка. Шаров диаметром не меньше 16 семь (16, 16, 18, 19, 23, 27, 27). Каждый из них можно положить только в коробку с ребром не меньше 16, а таких коробок пять (17, 19, 26, 28, 28). В коробку кладут не более одного шара, поэтому хотя бы 7 − 5 = 2 шара останутся неупакованными. Значит, упаковано не больше 11 − 2 = 9 шаров.

    Ответ: 9.

    Ответ: 9
    5

    Сначала реши основную задачу

    3 задачи без подсказок

    Те же шары и коробки, другие числа.