Тема 19. Задачи на теорию чисел
19.22 Оценка + пример
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела задачи на теорию чисел
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#27143

У Вани есть несколько пакетов с вещами, каждый из которых весит целое число килограммов. Он хочет разложить все эти пакеты, не перекладывая их содержимое, по n  имеющимся у него рюкзакам. В каждый рюкзак можно положить любое число пакетов, суммарная масса которых не превосходит m  килограммов.

а) Сможет ли Ваня таким образом разложить семь пакетов, которые весят 3, 6, 9, 12, 15, 18, 21 кг, если n= 3,  m = 29?

б) Сможет ли Ваня таким образом разложить семь пакетов, которые весят 6, 12, 14, 15, 19, 22, 25 кг, если n = 3,  m = 38?

в) Какое наименьшее значение может принимать m,  чтобы Ваня при n= 4  смог разложить таким образом девять пакетов, которые весят 3, 7, 9, 11, 13, 15, 17, 19, 21 кг?

Показать ответ и решение

а) Суммарная масса вещей в килограммах в пакетах у Вани равна

3+ 6+ 9+ 12+ 15+ 18+ 21= 84

Заметим, что масса каждого пакета кратна 3, следовательно, масса любого числа пакетов также будет кратна 3. Значит, в любой рюкзак поместится число пакетов, суммарная масса которых кратна 3. Тогда суммарная масса в каждом рюкзаке не превосходит не 29 кг, а 27 кг. Но 27 ⋅3 = 81< 84.  Следовательно, семь таких пакетов разместить не удастся.

б) Суммарная масса вещей в килограммах в пакетах равна

6+ 12+ 14+ 15+ 19 + 22 +25 = 113

Если рюкзаков 3 и в каждом не более 38 кг, то всего уместится не более 3 ⋅38 = 114  кг. Тогда в два рюкзака должно поместиться ровно по 38 кг, а в третий — 37 кг.

Переберем все варианты, какими пакетами можно набрать 37 кг:

1.

12+ 25  кг, тогда остаются пакеты по 6, 14, 15, 19, 22 кг. Пакет в 22 кг должен попасть в один из двух оставшихся рюкзаков, где должно быть суммарно 38 кг, но среди пакетов нет пакета такой массы, который бы в сумме с 22 кг дал 38 кг. Если с пакетом массой 22 кг будет лежать хотя бы два других, то их общая масса будет не меньше 22+ 6+ 14 = 42  кг. Следовательно, в этом случае ничего не получается.

2.

15+ 22  кг. Тогда остаются пакеты по 6, 12, 14, 19, 25 кг. Пакет в 25 кг должен попасть в один из двух оставшихся рюкзаков, где должно быть суммарно 38 кг, но среди пакетов нет пакета такой массы, который бы в сумме с 25 кг дал 38 кг. Если с пакетом массой 25 кг будет лежать хотя бы два других, то их общая масса будет не меньше 25+ 6+ 12 = 43  кг. Следовательно, в этом случае ничего не получается.

3.

6+ 12+ 19  кг. Тогда остаются пакеты по 14, 15, 22, 25 кг. Пакет в 25 кг должен попасть в один из двух оставшихся рюкзаков, где должно быть суммарно 38 кг, но суммарная масса пакета в 25 кг и любого другого из оставшихся не меньше 25 + 14 = 39  кг. Следовательно, в этом случае ничего не получается.

Других вариантов набрать 37 кг пакетами с данными массами нет, значит, Ваня не сможет разложить такие пакеты по трем рюкзакам.

в) Суммарная масса вещей в килограммах в пакетах равна

3+ 7+ 9+ 11+ 13+ 15+ 17+ 19 +21 = 115

Заметим, что минимальное m  мы получим в том случае, если масса во всех рюкзаках будет одинаковой. Так как ближайшее сверху к 1154-  целое число равно 29, то m ≥ 29.  Тогда в трех рюкзаках должно быть по 29 кг, а в четвертом 28 кг.

Пакет в 21 кг должен попасть в один из рюкзаков, но среди других пакетов есть только один пакет такой массы, который бы в сумме с 21 кг дал 28 или 29 кг — это пакет массой 7 кг. Тогда пакеты массой в 7 и 21 кг обязаны лежать в одном рюкзаке, значит, остальные рюкзаки должны весить по 29 кг.

Рассмотрим пакет массой 19 кг. Среди оставшихся пакетов нет таких, которые бы в сумме с 19 кг дали бы 29 кг. Следовательно, в этом случае ничего не получается.

Пусть m = 30.  Тогда распределим пакеты по рюкзакам следующим образом:

9 +21 =30, 11 +19 = 30, 13+ 17 = 30, 3+ 7+ 15= 25
Ответ:

а) Нет, не сможет

б) Нет, не сможет

в) 30

Критерии оценки

Содержание критерия

Балл

Верно получены все перечисленные (см. критерий на 1 балл) результаты

4

Верно получены три из перечисленных (см. критерий на 1 балл) результатов.

3

Верно получены два из перечисленных (см. критерий на 1 балл) результатов.

2

Верно получен один из следующий результатов:

— обоснованное решение в пункте а);

— обоснованное решение в пункте б);

— искомая оценка в пункте в);

— пример в пункте в), обеспечивающий точность предыдущей оценки.

1

Решение не соответствует ни одному из критериев, перечисленных выше

0

Максимальный балл

4

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!