For a positive integer $M$, if there exist integers $a$, $b$, $c$ and $d$ so that: \[ M \leq a < b \leq c < d \leq M+49, \qquad ad=bc \]then we call $M$ a GOOD number, if not then $M$ is BAD. Please find the greatest GOOD number and the smallest BAD number.
Problem
Source: China TST 2006
Tags: number theory unsolved, number theory
19.06.2006 23:32
First, one observation: If all four numbers $a,b,c,d$ can be equal, there is no point for solving this problem, so I think there is a mistake in a statement of the problem. I suppose that it's $M\leq a<b\leq c<d\leq M+49$. I found the greatest GOOD number, and I am pretty sure that all numbers not greater then that are GOOD but i can't prove that (for now). Suppose that $b=a+k_1,c=a+k_2$ and $d=a+k_3$ where $0<k_1\leq k_2<k_3<50$. Then from $ad=bc$ we get $k_3-k_2-k_1=\frac{k_1k_2}a$. So $50>k_3>k_1+k_2$, so $max\{k_1+k_2\}=48 \Rightarrow max\{k_1k_2\}=24^2$. The last one implies that $a\leq24^2$, so if $M\geq 24^2+1$ then $a\geq M\geq 24^2+1$ contradiction! If $M=24^2$ there is a solution: $a=24^2,b=c=24^2+24,d=24^2+49$, so greatest GOOD number is $24^2$. For now, this is it, I'll be back soon bye
20.06.2006 13:16
Well, I guess you're wrong. I assume the condition is $a<b \leq c <d$. If $ad=bc$ we may find $m,n,p,q$ with $a=mn, b=mp, c=nq, d=pq$ then $m<q, n<p$ so $(p-1)(q-1)\geq mn=a$, and the new system $(p-1)(q-1), (p-1)p, (q-1)q, pq$ also satisfies the condition. Thus we have come to the following characterization: A number $M$ is bad if and only if $pq\leq M+49$ implies $(p-1)(q-1)<M$. Now if $M<18^2$ then $M$ id good, because if we let $(k-1)^2<M+49 \leq k^2$ and $r\leq \sqrt{2k-1}$ with $k^2-r^2\leq M+49<k^2-(r-1)^2$ we take $p=k+r, q=k-r$ yielding $(k-1)^2-r^2 \leq M-1 =m+49-50 <k^2-(r-1)^2-50$ so $k+r \geq 25$ which implies $k \geq 19$. Now we have some work to do (I mean $p=15, q=22$ make all numbers from $330$ to $343$ good and so on) till we get the desired number. I think it's 470 or smth close.
20.06.2006 22:03
I really don't understand what you want to say. I said (and proved) that greatest GOOD number is $24^2=576$ and I found one $a,b,c,d$ which are fulfilling given condition, so obviously is not, like you said,"470, or something close".
16.02.2012 14:32
The greatest bad number is 443
10.07.2017 20:47
Alright, let's give this ROBUST problem its due diligence Quote: For a positive integer $M$, if there exists integers $a$, $b$, $c$, $d$ such that $ad=bc$ and \[ M \le a < b \le c < d \le M + 49 \]then we say that $M$ is good, otherwise we say that $M$ is bad. Determine the greatest good number and the smallest bad number. The largest good number is $24^2=576$ and the smallest bad number is $443$. We prove this through a series of several claims. Lemma: The number $M$ is good if and only if: there exist integers $p$ and $q$ for which $(p+1)(q+1) \le M + 49$ but $pq \ge M$. Proof. First, assume $M$ is good. Then given $ad=bc$ we set $a=wx$, $d=yz$, $b=wy$, $c=xz$. Then $a < b$ implies $x < y$, and $b < d$ implies $w < z$. Then $M \le a \le wx \le (z-1)(y-1)$ so we just take $p = z-1$ and $q = y-1$. For the converse direction, if WLOG $p \le q$ then take $(w,x,y,z) = (p,q,q+1,p+1)$ to get $a$, $b$, $c$, $d$. $\blacksquare$ It is now easy to determine the largest good integer. Lemma: The largest good integer is $576 = 24^2$. Proof. To see $576$ is good, take $p=q=24$ in the lemma above. Conversely, assume $M$ is good, so $p$ and $q$ exist as described above. Then we must have $p+q+1 \le 49$ hence $p+q \le 48$. So $M \le pq \le 24^2 = 576$. $\blacksquare$ It remains to determine the smallest bad integer. First, we contend that: Lemma: Every integer $M \le 288$ is good. Proof. Note that there is some multiple of $13$ in $\{M+37, M+38, \dots, M+49\}$, call it $K$. We claim that we can take $q = 12$, and $p = K/13-1$. Indeed, \[ pq = \frac{12}{13}K - 12 \ge \frac{12}{13} (M+37) - 12 = M + \frac{12 \cdot 24 - M}{13} \ge M \]as desired. $\blacksquare$ Lemma: Every integer $287 \le M \le 442$ is good. Proof. Note that any pair $(p,q)$ of integers is a witness to all $pq - \delta \le M \le pq$ being prime, where $\delta = 48-p-q$. In light of this, we 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} \]For readability we have placed dividing lines under any pair with $|p-q| \le 1$. Since the intervals $[pq-\delta, pq]$ cover $[287, 442]$, the lemma is proved. $\blacksquare$ Lemma: The number $M = 443$ is bad. Proof. Assume for contradiction $pq$ exists, meaning $pq \ge 443$ and $(p+1)(q+1) \le 492$. Then $pq \le 491 - (p+q)$. Now $p+q \ge 2\sqrt{443} \implies p+q \ge 43$, hence $pq \le 448$. Hence $K = pq \in [443, 448]$. We now compute the factorization of each $K$ with $p+q$ minimal (in other words $p$ and $q$ as close as possible). \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) \le 492$, so $443$ is bad. $\blacksquare$
03.02.2024 18:13
The greatest good number is $576$ and the smallest bad number is $443$. Claim: $M$ is good iff there exist positive integers $x \le y$ (WLOG) such that $xy \ge M$ and $(x+1) (y+1) \le M + 49$ (or in other words $(x+1) (y+1) - 49 \le M \le xy$). Proof: The if direction is true by considering $a = xy, b = (x+1) y, c = x(y+1)$, and $d = (x+1)(y+1)$. Now we prove the only if direction. Suppose such $x,y$ do not exist, but we had $a, b, c, d$ where $ad = bc$ and $M \le a < b \le c < d \le M + 49$. By Four Number Lemma, there exist positive integers $p,q,r,s$ with $pq = a, rs = d, pr = b, qs = c$. We must have $q < r$ and $p < s$. Therefore $rs \ge (p+1) (q+1)$, so $pq \ge M$ and $(p+1) (q+1) \le M + 49$, as desired. $\square$ Clearly $576$ is good by setting $x = y = 24$. If $M$ is good, then $xy \ge M$ and $(x+1) (y+1) \le M + 49$ for some $x,y$, so $x + y \le 48$, meaning the maximal value for $xy$ is $24\cdot 24 = 576$, hence all good numbers are at most $576$, so $576$ is the largest good number. Now it remains to prove that $443$ is the smallest bad number. Claim: All $M \le 290$ are good. Proof: Let $10y$ denote the smallest multiple of $10$ at least $M$. Setting $x = 10$ and $y = y$ gives that if $11(y+1) - 49 \le M \le 10y$ implies $M$ is good. Let $M = 10y - c $, where $0\le c \le 9$. We have $11 y - 38 \le 10y - c$, so $y \le (38 - c)$. Since $c$ is at most $9$, any $y \le 29$ works, meaning any $M \le 290$ is good. $\square$ Now we prove that every integer in $[291,442]$ is good. For $[291,300]$ take $(x,y) = (15,20)$. For $[301,311]$ take $(x,y) = (13,24)$. For $[312,324]$ take $(x,y) = (18,18)$. For $[325,330]$ take $(x,y) = (15,22)$. For $[331,340]$ take $(x,y) = (17,20)$. For $[341,350]$ take $(x,y) = (14,25)$. For $[351,361]$ take $(x,y) = (19,19)$. For $[362,368]$ take $(x,y) = (16,23)$. For $[369,378]$ take $(x,y) = (18,21)$. For $[379,384]$ take $(x,y) = (16,24)$. For $[385,390]$ take $(x,y) = (15,26)$. For $391$ take $(x,y) = (15,28)$. For $[392,400]$ take $(x,y) = (20,20)$. For $[401,408]$ take $(x,y) = (17,24)$. For $[409,414]$ take $(x,y) = (18,23)$. For $[415,420]$ take $(x,y) = (20,21)$. For $[421,425]$ take $(x,y) = (17,25)$. For $[426,432]$ take $(x,y) = (18,24)$. For $[433,434]$ take $(x,y) = (14,31)$. For $[435,441]$ take $(x,y) = (21,21)$. For $442$ take $(x,y) = (17,26)$. Therefore every positive integer less than $443$ is good. It remains to show that $443$ is bad. Suppose there existed $x,y$ where $(x+1)(y+1) - 49 \le 443 \le xy$. Let $xy = 443 + c$. We must have $xy + x + y - 48 \le xy - c \le xy$, so $x + y \le 48 - c \le 48$. However, since $xy \ge 443$, we have $x + y \ge 2\sqrt{xy} > 42$, so $c < 6$. Now it remains to disprove $c\in [0,5]$. If $c=0$, then $xy = 443$. To check that $443$ is prime, we see it is $420 + 23$, so it can't be divisible by $2,3,5,7$. It is also $143 + 300$, so it isn't divisible by $11$ or $13$, and it is $323 + 120$, so it isn't divisible by $17$ or $19$. If $443$ was composite, then it would have a prime factor under $\sqrt{443} < 22$, but we proved this is impossible. Thus, we must have $(x,y) = (1,443)$ and permutations, so $x + y = 444 > 48$, absurd. If $c = 1$, then $xy = 444$ and $x + y \le 48$. However, one of $x,y$ must be a multiple of $37$ since $37 \mid 444$ and $37$ is prime. If the multiple of $37$ is over $74$, then it's obviously impossible. Thus, one of $x,y$ is equal to $37$, so the other one must be $12$, meaning $x + y = 49 > 48$, absurd. If $c = 2$, then $xy = 445$ and $x + y \le 48 - c = 46$. Then since $\frac{445}{5} = 89$ is prime, one of $x,y$ is a multiple of $89$, so $x + y > 89$, absurd. If $c = 3$, then $xy = 446$, and $x + y \le 45$. We see that $\frac{446}{2} = 223$ is prime because it is $2\cdot 3\cdot 5\cdot 7 + 13$, $11\cdot 20 + 3$, $13\cdot 17 + 2$ so it can't be a multiple of any prime under $\sqrt{223}$. Therefore, one of $x,y$ is a multiple of $223$, so $x + y \ge 223$, absurd. If $c = 4$, then $xy = 447$ and $x + y \le 44$. Since $\frac{447}{3} = 149$ is prime, one of $x,y$ is a multiple of $149$, so $x + y \ge 149$, absurd. If $ c= 5$, then $xy = 448$ and $x + y \le 43$. Clearly $7\mid 448$, so one of $(x,y)$ is a multiple of $7$. If one of $(x,y)$ is $7$ or $14$, then either $x + y = 7 + 64$ or $14 + 32$, both of which exceed $43$. Since $21\nmid 448$, neither of $x,y$ can equal $21$. Now if one of $x,y$ is $28$, then $x + y = 28 + 16 = 44 > 43$. Otherwise, one of $x,y$ is a multiple of $7$ over $42$ (since $35$ and $42$ don't divide $448$), so $x + y > 43$, absurd.