Константин Кноп предложил занятную задачку на взвешивание.

У царя Гериона есть 11 внешне малоразличимых слитков, весом 1,2,3,...,11 кг (ну да, древние греки первыми изобрели килограмм).
И есть мешок, выдерживающий вес 11 кг — при перегрузе он порвётся.

Архимед узнал вес всех слитков и хочет доказать Гериону, что конкретный слиток весит 1 кг.

За какое минимальное количество взвешиваний единственным мешком он сможет это сделать?
Взвешивание состоит в том, чтобы положить один или несколько слитков в мешок, поднять его и не порвать, либо порвать (это было бы последнее взвешивание).

P.S.
Буду рад узнать и другие задачи на взвешивание, кроме набивших оскомину баянистых про одну фальшивую монету. То есть, можно и про фальшивую монету, но чтобы был какой-нибудь элемент внезапности, наподобие того же непрочного мешка.

Здравствуйте, Кодт, Вы писали:

К>Константин Кноп предложил занятную задачку на взвешивание.
Константин всё так же стервенело ловит ЧГК-читеров или его таки отпустило?

К>У царя Гериона есть 11 внешне малоразличимых слитков, весом 1,2,3,...,11 кг (ну да, древние греки первыми изобрели килограмм).
К>И есть мешок, выдерживающий вес 11 кг — при перегрузе он порвётся.

К>Архимед узнал вес всех слитков и хочет доказать Гериону, что конкретный слиток весит 1 кг.

К>За какое минимальное количество взвешиваний единственным мешком он сможет это сделать?
К>Взвешивание состоит в том, чтобы положить один или несколько слитков в мешок, поднять его и не порвать, либо порвать (это было бы последнее взвешивание).

Ну, для начала надо определиться с нотациецей.
Я предлагаю такую:
Строка вида
{1,2,3,4,5}{6, 7, 8, 9, 10, 11} означает, что Архимед уже сумел разделить слитки взвешиваниями на 2 кучки, так, что Герион понимает, что в одной лежат слитки
1,2,3,4,5, а в другой 6, 7, 8, 9, 10, 11 кг весом.
Строка вида
1+2+3+4 = 10
Означает, что Архимед положил в мешок слитки 1, 2, 3 и 4 кг весом и приподнял. Если сумма меньше 12, то мешок не порвётся...

	Я знаю решение из 5 взвешиваний...
	{1,2,3,4,5,6,7,8,9,10,11} 1+2+3+4 = 10 1+2+3+5 = 11 {1,2,3,4,5}{6, 7, 8, 9, 10, 11} 6+1+2 = 9 6+1+3 = 10 6+1+4 = 11 {1}{2,3,4}{5}{6}{7, 8, 9, 10, 11} Прикольно, что ещё и мешок не рвём Наверное, если рвать, можно короче, но не уверен. Можно тупо компиком перебрать, но пока лень...

К>P.S.
К>Буду рад узнать и другие задачи на взвешивание, кроме набивших оскомину баянистых про одну фальшивую монету. То есть, можно и про фальшивую монету, но чтобы был какой-нибудь элемент внезапности, наподобие того же непрочного мешка.
Ну, как бе... и это только по-русски и яндекс...
Например
Кстати, у кого есть доступ, стоит добавить задачи с мешком сюда...

Есть две комбинации чисел, если их представить в двух слитках, в сумме дающие 11.
2+9 = 11
1+10 = 11

Первое взвешивание
1+9 = 10 мешок не рвется, откладываем слиток в 9кг
1+10 = 11 мешок не рвется, откладываем слиток в 10кг
2+9 = 11 мешок не рвется, откладываем слиток в 9кг
2+10 = 12 мешок рвется
Значит в первой паре был слиток весом 1 кг.
Если нам попадется слиток весом в 3 и больше коллограма

Здравствуйте, -n1l-, Вы писали:

N>Есть две комбинации чисел, если их представить в двух слитках, в сумме дающие 11.
N>2+9 = 11
N>1+10 = 11

N>Первое взвешивание
N>1+9 = 10 мешок не рвется, откладываем слиток в 9кг
N>1+10 = 11 мешок не рвется, откладываем слиток в 10кг
N>2+9 = 11 мешок не рвется, откладываем слиток в 9кг
N>2+10 = 12 мешок рвется

Ты всего лишь показал Гериону, что есть две пары, которые не рвут мешок.
Таких пар очень много...
Пока что всё, что м можем утверждать, что среди этих 4-х нет 11...



например, та же схема:
3+8 = 10
2+9 = 11

2+8 = 10, откладываем 8
2+9 = 11, откладываем 9
3+9 = 12 и мы впарили 2, как 1, это если Герион нам поверит, конечно...

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

И причем это верное предположение так как

Архимед узнал вес всех слитков и хочет доказать Гериону, что конкретный слиток весит 1 кг.

Нужно ждать кодта за деталями к задаче.

Здравствуйте, -n1l-, Вы писали:

N>Ты в своем решении делаешь то же самое, ты предполагаешь что уже знаешь вес какого-то слитка.
1) Вес слитков известен по условию. Архимед их как-то взвесил, и теперь ему надо убедить Гериона в том, что конкретно вот этот слиток — 1кг...

N>Например в твоем случае есть еще куча других комбинаций в три слитка которые не рвут мешок.
Ну положим, что Архимед читер. Он написал на слитках веса от 1 до 11, а на самом деле там другие.
Покажи перестановку чисел от 1 до 11, которая при подстановке в моё решение, не рвёт мешки пять раз, но показывает не на 1, а не что-то другое...

Здравствуйте, Erop, Вы писали:

К>>Константин Кноп предложил занятную задачку на взвешивание.
E>Константин всё так же стервенело ловит ЧГК-читеров или его таки отпустило?

Про это я не знаю.
Раньше он чередовал интересные задачки с внутричегекашными дрязгами, но поскольку я в этом никаким боком, то просто игнорировал.
А потом надолго замолчал в ЖЖ вообще. Может, в фейсбучике воюет или вообще в линкедине каком.

E>Я знаю решение из 5 взвешиваний...

Я знаю решение из 2 взвешиваний
(UPD. убрал спойлер)

E>Например

Про 40-кг комплект гирь не знал, занятно. А остальные — ну так себе...

E>Кстати, у кого есть доступ, стоит добавить задачи с мешком сюда...

Это же википедия! заходи да правь. Или я чего-то не понимаю?

Здравствуйте, -n1l-, Вы писали:

N>

N>Архимед узнал вес всех слитков и хочет доказать Гериону, что конкретный слиток весит 1 кг.

N>Нужно ждать кодта за деталями к задаче.

Тебе что-то не ясно в условии?
Есть 11 слитков bar_1, bar_2,.. bar11
Они весят от 1 до 11
Мы должны найти такую минимальную последовательность неравенств вида
bar_i + bar_j + ... + bar_n < 12
И, возможно, одного вида
bar_i + bar_j + ... + bar_n >= 12

Что они могут все одновременно выполняться только если bar_1 = 1

Чем последовательность 6+1+2 = 9 будет отличатся от 1+3+7 = 11 в данной задаче?

Ну вот я и нашел.

Здравствуйте, Кодт, Вы писали:

К>А потом надолго замолчал в ЖЖ вообще. Может, в фейсбучике воюет или вообще в линкедине каком.
Ну я, как вовлечённый, раньше его ЖЖ предпочитал не читать


E>>Я знаю решение из 5 взвешиваний...

К>Я знаю решение из 2 взвешиваний
(убрал спойлер — Кодт)

Круто! В одно, очевидно нельзя...

К>Про 40-кг комплект гирь не знал, занятно. А остальные — ну так себе...
Ну я гуглил три секунды только
updt: про фальшивые гири, кстати, если допустить и ошибку в виде перестановки маркировок, тоже необычно...

К>Это же википедия! заходи да правь. Или я чего-то не понимаю?
Ну одно время там не всем разрешали, но может снова всем можно

Здравствуйте, -n1l-, Вы писали:

N>Чем последовательность 6+1+2 = 9 будет отличатся от 1+3+7 = 11 в данной задаче?

Ты про моё решение?

Мы показали Гериону две группы по 4 слитка, которые не рвут мешок.
Три общих слитка в этих группах — 1, 2, 3
те, два которые менялись — 4,5

дальше берём один из группы 6-11, и два из 1-5...

