Problem done/OMJ/XXI/21.2.3.tex

% Combinatorics

\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 3}

\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}

Pola prostokątnej planszy $1\times 100$ są ponumerowane kolejno
liczbami całkowitymi od 1 do 100. Pionek początkowo stał na
polu o numerze $n$. W pierwszym ruchu przesunięto go o jedno
pole, w drugim — o dwa pola, w trzecim — o trzy pola itd.
Okazało się, że po wykonaniu 99 ruchów pionek odwiedził każde
pole dokładnie raz. Wyznacz wszystkie możliwe wartości $n$.

\emph{Uwaga}. Przesunięcie pionka o $k$ pól oznacza bezpośrednie przemieszczenie go między polami, których numery różnią się o $k$.

\bigskip

\noindent\textbf{Solution:}

Spróbujmy zrobić to \emph{od tyłu}, tzn. spróbujmy zacząć od pola ostatniego i każdym
ruchem zmniejszać skok.

Zauważmy, że w takim razie w pierwszym ruchu musimy wykonać skok o długości 99.
Skok ten można zrobić tylko jeśli będę miał na prawo 99 albo na lewo 99 pól.

Dlatego końcowym polem (czyli początkowym w odwrotnej konfiguracji) może być jedynie pole pierwsze albo setne.

Rozważmy te dwa przypadki:

Gdyby końcowym polem było ostatnie pole to w pierwszym ruchu skaczemy o 99 pól na lewo. 
Czyli doskakujemy na pole o numerze $100-99=1$.

Teraz mam zrobić skok o 98 pól, ale zauważmy, że pole nr 1 ma na prawo dokładnie 98 pól! 
Bo pole o numerze 100 jest już odwiedzone. Zatem muszę przejść na pole $1+98=99$.

I zauważmy, i tak dalej, i tak dalej, zawsze będę miał jedną możliwość na które pole tu skoczyć.

Na końcu otrzymam pole o nr 50.

Podobnie dla drugiego przypadku: zawsze będzie dokładnie jedna możliwość na wykonanie skoku.
W tym przypadku skończę na polu o nr 51.

Podsumowując: rozważywszy dwa przypadki końcowego pola dochodzimy do wniosku, że
jedynymi startowymi polami mogłyby być 50 i 51.

\textbf{Odpowiedź: } $n \in \left\{50,51\right\}$

\end{document}