К дню знаний - задача из школьного детства:
Есть чашечные весы и шесть гирек весом 1,2,3,4,5,6 подписанные 1,2,3,4,5,6. Каково минимальное количество взвешиваний чтобы гарантировано определить правильно или неправильно подписаны гирьки?
Ответ в формате "Число взвешиваний: Последнее взвешивание", типа 4: 16 25.

(130) нет, третье берём (1,5,7) (4,9). Трёх всё равно хватает

(131) конечно, линейная оценка (N-4) крайне грубая, по идее должно быть что-то ~log(N)

(132) минимальные и максимальные + известные?

(134) Да

(133) думаю log(n)+x, где x=0|1 от четности n

(132) По-моему сходится. Красиво!

(136) не-не-не. Любишь ты упрощать и шапками кидаться. Функция может быть даже убывающей в некоторых точках (возможно в каких-то частных случаях решение ищется проще). Во-вторых с чего вдруг основанием логарифма должно быть e, там может быть какой- коэффициент.

(133) просто интуитивная оценка (ожидание). Сама формула может быть сложной, а может её вообще нет.

8 гирек тогда получается
1. (1,2,3,4,5)=(7,8) [1,2,3,4,5] [6] [7,8]
2. (1,2,3,7)=(5,8) [1,2,3] [4] [5] [6] [7] [8]
3. (8,1) = (6,3) [1] [2] [3] [4] [5] [6] [7] [8]

получается для первого шага надо набирать слева и справа сплошняком, без пропусков
сначала попробовать уравнять максимальное N набором суммы минимальных с 1
если не вышло с одним N то взять N и предыдущее и т.д.

интересно а это можно использовать как метод специфической сортировки?
когда известно что все числа в массиве уникальные и без пропусков

(141) точнее не сортировки а проверки на отсортированность

(142)+ количество условных операций уменьшается, только операции сложения, которая малозатратная

(140) 1. логично
2. а вот это вовсе необязательно, возможны (имхо, пока не доказано обратное) ситуации когда набор нескольких может быть выгоднее одиночного N.

(144) да, набор нескольких максимальных может быть выгоден при большом N
причем можно прикинуть что оптимальный размер группы это число шагов

так что сначала надо выяснить точную формулу числа шагов от N

У меня есть подозрения, что функция действительно немонотонная, и для 9ки не обойтись 3мя взвешиваниями, так как первое взвешивание даст разбивку на 2 группы в отличие от первого взвешивания для 8 и 10, где мы помимо двух групп (старшая и младшая) сразу получили третью, да ещё и с проверенным элементом.

(146) я об этом и писал в (138). Я всё-таки поясню логику оценки log(N): на каждом шаге количество групп у нас при нормальном раскладе увеличивается в 2-3 раза

(146) меньше 4 шагов для [1..9] у меня не выходит

1. 1+2+3+4+5+6 < 7+8+9 ? 21<24 [1..6][7..9]
2. 1+2+3+4+5 = 6+9 ? 15=15 [1..5][6][7,8][9]
3. 1+2+3+7 = 5+8 ? 13=13 [1,2,3][4][5][6][7][8][9]
4. 1+2 = 3 ?

(148) 1. не проходит: 6 и 7 можно поменять местами

(149) следующим шагом проверка

(148) (149) Ну 9 в любом случае можно взвешиванием 8<9 свести к 8, а там ещё 3 взвешивания. Но вот можно ли меньше 4?
(147) Тоже к этому склонялся. Но тут какая-то такая штука - есть красивые числа (вида k(k+1)/2 типа 6,10,15,21 - суммы арифметической прогрессий) - для них есть оптимизация по х1+..+xk=xn для старшей гирьки.
Есть другие красивые числа: если 8*n - полный квадрат, то для них есть оптимизация х1+..+xk=x/n-1/+xn для двух старших гирек. Т.е. 8,18,32,50..
Для трех старших гирек оптимизация еще реже: если 2*(n*n+n) - полный квадрат, т.е. это 8,49,288...
Возможно, правда, то есть и другие возможности оптимизации по комбинированию весов, а не только методом страрший-младший.
Но пока - чем больше n, тем реже нам будут встречаться красивые числа и тем дольше нам к ним добираться методом сравнения. Да и потом внутри полученных групп много какого-то другого, что сильно зависит от размера получившихся на предыдущем взвешивании групп.
То есть, если у нас n чисел, а ближайшее красивоe - N, мы сначала должны сделать n-N взвешиваний, а только потом оптимизироваться.
Тогда это число взвешиваний будет зажато между квкорень(n-1) и квкорень(n+1). Вот здесь у нас будет один логарифм по основанию 2, а потом добавиться ещё слагаемые - это уже кусок функции учитывающий оптимизацию - тоже по всей видимости логарифм с полупеременным хвостом.
Так, я пока закончился.
ЗЫ Я совсем не ожидал, что мы дойдём досюда

