2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Abr001am Mar 15 '18 at 20:20
1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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:

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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