Problem B. 5262. (October 2022)

B. 5262. Louisa wrote down a natural number, not containing 0 but containing at least two different digits. Then she also listed all the numbers which can be formed by permuting the digits of the original number. What is the maximum of the greatest common divisor of all the numbers (including the original one)?

Proposed by Katalin Abigél Kozma, Győr

(3 pont)

Deadline expired on November 10, 2022.

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

Megoldás. Azt igazoljuk, hogy a legnagyobb közös osztó legfeljebb 63 lehet.

A leírt szám két különböző számjegye legyen \(\displaystyle a\) és \(\displaystyle b\), melyekre \(\displaystyle 1\leq a<b\leq 9\). A lapra írt számok között van olyan, amely \(\displaystyle \overline{ab}\)-re végződik, és ha itt csak az utolsó két jegyet cseréljük fel, akkor a szám végződése \(\displaystyle \overline{ba}\) lesz (a többi jegy pedig változatlan marad). Ennek a két számnak a különbsége \(\displaystyle \overline{ba}-\overline{ab}=(10b+a)-(10a+b)=9(b-a)\). A lapra írt számok legnagyobb közös osztója ennek a különbségnek is osztója kell legyen. Ha \(\displaystyle a=1,b=9\), akkor ez a különbség \(\displaystyle 9\cdot8=72\), minden más esetben \(\displaystyle 9(b-a)\leq 9\cdot 7=63\). Ha a felírt szám nem csak 1-esekből és 9-esekből áll, akkor tehát azt kapjuk, hogy a legnagyobb közös osztó legfeljebb 63. Ha szám minden jegye 1-es vagy 9-es, akkor a legnagyobb közös osztó osztója a 72-nek, de mivel páratlan számok legnagyobb közös osztója, így páratlan lévén a 9-nek is osztója kell legyen. Tehát azt kaptuk, hogy a legnagyobb közös osztó biztosan legfeljebb 63.

Akkor lehet 63, ha \(\displaystyle a=1,b=8\) (és más jegy nincsen) vagy ha \(\displaystyle a=2,b=9\) (és más jegy nincsen). Próbálkozzunk például az 1-es és 8-as jegyekkel. Olyan számot keresünk, ami 63-mal osztható, vagyis 7-tel és 9-cel kell oszthatónak lennie. A 9-cel való oszthatóság teljesül, ha például ugyanannyi 1-est és 8-ast használunk. A 18 nem osztható 7-tel, a 1188 sem, viszont a \(\displaystyle 111\,888\) igen. Tehát \(\displaystyle 63\mid 111\,888\), tegyük fel, hogy Lenke ezt a számot írta először a lapra. A számjegyek sorrendjének megváltoztatásával összesen \(\displaystyle \binom{6}{3}=20\)-féle szám kapható (a \(\displaystyle 111\,888\)-at is számolva), megmutatjuk, hogy ezek mindegyike osztható 63-mal. Világos, hogy mindegyikhez eljuthatunk úgy, hogy a \(\displaystyle 111\,888\) számból indulva mindig két szomszédos (különböző) jegyet cserélünk fel. Így mindig \(\displaystyle 18\leftrightarrow81\) csere történik, ezért a változtatás során a szám értéke \(\displaystyle \pm(81-18)\cdot 10^i=\pm63\cdot 10^i\)-nel változik, és így végig 63-mal osztható marad.

Tehát a lapon szereplő számok legnagyobb közös osztója legfeljebb 63 lehet. Ennyi lehet is, például, ha Lenke a 111888 számot írta le.

Statistics:

134 students sent a solution.
3 points:	82 students.
2 points:	25 students.
1 point:	16 students.
Unfair, not evaluated:	6 solutionss.

Problems in Mathematics of KöMaL, October 2022