# A hard constructive counting problem

In how many ways can we pick three different numbers out of the group $$1,2,3,\ldots,100$$ such that the largest number is larger than the product of the two smaller ones? (The order in which we pick the numbers does not matter.

I tried to use casework on the two smaller numbers, but the cases got out of control Any solutions? Thanks

• I think the problem statement is identical of phrasing it that way: "how many couples of 2 numbers exist in such the product doesn't exceed 100", or m i wrong ? – Abr001am Mar 15 '18 at 20:20

## 2 Answers

I used the same idea as John constructed a short macro to calculate the number of combinations which only took a second to calculate.

Basically for any $x_1 \times x_2 < 100$, the number of possibilities for $x_3$ equals $100-(x_1 \times x_2)$.

In this code, suppose the variable i is the lowest picked value and j is the 2nd lowest picked value.

For i = 1 to 10
For j = i+1 to 100
If i*j < 100 Then
Combos = Combos + (100 - i*j)
End If
Next j
Next i

Let $j$ be the smallest, $k$ be the second smallest, and $l$ be the largest of the three numbers. Then we want $$j\geq1,\quad k\geq j+1,\quad j\cdot k+1\leq l\leq100\ .$$ Given $j$ and $k$ with $j\cdot k\leq99$ there are $100-j\cdot k$ choices for $l$. If $j\cdot k>99$ there are no choices for $l$. Given $j\geq1$ we may choose an admissible $k$ in the interval $j+1\leq k\leq\left\lfloor{99\over j}\right\rfloor$. The largest $j$ for which such $k$ exist is $j=9$.

The number $N$ of admissible triples $(j,k,l)$ therefore is given by $$N=\sum_{j=1}^9\sum_{k=j+1}^{\lfloor99/j\rfloor}(100-j\,k)=10\,353\ ,$$ as the following Mathematica output shows:

• Very nice! I've deleted my answer because this made me realise I had a mistake. – kvantour Mar 15 '18 at 20:51