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.

Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $ such that

condition 1: $1 \leq a_i \leq 7$

condition 2: $1 \leq b_i \leq 4$

condition 3: $\sum_{i=1}^{4} {a_i} = 10$

condition 4: $\sum_{i=1}^{4} {b_i} = 7$

Is there a general solution to find the number of integer solutions for an inequality like this given conditions? The way I'm finding the number of solution is by generating all possible solutions and check to see if they satisfy all the conditions or not. This solution is very time-consuming. A computer program which can find the number of solutions is very much appreciated.

share|improve this question

closed as not a real question by Andres Caicedo, no identity, Noah Snyder, Thomas, Arkamis Oct 24 '12 at 13:50

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

4  
After taking the time to answer your question, I discovered your other questions: here, here and here. Hmm... –  Douglas S. Stones Oct 24 '12 at 2:59
    
@DouglasS.Stones so how do we call this, quadruplicate? –  Jean-Sébastien Oct 24 '12 at 3:09
    
possible duplicate of Count the number of integer solutions for $a \times b \geq k$? –  Noah Snyder Oct 24 '12 at 11:58
    

1 Answer 1

There's several ways to answer this problem computationally, and which is best depends on (a) personal preference, and (b) how, if at all, you're planning on re-using the code.

A brute force method is to have 8 nested for loops and, inside these for loops, have an if statement for the three conditions ($\sum_i a_i b_i \geq 8$, $\sum_i a_i=10$, and $\sum_i b_i=7$). On modern computers, this would take an almost infinitesimal amount of time to run (it'd probably take you longer to hit the "enter" key than the program takes to run). However, this approach would not have "scalability", in that, if you next asked for $9$ variables we would need to rewrite the code.

I wrote a solution in GAP, which has a bit better scalability (although, the code will still need to be edited, it can be edited rather easily). It's still quite brute-force and is not optimised.

Clearly, given a solution, we can permute the $a_i$'s and $b_i$'s to obtain another (not necessarily distinct) solution. So, this code iterates through the $a_i$'s and $b_i$'s in non-increasing order, and finds the number of permutations of the lists $(a_i)$ and $(b_i)$.

A:=RestrictedPartitions(10,[1..7],4);
B:=RestrictedPartitions(7,[1..4],4);

nr_orbits:=0;
count:=0;
for a in A do
  a_orbit_size:=OrbitLength(SymmetricGroup(4),a,Permuted);
  for b in B do
    b_orbit_size:=OrbitLength(SymmetricGroup(4),b,Permuted);
    if(a*b>=8) then
      nr_orbits:=nr_orbits+1;
      orbit_size:=a_orbit_size*b_orbit_size;
      count:=count+orbit_size;
      Print(nr_orbits," ",a," ",b," orbit size: ",orbit_size,"\n");
    fi;
  od;
od;
Print("Counted ",count," solutions to the inequality.\n");

which returns:

1 [ 3, 3, 2, 2 ] [ 2, 2, 2, 1 ] orbit size: 24
2 [ 3, 3, 2, 2 ] [ 3, 2, 1, 1 ] orbit size: 72
3 [ 3, 3, 2, 2 ] [ 4, 1, 1, 1 ] orbit size: 24
4 [ 3, 3, 3, 1 ] [ 2, 2, 2, 1 ] orbit size: 16
5 [ 3, 3, 3, 1 ] [ 3, 2, 1, 1 ] orbit size: 48
6 [ 3, 3, 3, 1 ] [ 4, 1, 1, 1 ] orbit size: 16
7 [ 4, 2, 2, 2 ] [ 2, 2, 2, 1 ] orbit size: 16
8 [ 4, 2, 2, 2 ] [ 3, 2, 1, 1 ] orbit size: 48
9 [ 4, 2, 2, 2 ] [ 4, 1, 1, 1 ] orbit size: 16
10 [ 4, 3, 2, 1 ] [ 2, 2, 2, 1 ] orbit size: 96
11 [ 4, 3, 2, 1 ] [ 3, 2, 1, 1 ] orbit size: 288
12 [ 4, 3, 2, 1 ] [ 4, 1, 1, 1 ] orbit size: 96
13 [ 4, 4, 1, 1 ] [ 2, 2, 2, 1 ] orbit size: 24
14 [ 4, 4, 1, 1 ] [ 3, 2, 1, 1 ] orbit size: 72
15 [ 4, 4, 1, 1 ] [ 4, 1, 1, 1 ] orbit size: 24
16 [ 5, 2, 2, 1 ] [ 2, 2, 2, 1 ] orbit size: 48
17 [ 5, 2, 2, 1 ] [ 3, 2, 1, 1 ] orbit size: 144
18 [ 5, 2, 2, 1 ] [ 4, 1, 1, 1 ] orbit size: 48
19 [ 5, 3, 1, 1 ] [ 2, 2, 2, 1 ] orbit size: 48
20 [ 5, 3, 1, 1 ] [ 3, 2, 1, 1 ] orbit size: 144
21 [ 5, 3, 1, 1 ] [ 4, 1, 1, 1 ] orbit size: 48
22 [ 6, 2, 1, 1 ] [ 2, 2, 2, 1 ] orbit size: 48
23 [ 6, 2, 1, 1 ] [ 3, 2, 1, 1 ] orbit size: 144
24 [ 6, 2, 1, 1 ] [ 4, 1, 1, 1 ] orbit size: 48
25 [ 7, 1, 1, 1 ] [ 2, 2, 2, 1 ] orbit size: 16
26 [ 7, 1, 1, 1 ] [ 3, 2, 1, 1 ] orbit size: 48
27 [ 7, 1, 1, 1 ] [ 4, 1, 1, 1 ] orbit size: 16
Counted 1680 solutions to the inequality.
share|improve this answer
    
You only need 6 nested loops since once three of the a-s or b-s are chosen, the fourth is determined. –  marty cohen Oct 24 '12 at 3:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.