Number theoryDifficulty 8.3ShortlistFind the answer
For a positive integer M, if there exist integers a, b, c and d so that: M≤a<b≤c<d≤M+49,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.
A number or a short expression. Spacing and $ signs are ignored.
Solution
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≤a<b≤c<d≤M+49,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)≤M+49 and pq≥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≤a≤wx≤(z−1)(y−1). Take p=z−1 and q=y−1. 2. Converse: If p≤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=242.
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≤49 hence p+q≤48. Thus, M≤pq≤242=576.
### Smallest BAD Number
Lemma: Every integer M≤288 is GOOD.
Proof: 1. There is some multiple of 13 in {M+37,M+38,…,M+49}, call it K. 2. Take q=12 and p=13K−1. Then: pq=1312K−12≥1312(M+37)−12=M+1312⋅24−M≥M.
Lemma: Every integer 287≤M≤442 is GOOD.
Proof: 1. Any pair (p,q) of integers is a witness to all pq−δ≤M≤pq being prime, where δ=48−p−q. 2. Construct the following 24 cases: p⋅q15⋅2014⋅2215⋅2118⋅1815⋅2218⋅1914⋅2519⋅1914⋅2617⋅2219⋅2016⋅2413⋅3018⋅2220⋅2017⋅2418⋅2316⋅2620⋅2117⋅2518⋅2415⋅2921⋅2117⋅26pq300308315324330342350361364374380384390396400408414416420425432435441442δ1312121211119108998588776766465pq−δ287296303312319331341351356365371376385388392401407410413419426431435437 Since the intervals [pq−δ,pq] cover [287,442], the lemma is proved.
Lemma: The number M=443 is BAD.
Proof: 1. Assume for contradiction pq exists, meaning pq≥443 and (p+1)(q+1)≤492. Then pq≤491−(p+q). 2. Now p+q≥2443⟹p+q≥43, hence pq≤448. 3. Compute the factorization of each K with p+q minimal: 443444445446447448=1⋅442=12⋅37=5⋅89=2⋅233=3⋅149=16⋅28 All of these fail the inequality (p+1)(q+1)≤492, so 443 is BAD.
The answer is: The greatest GOOD number is 576 and the smallest BAD number is 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.