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

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

Задача 1#1190

Имеется 8 кучек камней, причем во всех кучах число камней разное (куча может состоять из любого, не меньшего 1, числа камней). Известно, что любую из куч можно убрать и все камни из нее разложить по другим кучам так, чтобы число камней в них стало одинаковым. Какое наименьшее число камней может быть в самой большой куче?

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

Пусть ai  , где i = 1...8  – число камней в каждой куче после того, как кучи упорядочили по возрастанию числа камней в них. То есть a1 < a2 < ... < a8   . Тогда a1 ≥ 1  (следует из условия), a2 ≥ 2,..., a8 ≥ 8  .
Пусть мы взяли первую кучу и раскладываем из нее камни по остальным кучам так, чтобы количество в них стало одинаковым. Тогда, так как во всех кучах разное количество камней, наилучший исход (наименьшее количество камней в 1-ой куче) для нас будет таким: ничего не класть в 8-ую кучу, положить 1 камень в 7-ую, 2 камня в 6-ую, 3 камня в 5-ую, 4 камня в 4-ую, 5 камней в 3-ю и 6 камней во 2-ую. Следовательно, в первой куче должно быть как минимум 1 + 2 + 3 + 4 + 5 + 6  камней. То есть a1 ≥ 21  . Следовательно, a2 ≥ 22  и т.д., a8 ≥ 28  .
Утверждаем, что наименьшее возможное количество камней в большой куче – 28. Приведем пример: пусть у нас есть 8 куч камней, в которых 21, 22, 23, 24, 25, 26, 27, 28 камней соответственно.
Разложение 1-ой кучи по остальным мы уже продемонстрировали выше. Аналогично можно проверить, что это условие выполняется для любой другой кучи: после разложения камней в оставшихся семи кучах будет по 28 камней.

Ответ: 28

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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