2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Три весёлых гири
Сообщение25.01.2023, 23:25 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Три весёлых гири
Сообщение26.01.2023, 03:32 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Три весёлых гири
Сообщение26.01.2023, 08:11 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Я даже проснулся от гнетущего молчания в теме. Наверное, я не так понял условие. Когда в босоногом на базаре торговал, то гири ставились и справа, и слева. То есть уравновешивание предметов означало $ \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]



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

Правильно :?: :?: :?:

 Профиль  
                  
 
 Re: Три весёлых гири
Сообщение26.01.2023, 08:44 
Заслуженный участник
Аватара пользователя


15/10/08
11535
gris в сообщении #1578807 писал(а):
Правильно :?: :?: :?:
Думаю, да. Но у меня тоже, собственно, перебор. Только на бумаге. Могу ошибаться.

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

 Профиль  
                  
 
 Re: Три весёлых гири
Сообщение26.01.2023, 13:55 


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

 Профиль  
                  
 
 Re: Три весёлых гири
Сообщение27.01.2023, 11:09 


02/04/18
240
Утундрий в сообщении #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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

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



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

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


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

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