(150) Я имел в виду, что для 9 гирек можно первым взвешивание отделить гирьку 9: 8<9, а потом оставшиеся гирьки взвесить способом (139) - итого 4 взвешивания.
А у тебя наверное 4) 1+6=3+4 будет достаточно

(152) 2. 1+2+3+4+5 = 6+9
тут тоже проверяется 6-ка, если она 7 то равенства не будет

(153)+ суть в том что я (148) выполнял по алгоритму, который можно закодить
да он возможно не находит самый лучший вариант, но вполне рабочий выдает

(154) Нет. Вторым взвешиванием ты тоже  не проверяшь 6 и 7.
123457<698
12345=78
И [12345] [67] [89] остается под вопросом. Возможно остальными двумя взвешиванием это подбирается, но, согласись, не очень похоже на алгоритм, дающий заведомо работающий результат.

Ну и если прикладной вариант алгоритма пробовать реализовать, то любой наш оптимизированный вариант заведомо проигрывает попарному сравнению. Если только не сделать 'взвешивание" ооочень дорогим.

(155) да пропустил 7+8=15
1. 1+2+3+4+5+6 < 7+8+9 ? [1..5][6,7][8,9]
2. 1+2+3+6+8 < 5+7+9 ? [1..3][4][5][6][7][8][9]
3. 1+2=3 ?

(155) про прикладной алгоритм я подразумевал как раз составление вот этих равенств
попарное сравнение на больших N (сотни тысяч, миллионы и более) слишком затратно
например для N=1000 попарно сравнить это 2000 Если
а если "суммировать пополам" то сумм <1000 и одно Если

(157) *и одно Если на каждый шаг, а кол-во шагов для 1000 имхо <10

Алгоритм кстати относительно простой
1. Балансировка в левую подряд слева, в правую подряд справа, подбираем минимальную разницу <=
2. Разбивка на выявленные группы, это самое сложное ибо перестановки
3. Повторяем но уже влево и вправо берем из разных групп аналогично слева и справа

(157) Попарное сравнение требует n-1 сравнений:
1)   1<2
2)   2<3
     ..
n-1) n-1<n

(156) Не согласен с записью [1..5][6,7][8,9] после первого взвешивания, оно вообще никак следует из взвешивания.

(159) Мой пессимизм по поводу работы твоего алгоритма включает следующие мысли:
1) Поиск числа-разделителя - это извлечение квадратного корня, операция довольно дорогая;
2) Для N=1000 число-разделитель - 707, дырка, создаваемая этим числом - 56 грамм. То есть обмен местами, например, гирек 700 и 720 не изменит результат взвешивания. Т.е у тебя будут гирьки 679 до 735 в серой зоне - про которые ты не можешь сразу сказать в какой они группе. А пока есть неотделенные гирьки, ты не можешь быть уверенным ни в одном числе в группах. То есть после взвешивания по границе числа-разделителя тебе понадобятся дополнительные проверочные взвешивания;
3) Если алгоритм будет включать разные виды сравнения < > = <= >=, то перед каждым сравнением тебе надо провести такое же контрольное, где ты должен определить какой знак должен быть. То есть просчитать сумму индексов массива слева и справа, определить результат сравнения, потом аналогично просчитать сумму уже элементов массива слева и справа, определить результат сравнения, а потом сравнить одинаковы ли результаты сравнения. Это фактически удвоит количество необходимых операций сравнения и суммирования.
4) Если стоимость операции суммирования сравнима со стоимостью операции сравнения (а где это не так?), то попарное сравнение выиграет на первом же взвешивании.
5) Отделив группу справа с помощью числа-разделителя ты всё равно будешь вынужден как-то упорядочивать группу старших чисел между собой, то есть для N=1000 тебе понадобится как минимум еще 1000-707+2=295 взвешиваний, которые ты вынужден будешь делать. Возможно их можно группировать чтобы использовать при определении элементов из младших групп, но по какому принципу? Тем более, что если при этом брать не больше одного за раз, то количество взвешиваний будет то же - 295.
6) Возможно в той ссылке на Википедии, которую ты мне любезно дал, уже есть что-то подобное с каким-нибудь красивым названием "метод золотого сечения". Тут я не силён.