Так как мы смогли предъявить три набора 6+1+х, 6 не может быть 7...

Ок я беру две группы:

{1..8}{9,10}
11 вообще не использую.

Ну и вот у меня комбинации по два взвешивания. И если я беру 9, то там никак не может оказаться 8...

Здравствуйте, -n1l-, Вы писали:

N>Ну вот я и нашел.

Что нашёл? Пдстановку? Покажи?

Что на что заменить?
bar_1 = 1
bar_2 = 2
bar_3 = 3
bar_4 = 4
bar_5 = 5
bar_6 = 6
bar_7 = 7
bar_8 = 8
bar_9 = 9
bar_10 = 10
bar_11 = 11

Здравствуйте, -n1l-, Вы писали:

N>Ок я беру две группы:

N>{1..8}{9,10}
N>11 вообще не использую.

N>Ну и вот у меня комбинации по два взвешивания. И если я беру 9, то там никак не может оказаться 8...

Ну смотри. Ты показал Г 11 слитков, назвав их bar1, bar_2,.. bar_11
Дальше взвесил 4 слитка

bar_2+bar_9
bar_1+bar_10
bar_1+bar_9
bar_2+bar_10 тут мешок порвался
Так?

Смотри, перестановка bar_1 = 2; bar_2 = 3; bar_9 = 8; bar_10 = 9
Даст тот же результат взвешиваний...

Здравствуйте, Erop, Вы писали:

{1,2,3,4,5,6,7,8,9,10,11}
1+2+3+4 = 10
1+2+3+5 = 11
{1,2,3,4,5}{6, 7, 8, 9, 10, 11}
6+1+2 = 9
6+1+3 = 10
6+1+4 = 11
{1}{2,3,4}{5}{6}{7, 8, 9, 10, 11}

Ну смотри. Ты показал Г 11 слитков, назвав их bar1, bar_2,.. bar_11
E>Дальше взвесил 3 слитка
bar_6+bar_1+bar_2 = 9
bar_6+bar_1+bar_3 = 10
bar_6+bar_1+bar_4 = 11

Смотри, перестановка bar_6 = 1; bar_1 = 2; bar_4 = 3;
Даст тот же результат взвешиваний...

Здравствуйте, -n1l-, Вы писали:

N>Здравствуйте, Erop, Вы писали:

N>{1,2,3,4,5,6,7,8,9,10,11}
N> 1+2+3+4 = 10
N> 1+2+3+5 = 11
N>{1,2,3,4,5}{6, 7, 8, 9, 10, 11}
N> 6+1+2 = 9
N> 6+1+3 = 10
N> 6+1+4 = 11
N>{1}{2,3,4}{5}{6}{7, 8, 9, 10, 11}

N>Ну смотри. Ты показал Г 11 слитков, назвав их bar1, bar_2,.. bar_11
E>>Дальше взвесил 3 слитка
N> bar_6+bar_1+bar_2 = 9
N> bar_6+bar_1+bar_3 = 10
N> bar_6+bar_1+bar_4 = 11

N>Смотри, перестановка bar_6 = 1; bar_1 = 2; bar_4 = 3;
N>Даст тот же результат взвешиваний...

Тогда на каком-то из
bar_1+bar_2+bar3+bar_4
bar_1+bar_2+bar3+bar_5

мешок порвётся...

И?
Как это оправдывает твое решение. где ты точно знаешь какой из слитков сколько весит и не оправдывает мое, где происходит тоже самое.
В условии задачи есть такой пунктик.

Здравствуйте, -n1l-, Вы писали:

N>И?
N>Как это оправдывает твое решение. где ты точно знаешь какой из слитков сколько весит и не оправдывает мое, где происходит тоже самое.
N>В условии задачи есть такой пунктик.

Смотри, надо найти такую последовательность взвешиваний, которая невозможна, если bar_1 != 1.
Я тебе предложил перестановку, которая ломает
Я не полную привёл, но ты остальные не используешь, но можно и какую-нибудь полную привести. Например такую:

bar | кг
  1 | 2 
  2 | 3
  3 | 1
  4 | 4
  5 | 5
  6 | 6
  7 | 7
  8 | 10
  9 | 8
 10 | 9
 11 | 11

Попробуй показать такую же фальсифицирующую bar_1 перестановку для моего решения...