"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

Задачи на логику и сообразительность




О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!


Справочная



Признаки делимости
Площади фигур


Реклама






задача: Черномор и богатырская зарплата

Задачу прислал: Админ


Сложность: средняяТридцать три богатыря нанялись охранять Лукоморье за 240 монет. Хитрый дядька Черномор может разделить богатырей на отряды произвольной численности (или записать всех в один отряд), а затем распределить всё жалованье между отрядами.
Каждый отряд делит свои монеты поровну, а остаток отдаёт Черномору. Какое наибольшее количество монет может достаться Черномору, если:
а) жалованье между отрядами Черномор распределяет как ему угодно;
б) жалованье между отрядами Черномор распределяет поровну?

Авторы задачи И. В. Раскина, А. В. Хачатурян



Ответ





Решение задачи





Ваши ответы на задачу


ответов: 11

не представился 2018-07-17 00:17:34 пишет:
Решение
С отряда в N богатырей Черномор получит в лучшем случае N – 1 монету, так как остаток меньше делителя. Значит, всего он получит не более, чем 33 – K монет, где K – число отрядов. Но если отряд всего один, то, поскольку 240 = 33·7 + 9, Черномору достанется лишь
9 монет. Значит, 32 монеты Черномору получить не удастся.

а) Покажем, как получить 31 монету. Например, Черномор делит богатырей на 2 отряда: в первом – 32 богатыря, а во втором – всего один. Он может дать первому отряду 63 монеты (из которых получит 31), а остальные 177 монет отдать единственному богатырю из второго отряда.

б) Чтобы получить 31 монету, Черномор должен разделить богатырей на два отряда и выдать каждому отряду по 120 монет. При этом с отряда в N человек он должен получить N – 1 монету. Это значит, что 121 должно делиться на N. Однако 121 делится только на 1, 11 и 121, а из двух таких чисел невозможно сложить 33. Поэтому 31 монету Черномору получить не удастся.
А вот получить 30 монет можно. Образуем, например, один отряда из 27 богатырей и два отряда по 3 богатыря. Каждый отряд получает по 80 монет, и, поскольку 81 делится на численность каждого отряда, «откат» составит 26 + 2 + 2 = 30 монет.


Ответ
а) 31 монета; б) 30 монет.
   Админ:

Kirill 2016-04-11 22:57:13 пишет:
80 отрядов по 2 человека каждому отряду по 3 монеты остаток 80 достанется хитрому дядьке

Гидон 2016-04-11 15:04:11 пишет:
Ответ:

Случай а) - 31 монета.

Случай б)
1. Если необходимо раздать все монеты до одной - 27 монет.
2. Если можно присвоить остаток - 31 монета.

2.

Обоснование:

Случай а): Наибольшее количество монет, возвращаемое одним отрядом, на единицу меньше количества людей в отряде. Следовательно, для получения максимальной выгоды, Черномору следует распределить всё жалование таким образом, чтобы как можно большее число отрядов получило монет на одну меньше чем количество людей в них. Два отряда
по два человека вернут всего по одной монете, сколько бы им не выделили денег. Один отряд из четырёх человек максимум вернёт три. Значит, чем больше будут отряды, и чем меньше их будет, тем лучше для Черномора. 33 человека не вернут 32 монеты,так как делят монеты они поровну, следовательно каждый заберёт себе по 7 монет и остаток составит 9 монет, потому отряд из 33-х человек - не лучшая идея. Исходя из вышесказанного следует разбить людей на два отряда, например, 32 человека и 1 человек(или 16 и 17 и т.д). Выдать 32-м любую сумму, при делении на 32 дающую остаток 31. А оставшемуся человеку отдать остальное. Но чтобы тот не сильно обогатился, и не затмил Черномора, лишив того должности казначея, необходимо первой группе выдать максимально возможное число денег из имеющихся (естественно дающее остаток 31 при делении на 32). Увеличение количества отрядов необходимо уменьшит число монет, достающихся Черномору. Так что максимальное возможное число монет для Черномора - 31.

