Zadanie

Všimli ste si, že Aňa je palindróm? Aňa si to všimla a všetkým vedúcim to s radosťou oznámila, keď prišla na párty. Vedúcich to neohúrilo. Avšak inšpirovalo ich to a začali zisťovať, koľko je \(6\)-ciferných palindrómov (nezačínajúcich nulou), ktoré sú deliteľné číslom \(7\). Zistite to aj vy.

Poznámka: Palindróm je číslo, ktoré keď prečítame odzadu (teda cifry sú v opačnom poradí), tak je zhodné s pôvodným číslom. Napríklad číslo \(1578751\) je \(7\)-ciferný palindróm.

Označme si nejaký \(6\)-ciferný palindróm ako \(ABCCBA\), pričom \(A,\, B,\, C\) sú jeho cifry. To si ďalej vieme prepísať nasledovne \[ABCCBA = 100000 \cdot A + 10000 \cdot B + 1000 \cdot C + 100 \cdot C + 10 \cdot B + A = 100001 \cdot A + 10010 \cdot B + 1100 \cdot C.\] Pozrime sa, čo pre tieto cifry musí platiť, aby bol výsledný palindróm násobkom \(7\). Vieme, že ak od tohto výrazu odpočítame alebo pripočítame násobok \(7\), na jeho deliteľnosti sa nič nezmení. Čísla, ktorými násobíme \(A,\, B\) a \(C\), preto vieme vydeliť \(7\) a počítať ďalej len s ich zvyškami po delení. Platí, že \(100001 = 7 \cdot 14285 + 6,\, 10010 = 7 \cdot 1430,\, 1100 = 7 \cdot 157 + 1\). Môžeme si napríklad všimnúť, že hodnotu cifry \(B\) môžeme zvoliť ľubovoľne – na deliteľnosti palindrómu nič nezmení.

Zostáva nám určiť, pre ktoré dvojice cifier \(A\) a \(C\) bude číslo \(6 A + C\) násobkom \(7\). Tu už vieme jednoducho vyskúšať jednotlivé možnosti pre \(A\) a dopočítať \(C\). Ešte si však zjednodušíme prácu. \[6 \cdot A + C = 7 \cdot A + (C - A).\] Číslo \(7 \cdot A\) je isto násobkom sedmičky, takže potrebujeme, aby rozdiel \(C - A\) bol tiež jej násobkom. Keďže sú obe čísla cifry, ich rozdiel musí byť \(0\) alebo \(\pm 7\). Pre \(C = A\) dostaneme \(9\) možností (keďže \(A\) nemôže byť \(0\)), pre \(C = A + 7\) dve, a pre \(C = A - 7\) tri (\(C\) môže byť nula).

Dokopy sme našli \(14\) možností pre dvojicu \(A,\, C\). K nim môžeme zvoliť cifru \(B\) ľubovoľne. Celkový počet šesťciferných palindrómov tak bude \(14 \cdot 10 = 140\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.