Problem OM 73.2.5

% NumberTheory, Integers, ConstructiveProof

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage} 
\usepackage{polski}
\usepackage{enumitem}
\usepackage{titlesec}
\usepackage{fontspec}
\setmainfont{Linux Libertine O}

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

\titlespacing*{\section}
  {0pt}    % left
  {3pt}   % space before (reduce this)
  {3pt}    % space after (reduce this)

\newcommand{\Name}{Hostek}                
\newcommand{\Email}{your.email@example.com}   
\newcommand{\ProblemNumber}{LXXIII OM, etap 2, zadanie 5}               

\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}{16}\selectfont

\section*{Problem Statement}
Dodatnią liczbę całkowitą $n$ nazwiemy dobrą jeśli istnieje dodatnia liczba całkowita $k$, dla której $n = k(k + 1)$. Rozstrzygnąć,
czy istnieje $2022$ parami różnych dobrych liczb, których suma jest
również dobrą liczbą.
\bigskip

\section*{Solution}
\subsection*{Konstrukcja liczb}
Rozważmy następujący zbiór liczb:
\begin{itemize}
    \item $2021$ liczb postaci $k(k+1)$ dla $k = 1, 2, \ldots, 2021$
    \item Dodatkową liczbę postaci $(x-1)x$, gdzie:
    \[
    x = \frac{1}{2} \sum_{k=1}^{2021} k(k+1)
    \]
\end{itemize}

\subsection*{Weryfikacja własności}
\begin{enumerate}[label=(\roman*)]
    \item \textbf{Poprawność liczb dobrych:}
    \begin{itemize}
        \item Każda liczba $k(k+1)$ jest dobra z definicji.
        \item Liczba $(x-1)x$ jest dobra, gdyż odpowiada wartości $k = x-1$.
    \end{itemize}
    
    \item \textbf{Różnowartościowość:}
    \begin{itemize}
        \item Liczby $k(k+1)$ są parami różne dla różnych $k$.
        \item Liczba $(x-1)x$ jest większa niż jakakolwiek z liczb $k(k+1)$ dla $k \leq 2021$, ponieważ:
        $$x = \frac{1}{2} \sum_{k=1}^{2021} k(k+1) \geq \frac{1}{2} \cdot 2021 \cdot 2022$$
        $$\Rightarrow \frac{1}{2}(x-1)x \gg \frac{1}{2} \cdot 2021 \cdot 2022$$
    \end{itemize}
    
    \item \textbf{Suma liczb:}
    Obliczmy całkowitą sumę:
    \begin{align*}
        S &= (x-1)x + \sum_{k=1}^{2021} k(k+1) \\
          &= (x-1)x + 2x \quad \text{(z definicji $x$)} \\
          &= x^2 - x + 2x \\
          &= x(x + 1)
    \end{align*}
    Otrzymana suma $x(x+1)$ jest liczbą dobrą (odpowiada $k = x$).
\end{enumerate}

\subsection*{Intuicja geometryczna}
Liczby dobre odpowiadają polom prostokątów o bokach różniących się o 1. Sumując odpowiednio dobrane prostokąty, możemy skonstruować większy prostokąt tego typu. Kluczowa obserwacja:
\[
\underbrace{(x-1)x}_{\text{duży prostokąt}} + \underbrace{\sum \text{małe prostokąty}}_{2x} = x(x+1)
\]
Działa to dzięki algebraicznej tożsamości $x(x+1) = (x-1)x + 2x$, gdzie $2x$ rozkłada się na sumę ciągu liczb dobrych.

\subsection*{Uogólnienie}
Dla dowolnego $r \in \mathbb{N}$ wystarczy:
\begin{itemize}
    \item Wybrać $r-1$ liczb postaci $k(k+1)$ dla $k = 1, 2, \ldots, r-1$
    \item Zdefiniować $x = \frac{1}{2} \sum_{k=1}^{r-1} k(k+1)$
    \item Dodać liczbę $(x-1)x$
\end{itemize}
Suma $r$ liczb będzie zawsze równa $x(x+1)$, co kończy dowód.

\section*{Odpowiedź}
Tak, istnieje 2022 parami różnych liczb dobrych o sumie będącej liczbą dobrą.


\end{document}