Maths Olympiad Prep

Library / /76 of 97

Number theory Difficulty 8.3 Shortlist Find the answer

For a positive integer MM, if there exist integers aa, bb, cc and dd so that:
Ma<bc<dM+49,ad=bc M \leq a < b \leq c < d \leq M+49, \qquad ad=bc
then we call MM a GOOD number, if not then MM is BAD. Please find the greatest GOOD number and the smallest BAD number.

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

Solution

For a positive integer M M , we need to determine if it is a GOOD or BAD number based on the existence of integers a,b,c, a, b, c, and d d such that:
Ma<bc<dM+49,ad=bc. M \leq a < b \leq c < d \leq M + 49, \qquad ad = bc.

We aim to find the greatest GOOD number and the smallest BAD number.

### Greatest GOOD Number

Lemma: The number M M is GOOD if and only if there exist integers p p and q q such that (p+1)(q+1)M+49(p+1)(q+1) \leq M + 49 and pqM pq \geq M .

Proof:
1. **If M M is GOOD:** Given ad=bc ad = bc , set a=wx a = wx , d=yz d = yz , b=wy b = wy , c=xz c = xz . Then a<b a < b implies x<y x < y , and b<d b < d implies w<z w < z . Thus, Mawx(z1)(y1) M \leq a \leq wx \leq (z-1)(y-1) . Take p=z1 p = z-1 and q=y1 q = y-1 .
2. Converse: If pq p \leq q , take (w,x,y,z)=(p,q,q+1,p+1) (w, x, y, z) = (p, q, q+1, p+1) to get a,b,c,d a, b, c, d .

Using this lemma, we determine the largest GOOD number.

Lemma: The largest GOOD number is 576=242 576 = 24^2 .

Proof:
1. To see 576 576 is GOOD, take p=q=24 p = q = 24 .
2. Conversely, if M M is GOOD, then p p and q q exist such that p+q+149 p+q+1 \leq 49 hence p+q48 p+q \leq 48 . Thus, Mpq242=576 M \leq pq \leq 24^2 = 576 .

### Smallest BAD Number

Lemma: Every integer M288 M \leq 288 is GOOD.

Proof:
1. There is some multiple of 13 in {M+37,M+38,,M+49} \{M+37, M+38, \dots, M+49\} , call it K K .
2. Take q=12 q = 12 and p=K131 p = \frac{K}{13} - 1 . Then:
pq=1213K121213(M+37)12=M+1224M13M. pq = \frac{12}{13}K - 12 \geq \frac{12}{13} (M+37) - 12 = M + \frac{12 \cdot 24 - M}{13} \geq M.

Lemma: Every integer 287M442 287 \leq M \leq 442 is GOOD.

Proof:
1. Any pair (p,q) (p, q) of integers is a witness to all pqδMpq pq - \delta \leq M \leq pq being prime, where δ=48pq \delta = 48 - p - q .
2. Construct the following 24 cases:
pqpqδpqδ1520300132871422308122961521315123031818324123121522330113191819342113311425350934119193611035114263648356172237493651920380937116243848376133039053851822396838820204008392172440874011823414740716264166410202142074131725425641918244326426152943544312121441643517264425437 \begin{array}{cccc} p \cdot q & pq & \delta & pq - \delta \\ \hline 15 \cdot 20 & 300 & 13 & 287 \\ 14 \cdot 22 & 308 & 12 & 296 \\ 15 \cdot 21 & 315 & 12 & 303 \\ 18 \cdot 18 & 324 & 12 & 312 \\ \hline 15 \cdot 22 & 330 & 11 & 319 \\ 18 \cdot 19 & 342 & 11 & 331 \\ \hline 14 \cdot 25 & 350 & 9 & 341 \\ 19 \cdot 19 & 361 & 10 & 351 \\ \hline 14 \cdot 26 & 364 & 8 & 356 \\ 17 \cdot 22 & 374 & 9 & 365 \\ 19 \cdot 20 & 380 & 9 & 371 \\ \hline 16 \cdot 24 & 384 & 8 & 376 \\ 13 \cdot 30 & 390 & 5 & 385 \\ 18 \cdot 22 & 396 & 8 & 388 \\ 20 \cdot 20 & 400 & 8 & 392 \\ \hline 17 \cdot 24 & 408 & 7 & 401 \\ 18 \cdot 23 & 414 & 7 & 407 \\ 16 \cdot 26 & 416 & 6 & 410 \\ 20 \cdot 21 & 420 & 7 & 413 \\ \hline 17 \cdot 25 & 425 & 6 & 419 \\ 18 \cdot 24 & 432 & 6 & 426 \\ 15 \cdot 29 & 435 & 4 & 431 \\ 21 \cdot 21 & 441 & 6 & 435 \\ \hline 17 \cdot 26 & 442 & 5 & 437 \end{array}
Since the intervals [pqδ,pq][pq - \delta, pq] cover [287,442][287, 442], the lemma is proved.

Lemma: The number M=443 M = 443 is BAD.

Proof:
1. Assume for contradiction pq pq exists, meaning pq443 pq \geq 443 and (p+1)(q+1)492(p+1)(q+1) \leq 492. Then pq491(p+q) pq \leq 491 - (p+q) .
2. Now p+q2443    p+q43 p+q \geq 2\sqrt{443} \implies p+q \geq 43 , hence pq448 pq \leq 448 .
3. Compute the factorization of each K K with p+q p+q minimal:
443=1442444=1237445=589446=2233447=3149448=1628 \begin{align*} 443 &= 1 \cdot 442 \\ 444 &= 12 \cdot 37 \\ 445 &= 5 \cdot 89 \\ 446 &= 2 \cdot 233 \\ 447 &= 3 \cdot 149 \\ 448 &= 16 \cdot 28 \end{align*}
All of these fail the inequality (p+1)(q+1)492(p+1)(q+1) \leq 492, so 443 443 is BAD.

The answer is: The greatest GOOD number is 576\boxed{576} and the smallest BAD number is 443\boxed{443}.

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.