Модификация старой задачи про мешки с монетами

[juna]

Есть давно известная задачка:
Имеется 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 дней. А Вы?

[Shadow]

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

[svv]

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

[Sender]

Shadow в сообщении #1148368 писал(а):

Записываем числа в двоичном виде (с старшими нулями) и на каждом ходу превращаем единички в каждом столбце в нули.

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

[svv]

juna в сообщении #1148345 писал(а):

я могу за 9 дней. А Вы?

У меня получается, что за 9 дней нельзя. Вы можете сообщить мне, по сколько монет Вы забираете в каждый из девяти дней? (Можно «по секрету», через личку.) А я скажу, с каким мешочком при этом будут проблемы.

[Geen]

Shadow в сообщении #1148368 писал(а):

Но насчет оптимальности такого алгоритма не уверен.

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

[Shadow]

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

[juna]

Нет, я ошибся - просто первый день считал в программе нулевым . Извините.

Моя мотивация была следующая: поскольку в однородной совокупности это можно сделать за один день, значит нужно изымать типичного представителя статистической совокупности.
Вот и захотелось найти формулу для типичного представителя. Для кучи 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] можно существенно короче (типичный представитель очевиден).

[svv]

juna
У Вас есть мешочки, имеющие одно и то же количество монет. В первом сообщении таких было немного, а теперь Вы ими люто злоупотребляете . Объясните, пожалуйста, разве ответ изменится, если мы из каждой «равномонетной» группы оставим только по одному мешочку?

[juna]

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

[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 также работает. Люфт возникает. В общем можно считать, что кроме условия - за минимальное количество дней, в задаче добавляется еще одно условие - с минимальным суммарным количеством монет, вынимаемых из одного мешочка за каждый день. Степени двойки видимо дают максимум этой суммы.

[svv]

Вы для поиска того, что я называю «базовый набор», написали программу (на 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

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

[juna]

svv

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

[svv]

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

[juna]

Давайте потестим...

juna в сообщении #1148915 писал(а):

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

svv в сообщении #1149170 писал(а):

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

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

svv

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

[svv]

Вкратце: программа помогла уверенно определить, что 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-дневного решения не существует.