Problem A. 717. (February 2018)

A. 717. We say that a positive integer is lazy if it has no prime divisor greater than $\displaystyle 3$. Prove that there are at most two lazy numbers strictly between two consecutive square numbers.

Proposed by: Zoltán Gyenes and Géza Kós, Budapest

(5 pont)

Deadline expired on March 12, 2018.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. A "lusta" számokat osszuk négy "típusba": ezek a $\displaystyle k^2$, $\displaystyle 2k^2$, $\displaystyle 3k^2$, illetve $\displaystyle 6k^2$ alakú számok.

Először azt mutatjuk meg, hogy két szomszédos négyzetszám között nem szerepelhet két azonos típusú lusta szám. Tegyük fel indirekte, hogy valamilyen $\displaystyle a,x$ egészekkel és $\displaystyle b\in\{2,3,6\}$ számokkal

$\displaystyle a^2 < bx^2 < b(x+1)^2 <(a+1)^2. $

Ekkor $\displaystyle \frac{b(x+1)^2}{bx^2} < \frac{(a+1)^2}{a^2}$, átrendezve $\displaystyle x>a$; ez viszont ellentmond annak, hogy $\displaystyle (x+1)^2<(a+1)^2$.

Most tehát tegyük fel, hogy — a feladat állításával szemben — valamilyen $\displaystyle a$ pozitív egésszel három lusta szám is szerepel $\displaystyle a^2$ és $\displaystyle (a+1)^2$ között; mint láttuk, ez csak úgy lehet, ha egy-egy $\displaystyle 2k^2$, $\displaystyle 3k^2$, illetve $\displaystyle 6k^2$ típusú számunk van:

$\displaystyle a^2 < \quad 2^{p_1}3^{q_1}, \quad 2^{p_2}3^{q_2}, \quad 2^{p_3}3^{q_3} \quad < (a+1)^2. $

A három lusta szám között egy-egy $\displaystyle 2k^2$, $\displaystyle 3k^2$, illetve $\displaystyle 6k^2$ típusú van; emiatt $\displaystyle p_1,p_2,p_3$ közül és $\displaystyle q_1,q_2,q_3$ közül is pontosan az egyik páros, a másik kettő páratlan.

Feltételezzük, hogy $\displaystyle a\ge3$ (a kis $\displaystyle a$ értékeket majd a megoldás végén ellenőrizzük). Ekkor $\displaystyle (a+1)^2<2a^2$, így az $\displaystyle [a^2,(a+1)^2]$ intervallumban semelyik egész nem oszthatja semelyik másik egészt sem. Ebből következik, hogy az $\displaystyle 2^{p_1}3^{q_1}$, $\displaystyle 2^{p_2}3^{q_2}$ és $\displaystyle 2^{p_3}3^{q_3}$ számok sem lehetnek egymás osztói. Emiatt a $\displaystyle p_1,p_2,p_3$ páronként különbözők, és a $\displaystyle (q_1,q_2,q_3)$ sorozat ellentétesen rendezett, mint a $\displaystyle (p_1,p_2,p_3)$ sorozat; az általánosság csorbítása nélkül feltehetjük, hogy $\displaystyle p_1<p_2<p_3$ és $\displaystyle q_1>q_2>q_3$.

Vizsgáljuk most az

$\displaystyle w = \frac{2^{p_1}3^{q_1} \cdot 2^{p_3}3^{q_3}}{2^{p_2}3^{q_2}} = 2^{p_1-p_2+p_3}\cdot 3^{q_1-q_2+q_3} $

számot. A jobbalon mindkét kitevő pozitív: $\displaystyle p_1-p_2+p_3>p_3-p_2>0$ és $\displaystyle q_1-q_2+q_3>q_1-q_2>0$, továbbá, $\displaystyle p_1,p_2,p_3$ és $\displaystyle q_1,q_2,q_3$ között is pontosan az egyik páros, tehát $\displaystyle p_1-p_2+p_3$ és $\displaystyle q_1-q_2+q_3$ is páros. A $\displaystyle w$ egy lusta négyzetszám.

A $\displaystyle w$ számra

$\displaystyle w > \frac{(a^2)^2}{(a+1)^2} > (a-1)^2, \quad\text{és}\quad w < \frac{((a+1)^2-1)^2}{a^2} = (a+2)^2, $

ezért a $\displaystyle w$ négyzetszám értéke csak $\displaystyle a^2$ vagy $\displaystyle (a+1)^2$ lehet. Bármelyik is következzen be, most már mind a négy típusú lusta szám előfordul az $\displaystyle [a^2,(a+1)^2]$ intervallumban. Újra definiálva és rendezve a kitevőket, a négy lusta szám legyen

$\displaystyle a^2 \le \quad 2^{u_1}3^{v_1}, \quad 2^{u_2}3^{v_2}, \quad 2^{u_3}3^{v_3}, \quad 2^{u_4}3^{v_4} \quad \le (a+1)^2, $

ahol $\displaystyle u_1<u_2<u_3<u_4$ és $\displaystyle v_1>v_2>v_3>v_4$.

A lusta párok legnagyobb közös osztóira

$\displaystyle 2^{u_1}3^{v_2} = \mathrm{gcd}\big(2^{u_1}3^{v_1},2^{u_2}3^{v_2}\big) \le \big|2^{u_1}3^{v_1}-2^{u_2}3^{v_2}\big| \le 2a, $

$\displaystyle 2^{u_2}3^{v_3} = \mathrm{gcd}\big(2^{u_2}3^{v_2},2^{u_3}3^{v_3}\big) \le \big|2^{u_2}3^{v_2}-2^{u_3}3^{v_3}\big| \le 2a, $

$\displaystyle 2^{u_3}3^{v_4} = \mathrm{gcd}\big(2^{u_3}3^{v_3},2^{u_4}3^{v_4}\big) \le \big|2^{u_3}3^{v_3}-2^{u_4}3^{v_4}\big| \le 2a, $

(egyenlőség legfeljebb csak az egyik egyenlőtlenségben lehet), összeszorozva

$\displaystyle a^4 \le (2^{u_2}3^{v_2})\cdot(2^{u_3}3^{v_3}) \le 2^{u_1}3^{v_2}\cdot 2^{u_2}3^{v_3}\cdot 2^{u_3}3^{v_4} < (2a)^3 $

$\displaystyle a<8. $

Ezzel igazoltuk az állítást $\displaystyle a\ge8$ esetén.

Az $\displaystyle a=1,2,\ldots,7$ esetekben a következő lusta számok fordulnak elő $\displaystyle a^2$ és $\displaystyle (a+1)^2$ között:

$1\ldots4$ között:	$2$ és $3$;
$4\ldots9$ között:	$6$ és $8$;
$9\ldots16$ között:	$12$;
$16\ldots25$ között:	$18$ és $24$;
$25\ldots36$ között:	$27$ és $32$;
$36\ldots49$ között:	$48$;
$49\ldots64$ között:	$54$.

Tehát az állítás $\displaystyle a\le7$ esetén is igaz.

Statistics:

9 students sent a solution.

5 points: Gáspár Attila, Imolay András, Janzer Orsolya Lili, Schrettner Jakab.

4 points: Beke Csongor, Bukva Balázs, Matolcsi Dávid.

0 point: 2 students.

Problems in Mathematics of KöMaL, February 2018

9 students sent a solution.
5 points:	Gáspár Attila, Imolay András, Janzer Orsolya Lili, Schrettner Jakab.
4 points:	Beke Csongor, Bukva Balázs, Matolcsi Dávid.
0 point:	2 students.

Already signed up?
New to KöMaL?