Problem B. 5281. (December 2022)

B. 5281. Let \(\displaystyle d > 1\) denote a positive integer. Prove that there exists a positive integer that has the same number of factors divisible by \(\displaystyle d\) as factors not divisible by \(\displaystyle d\).

Proposed by B. Hujter, Budapest

(5 pont)

Deadline expired on January 10, 2023.

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

Megoldás. Legyen \(\displaystyle d\) prímtényezős felbontása

\(\displaystyle d = p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_n^{k_n},\)

itt \(\displaystyle p_1,p_2,\ldots,p_n\) különböző prímszámok és \(\displaystyle k_1,k_2,\ldots,k_n\) pozitív egészek.

Keressük a feladat megoldását jelentő \(\displaystyle N\) számot

\(\displaystyle N = p_1^{k_1+\ell_1} \cdot p_2^{k_2+\ell_2} \cdot \ldots \cdot p_n^{k_n+\ell_n} \)

alakban, ahol \(\displaystyle \ell_1,\ell_2,\ldots,\ell_n\) nemnegatív egészek.

\(\displaystyle N\) osztói azok a

\(\displaystyle p_1^{m_1} \cdot p_2^{m_2} \cdot \ldots \cdot p_n^{m_n}\)

alakú számok, ahol \(\displaystyle m_i \in \{0 , 1, \ldots, k_i+\ell_i\}\) minden \(\displaystyle i\)-re. Ezen számok közül azok oszthatók \(\displaystyle d\)-vel, amelyeknél minden \(\displaystyle i\)-re teljesül, hogy \(\displaystyle m_i \in \{ k_i,k_i+1,\ldots,k_i + \ell_i\}\). Az \(\displaystyle m_i\) kitevők egymástól függetlenül választhatók meg, így az \(\displaystyle N\) számnak összesen

\(\displaystyle (k_1+\ell_1+1)\cdot(k_2+\ell_2+1)\cdot\ldots\cdot(k_n+\ell_n+1) \)

osztója van, és ezek közül

\(\displaystyle (\ell_1+1)\cdot(\ell_2+1)\cdot\ldots\cdot(\ell_n+1) \)

darab lesz osztható \(\displaystyle d\)-vel. Az a célunk, hogy az előbbi szám az utóbbinak kétszerese legyen.

Az egyszerűség kedvéért vezessük be az \(\displaystyle \ell'_i = \ell_i+1\) jelölést. A feladatunk így ekvivalens a következő állítással:

Tetszőleges \(\displaystyle k_1,k_2,\ldots,k_n\) pozitív egészekhez lehet választani olyan \(\displaystyle \ell'_1,\ell'_2,\ldots,\ell'_n\) pozitív egészeket, amelyekre

\(\displaystyle \frac{k_1+\ell'_1}{\ell'_1} \cdot \frac{k_2+\ell'_2}{\ell'_2} \cdot \ldots \cdot \frac{k_n+\ell'_n}{\ell'_n} = 2. \)

Egy lehetséges módszer megfelelő \(\displaystyle \ell'_i\) számok megválasztására a következő. Legyen minden \(\displaystyle 2 \leq i \leq n\) esetén \(\displaystyle \ell'_{i} = k_{i-1} + \ell'_{i-1}\), azaz a szorzatban minden tört számlálója megegyezik a következő tört nevezőjével. Így egyszerűsítés után csak az első tört nevezője és az utolsó tört számlálója marad, azaz:

\(\displaystyle \frac{k_n+\ell'_n}{\ell'_1} = 2, \)

itt persze \(\displaystyle \ell'_n = \ell'_{1} + k_{1} + k_2 + \ldots + k_{n-1}\). Ha tehát \(\displaystyle \ell'_1\)-et így választjuk meg:

\(\displaystyle \ell'_1 = k_1 + k_2 + \ldots + k_n, \)

akkor teljesül a kívánt

\(\displaystyle \frac{k_1+\ell'_1}{\ell'_1} \cdot \frac{k_2+\ell'_2}{\ell'_2} \cdot \ldots \cdot \frac{k_n+\ell'_n}{\ell'_n} = \frac{k_n+\ell'_n}{\ell'_1} = \frac{2(k_1+k_2+\ldots+k_n)}{k_1+k_2+\ldots+k_n} = 2 \)

egyenlőség.

Megjegyzés. Egy alternatív (bár hasonlóan működő) lehetőség az \(\displaystyle \ell'_i\) számok megválasztására: legyen \(\displaystyle \ell'_i = k_i (n+i-1)\) minden \(\displaystyle i\)-re. Ekkor

\(\displaystyle \frac{k_1+\ell'_1}{\ell'_1} \cdot \frac{k_2+\ell'_2}{\ell'_2} \cdot \ldots \cdot \frac{k_n+\ell'_n}{\ell'_n} = \frac{k_1 (n+1)}{k_1 n} \cdot \frac{k_2 (n+2)}{k_2 (n+1)} \cdot \ldots \cdot \frac{k_n (2 n)}{k_n (2n-1)} = \frac{2n}{n} = 2. \)

Statistics:

72 students sent a solution.
5 points:	52 students.
4 points:	2 students.
3 points:	6 students.
2 points:	5 students.
1 point:	3 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, December 2022