Случай б): Если жалованье между отрядами следует распределить поровну, и раздать нужно все монеты, тогда число отрядов должно быть делителем 240 и он должен лежать в пределах от 1-го до 30-и, так как больше 33-х групп создать нельзя. Тогда множество содержащее в себе возможные варианты распределения людей будет выглядеть следующим образом: {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30}. Значит, чтобы получить
наибольшую возможную выгоду, произведение числа монет, доставшегося каждому богатырю в группе и числа богатырей должно в своём младшем разряде содержать минимально возможную цифру от 1 до 9, так как большинство из перечисленных делителей при делении
числа 240 на них, дают в результате числа с нулём в младшем разряде. Так же, число групп должно быть минимально возможным, по причинам названным в решении случая а). Вышеназванным критериям удовлетворяет вариант деления богатырей на две группы(31 и 2). В этом случае Черномор получает 27 монет.

Есле же Черномор себе забирает ещё и остаток от того, что не удалось разделить между богатырями, тогда следует вычислить какой делитель даёт наибольший остаток и делитель этот должен быть наименьшим, так как мы помним об увеличении количества групп. Самый большой остаток у делителя 27 - аж 24 монеты, но групп слишком много, потому получить Черномор может максимум 28 монет. При разбиении богатырей на 22 группы остаток от деления составит 20 монет, и богатыри из 11 групп вернут по одной монете. Итого 31 монета. Такая же выручка получается при делении богатырей на 11 групп(2 по 11, 7 по 1 и 2 по 2) и на 9(3 по 9 и 6 по 1).
   Админ:

KoKos 2015-11-14 05:41:44 пишет:
Ага... Ж) Нашел простой способ доказать невозможность получения 32 монет сдачи. Забываем про максимизацию сдачи и рассматриваем минимизацию потерь. ;) Казалось бы - одно и то же? А не совсем. :))) Минимизация потерь дает нам возможность не рассматривать составные количества отрядов. Действительно, если для простого эн потеря при первоначальном делении между отрядами составляет Х = эн-С0, то для любого составного количества отрядов У*эн, хотя сдача и может оказаться большей, но потеря будет гарантированно не меньше того же Х. То бишь, чтобы попытаться получить 32 сдачи, нам надо сперва найти такое простое количество отрядов, что потеря при делении составит только 1 - или, другими словами, найти простой делитель 241. Кандидатов остается всего ничего - 2,3,5,7,11 и 13. И ни один из них не подходит.

Таким образом, потерять всего одну монету на дележе и получить 32 монеты сдачи Дяде Ч не светит - и 31 монета остается абсолютным рекордом. :)
   Админ: браво!

KoKos 2015-11-13 22:45:28 пишет:
Да, ну так вот, про максимумы. Вспомним старый анекдот, про "эн - мало, пусть будет ка... и оба реактивные". :) Рассмотрим любой ка-тый отряд Ока. Независимо от размера жалования Жка, положенного отряду, сдача с него Ска, достающаяся Дяде Ч всегда строго Ска<Ока. Или в смысле потенциально возможного максимума, Ска=Ока-1 - больше никак. Соответственно, максимально возможная сумма всех сдач с отрядов О1, О2, ..., Оэн равна О1-1+О2-1+...Оэн-1 = О1+О2+...+Оэн-1*эн = 33-эн. Это в случае а). В случае б) у нас появляется еще одна дополнительно возможная сдача С0 от начального раздела между отрядами. И максимум этой сдачи равен как раз эн-1 (ибо делим на эн). Таким образом общий максимум сдачи в случае б) равен 33-эн + эн-1 = 33-1 = 32.

Общего алгоритма для поиска, надежно обоснованного, я, к сожалению, не вижу. Все варианты перебирать тоже лень. :))) Но 31 получаем довольно быстро и просто - делим на 11 отрядов.

О1=22, О2=2, О3=...О11=1
С0=9, Ж1=...Ж11=21 (по условию)
С1=21, С2=1, С3=С11=0
общая сдача - 31.

KoKos 2015-11-13 15:56:19 пишет:
И если считать "интереснее", то тогда вариант Б - тоже 31 монета (пока). Подробно сейчас не могу написать, некогда. В двух словах, решение для Б-31 найдено, и можно достаточно легко доказать, что абсолютный из всех возможных максимумов в случае Б равен 32, но решения для 32 еще не найдено, а может быть и нет вовсе. :)

KoKos 2015-11-13 15:48:00 пишет:
Админ, у меня же больше? 8))) Вариант А - 31 монета. В самом первом ответе.
   Админ: да видел я, видел :))

не представился 2015-11-13 15:38:22 пишет:
Ответ а)

GMan1990 2015-11-13 11:27:33 пишет:
Из того как понял условие, мы должны разбить отряд на группы, так выходит максимально эффективно.
Армию нужно разделить на достаточно большие отряды.
Я сделал так:
5, 7, 7, 7, 7 - т.е. числа являются простыми.
Далее делим между ними деньги. Необходимо проследить логику:
5 человек * на 2 в результате 10 - это очевидно.
Делаем малость хитрость, для достижения максимального остатка, из 10 вычитаем единицу, получаем 9, при делении 9 на 5, получаем максимальный остаток 8.
От сюда пляшем в том же направлении:
9/5 = 1; 1*5=5; 9-5 = 4 - это количество монет возвращаемые Дяде;
62/7 = 8; 8*7=56; 62-56=6 - эту процедуру повторяем 3 раза, в итоге 6*3 = 18 монет вернётся дяде;
и оставшийся отряд:
45/7=6; 6*7=42; 45-42=3 - в копилку ещё 3 монеты, это не идеальный случай - может быть ест лучшие комбинации, но рабочее время сильно на это не потратишь)
В итоге: 4+6*3+3=25 монет.
Это по варианту А.
Жду комментариев) И недочётов)
   Админ: пока не буду комментировать, просто зафиксируем результат:
Вариант А - 25 монет. Кто больше?

KoKos 2015-11-12 01:01:34 пишет:
Вопрос в том, куда девается в случае б) остаток от первоначального раздела жалованья поровну между отрядами? Это никак не оговорено в условии. Тоже отходит Дяде Ч, вместе с остатками от деления внутри отрядов? 8) В таком случае теоретически возможно превышение начального предположения про 33-эн. Но возможно в случае б) Дядя Ч обязан подобрать количество отрядов так, чтоб между ними жалованье разделилось без остатка? Условие можно трактовать и так...

Админ, внесите ясность, пожалуйста?
   Админ: Давайте считать, что остаток тоже отходит Черномору, так интереснее.

KoKos 2015-11-12 00:48:10 пишет:
Для начала сразу отсчитаем и отбросим выродок одного отряда. Если я правильно понял условие, то варианты а) и б) в этом случае абсолютно идентичны и, выдав отряду всю сумму, Дядя Ч получит свои 9 монет сдачи.

Далее, при делении на два и более (пусть эн) отрядов О1, О2, ..., Оэн - теоретически возможный максимум для Дяди Ч составит ровно 33-эн монет. Вопрос лишь в том, достижим ли он? :)

Случай а) вполне прозаичен: два отряда, О1=32, О2=1, Ж1=31, Ж2=209, сдача будет 31 монета от первого отряда. Можно проделать то же самое менее жестоко, но и менее наглядно. :))) Главное, достижимость максимума подтверждена. Сейчас придумаю, что можно сделать со случаем б) и продолжу.

Добавьте комментарий:
Автор:

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Гостевая книга:
Bramki : He developed a way to attack compressed chlorine from cylinders into an absorption keep in which not...
Задача Взлёт или посадка?:
не представился : [скрыто]
Задача Ириски из кармана:
не представился : [скрыто]
Задача Для начинающих программистов:
Арман : [решил задачу]
Задача Скользящие бревна:
KoKos : [скрыто]
Задача Продолжите последовательность:
ваал : [скрыто]
Админ: обоснуйте
Задача :
Крошка сью : [скрыто]
Задача Задача с собеседования в Adobe:
Eleria : [скрыто]
Задача продолжить ряд:
Баке : [скрыто]
Задача Кот ученый и мышка в норках:
KoKos : [скрыто]
Админ: хорошая задача, пусть будет еще раз :)
Задача Четыре таблетки:
Кирилл : [решил задачу]
Задача Кофе с молоком:
не представился : [скрыто]
Задача Пруд с кувшинками:
Анатолий : [скрыто]
Задача Для начинающих программистов:
Алекс : [решил задачу]
Задача Таблички с цифрами:
не представился : [скрыто]
Админ: осталось сосчитать



Реклама



© 2009-201x Логические задачи