In how many ways can we pick three different numbers out of the group $1,2,3,\dots,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.)
$\endgroup$ 42 Answers
$\begingroup$So we need $1\le a< b$ and $ab < c \le 100$
So $b < \frac ca \le \frac {100}a$ so $a < \frac {100}a$ and
$a^2 < 100$ so $a < 10$.
And $ab < 100$ so $ab \le 99$ so $b \le \frac{99}a$ so $b \le \lfloor \frac {99}a \rfloor$.
And $b+1 \le c \le 100$.
So the number or ways are:
So solution is $\sum_{a=1}^9(\sum_{b=a+1}^{\lfloor \frac {99}a\rfloor}(\sum_{c=ab+1}^{100} 1))=$.
$\sum_{a=1}^9(\sum_{b=a+1}^{\lfloor \frac {99}a\rfloor}[100-ab])$
$\sum_{b=2}^{99}(100-b) + \sum_{b=3}^{49}(100-2b) + \sum_{b=4}^{33}(100-3b) + \sum_{b=5}^{24}(100-4b)+ \sum_{b=6}^{19}(100-5b) + \sum_{b=7}^{16}(100-6b) + \sum_{b=8}^{14}(100-7b) + \sum_{b=9}^{12}(100-8b) + \sum_{b=10}^{11}(100-9b)=$
$\sum_{k=1}^{98}k + \sum_{k=2;+2}^{94}k + \sum_{k=1;+3}^{88}k + \sum_{k=4;+4}^{80}k+ \sum_{k=5;+5}^{70}k + \sum_{k=4;+6}^{58}k + \sum_{k=2;+7}^{44}k + \sum_{k=4;+8}^{28}k + \sum_{k=1;+9}^{10}k=$
$\sum_{k=1}^{98}k + \sum_{k=1}^{47}2k + \sum_{k=0;}^{29}(3k+1) + \sum_{k=1}^{20}4k+ \sum_{k=1}^{14}5k + \sum_{k=0}^{9}6k+4 + \sum_{k=0}^{7}7k+2 + \sum_{0}^{3}8k+4 + \sum_{k=0}^{1}9k+1=$
$\frac{98*99}2 + 2*\frac{47*48}2 + 3\frac{29*30}2 +30 + 4*\frac{20*21}2+ 5\frac{14*15}2+ 6\frac{9*10}2+4*10 + 7*\frac{7*8}2+ 2*8+ 8\frac{3*4}2+4*4 +9*\frac {1*2}2+2*1=$
$49*99 + 47*48 + 3*29*15 + 30 + 2*20*21 + 5*7*15 + 3*9*5 + 40 + 7*7*4+16 +4*3*4+16 +9 + 2=$
$49*99 + 47*48 + 29*45 + 30 + 20*42 + 35*15 + 27*5 + 40 + 49*4 + 32+48+11=10269$
$\endgroup$ $\begingroup$The result is simply given by selecting all the numbers greater than their product:$$ s=\sum_{i=1}^{98}\sum_{j=i+1}^{99} \max(100-ij,0) = 21320 $$
$\endgroup$
