Здравствуйте, -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: сделал небольшой рефакторинг, чтоб понятней было
Здравствуйте, Буравчик, Вы писали:
Б>Ты имел ввиду наоборот? Интереснее программа, которая ищет решения (или доказывает невозможность).
Про доказывает невозможность — самая интересная.
А вот та, которая проверяет хитрее, той, которая ищет...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском