Три весёлых гири

[Утундрий]

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

Сколько всего монет получил раб, если известно, что веса всех трёх гирь различны и
кратны лоту? Также известно, что купец дал рабу наименьший по весу набор гирь, не позволивший тому заработать сперва больше одной монеты.

[gris]

сначала купец дал 1 4 8, а раб вместо 4 взял 3=4-1.
то есть наб0р 1 3 8 взвешивает всё от 2 до 12
обосновал.

[gris]

Я даже проснулся от гнетущего молчания в теме. Наверное, я не так понял условие. Когда в босоногом на базаре торговал, то гири ставились и справа, и слева. То есть уравновешивание предметов означало $ \pm a \pm b ... \pm z ==0$ с произвольным выбором знаков.
Допустим, что среди первоначального набора есть гиря 1 лот. Из условия купца вторая гиря не может быть ни 2, ни 3. Допустим 4. Третья ни 5, ни 6, ни 7. Иначе уравновесим 2 лота. Набор 1 4 8 с общей массой 13 подходит. Набор 1 5 7 не подходит. Дальше больше 13.
Допустим первая 3, вторая 4 и третья вынужденно 7. Уже 14. И дальше больше. Итак, 1 4 8 набор купца.
Допустим, меняем 1. На чётное нельзя, не уравновесим 3. Нечётные не дают 2.
Допустим, меняем 4. Пробуем доступные. 1 3 8 даёт всё до 12; 1 5 8 даёт всё до 9; 1 7 8 даёт всё до 3; 1 9 8 даёт всё до 3; 1 11 8 даёт всё до 5; 1 12 8 даёт всё до 1; 1 13 8 даёт всё до 1;
Допустим, меняем 8. Пробуем доступные. 1 3 4 даёт всё до 8; 1 5 4 даёт всё до 6; 1 7 4 даёт всё до 1; 1 9 4 даёт всё до 1; 1 11 4 даёт всё до 1; 1 12 4 даёт всё до 1; 1 13 4 даёт всё до 1;
Итак, 1 4 8 превращённое в 1 3 8 даёт 13 монет!

(Оффтоп)

Конечно, перебор плохо. Но я сперва не до конца прочёл условие и подумал, что гирю надо не менять, а добавлять. Я в любимом PARI начирикал.

{
w=vector(16);
for( a=-1,1,
for( b=-1,1,
for( c=-1,1,
  k=a*1+b*4+c*8;
  if( k>0, w[k]=1)
)));
\\print("weight to replace: ",w);}
 
for( i=1,16, if( i==1 || i==4 || i==8 || w[i]==0, next); 
  lots=vector(31);
  for( a=-1,1,
  for( b=-1,1,
  for( c=-1,1,
  for( d=-1,1,
    k=a*1+b*4+c*8+d*i;
    if( k>0, lots[k]++)
  ))));  
  for( j=1,31, 
    if( lots[j]==0, 
      print1 ("able ",j-1," for[1 4 8 ",i," : [") ;
      for( m=1,28, print1(lots[m]," ")  ); print("]"); 
      break) 
    );
)}

able 16 for[1 4 8  3 : [3 3 3 4 3 3 3 4 2 2 2 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
able 14 for[1 4 8  5 : [3 3 3 4 3 2 2 4 3 2 1 2 2 1 0 1 1 1 0 0 0 0 0 0 0 0]
able 16 for[1 4 8  7 : [2 3 4 5 3 2 2 2 1 2 3 3 1 1 1 1 0 1 1 1 0 0 0 0 0 0]
able 14 for[1 4 8  9 : [2 2 3 5 4 2 1 2 2 1 1 3 3 2 0 1 1 1 0 1 1 1 0 0 0 0]
able 16 for[1 4 8 11 : [2 2 3 3 2 2 3 3 1 1 2 2 1 2 2 2 0 1 1 1 0 1 1 1 0 0]
able  1 for[1 4 8 12 : [3 0 3 3 3 0 3 3 3 0 2 2 2 0 2 2 2 0 1 1 1 0 1 1 1 0]
able 14 for[1 4 8 13 : [2 1 2 3 3 1 1 3 3 2 1 2 2 1 0 2 2 2 0 1 1 1 0 1 1 1]

И что максимально? Прочитал ещё услови, ещё перепутал и наконец уже во сне подкорректировал программку и получил результат. Захотелось обобщить.

Правильно

[Утундрий]

gris в сообщении #1578807 писал(а):

Правильно

Думаю, да. Но у меня тоже, собственно, перебор. Только на бумаге. Могу ошибаться.

Олимпиадное решение пока не придумал.

[zykov]

Вообще про гири - оптимально брать степени тройки (1, 3, 9, 27...).
Чтобы понять, как гири расставить, нужно число записать в троичной системе, но не с цифрами (0, 1, 2), а с цифрами (-1, 0, 1).

[Dendr]

Утундрий в сообщении #1578810 писал(а):

Олимпиадное решение пока не придумал.

Ну, допустим, как-то так...

Раз раб смог взвесить один лот, либо была дана гиря единичной массы, либо две гири с разницей $1$, либо одна гиря весит на $1$ больше или меньше двух других. То есть: дан набор $\{1, x\ge2, y>x\}$, либо $\{x>1, x+1, y>1\}$, либо $\{x>1, y>x+1, x+y\pm1\}$. Но два лота взвесить не мог.
Соберем все варианты весов, которые раб мог бы составить.
Из первого набора: $1, x, y, 1+x, 1+y, x+y, 1+x+y, x-1, y-1, y-x-1, y-x, y-x+1, x+y-1$. Ни одно из этих чисел не равно $2$, значит (отбрасывая априорные случаи: $x$ начинается с двух, $y$ - с трех, их сумма с пяти), $x\ne2, x\ne3, y\ne3, y-x\ne2, y-x\ne3, y-x\ne1$ Тогда $x\ge4, y-x\ge4$, откуда суммарный вес трех гирь не меньше $1+x+y=1+2x+(y-x)\ge1+2\cdot4+4=13$. И достигается этот минимум только при превращении всех нестрогих неравенств в равенства, то есть $\{1, 4, 8\}$.
При рассмотрении второго набора заметим, что мы не допускаем вес никакой гири равным $1$ или $2$. То есть $x\ge3, y\ge3$. Если $y>x$, то следует исключить случаи $y=x+2, x+3$, значит, $y-x\ge4$, тогда суммарный вес трех гирь будет $x+(x+1)+y=3x+1+(y-x)\ge3\cdot3+1+4=14>13$. Если $x>y$, то $x-y\ne2, x+1-y\ne2$, откуда $x-y\ge3$, суммарный вес $y+x+(x+1)=3y+2(x-y)+1\ge3\cdot3+2\cdot3+1=17>13$.
В третьем наборе имеем аналогично $x\ge3, y-x\ge3$, тогда $x+y+(x+y\pm1)=2(x+y)\pm1=4x+2(y-x)\pm1\ge4\cdot3+2\cdot3-1=17>13$.
Итак, вес гирь, выданных купцом - $\{1, 4, 8\}$.

Менять самую маленькую гирю раб не мог: набор $\{x, 4, 8\}$ помогает взвесить $4, 8, x, x+4, x+8, 12, x+12, |x-4|, |x-8|, |x-12|$, то есть во всех возможных случаях, когда используется новая гиря, веса одинаковой четности. Тогда взвесить $2$ и $3$ одновременно невозможно.

Пусть он поменял самую большую гирю. Набор $\{1, 4, x\}$ дает разновесы для $1, 4, x, 5, x+1, x+4, x+5, 3, x-1, |x-4|, |x-5|, x+3, |x-3|$.
Всего $13$ вариантов, но они собираются в тройки: $(3, 4, 5)$, $(x-1, x, x+1)$, $(x+3, x+4, x+5)$, $(|x-5|, |x-4|, |x-3|)$. Вес двух лотов должен быть среди одной из них, но тогда эта тройка либо $(0, 1, 2)$, либо $(1, 2, 3)$, либо $(2, 3, 4)$. В любом случае получим, что мы собрали все веса от $1$ до $5$ и еще две тройки, возможно, с перекрывающимися значениями, то есть не больше $11$ различных весов. Не станем анализировать глубже, просто запомним этот результат, что в этом случае максимальный заработок раба теоретически равен одиннадцати монетам.

Рассмотрим теперь вариант, когда у раба набор $\{1, x, 8\}$. Тогда он может взвесить $1, 8, 9, x, x+1, x+8, x+9, 7, x-1, |x-8|, |x-9|, |x-7|, x+7$.
Снова обратим выделим тройки: $(7, 8, 9)$, $(x-1, x, x+1)$, $(x+7, x+8, x+9)$, $(|x-7|, |x-8|, |x-9|)$. Необходимо взвесить также веса от $2$ до $6$ включительно. Для этого нам понадобится занять две тройки, которые либо перекроются друг с другом для четырех лотов, либо одна перекроется с явным значением - $1$ или $7$. Еще одна тройка должна будет занять веса, большие $9$.
Очевидно, что вторая и третья тройки из приведенного списка не могут быть рядом. Значит, используется четвертая. А третья - как раз и будет занимать большие веса. Для лучшего результата нам потребуется $(x+7, x+8, x+9)=(10, 11, 12)$, что позволит рабу получить двенадцать монет. Проверим $x=3$.

Тогда получатся тройки $(2, 3, 4)$ и $(4, 5, 6)$, что покрывает промежуток полностью. Таким образом, отложенное ранее рассмотрение можно не проводить, и ответ на задачу: купец выдал рабу гири $\{1, 4, 8\}$, а потом тот заменил $4$ на $3$.