Problem done/OMJ/XXI/21.2.2.tex

% NumberTheory, Divisilibity, Constructive

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage}
% \usepackage{polski}
\usepackage{graphicx}
\usepackage{float}
\usepackage{fontspec}
\usepackage{enumitem}
\usepackage{unicode-math}
\usepackage[most]{tcolorbox}

\setmainfont{Linux Libertine O}
\newfontfamily\russianfont{Linux Libertine O}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot,
    headheight=50pt, a4paper]{geometry}

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{XXI OMJ, etap 2, zadanie 2}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\Name \\ \Email}
\fancyhead[C]{\ProblemNumber}
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}
\fontsize{15}{18}\selectfont

\section*{Problem Statement}

W zapisie dziesiętnym dodatniej liczby całkowitej $n$ każda
cyfra jest różna od 0 oraz żadna cyfra nie pojawia się więcej niż
raz. Ponadto liczba $n$ jest podzielna przez każdą ze swoich cyfr.
Wykaż, że liczba $n$ ma co najwyżej 7 cyfr.

\bigskip

\noindent\textbf{Solution:}

Przypomnijmy sobie najpierw pewne cechy podzielności, które przydadzą się w rozwiązaniu zadania:
\begin{itemize}
    \item cecha podzielności przez 2: cyfra jedności musi być podzielna przez 2
    \item cecha podzielności przez 3: suma cyfr musi być podzielna przez 3
    \item cecha podzielności przez 4: liczba stworzona z dwóch ostatnich cyfr musi być podzielna przez 4
    \item cecha podzielności przez 5: cyfra jedności musi być podzielna przez 5
    \item cecha podzielności przez 6: liczba jest podzielna jednocześnie przez 2 i przez 3
    \item cecha podzielności przez 7: suma przemienna bloków cyfr o długości 3 od prawej do lewej jest podzielna przez 7. Przykład:
    \[
    1,369,851: 851 - 369 + 1 = 483 = 7\cdot69
    \]
    \item cecha podzielności przez 8: liczba stworzona z trzech ostatnich cyfr musi być podzielna przez 8
    \item cecha podzielności przez 9: suma cyfr musi być podzielna przez 9
\end{itemize}

Zauważmy, że gdyby liczba $n$ miała w swoim zapisie cyfrę 5, 
to musiałaby mieć tę cyfrę na pozycji jedności.
Bo cecha podzielności przez 5 mówi, że cyfra jedności musi być albo 0 albo 5,
a tutaj 0 jest zakazane.

A gdyby miała na pozycji jedności cyfrę 5, to nie mogłaby być podzielna ani przez 2 ani przez 4 ani przez 8 ani przez 6.

Dlatego się nie opłaca brać cyfry 5.

Rozważmy, dlatego, teraz zbiór cyfr taki:
\[
S = \left\{ 1,2,3,4,6,7,8,9 \right\}
\]

Zbiór ten ma 8 elementów. Spróbujmy skonstruować liczbę $n$ siedmiocyfrową:
\[
n = 7916832
\]

Zauważmy, że ta liczba $n$ spełnia wszystkie swoje założenia:
\begin{itemize}
    \item podzielna przez 1: oczywiste
    \item podzielna przez 2: cyfra jedności jest podzielna przez 2
    \item podzielna przez 3: $7+9+1+6+8+3+2=36=3\cdot12$
    \item podzielna przez 6: jest podzielna przez 2 i przez 3
    \item podzielna przez 7: $832-916+7=-77=-7\cdot11$
    \item podzielna przez 8: $832$ jest podzielna przez 8
    \item podzielna przez 9: $7+9+1+6+8+3+2=36=9\cdot4$
\end{itemize}

Zauważmy, że nie da się zaiste stworzyć ze zbioru $S$ ośmiocyfrowej liczby spełniającej warunki.

Ponieważ suma tych cyfr: $1+2+3+4+6+7+8+9=40$ nie jest podzielna przez 9. 
Więc gdyby wziąć liczbę $n$ złożoną z tych cyfr to warunek podzielności przez 9 nie będzie spełniony.

Podsumowując: udowodniliśmy, że nie można wziąć wszystkich ośmiu cyfr, ponieważ
cecha podzielności przez 9 nie byłaby spełniona a ponadto pokazaliśmy konstrukcję
liczby $n$ zawierającą 7 cyfr. To dowodzi, że cyfra $n$ może mieć co najwyżej 7 cyfr.

Co należało dowieść. \qed

\end{document}