НО! А вдруг?

(156) Нет. 8 и 7 меняются местами.

А для 9 так вроде работает?
1. 123 < 7? [123] [45689] [789]
2. 12457 < 389? [12] [45] [89]
3. 1348 = 259?

(160)  Для N=1000 число-разделитель - 707
Тебе же необязательно разбивать на 2 группы, а даже лучше на 3.
Первым взвешиванием можно разбить на 3 группы без серых зон: [1..681][682..732][733..1000]

(162) Нет.
в 1. может оказаться например 125<9

(164) Согласен, аргументация неверная. Но схема, возможно, все равно работает. Не уверен, что можно придумать перестановку, которая ее сломает. 3 и 5 действительно могут быть перепутаны, но только если перепутаны 7 и 9, а там начнет ломаться второе или третье взвешивания. И так далее.
Но доказать пока не могу.

(165) перепутаны не 3 и 5, а у тебя все числа в "серой" зоне
По сути ты знаешь только, что в первой группе точно была "1" и не было ничего >5, а твоя "7" на самом деле от 7 до 9. При таких вводных смысла во втором взвешивании нет, там слева и справа почти что угодно.

(162) Да. Поздравляю. Проверил простым перебором.

(166) Выводы у (162) неверные по итогам взвешивания, но решение оказалось правильное.

Итого пока: 0,1,2,2,2,2,3,3,3,3.
11 гирек за 4: 11>10 и 3 взвешивания для 10 оставшихся гирек. Может кто-нибудь придумает в 3?

И решение (162), кстати иллюстрирует, что возможны комбинации, когда каждое конкретное взвешивание не даёт особого результата, но постепенно сужает круг: уменьшает количество вероятных распределений весов по гирькам до одного единственного.

(167) Держи на 11, вроде все четко
1234 < 11? [1234] [5678910]
15611 = 4910? [23] [56] [78] [910]
24579 = 36810?

Много гирек, тяжело уже мысленно следить. Написал бы кто приблуду на 1с:
1. Задаётся количество номеров гирек.
2. Первое взвешивание: номера слева и справа
Полный перебор всех вариантов с выводом подходящих
3. Второе взвешивание.
Полный перебор всех вариантов с выводом подходящих и с учётом 1.
...

(167) Проверь пожалуйста перебором, раз у тебя он запрограммирован, нечеткое решение на 12
123456 < 1112? [123456(7)] [(6)78910(11)] [(10)1112]
12711 = 5610? [12] [34] [56] [89] ?
135811 = 24679?

(169) Да!
Но чёрт возьми, как? (с)
Магия какая-то...

(170) Тут patapum уже забрёл туда, где после первого взвешивания остаются почти все комбинации, а их n! - вывод подходящих займёт продолжительное время)
Ещё прикол в том, что порядок взвешиваний не важен, так что даже те которые мы подобрали можно перевернуть так, что до последнего взвешивания будет больше количество вариантов.


(171) Если мы в таком темпе будем продвигаться, я на аэродром не попадаю!
Я проверку набросал за пару минут в 1С, а с перебором триллиона комбинаций - это надо куда-нибудь в си. Может у кого есть под рукой?

Может и для n<=10 можно уменьшить число взвешиваний? 7 за 2?

(179) Не сразу понятно 12711 = 12,7,11 или 1,2,7,11?
Если
(1,2,3,4,5,6)<(11,12)
(1,2,7,11)=(5,6,10)
(1,3,5,8,11)=(2,4,6,7,9)
То
1,2,3,4,5,7,6,8,10,9,12,11.

Нет.

(173) Да, план был такой, но не срослось. Первое неравенство плохо вырезает, разница 2, вариативности много, и сравнений осталось много
(172) Попробуй прогнать на 7: 236 = 47, 137 = 56. А вдруг?
Общий метод на 7ке не срабатывает, 123 < 7 вырезает [123] [456] и 7, но дальше надо брать 14 против 36, а уравновесить их нечем

(174) Нет
1,2,3,4,5,6,7
1,2,5,6,7,3,4
2,1,3,5,4,7,6
2,1,5,7,6,4,3
2,5,1,3,6,4,7
3,6,1,4,7,2,5
5,2,1,6,3,7,4
6,3,1,7,4,5,2

Упрощенно подход тогда видится таким:
1) Делим массив на 3 группы (на худой конец 2): младшие, средние и старшие, так чтобы сумма младших равна сумме старших или на 1 меньше.
2) Дальше берём старших из одних групп и младших из других. Одна из групп может быть общей (лучше самая многочисленная -младшая?), её можно на 3 части поделить - старшие к старшим, младшие к младшим.
3) Получаем 4-9 групп - делим их по тому же принципу, подбирая из некоторых из них старшие элементы, а из некоторых младшие. То есть каждую группы поделим пополам, а одну - можно на три части.
4) Если на каких-то этапах получаем группу из одного элемента - можем использовать его в комбинировании других весов для получения нужных сумм. Да и серые группы целиком можно использовать для комбинирования сумм, а уже потом разделять.
5) Всегда возможно, что для конкретной математики деление на группы не удастся получить как хотелось бы, и понадобятся корректировки.
6) Если на каком-то этапе что-то не получается, то можно дополнительными взвешиваниями ситуацию разрулить, или возможно сам по себе полученный набор отсеет серые места.
Мы изобрели бинарный поиск или что-то типа? Не силён в теории просто.

Функция похоже натуральный логарифм?

(176) цель на каждом шаге уменьшить максимальный размер получающихся групп.
Поэтому каждую группу делим на 3 части.
Когда групп несколько, то стараемся большие группы делить ровнее, а дисбаланс закрывать из маленьких.
Функция логарифм, но не натуральный. В пределе по основанию 3. Но предел недостижим, например на первом шаге разделить на 3 равные части никак не получится.
Конечно очень прикольно получится, если за счёт этих поправок окажется натуральный логарифм, но выглядит фантастикой

(176) Какой-то бинарно-тринарный поиск получается... Вот вам пока 15 гирек за 3 взвешивания, чтобы немонотонность функции найти.
1. 1234567 < 14;15? [1234567] [89;10;11;12;13] [14;15]
2. 1238;14;15 = 567;12;13? [123] 4 [567] 8 [9;10;11] [12;13] [14;15]
3. 1589;12 < 37;11;15

Так что решили в конце? Ушлоганы на рынке обманут по любому?

(179) Подготовленный 1сник за 2-3 необходимых и достаточных действия с гирьками объяснит быдлу в чём тот не прав.

(180) а бегает он хорошо? )

(178) Проверю попозже, надо будет алгоритм перебора чуть соптимизировать, может тогда 15 вытянет. И результат второго взвешивания для меня не выглядит беспорным - надо проверить.
В (177) прям как из  своей головы прочитал - те же мысли, за одним исключением: "каждую группу делим на 3 части" - не согласен.

(182) 2. почему? Деля 3 должны быстрее придти к цели

(181) Конечно, ведь перед этим он читал про бег  Кто бежит?

(183) Видимо ступил, согласен.

(182) Можешь проверить, но вроде бы он гарантирован. Что может быть не так со вторым взвешиванием? Первое разделило четко без вопросов. Во втором мы берем строго по алгоритму: влево самые маленькие из групп, вправо самые большие. Ну кинули влево целиком группу 14;15, так в ее суммарном весе мы уверены. Я как раз взял 15-ку, поскольку там четко делит первое взвешивание и дальше надо просто веса подобрать.
А вот 12 - это классический пример полной гадости. Нельзя построить первое взвешивание, чтобы оно разбило без неопределенности. Например, начало как я рисовал 123456 < 11;12? - делит примерно на [123456] [789;10] [11;12]. Но только могут быть перепутаны 6 и 7, 10 и 11. И как дальше разбираться с такими группами - непонятно.

(186) Думаю, что в общем случае нельзя взвешивать уверенно взвешивать и младших, и старших из двух разных групп. Имено это я хотел выразить словами про "3 части", но не сумел. Просто часто такие косяки подправляет математика или последующие взвешивания. Но вряд ли всегда.
В твоем случае на весах  вместо
1238;14;15 = 567;12;13
могут быть
1238;14;15 = 467;11;13

(187) В этом случае надо подбирать не = а <

(187) Почему нельзя? Можно. Если слева у нас только младшие из групп, а справа только старшие, то заменив что-то в левой части, ты левую часть увеличишь, а в правой части - правую уменьшишь. И то и другое приведет перекосу, причем в одну сторону, то есть нельзя компенсировать одно другим.
В конкретном примере ты уменьшил правую часть на 2, а левую оставил прежней. Равенство неверно, значит нумерация нарушена, дальше можно не взвешивать.

(187) ты же сам выше высказывал очень важную мысль: порядок взвешиваний НЕ важен. Но поменяв порядок взвешиваний для человека всякая логика теряется: например если для исходной задачи мы взвесили 5+3 6+1, мы казалось бы не получили ценной информации (все гири остались в серой зоне), но мы всего в одном взвешивании от результата!
Поэтому (имхо в общем случае) нет большой необходимости гнаться за точными равенствами или +1, достаточно правильно разбивать на пересекающиеся группы. Т.е. все серые зоны разрулятся при последующих взвешиваниях, эту мысль ты тоже высказывал.

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

(190) Угу фактически составление системы уравнений (неравенств)
У которой есть только одно решение

(191)+ Тут получается обратная задача решению системы - наоборот ее построить
Для заданных N переменных Xn, где X(n+1) = Xn + 1

(190) Нет большой необходимости гнаться за точными равенствами или +1, достаточно правильно разбивать на пересекающиеся группы - классно, только алгоритм такого разбиения фиг придумаешь, а находить его перебором - просто умрешь. На один готовый (!) пример на 15 вычислительной мощности не хватает... Так что, пока я другого способа, чем подбирать на равенство или +1 не вижу. Если видишь, реши 12 за три взвешивания )))
Ну и бонусом для 13:
1. 12345678 = 11;12;13? [12345678] [9;10] [11;12;13]
2. 1239;11;12 = 78;10;13? [123] [456] [78] 9 10 [11;12] 13
3. 1479 36;12

>реши 12 за три взвешивания
1. 1+2+3+4 < 12 ? [1..5][6..9][10,11,12]
2. 1+2+3+4+6+10 = 5+9+12 ? [1234][5][6][7,8][9][10][11][12]
3. 1+2+7+6 < 4+8+5 ?

(194)+ проверьте плиз
если верно то алгоритм вполне работает

(193) если утверждения верны, то "решить" не проблема. Проблема решение проверить)))

(187) Слишком много и слишком быстро, видимо я немножко оверфлоу. Ещё ж куча мыслей интересных - мерещатся трапеции, которые мы делим 2 линиями параллельными основаниям на три равные по площади части)
Плюс Garykom в (192) завел речь о СЛАУ, а там миллионами от гугла запахло (или это программистская байка?).

И алгоритм для проверки надо соптимизировать, хотя бы до 15 гирек

(194) у тебя во всех 3 взвешиваниях 1+2 вместе, т.е. различить ты их заведомо не сможешь

(198) да, тогда только за 4 взвешивания

(197) а 12 проверяется?
вот на всидку
1. 1+2+3+4+5 < 11+12
2. 1+2+6+7+11 = 5+10+12
3. 1+3+6+8+10+12= 2+4+5+7+9+11

(200) не проверяй, 10 и 12 явно можно поменять местами

Вообще интресная трактовка:
у нас есть log2(N!) бит информации,
каждое взвешивание дает какое-то количество бит (тоже можно посчитать).
Задача сводится к получению максимально количества информации на каждом шаге, большая проблема что нужно только новая информация полученная за шаг.

+(202) от бит конечно же можно уйти и считать просто количество оставшихся вариантов (подходящих перестановок) после каждого взвешивания

