Автор Тема: Монеты в мешочках  (Прочитано 2548 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Илья

  • Эксперт
  • ******
  • Сообщений: 3617
    • Просмотр профиля
Монеты в мешочках
« : 30 Декабрь 2009, 18:12:49 »
Имеется 2009 мешочков с 1, 2, 3,..., 2008 и 2009 монетами. Каждый день разрешается взять из одного или нескольких мешочков по одинаковому числу монет. За какое минимальное число дней можно взять все монеты?

Lazer

  • Гость
Re: Монеты в мешочках
« Ответ #1 : 30 Декабрь 2009, 18:44:31 »
1005

Оффлайн Илья

  • Эксперт
  • ******
  • Сообщений: 3617
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #2 : 30 Декабрь 2009, 18:47:42 »

Оффлайн fortpost

  • Ветеран
  • *****
  • Сообщений: 582
    • Просмотр профиля
    • E-mail
Re: Монеты в мешочках
« Ответ #3 : 26 Июнь 2018, 18:58:18 »
1005
Многовато будет! Хватит и 11.

Оффлайн николай

  • Эксперт
  • ******
  • Сообщений: 5478
    • Просмотр профиля
    • E-mail
Re: Монеты в мешочках
« Ответ #4 : 26 Июнь 2018, 19:43:13 »
 :)

Оффлайн GreenGoGo

  • Пользователь
  • **
  • Сообщений: 56
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #5 : 27 Июнь 2018, 12:15:02 »

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1720
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #6 : 27 Июнь 2018, 12:29:39 »
1005
Многовато будет! Хватит и 11.
Это как?
Первый день по 1 монете из мешков, где нечетное число монет
Второй день по 2 монеты из мешков, где число монет не кратно 4
Третий день по 4 монеты, из тех, где не кратно 8
И тд

Оффлайн South Paw Mary

  • Эксперт
  • ******
  • Сообщений: 1339
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #7 : 27 Июнь 2018, 13:05:11 »
Можно еще быстрее. Разделите общее количество монет на 2009 - это и будут дни.

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1720
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #8 : 27 Июнь 2018, 13:40:25 »
Можно еще быстрее. Разделите общее количество монет на 2009 - это и будут дни.
это будет как раз-таки 1005. Совсем не быстрее.  :no:

Оффлайн South Paw Mary

  • Эксперт
  • ******
  • Сообщений: 1339
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #9 : 27 Июнь 2018, 17:08:15 »
Это я подсказываю ответ на свою загадку про треугольник.

Оффлайн guerrino

  • Новичок
  • *
  • Сообщений: 11
    • Просмотр профиля
Re: Монеты в мешочках
« Ответ #10 : 05 Август 2018, 00:18:33 »
Найдем максимальное количество монет, которое мы можем взять за первый день. Пусть мы берем A монет из B мешочков. Заметим, что сумма A+B = 2010 постоянна для любого дня при условии, что мы хотим взять максимальное число монет. Произведение A*B - количество монет, которое мы возьмем. При фиксированной сумме A+B, максимальное значение произведения A*B достигается при равенстве A и B. Другими словами, максимальное количество монет, которое мы можем взять в первый день равняется (2010/2)2 = 10052. После того как мы взяли это количество монет мы можем перераспределить по местам новые числа, так, чтобы они стояли в порядке неубывания и отличались не более, чем на 1. То есть алгоритм таков: n оставшихся мешочков (расположенных в порядке неубывания по количеству в них монет) и делим "пополам" на две группы. В большей группе из каждого мешочка достаем максимально возможное число монет. Операция продолжается до тех пор, пока мы не получим в каждом из оставшихся мешочков по 1 монете. Пусть минимальное искомое число дней равно k. Из вышесказанного следует, что 2k-1=2009 (k-1, а не k, так как в последний день мы не разделяем на группы), откуда k после округления равно 11. Если мешочков произвольное число n, то число дней равняется числу цифр в двоичной записи n