China Team Selection Test

For a positive integer $M$, we need to determine if it is a GOOD or BAD number based on the existence of integers $a, b, c,$ and $d$ such that:
$$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$ is GOOD if and only if there exist integers $p$ and $q$ such that $(p+1)(q+1) \leq M + 49$ and $pq \geq M$.

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

Using this lemma, we determine the largest GOOD number.

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

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

### Smallest BAD Number

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

Proof:
1. There is some multiple of 13 in $\{M+37, M+38, \dots, M+49\}$, call it $K$.
2. Take $q = 12$ and $p = \frac{K}{13} - 1$. Then:
$$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 $287 \leq M \leq 442$ is GOOD.

Proof:
1. Any pair $(p, q)$ of integers is a witness to all $pq - \delta \leq M \leq pq$ being prime, where $\delta = 48 - p - q$.
2. Construct the following 24 cases:
$$\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 - \delta, pq]$ cover $[287, 442]$, the lemma is proved.

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

Proof:
1. Assume for contradiction $pq$ exists, meaning $pq \geq 443$ and $(p+1)(q+1) \leq 492$. Then $pq \leq 491 - (p+q)$.
2. Now $p+q \geq 2\sqrt{443} \implies p+q \geq 43$, hence $pq \leq 448$.
3. Compute the factorization of each $K$ with $p+q$ minimal:
$$\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) \leq 492$, so $443$ is BAD.

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