===== №84 =====

Задача 84 являлась мини-конкурсом.\\ 
Дабы не ввести участников Марафона в заблуждение, сразу уточню,
что префикс "мини" не означает легкости этой задачи.
Просто конкурс состоял всего из одной задачи.
----

**Конкурсная задача №84** (9 баллов)   

Имеется двадцать мешков, наполненных одинаковыми с виду монетами.
В первом мешке каждая монета имеет вес 20 грамм, во втором - 21, 
в третьем 22, ... в двадцатом - 39. Мешки перепутаны и расставлены
в случайном порядке.\\
С помощью одного взвешивания на стрелочных весах (показывающих точный вес
в граммах) выяснить веса монет в каждом из мешков.
При этом во взвешивании желательно использовать по возможности меньше монет.

Примечания:

1. Мешки содержат, а весы вмещают (не теряя точности) столько монет, 
сколько потребуется для решения задачи.

2. 20 мешков взяты для того, чтобы исключить решение задачи компьютерным 
перебором. Впрочем, если кто-либо из участников сможет преодолеть эту трудность
(и убедить ведущего в корректности компьютерного решения), оно будет принято ;)

3. 9 баллов будут присуждаться тем участникам, в решениях которых будет 
использовано столько же монет, сколько в решении ведущего (разумеется,
достаточность указанного количества монет должна быть строго обоснована).
За решения более (менее) оптимальные, чем решение ведущего, будет начисляться
больше (меньше) девяти баллов.

4. Известное мне решение заведомо не оптимально.


** Решение **

Не нарушая общности, можно считать, что веса монет: 0, 1, 2,..., 19.\\
Возьмем из первого (не мешка с самыми легкими монетами, а первого в некой
нумерации) с<sub>1</sub>, из второго - с<sub>2</sub>, ..., из 20-го - с<sub>20</sub> монет.\\
Для каждой перестановки (a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>20</sub>) чисел 0, 1, ..., 19 образуем
сумму s = с<sub>1</sub>*a<sub>1</sub> + c<sub>2</sub>*a<sub>2</sub> + ... + c<sub>20</sub>*a<sub>20</sub>.\\ 
Очевидно, что набор с = (с<sub>1</sub>, с<sub>2</sub>, с<sub>3</sub>,..., с<sub>20</sub>) будет решением тогда и 
только тогда, когда все 20! таких сумм будут попарно различны.  

Очевидно, что решением будет набор (0, 1, 20, 20<sup>2</sup>, ..., 20<sup>18</sup>).\\
В самом деле, s будет 19-значным (если знаков 18, то припишем ведущий ноль)
числом в 20-ричной системе счисления без повторов цифр. Каждая цифра укажет
вес монет в соответствующем мешке (отсутствующая в s цифра укажет вес монет в
мешке, из которого не брали ни одной монеты). 

Приведенное выше решение обладает следующим свойством:\\
Пусть s = с<sub>1</sub>*a<sub>1</sub> + c<sub>2</sub>*a<sub>2</sub> + ...c<sub>k</sub>*a<sub>k</sub> + c<sub>k+1</sub>*a<sub>k+1</sub> + ... + c<sub>20</sub>*a<sub>20</sub>,\\ 
t = с<sub>1</sub>*b<sub>1</sub> + c<sub>2</sub>*b<sub>2</sub> + ...c<sub>k</sub>*b<sub>k</sub> + c<sub>k+1</sub>*b<sub>k+1</sub> + ... + c<sub>20</sub>*b<sub>20</sub>  и
a<sub>k</sub> < b<sub>k</sub>, а a<sub>k+1</sub> = b<sub>k+1</sub>, a<sub>k+2</sub> = b<sub>k+2</sub>, ..., a<sub>20</sub> = b<sub>20</sub> \\
Тогда s < t. Такие решения будем называть простыми.\\
Наша цель - построить минимальный набор, являющийся простым решением.

Ясно, что можно взять c<sub>1</sub> = 0 и c<sub>2</sub> = 1.\\
Пусть мы уже нашли c<sub>1</sub>, c<sub>2</sub>, ..., c<sub>k-1</sub>.\\
Возьмем b<sub>k</sub> = a<sub>k</sub> + 1 и a<sub>k+1</sub> = b<sub>k+1</sub>, ..., a<sub>20</sub> = b<sub>20</sub>.\\
t - s = c<sub>k</sub> + (b<sub>k-1</sub> - a<sub>k-1</sub>)*c<sub>k-1</sub> + ... + (b<sub>1</sub> - a<sub>1</sub>)*c<sub>1</sub>.\\
Поэтому в качестве c<sub>k</sub> годится \\ 
max[(a<sub>k-1</sub> - b<sub>k-1</sub>)*c<sub>k-1</sub> + ... + (a<sub>1</sub> - b<sub>1</sub>)*c<sub>1</sub>)] + 1,\\  
где подстановки (a<sub>i</sub>) и (b<sub>i</sub>) таковы, что a<sub>k+1</sub> = b<sub>k+1</sub>, ..., a<sub>20</sub> = b<sub>20</sub>.

При нечетных k требуемый максимум достигается при подстановках\\
a = (1, 2, ..., (k-3)/2, (k-1)/2, 20-(k-3)/2, 20-(k-1)/2, ..., 20, 20-(k-1)/2, a<sub>k+1</sub>, ..., a<sub>20</sub>),\\       
b = (20, 19, ..., 20-(k-5)/2, 20-(k-1)/2, (k-1)/2, (k-3)/2,...,1, 20-(k-3)/2, a<sub>k+1</sub>, ..., a<sub>20</sub>). 

