A hard constructive counting problem

Question

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

Answer 1

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

Answer 2

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: