# Finding the number of all possible pair products less than the product of two given numbers

Suppose the are two lists X,Y each has numbers from 1 to 110 , we are given given a element from X,Y each, then we have to find number of possible pair of factors from X,Y so that the product of each pair is less than the product of given pair. And if we select number from X, then it cannot be used to make pairs with same X value. And if we select number from Y, then it cannot be used to make pairs with same y value. For example I am given 1,4 then I cannot use 1 from X in any pair, Also I cannot use 4 as Y in any pair, And I have to find number of pairs whose product is less than 4 in this case, if we use 2,1 as pair then we cannot use 2 as X or 1 as Y again. I am not able to approach towards the solution. Can anyone help me in doing this?

• are you allowed to use linear programming (i.e., a computer ?) – Kuifje Aug 19 '19 at 9:50
• yes we can use linear programming – Xuji Kide Aug 20 '19 at 12:33

Let $$x_i$$ be a binary variable that takes value $$1$$ if and only if element $$i$$ from $$X$$ is selected, and likewise with $$y_j$$, $$Y$$.
Let $$\hat{x}$$ and $$\hat{y}$$ be the given items.
So you are looking for a pair $$(x_i,y_j)$$ such that $$i \times j \le \hat{x} \times \hat{y}$$.
You can minimize a dummy objective function (e.g., $$0$$) subject to : $$ix_ij y_j \le \hat{x}\hat{y} \\ \sum_{i, x_i \neq \hat{x} } x_i = 1 \\ \sum_{j, y_j\neq \hat{y} } x_j = 1 \\ x_i,y_j \in \{0,1\} \\$$
This will give you one pair. Then, iteratively, run the linear program and forbid existing pairs by adding constraints such as $$\sum_{i\in B_1} x_i + \sum_{i \in B_0} \left( 1-x_i \right )\le |B_1|+|B_0|$$ where $$B_1$$ is the set of variables that take value $$1$$ is the solution and $$B_0$$ is the set of variables that take value $$0$$.