Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Should the threshold on the first knob be (4), since the range on the next knob shrinks when the first knob reaches 5? –  Mike Spivey Sep 22 '11 at 2:47
    
After consideration, no. The minimum value for a knob to the right increases (the range starts to shrink) when the knob to its left goes above the threshold. So when the first knob goes above 5, the smallest possible value the next knob can have increases from 0 to 1, essentially decreasing its range. Thank you. –  Ben Richardson Sep 22 '11 at 3:44
    
Thanks for the clarification. So then should the second knob's threshold be 8, since "if the 30-max knob reaches value "7", the the 50-max lever is still 0-50, but when it reaches "8", the range changes to 1-50"? –  Mike Spivey Sep 22 '11 at 4:33
    
Yes, that makes sense to me. But we can just simplify the problem and treat all the knobs the same way. –  Ben Richardson Sep 22 '11 at 5:29
    
@user16487: Your response to Mike Spivey seems inconsistent with the description above. The number in parentheses seems to be the maximum that lever can be without restricting the next lever, so it should be 20(4). Then if the first lever is at 15, the second must be at least 11 and the third must be at least 4, right? –  Ross Millikan Sep 25 '11 at 16:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.