(200) А ты в первом неравенстве 6 специально не взял?
1+2+3+4+5+6 < 11+12 дает разницу 2. А у тебя 8, то есть заменить можно примерно все примерно всем

(202) Думаю, нет. Такая постановка задачи противоречит "мы казалось бы не получили ценной информации (все гири остались в серой зоне), но мы всего в одном взвешивании от результата!" в (190).

(205) ну там человеческая оценка информации. А математически, если мы уменьшили количество подходящих перестановок с N! до некоторого F, то мы получили (log2(N!)-log2(F)) бит информации

(204) да специально, общее предположение было, что делить нужно на как можно более равные (по числу членов) группы.

(205) Попробуй, когда будет время, на 12 прогнать
1+2+3+4+5+6 = 10+11
1+2+7+11 = 5+6+10
3+5+8+12 = 2+4+6+7+9

(207) А я думаю, что делить надо на равные части не по числу членов, а по сумме. Поэтому-то у меня прямоугольная трапеция и возникла (перед первым взвешиванием прямоугольный треугольник). То есть по сути  если представить наши числа на оси координат, где х-номер, у-значение, получиться прямоугольный треугольники. А перпендикуляры из обоих чисел-разделителей (тех которые поделят наши группы для "правильного" взвешивания) - поделят наш треугольник на три равные по площади части.

(208) Только что запустился с твоими 15.
"Сейчас его отмоют от крови и он снова будет готов к работе" (КВН Питер)

(206) Не согласен с "на каждом шаге". Решение задачи - получение информации, но каждый шаг по отдельности не обязан максимизировать полученную информацию. Наш максимум информации - одна гирька в каждой группе. У нас же алгоритм по сути - должен быть решетом (в хорошем смысле), зачем нам на одном шаге информацию о весе конкретной гирьке, если мы можем этим шагом улучшить оценку множества гирек?
Для 15 гирек: Вместо 1+2+3+4+5=15 лучше 1+2+3+4+5+6+7 < 14+15
Но это всё так - мысли вслух. Информация - абстракция, поэтому в зависимости от вкладываемого смысла, думаю, можно любые трактовки делать.

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

(212) Ну наш перебор уже сильно похож на алгоритм, нет? Понятно, что математика там свои поправки вносит, но уже 15 за 3 маячит!

(178) Поздравляем Патапума!

15 гирек за 3 взвешивания:
1. 1+2+3+4+5+6+7 < 14+15
2. 1+2+3+8+14+15 = 5+6+7+12+13
3. 1+5+8+9+12 < 3+7+11+15

(208) Нет. 12 гирек не решены.

1,3,7,4,2,6,5,8,9,12,11,10

1. 1+3+7+4+2+6=12+11
2. 1+3+5+11=2+6+12
3. 7+2+8+10=3+4+6+5+9

(215) Печалька... А это единственная перестановка, которая подходит или еще есть? Интересно, насколько сито хорошее получилось
Вообще, 3 взвешивания могут получиться до 18, если повезет (раз 6 можно за два). Решены: 7, 8, 9, 10, 11, 13, 15. 12 и 14 явно проблемные.

(216) Не, там сотни перестановок.
13 проверяю пока - час где-то займёт, там оптимизироваться тяжело в проверке.
Да и в остальных возможны оказии с понижением оценки, а вдруг? 7 за 2, например, надо бы посмотреть.

Мог 13 и не проверять, оно математически точное, как и 15.
7 за 2 - моя ставка, что не получится.
Начало было срастаться 19 за 3, теоретически могло сработать. Проверка 12345678 < 18;19 - делит на диапазоны 8 гирек, 9 и 2. Но на втором шаге не сошлось уравновесить.

Да, в (151) были формулы для некоторых красивых чисел: 6,8,10,15,18,21,32,49,50.. Соответственно на 1 больше тоже будут красивыми, но /возможно/ с потерей одного взвешивания (6 за 2, 7 за 3).
Ну и сложность проверки, конечно, уже близка к моей предельной...

(193) Поздравляем Патапума!

13 гирек за 3 взвешивания:
1. 1+2+3+4+5+6+7+8 = 11+12+13
2. 1+2+3+9+11+12 = 7+8+10+13
3. 1+4+7+9 = 3+6+12

