Показать скрытый текст
Чтобы попытаться разделить m шок на n чел нужно вылажить их в ряд одну за другой и отмеряя отрезки длиной m/n шок делать надрез. При этом если разделить можно, то каждый новый надрез должен начинаться на новой шок.
Если m/n<1/2, то очевидно на 1 шок 2 надреза.
Для упрощения докажем, что нельзя разделить если m и n взаимопросты и m=n-p, где m> p>=2
(если НОД(m,n)>1, то после сокращения дробь m/n будет иметь взаимопростые числ и знам)
Так как p>=2, то существует l<n такое, что n+1>pl>n, p(l-1)<n
Тогда
l-1>m/n*(l-1)=(n-p)(l-1)/n=l-1-p(l-1)/n>l-2
m/n*l=(n-p)l/n=l-lp/n<l-1
Значит, на l-1 шоколадке будет 2 надреза.
