1
$\begingroup$

I am trying to solve the following combination problem.

You have 4 knobs or levers that have maximum values, such as 0-20, 0-30, 0-50 and 0-100. Their total values must equal an amount, say 47. Their values are also linked in a chain, each knob being connected to the one to its right.

The additional rule/constraint is; a knob/lever's minimum value must rise when a knob to the left moves above a specific threshold.

For example, the 2nd knob's minimum value must rise when the 20-max lever (1st one) goes above the value 5. When the the 20-max lever is 5 or below, the 30 lever can be from 0-30. But, if the 20-max lever reaches 6, then the 30-lever can be only 1-30. If 7, then 2-30.

The problem would be defined as this with the defined "thresholds" in parenthesis:

$[{0-20 (5) ] + [0-30 (7) ] + [0-50 (20) ] + [0-100] = 47}$

I know I can find all the possible combinations using inclusion-exclusion and binomial coefficients using ${50\choose3}$ and the maximum constraints ${20\choose3}-{30\choose3}-{50\choose3}-{100\choose3}$. But would be over counting the what's possible because it would not take into account the threshold constraint, which can limit the range/maximums of a set.

How can one use inclusion-exclusion (or another method) to obtain all the possible combinations using the two constraints together?

Thank you.

  • 0
    If the first lever is 5, the second lever can still be 0-30. However, when the first lever goes up to 6 (goes above the threshold 5), the second must be at least 1. So, if the first lever is at 15, the second must be at least 10 and the third must be at least 3. The lever restricts the one to the right if it goes above the number in the parenthesis. Does this clarification help solve the problem? I have re-edited the description, as I see now why it is confusing. Thank you.2011-09-25

0 Answers 0