Для конкретных значений k эти подстановки выглядят не так страшно, как в
общем виде. Например, при k = 9 \\
a = (1,  2,  3,  4, 17, 18, 19, 20, 16, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15),\\ 
b = (20, 19, 18, 16, 4, 3,  2,  1,  17, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15).

При четных k соответствующие подстановки:\\
a = (1, 2, ..., k/2-1, x+1, 20-k/2, 20-(k-2)/2,..., 20, x, a<sub>k+1</sub>, ..., a<sub>20</sub>),\\
b = (20, 19, ..., 20-k/2, x, k/2-1,  k/2-2, ..., 1,  x+1, a<sub>k+1</sub>, ..., a<sub>20</sub>),\\
где x - любое из диапазона k/2...18-k/2.

Объединяя эти случаи, получим:

<m> c_{k} = 1 + c_{m} + sum{i=1}{m}{(21 - 2i)*(c_{k-i} - c_{i})} (!) </m>, где m = [k/2].

К с<sub>1</sub> и С<sub>2</sub> добавим c<sub>3</sub>, c<sub>4</sub>, ..., c<sub>20</sub>, найденные по формулам (!):

с<sub>1</sub> = 0\\
с<sub>2</sub> = 1\\
с<sub>3</sub> = 20\\
с<sub>4</sub> = 382\\
с<sub>5</sub> = 7583\\
с<sub>6</sub> = 150575\\
с<sub>7</sub> = 2995270\\
с<sub>8</sub> = 59583716\\
с<sub>9</sub> = 1185362498\\
с<sub>10</sub> = 23581699460\\
с<sub>11</sub> = 469137721669\\
с<sub>12</sub> = 9333093638159\\
с<sub>13</sub> = 185673936682779\\
с<sub>14</sub> = 3693824593531841\\
с<sub>15</sub> = 73485489860293368\\
с<sub>16</sub> = 1461931145788096982\\
с<sub>17</sub> = 29083873284686161512\\
с<sub>18</sub> = 578598853768938868016\\
с<sub>19</sub> = 11510730716885865621286\\
с<sub>20</sub> = 228996170271688893675650

Просуммировав С<sub>i</sub> получим простое решение, использующее 
241116123021589624090767 монет, что на 34824929609989323277654 монет меньше, 
чем 1 + 20 + ... + 20<sup>18</sup> монет.

Найденное решение является лучшимм в классе простых решений, но, конечно
же не самым оптимальным.\\  
Уже для 5 мешков решение, построенное по формулам (!) (естественно с заменой
21 на 6), дает набор (0, 1, 5, 22, 98) с суммой 126, в то время как простой
перебор показывает, что оптимальным решением будет набор (0, 2, 5, 21, 91) 
с суммой 119.
 
Олег Полубасов предложил способ позволяющий получать решения оптимальнее 
простых.\\ 
Рекурсивное описание и обоснование этого метода являются результатом работы
некой компьютерой программы.\\
Поскольку итоговый документ получается весьма объемным, а используемые в нем
обозначения отличны от принятых здесь, он прилагается в отдельном сообщении{{:marathon:pbas_84.txt|:marathon:pbas_84.txt}}.
Здесь же я приведу лишь один набор с<sub>i</sub>, полученный этим методом:

с<sub>1</sub>  = 0\\
с<sub>2</sub>  = 9\\
с<sub>3</sub>  = 20\\
с<sub>4</sub>  = 381\\
с<sub>5</sub>  = 7260\\
с<sub>6</sub>  = 144276\\
с<sub>7</sub>  = 2864893\\
с<sub>8</sub>  = 56994127\\
с<sub>9</sub>  = 1133762542\\
с<sub>10</sub> = 22555232416\\
с<sub>11</sub> = 448715673503\\
с<sub>12</sub> = 8926815545228\\
с<sub>13</sub> = 177591358923194\\
с<sub>14</sub> = 3533028620029147\\
с<sub>15</sub> = 70286590786211882\\
с<sub>16</sub> = 1398291777251722095\\
с<sub>17</sub> = 27817822320525771015\\
с<sub>18</sub> = 553411849636947006320\\
с<sub>19</sub> = 11009656751280514450481\\
с<sub>20</sub> = 219027731084943424487352\\

Sum  = 230620089806568708826141, что существенно меньше суммы c<sub>i</sub>, полученных
по формулам (!).\\ 
В то же время ясно, что и это решение не оптимально. 


** Обсуждение **

С условием этой задачи (для разных количеств мешков) я сталкивался не раз.
Однако ни разу не встречал решения лучше, чем 0 + 1 + 20 + ... + 20<sup>18</sup>.\\
Набор с суммой 241116123021589624090767 - это тот ответ, получив который 
я решил поместить данную задачу в марафон. Именно за его получение и 
обоснование в третьем пункте примечания обещано 9 баллов.

Разумеется, формулы (!) и метод, предложенный Олегом Полубасовым,
тривиально обобщаются на любое число мешков.\\ 
Например, формулы (!) для n мешков выглядят так: 

<m> c_{k} = 1 + c_{m} + sum{i=1}{m}{(n +1 - 2i)*(c_{k-i} - c_{i})} </m>, где m = [k/2]

** Награды **

Победителем конкурса, который являла собой задача 84, стал Олег Полубасов.
С чем я Олега и поздравляю!

За правильное и более оптимальное, чем у ведущего, решение задачи 84
Олег Полубасов получает 15 призовых баллов. За решение, совпадающее с 
решением ведущего Анатолий Казмерчук получает 9 призовых баллов.
За очевидное, но не слишком оптимальные решение Галина Крюкова и 
Николай Дерюгин получают по 3 призовых балла. За столь же очевидные, 
но еще менее оптимальное решение Влад Франк получает 2 призовых балла.


** Эстетическая оценка задачи - 5 баллов **
----