It can be shown that the following cutting strategy is optimal. We arrange the sausages in a single line, one after the other (thus obtaining a line segment consisting of ~N~ shorter line segments). Cutting this line into ~M~ equal segments yields the required solution.

Although we are conceptually making ~M-1~ cuts, some of them are not actual cuts, but fall between sausages (shorter line segments) instead. For example, with two sausages and four tasters, the first cut is real, dividing the first sausage in half, the second cut is not real because it is actually between the two sausages, and the third cut is real, dividing the second sausage in half.

We therefore need to count the "between" cuts. For the ~K^\text{th}~ cut to be a between-cut, the first ~K~ out of the ~M~ portions must consist of the first ~X~ sausages, where ~X~ is an integer. In other words, ~K / M~ out of ~N~ sausages equals ~X~ sausages. ~X~ can then be obtained: ~X = (K \times N) / M~. It is now clear that ~X~ will be an integer (and the cut a between-cut) if ~M~ divides ~K \times N~. We can simply use a for loop to check, for each possible ~K~ from ~1~ to ~M-1~, whether it is a real cut or a between-cut.

Alternatively, there is an explicit formula: ~\text{solution} = M - \gcd(N, M)~. Proof is left as an exercise for the reader.