У царя Гериона есть 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, то мешок не порвётся...
Прикольно, что ещё и мешок не рвём
Наверное, если рвать, можно короче, но не уверен. Можно тупо компиком перебрать, но пока лень...
К>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, это если Герион нам поверит, конечно...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Ты в своем решении делаешь то же самое, ты предполагаешь что уже знаешь вес какого-то слитка.
Например в твоем случае есть еще куча других комбинаций в три слитка которые не рвут мешок.
Здравствуйте, -n1l-, Вы писали:
N>Ты в своем решении делаешь то же самое, ты предполагаешь что уже знаешь вес какого-то слитка.
1) Вес слитков известен по условию. Архимед их как-то взвесил, и теперь ему надо убедить Гериона в том, что конкретно вот этот слиток — 1кг...
N>Например в твоем случае есть еще куча других комбинаций в три слитка которые не рвут мешок.
Ну положим, что Архимед читер. Он написал на слитках веса от 1 до 11, а на самом деле там другие.
Покажи перестановку чисел от 1 до 11, которая при подстановке в моё решение, не рвёт мешки пять раз, но показывает не на 1, а не что-то другое...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
К>>Константин Кноп предложил занятную задачку на взвешивание. E>Константин всё так же стервенело ловит ЧГК-читеров или его таки отпустило?
Про это я не знаю.
Раньше он чередовал интересные задачки с внутричегекашными дрязгами, но поскольку я в этом никаким боком, то просто игнорировал.
А потом надолго замолчал в ЖЖ вообще. Может, в фейсбучике воюет или вообще в линкедине каком.
E>Я знаю решение из 5 взвешиваний...
Я знаю решение из 2 взвешиваний
(UPD. убрал спойлер)
E>Например
Про 40-кг комплект гирь не знал, занятно. А остальные — ну так себе...
E>Кстати, у кого есть доступ, стоит добавить задачи с мешком сюда...
Это же википедия! заходи да правь. Или я чего-то не понимаю?
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
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Кодт, Вы писали:
К>А потом надолго замолчал в ЖЖ вообще. Может, в фейсбучике воюет или вообще в линкедине каком.
Ну я, как вовлечённый, раньше его ЖЖ предпочитал не читать
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...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, -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
Даст тот же результат взвешиваний...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Ну смотри. Ты показал Г 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 перестановку для моего решения...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, -n1l-, Вы писали:
N>Ты так ничего и не доказал.
Ну строго мне доказывать лень
Я там указал леммы, что типа bar1, bar2,.. bar5 содержит перестановку 1, 2,.. 5, а остальные — перестановку 6,.. 11
Это я записывал так:
{1, 2, 3, 4, 5}{6, 7, 8, 9, 10, 11}
Леммы мне доказывать лень, IMHO, они очевидны. После того, как в записи взвешиваний попалась запись леммы, она уже является доказанной. Соответственно её можно использовать в дальнейших рассуждениях...
N>Ты маркируешь слитки, я делаю тоже самое.
Я утверждаю следующее.
Если проделать те 5 взвешиваний, то не получится подобрать такую перестановку маркировок на слитках, что bar1!=1
Если ты не согласен -- предъяви перестановку, которая не рвёт мешок ни в одном из тех 5 взвешиваний...
Но есть решение из 2-х. Очень классное, кстати...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, -n1l-, Вы писали:
N>Со слитками 7 8 9 мешок тоже порвется и что?
А при верной маркировке, не порвётся ни на одном из 5...
Ну и ещё есть сколько-то маркировок, при которых тоже не порвётся, но все они обладают тем свойством, что bar_1 = 1...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
N>Ну у меня при верной маркировке тоже все сходится.
А надо, что бы при любой, где bar_1 != 1 не сходилось...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Буравчик, Вы писали:
Б>Я тоже нашел за 2 взвешивания! Б>Если бы ты не сказал, что оно существует, не нашел бы...
Чорт. Плохо убрал спойлер
Ну и по правде сказать, я встал на плечи гигантов: посмотрел, какие неверные ответы были в комментариях у Кнопа, и понял, какую возможность они там не использовали.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Буравчик, Вы писали:
Б>>Я тоже нашел за 2 взвешивания! Б>>Если бы ты не сказал, что оно существует, не нашел бы...
К>Чорт. Плохо убрал спойлер
Блин... Если бы ты не сказал, что ты плохо убрал спойлер, я не догадался бы сейчас посмотреть твое решение
К>Ну и по правде сказать, я встал на плечи гигантов: посмотрел, какие неверные ответы были в комментариях у Кнопа, и понял, какую возможность они там не использовали.
А я написал программу, которую хотел Егор.
Потом посмотрел твой пост про два взвешивания.
И потом (после пятой попытки) запуска программы получил наконец нормальный вариант.
Здравствуйте, Буравчик, Вы писали:
К>>Чорт. Плохо убрал спойлер Б>Блин... Если бы ты не сказал, что ты плохо убрал спойлер, я не догадался бы сейчас посмотреть твое решение
Я-то имел в виду, что стёр решение, но не количество шагов.
К>>Ну и по правде сказать, я встал на плечи гигантов: посмотрел, какие неверные ответы были в комментариях у Кнопа, и понял, какую возможность они там не использовали.
Б>А я написал программу, которую хотел Егор. Б>Потом посмотрел твой пост про два взвешивания. Б>И потом (после пятой попытки) запуска программы получил наконец нормальный вариант.
Дык, этюд для программистов!
А покажи свою программу, что ли.
, интереснее написать программу, которая проверяет решения...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Кодт, Вы писали:
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
import qualified Data.Map as Map
import Data.List
-- список взвешиваний
actions =
[ [1, 2, 3, 4]
, [1, 2, 3, 5]
, [1, 2, 6]
, [1, 3, 6]
, [1, 4, 6]
]
-- запускаем
main = find_kontrprimer actions of
Nothing -> putStrLn "ok"
Just mapper -> putStrLn $ "bad solve\n" ++ show mapper
-- максимальный вес, который выдерживает мешок
bag_max_weight = 11
-- слитки
boxes = [1..11]
-- проверка, что мешок не порвется
bag_unhurt acts = all (<= bag_max_weight) $ map sum acts
-- перестановка слитков во взвешиваниях
convert_boxes acts mapper = map (map (mapper Map.!)) acts
-- список перестановок весов слитков, список словарей (старый вес => новый вес)
mappers = [ Map.fromList $ zip boxes new_boxes | new_boxes <- permutation boxes]
-- проверка, что данная перестановка является контрпримером для взвешиваний
-- т.е. при всех взвешиваниях мешок не порвался и это стало возможным когда слиток 1 имеет вес отличный от 1кг
is_kontrprimer mapper acts = (mapper Map.! 1 /= 1) && (bag_unhurt $ convert_boxes acts mapper)
-- поиск контрпримера
find_kontrprimer acts = find is_kontrprimer mappers
UPDATE: сделал небольшой рефакторинг, чтоб понятней было
Здравствуйте, Буравчик, Вы писали:
Б>Ты имел ввиду наоборот? Интереснее программа, которая ищет решения (или доказывает невозможность).
Про доказывает невозможность — самая интересная.
А вот та, которая проверяет хитрее, той, которая ищет...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском