Maths Olympiad Prep

Library / /152 of 168

Algebra Difficulty 2.6 Junior Find the answer

Each of a,ba, b and cc is equal to a number from the list 31,32,33,34,35,36,37,383^{1}, 3^{2}, 3^{3}, 3^{4}, 3^{5}, 3^{6}, 3^{7}, 3^{8}. There are NN triples (a,b,c)(a, b, c) with abca \leq b \leq c for which each of abc,acb\frac{ab}{c}, \frac{ac}{b} and bca\frac{bc}{a} is equal to an integer. What is the value of NN?

A number or a short expression. Spacing and $ signs are ignored.

Solution

We write a=3r,b=3sa=3^{r}, b=3^{s} and c=3tc=3^{t} where each of r,s,tr, s, t is between 1 and 8, inclusive. Since abca \leq b \leq c, then rstr \leq s \leq t. Next, we note that abc=3r3s3t=3r+st\frac{ab}{c}=\frac{3^{r} 3^{s}}{3^{t}}=3^{r+s-t}, acb=3r3t3s=3r+ts\frac{ac}{b}=\frac{3^{r} 3^{t}}{3^{s}}=3^{r+t-s}, and bca=3s3t3r=3s+tr\frac{bc}{a}=\frac{3^{s} 3^{t}}{3^{r}}=3^{s+t-r}. Since tst \geq s, then r+ts=r+(ts)r>0r+t-s=r+(t-s) \geq r>0 and so acb\frac{ac}{b} is always an integer. Since trt \geq r, then s+tr=s+(tr)s>0s+t-r=s+(t-r) \geq s>0 and so bca\frac{bc}{a} is always an integer. Since abc=3r+st\frac{ab}{c}=3^{r+s-t}, then abc\frac{ab}{c} is an integer exactly when r+st0r+s-t \geq 0 or tr+st \leq r+s. This means that we need to count the number of triples (r,s,t)(r, s, t) where rstr \leq s \leq t, each of r,s,tr, s, t is an integer between 1 and 8, inclusive, and tr+st \leq r+s. Suppose that r=1r=1. Then 1st81 \leq s \leq t \leq 8 and ts+1t \leq s+1. If s=1,ts=1, t can equal 1 or 2. If s=2,ts=2, t can equal 2 or 3. This pattern continues so that when s=7,ts=7, t can equal 7 or 8. When s=8s=8, though, tt must equal 8 since t8t \leq 8. In this case, there are 2×7+1=152 \times 7+1=15 pairs of values for ss and tt that work, and so 15 triples (r,s,t)(r, s, t). Suppose that r=2r=2. Then 2st82 \leq s \leq t \leq 8 and ts+2t \leq s+2. This means that, when 2s6,t2 \leq s \leq 6, t can equal s,s+1s, s+1 or s+2s+2. When s=7,ts=7, t can equal 7 or 8, and when s=8,ts=8, t must equal 8. In this case, there are 5×3+2+1=185 \times 3+2+1=18 triples. Suppose that r=3r=3. Then 3st83 \leq s \leq t \leq 8 and ts+3t \leq s+3. This means that, when 3s5,t3 \leq s \leq 5, t can equal s,s+1,s+2s, s+1, s+2, or s+3s+3. When s=6,7,8s=6,7,8, there are 3,2,13,2,1 values of tt, respectively. In this case, there are 3×4+3+2+1=183 \times 4+3+2+1=18 triples. Suppose that r=4r=4. Then 4st84 \leq s \leq t \leq 8 and ts+4t \leq s+4. This means that when s=4s=4, there are 5 choices for tt. As in previous cases, when s=5,6,7,8s=5,6,7,8, there are 4,3,2,14,3,2,1 choices for tt, respectively. In this case, there are 5+4+3+2+1=155+4+3+2+1=15 triples. Continuing in this way, when r=5r=5, there are 4+3+2+1=104+3+2+1=10 triples, when r=6r=6, there are 3+2+1=63+2+1=6 triples, when r=7r=7, there are 2+1=32+1=3 triples, and when r=8r=8, there is 1 triple. The total number of triples (r,s,t)(r, s, t) is 15+18+18+15+10+6+3+1=8615+18+18+15+10+6+3+1=86. Since the triples (r,s,t)(r, s, t) correspond with the triples (a,b,c)(a, b, c), then the number of triples (a,b,c)(a, b, c) is N=86N=86.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.