(219) ты что на 1С проверяшь?

(221) Я же не думал, что мы дойдем до 15 гирек) Там задача была про 6 гирек, ответ я на бумажке проверял.

И кстати (191) - интересная мысль. Там правда степень двойки, но на маленьких n можно попробовать на низком уровне поковыряться.

(222) Проверь еще один вариант на 12, пожалуйста. Как с подбором взвешиваний, есть результаты?
1+2+3+4+5+6 < 11+12? [1;2;3;4;5;6(7)] [(6)7;8;9;10(11)] [(10)11;12]
1+2+7 < 5+6? [1;2] [3;4] [5;6] 7 [8;9;10(11)] [(10)11;12]
1+3+8+11 = 6+7+10?

(223) Нет(
1,2,3,4,6,5,7,9,8,11,10,12
3,2,1,4,5,7,6,8,9,10,11,12
2,1,4,3,7,5,8,6,9,10,11,12
2,3,1,4,5,7,6,8,9,10,12,11
ну и ещё около 30, весь листинг не буду приводить

(224) Спасибо! Короче, лажа получается, если первым взвешиванием не получается поделить четко. Только для 9 срослось, непонятно почему...

(225) А про подбор взвешиваний - там задачка алгоритмически интересная и для небольших n в принципе реализуемая, но надо очень хорошо продумать алгоритм, когда-нибудь в далёком-далёком будущем, когда прям совсем будет настроение.
Просто тогда можно строго показать, что меньше взвешиваний нет, ну и найти все возможные варианты.
Итак:
числа: 1..n
2 операции взвешивания: больше, равно (третья "меньше" - зеркальный вариант "больше" не нужна)
3 операции учета веса гирьки: сложение, вычитание, обнуление (справа, слева, не стоит)

Пока в общих чертах видится так:
Мы к нашим n числам применяем одну из операций: сложение, вычитание, обнуление. Если результат >=0, то запоминаем взвешивание как "правильное". Повторяем с другим набором операций.
Искомое число взвешиваний - когда на следующем шаге нельзя будет получить "правильное" взвешивание.
Вернее их можно будет получить, но только повторяющие предыдущие или зеркальные к "равно" (когда гирьки меняются знаками) - тут можно просто счетчик количества тогда ввести ВсегоУжеИспользованоОпераций=ВсегоБольшеДо+2*ВсегоРавноДо и проверять, если на текущем шаге количество возможных операций равно ВсегоУжеИспользованоОпераций, то значит на предыдущем шаге мы нашли идеальный набор взвешиваний.
Ну и плюс обрубать концы если думаем найти за 3 взвешивания, то проверять надо только до 4го - а то проверкой в бесконечность устремимся.
Но что-то оценка сложности алгоритма не внушает оптимизма. Вроде ( 2*(3^n) ) и в степени "число взвешиваний + 1", ну с поправкой на то, что неудачные взвешивания проверять дальше не надо.

(226) Сомневаюсь, что есть такая формула. Это всё равно как вывести общую формулу простых чисел среди натуральных.

(227) Ну формулу пока и не искали. Хотя может когда найдём, то как раз и выведем формулу поиска простых чисел.
Но зато пришли к мнению, что предел функции ну очень похож на натуральный логарифм.
Ещё поразвлекались с поиском оптимального алгорима
А ещё проверка решения - нетривиальная задача...
А ещё показать, что решения лучше не существует...
А алгоритм в (226) это не "подбор взвешиваний", а "перебор всех взвешиваний", неправильно написал. Он чтобы показать, что решения лучше не существует и подобрать все возможные решения. Ну и понятно, что он относительно рабочий только для маленьких n.

(228) А сколько уже получилось взвешиваний для каждого натурального числа гирек?
0 1 2 2 ...

(229)До15: 01222233333х3х3
RomanYS предложил, Garicom развил, Papatum подхватил - и 15 за 3, никогда бы не подумал.

Дерзните - и, быть может, ваше имя впишут в эти страницы! Они ждут своих героев!

(230) Нет, спасибо.
А пока количество гирек на каждом интервале одинаковости укладывается в квадрат взвешиваний:
0^2 1^2 2^2 3^2