Путнику пришлось задерживаться в каком-то городке на 80 дней. Расплачиваться за гостиничное место ему было нечем,...

Для разомкнутой цепи, как я понимаю, логика следующая:
Когда мы пилим цепь, то обязательно получаем в придачу к двум получившимся цепочкам одно распиленное кольцо (то есть в итоге у нас получится некое n единичных распиленных звеньев). А также оптимальным распилом будет такой, у которого будет наименьшее количество коллизий (то есть такой, при котором все числа от 1 до k можно сложить как можно меньшим количеством вариантов, в наилучшем случае единственным образом).

А для этого можно воспользоваться двоичной системой :)
n + 1*(n+1) + 2*(n+1) + 4*(n+1) + .+(2^(n-1))*(n+1) > k / 2

n + (2^n - 1)*(n + 1) > k / 2
(n + 1) + (2^n - 1)*(n + 1) - 1 > k / 2
(2^n)*(n + 1) - 1 > k / 2
(2^n)*(n + 1) > k / 2 + 1
log(2, (2^n)*(n + 1)) > log(2, k / 2 + 1)
log(2, (2^n)) + log(2, (n + 1)) > log(2, k / 2 + 1)
n + log(2, (n + 1)) > log(2, k + 2) - 1
(n + 1) + log(2, (n + 1)) > log(2, k + 2)
n + 1 = m
m + log(2, m) > log(2, k + 2)

Стыдно, однако не знаю как дальше решить и выразить n через k.
Но значение можем подобрать..
log(2, 82) = 6.36
m = 5 (при m = 4 получим слева 6, что меньше чем 6.35)
n = 4

Надо сделать всего 4 разреза...
в цепочках должно получиться 5, 10, 20 и 40 звеньев, а также 4 единичных, образовавшихся посредством распилов и одно целое в остатке :)

Для замкнутой цепочки всё считается ровно так же, только проще
(n+1) + 1*(n+2) + 2*(n+2) + 4*(n+2) + .+(2^n)*(n+1) > k / 2
(n+1) + (2^(n+1) - 1)*(n+1) > k / 2
2^(n+1) > k / 2
log(2, 2^(n+1)) > log(2, k / 2)
n + 1 > log(2, k) - 1
n > log(2, k) - 2

log(2, k) - 2 = log(2, 80) - 2 = 4.32
То есть в указанной задаче с замкнутой цепочкой нужно сделать 5 распилов (больше чем 4.32)

тут как-то был один клоун, вопросы из задачника Ландау-Лифшица выдавал за школьные и очень радовался, когда никто решить не мог. Очень интересно, где он сейчас.

Для замкнутой цепи из 79 звеньев четырех распилов-то хватит? (но трех при этом не хватит)

элементарно, договориться, что после окончания 80-и дней он отдаст цепь целиком.

Вот за такое изложение и не любят олимпиадные задачи. Правильное решение того, что изложено (а не того, что задумывалось): он в первый день отдал всю цепь, получил сдачу в местных тугриках и в остальные дни расплачивался уже ими. Где-то в задаче сказано, что сдачу ему будут давать тоже звеньями, причём только при наличии оных у "хозяина"? Нет, нигде не сказано. Вот никто и не понял замысла.

Надо просто пилить так чтобы ещё дней на 40 там хватило опилок ..если виза позволяет. И когда кончатся звенья, перезаключить с хозяином договор на опилки, которые суть тоже золотой лом. Он раньше брал ломом и теперь возьмёт, а размер распила его до этого самого устраивал. Или стеснялся больше грамма за день брать.

Сложность и в то же время простота задачи в том, что пилить надо не каждый раз как надо платить, а сразу до начала расчётов. В конкретном случае 80 звеньев нет разницы замкнута или не замкнута цепь.
всего 5 резов - 5 разомкнутых звеньев. Целых - 5, 10, 20, 40.
На 79 звеньев надо было бы всего 4 реза. Не удачно 80.

Зачем по звену? Лучше сразу по бубну

Чтобы отдавать каждый день по звену и пилить как можно меньше, то пилить надо через одно. Один день будет целое передаваться, на другой день распиленное.