2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Модификация старой задачи про мешки с монетами
Сообщение01.09.2016, 18:09 
Заслуженный участник
Аватара пользователя


07/03/06
1892
Москва
Есть давно известная задачка:
Имеется 2009 мешочков с 1, 2, 3,..., 2008 и 2009 монетами. Каждый день разрешается взять из одного или нескольких мешочков по одинаковому числу монет. За какое минимальное число дней можно взять все монеты?

Однако здесь предполагается достаточно прямолинейное распределение монет по мешкам: 1, 2, 3,...,2009. Попытаемся ответить на этот вопрос в общем виде, для любого распределения монет по мешкам. Например, вот для такого распределения:
[8, 13, 16, 24, 25, 31, 39, 41, 44, 48, 57, 58, 70, 71, 80, 85, 86, 91,
92, 103, 115, 118, 122, 139, 142, 149, 151, 167, 178, 179, 180, 182, 188, 189,
193, 193, 204, 206, 207, 210, 215, 216, 217, 222, 234, 237, 239, 242, 251,
254, 261, 266, 273, 277, 279, 279, 287, 296, 303, 309, 311, 328, 331, 339,
346, 349, 362, 362, 366, 394, 406, 409, 415, 416, 416, 418, 421, 425, 426,
426, 431, 442, 444, 456, 461, 469, 469, 495, 500, 509, 511, 525, 525, 526,
526, 529, 541, 545, 547, 548, 557, 562, 575, 585, 589, 594, 597, 608, 614,
616, 620, 624, 646, 650, 653, 654, 655, 657, 658, 658, 659, 660, 661, 671,
674, 674, 677, 678, 696, 703, 708, 709, 720, 722, 736, 736, 738, 750, 754,
770, 771, 773, 773, 779, 804, 809, 810, 812, 813, 817, 818, 820, 827, 829,
831, 839, 840, 843, 844, 847, 849, 861, 862, 864, 867, 885, 898, 900, 907,
909, 909, 910, 915, 917, 919, 919, 920, 921, 926, 935, 936, 938, 940, 943,
944, 947, 954, 962, 974, 976, 977, 979, 981, 982, 984, 989, 992, 997, 999,
1000]
я могу за 9 дней. А Вы?

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение01.09.2016, 19:55 


26/08/11
2057
Я не знаю ответ на задчи, но за \lceil\log_2{n}\rceil$, где n - мешок с наибольшим числом монет, независимо от числа мешков, можно.
Записываем числа в двоичном виде (с старшими нулями) и на каждом ходу превращаем единички в каждом столбце в нули. Независимо от порядка.
Если повезет, можно и за меньше. Но насчет оптимальности такого алгоритма не уверен.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение02.09.2016, 01:38 
Заслуженный участник


23/07/08
10609
Crna Gora
Даны натуральные числа $a_1,\ldots,a_n$.
Набор натуральных чисел $b_1,\ldots,b_m$ назовём базовым, если любое $a_i$ можно представить в виде суммы, в которую каждое $b_k$ включается ровно один раз, либо не входит вообще.
(Однако среди чисел базового набора могут быть и совпадающие, поэтому в суммах могут встречаться равные слагаемые.)
Найти минимальный (по количеству чисел) базовый набор.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение02.09.2016, 09:46 


14/01/11
2914
Shadow в сообщении #1148368 писал(а):
Записываем числа в двоичном виде (с старшими нулями) и на каждом ходу превращаем единички в каждом столбце в нули.

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

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение02.09.2016, 21:21 
Заслуженный участник


23/07/08
10609
Crna Gora
juna в сообщении #1148345 писал(а):
я могу за 9 дней. А Вы?
У меня получается, что за 9 дней нельзя. Вы можете сообщить мне, по сколько монет Вы забираете в каждый из девяти дней? (Можно «по секрету», через личку.) А я скажу, с каким мешочком при этом будут проблемы.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение03.09.2016, 00:18 
Заслуженный участник
Аватара пользователя


01/09/13
4317
Shadow в сообщении #1148368 писал(а):
Но насчет оптимальности такого алгоритма не уверен.

В общем случае частных случаях, он не оптимален - например, две кучки 3 и 7 монет...

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение03.09.2016, 07:24 


26/08/11
2057
Нуууу :D Две кучи конечно. Обнуляем или ряд, или столбец в данном несложном алгоритме. Я его предложил просто потому, что juna
предложил 9 итераций для случайного (или нет) набора до 1023, а "алгоритм" гарантирует 10.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение03.09.2016, 20:31 
Заслуженный участник
Аватара пользователя


07/03/06
1892
Москва
Нет, я ошибся - просто первый день считал в программе нулевым :facepalm: . Извините.

Моя мотивация была следующая: поскольку в однородной совокупности это можно сделать за один день, значит нужно изымать типичного представителя статистической совокупности.
Вот и захотелось найти формулу для типичного представителя. Для кучи 1,2,3,...,2009 работает простое среднее арифметическое. Действительно, каждое такое вычеркивание удваивает количество нулей, поэтому верхняя оценка получается из $2009\cong 2^n$. Для произвольной последовательности среднее арифметическое уже не работает. Подыскал интересную форму среднего, которая всегда работает по верхней оценке $\lceil\log_2{n}\rceil$, и это могут быть не степени двойки:

Например, для представленной последовательности с разной степенью приближения этого среднего получаем следующие стратегии:
1) 509, 251, 125, 63, 32, 16, 8, 4, 2, 1.
2) 506, 251, 126, 62, 31, 16, 8, 4, 2, 1.
Видно, что это вариации вокруг предложенной последовательности степеней двойки: 512, 256, 128, 64, 32, 16, 8, 4, 2, 1.
Чем дальше максимальный член отстоит от степени двойки, тем менее похоже может быть это среднее на степени двойки. Например, для последовательности:
[1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 6, 8, 8, 8, 9, 9, 10, 10,
10, 10, 10, 10, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 16, 16, 17, 17, 19,
19, 19, 19, 19, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25,
25, 25, 26, 27, 27, 29, 30, 31, 31, 32, 32, 32, 33, 33, 33, 34, 34, 35, 35,
35, 36, 36, 37, 37, 38, 39, 40, 41, 41, 41, 42, 42, 45, 45, 45, 46, 47, 47,
47, 48, 48, 49, 49, 49, 49, 50, 51, 52, 52, 52, 52, 52, 53, 53, 53, 55, 55,
55, 56, 56, 56, 57, 57, 58, 58, 59, 60, 60, 60, 60, 61, 61, 62, 62, 63, 63,
64, 65, 65, 65, 65, 66, 66, 67, 68, 68, 68, 69, 70, 70, 70, 71, 72, 73, 73,
73, 74, 74, 74, 74, 74, 75, 75, 75, 75, 75, 76, 76, 77, 77, 78, 80, 80, 81,
81, 82, 82, 82, 82, 82, 83, 84, 84, 84, 85, 85, 85, 86, 86, 86, 86, 86, 86,
86, 86, 87, 88, 89, 90, 90]
Имеем:
Верхнее ограничение: 6.491853096329675
День: 1 Количество монет: 45
День: 2 Количество монет: 23
День: 3 Количество монет: 11
День: 4 Количество монет: 6
День: 5 Количество монет: 3
День: 6 Количество монет: 1
День: 7 Количество монет: 1

Но, можно 64, 32, 16, 8, 4, 2, 1. И, конечно, для многих последовательностей типа [1,2,3,400,400,400] можно существенно короче (типичный представитель очевиден).

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение03.09.2016, 23:20 
Заслуженный участник


23/07/08
10609
Crna Gora
juna
У Вас есть мешочки, имеющие одно и то же количество монет. В первом сообщении таких было немного, а теперь Вы ими люто злоупотребляете :-) . Объясните, пожалуйста, разве ответ изменится, если мы из каждой «равномонетной» группы оставим только по одному мешочку?

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение04.09.2016, 09:41 
Заслуженный участник
Аватара пользователя


07/03/06
1892
Москва
Не злоупотребляю, а экспериментирую. Конечно, в условиях задачи ничего не поменяется, если все повторяющиеся числа заменить одним числом. Но я ищу типичного представителя, который от такого действа может куда-нибудь уплыть. Собственно так и есть, уплывает, т.е. для последовательности

[1,2,3,4,6,8,9,10,12,13,14,16,17,19,21,22,23,24,25,26,27,29,30,31,32,33,34,35,36,37,38,39,40,41,42,45,47,48,49,50,51,52,53,55,56,57,58,59,60,61,62,63,64, 65,66,67,68,69,70,71,72,73,74,75,76,77,78,80,81,82,83,84,85,86,87,88,89,90]

мое среднее дает уже последовательность 46, 23, 11, 6, 3, 1,1, хотя последовательность 45, 23, 11, 6, 3, 1, 1 также работает. Люфт возникает. В общем можно считать, что кроме условия - за минимальное количество дней, в задаче добавляется еще одно условие - с минимальным суммарным количеством монет, вынимаемых из одного мешочка за каждый день. Степени двойки видимо дают максимум этой суммы.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение04.09.2016, 22:24 
Заслуженный участник


23/07/08
10609
Crna Gora
Вы для поиска того, что я называю «базовый набор», написали программу (на C++ ?). Я сделал то же самое. Только меня привлекали в первую очередь разреженные последовательности (как самая первая), для которых можно получить неожиданно маленький базовый набор.

Иногда удивляет изящество, с которым найденный набор порождает все заданные по условию числа. Например, для первых семи членов Вашей последовательности [8, 13, 16, 24, 25, 31, 39] достаточно базового набора из четырёх чисел [5, 8, 11, 20]:
8=8
13=5+8
16=5+11
24=5+8+11
25=5+20
31=11+20
39=8+11+20

Нахожу я это дело перебором. Полный перебор занимает много времени, но, к счастью, его можно значительно сократить, и для каждого искомого числа заранее задать относительно узкие границы.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение05.09.2016, 05:47 
Заслуженный участник
Аватара пользователя


07/03/06
1892
Москва
svv

Нет, конечно. Никакой переборной программы на C++ я не писал. Просто мои средние есть результат решения уравнений большой степени, действительный корень которых дает эти средние, которые в свою очередь в частности дают решения этой, на первый взгляд, чисто переборной задачи. Естественно, такие уравнения я решаю численно и в maxima.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение05.09.2016, 09:45 
Заслуженный участник


23/07/08
10609
Crna Gora
Очень хитро. Непостижимым образом Ваша магия выдаёт тот же набор [1,1,3,6,11,23,45], который первым честно :wink: находит моя переборная программа. Исходя из моего алгоритма, могу утверждать, что он и лексикографически первый (при сортировке элементов по возрастанию).
Последний же в лексикографическом порядке — [1,2,4,8,16,32,64], а всего найдено 3127 вариантов.

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение05.09.2016, 11:01 
Заслуженный участник
Аватара пользователя


07/03/06
1892
Москва
Давайте потестим...

juna в сообщении #1148915 писал(а):
в задаче добавляется еще одно условие - с минимальным суммарным количеством монет, вынимаемых из одного мешочка за каждый день


svv в сообщении #1149170 писал(а):
Исходя из моего алгоритма, могу утверждать, что он и лексикографически первый (при сортировке элементов по возрастанию).


Это кстати, косвенно свидетельствует, что это условие такие средние контролируют и учитывают как-то...

svv

Скажите, а последовательность из первого поста перебору поддалась? Какие решения получились?

 Профиль  
                  
 
 Re: Модификация старой задачи про мешки с монетами
Сообщение05.09.2016, 22:18 
Заслуженный участник


23/07/08
10609
Crna Gora
Вкратце: программа помогла уверенно определить, что 9 дней не хватило бы, но вряд ли потянула бы поиск всех 10-дневных вариантов.

Подробно в оффтопе.

(Оффтоп)

Сначала я хотел Вас переплюнуть и найти 8-дневное решение, ещё не зная, что 9-дневного нет. Чтобы не делать полный перебор, надо было как-то сократить поиск. Во-первых, потребуем, чтобы числа из базового набора были отсортированы по возрастанию:
$b_1\leqslant b_2 \leqslant ... \leqslant b_m$
Неубывание важно для последующего.

Дальше такая логика. $b_1$ не может быть больше $a_1=8$, иначе все последующие $b_k$ будут тоже больше $8$, и это число будет непокрытым (непредставимым в виде суммы каких-либо $b_k$ из базового набора). Значит, $1\leqslant b_1 \leqslant 8$.

Число $b_2$ не может быть больше $a_2=13$, иначе все последующие $b_k$ будут тоже больше $13$, и оно будет непокрытым. Значит, $b_1\leqslant b_2\leqslant 13$.

Число $b_3$ не может быть больше $a_3=16$, но здесь логика более сложная. Если оно будет больше, набора $[b_1,b_2]$ не хватит на покрытие и $8$, и $13$, и $16$, а последующие $b_k$ не помогут, потому что больше $16$.

Число $b_4$ может быть больше $a_4=24$ (базовый набор $[3, 8, 13]$ покрывает числа $[8, 13, 16, 24]$), но вот больше $25$ быть уже не может, потому что никакой набор $[b_1, b_2, b_3]$ не покроет первые пять членов исходной последовательности (это уже помог определить компьютер), а последующие на помощь не придут.

Дальнейшие ограничения тоже находил компьютер, причём затраченное время быстро росло:
$b_5\leqslant 41$
$b_6\leqslant 58$
$b_7\leqslant 92$
$b_8\leqslant 178$
Последнее было установлено с такой же натугой, с какой полководец Теренций вкатил в казначейство последнюю гигантскую монету в рассказе Я.Перельмана «Награда» (из книги Живая математика). Но теперь ясно, что совокупность первых восьми $b_k$ покроет в исходной последовательности числа не более $431$, это сумма их максимальных значений.Чтобы покрыть $442$, должно быть $b_9\leqslant 442$, но тогда суммы всех девяти не хватит, чтобы покрыть хвост последовательности $(885,898,...,999,1000)$.

Следовательно, 9-дневного решения не существует.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group