Problem done/OMJ/XIX/19.3.2.tex

% NumberTheory, Geometry, Combinatorics, DiophantineEquations

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

% dowod, proof
\newtcolorbox{redbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=red!5!white,
    colframe=red!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% lemat, lemma
\newtcolorbox{greenbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=green!5!white,
    colframe=green!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% twierdzonko, theorem
\newtcolorbox{bluebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=blue!5!white,
    colframe=blue!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% zasada, rule 
\newtcolorbox{yellowbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=yellow!5!white,
    colframe=yellow!70!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% Fakcik, fact
\newtcolorbox{purplebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=purple!5!white,
    colframe=purple!90!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% algorithm
\newtcolorbox{orangebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=orange!5!white,
    colframe=orange!70!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

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

\allowdisplaybreaks

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

\section*{Problem Statement}

Wyznacz najmniejszą liczbę całkowitą $n\geq1$ o tej własności,
że kwadrat o wymiarach $n\times n$ można rozciąć na kwadratowe
części o wymiarach $1\times1$ lub $2\times2$ w taki sposób, aby uzyskać po
tyle samo części każdego z tych dwóch rodzajów.

\bigskip

\noindent\textbf{Solution:}

\boxed{\textbf{Sposób 1:}}

Najpierw wprowadźmy lemat pomocniczy:

\begin{greenbox}{Lemat \ref{ll1}}
\begin{lemma}
    \label{ll1}
    Gdy mamy kwadrat $a\times a$, dla parzystego $a$ to da się zapełnić go w całości przy pomocy kwadratów $2\times2$.
\end{lemma}
\end{greenbox}

\begin{redbox}{Dowód lematu \ref{ll1}}
\begin{proof}
Ponieważ $a$ jest liczbą parzystą, możemy zapisać $a = 2k$ dla pewnego $k \in \mathbb{N}$. Oznacza to, że kwadrat $a \times a$ można podzielić zarówno w poziomie, jak i w pionie, na $k$ odcinków długości $2$, co daje w sumie siatkę $k \times k$ kwadratów o wymiarach $2 \times 2$.

Każdy z tych mniejszych kwadratów ma dokładnie taki rozmiar, jaki potrzebujemy ($2 \times 2$), a ponieważ cała plansza $a \times a$ została nimi pokryta bez zachodzenia na siebie i bez pozostawiania pustych miejsc, to znaczy, że da się ją całkowicie wypełnić kwadratami $2 \times 2$.

\end{proof}
\end{redbox}

Z tego możemy wyprowadzić następny lemat:

\begin{greenbox}{Lemat \ref{ll2}}
\begin{lemma}
    \label{ll2}
    Gdy mamy kwadrat $a\times a$, dla parzystego $a$ to da się zapełnić go w całości przy pomocy dowolnej liczby kwadratów $2\times2$ nie większej niż $\frac{a^2}{4}$ oraz pewnej liczby kwadratów $1\times1$. 
\end{lemma}
\end{greenbox}

\begin{redbox}{Dowód lematu \ref{ll2}}
\begin{proof}
Z wcześniejszego lematu wiemy, że gdy $a$ jest parzyste, to kwadrat $a \times a$ można w całości pokryć $\frac{a^2}{4}$ kwadratami $2 \times 2$ bez pustych miejsc.

Teraz pokażemy, że dla dowolnej liczby $k$, gdzie $0 \le k \le \frac{a^2}{4}$, również da się zapełnić cały kwadrat $a \times a$ przy pomocy $k$ kwadratów $2 \times 2$ oraz pewnej liczby kwadratów $1 \times 1$.

Używamy $k$ kwadratów $2 \times 2$, które pokrywają łącznie $4k$ pól. Pozostała powierzchnia to $a^2 - 4k$ jednostkowych pól. Każde z tych pól możemy zapełnić kwadratem $1 \times 1$.

Zatem całość można wypełnić $k$ kwadratami $2 \times 2$ oraz $a^2 - 4k$ kwadratami $1 \times 1$. Pokrycie jest możliwe dla każdego $k$ z podanego zakresu, ponieważ w skrajnym przypadku $k = \frac{a^2}{4}$ wypełniamy cały kwadrat wyłącznie kwadratami $2 \times 2$ (jak w poprzednim lemacie), a dla $k = 0$ używamy tylko kwadratów $1 \times 1$.

\end{proof}
\end{redbox}

Zauważmy, że mamy tyle samo części $1\times1$ i $2\times2$. Oznaczmy liczbę tych części przez $k$.

Wtedy sumaryczne pole naszego kwadratu jest równe: $1^2 \cdot k + 2^2 \cdot k = 5k$.

Ale zauważmy, że pole kwadratu (dużego) jest również równe $n^2$.

Zatem możemy przyrównać: $5k = n^2$. (Zachowajmy to na później)

Rozważmy przypadki: gdy $n$ jest parzyste i gdy nieparzyste. Spójrzmy na rysunek obrazujący te przypadki (patrz rys. \ref{r1}):

\begin{figure}[H]
    \centering
    \includegraphics[width=.8\textwidth]{img/19.3.2_i1.jpg}
    \caption{Porównanie przypadku nieparzystego i parzystego}
    \label{r1}
\end{figure}

Zauważmy, że przypadek nieparzysty to tak naprawdę kwadrat $(n-1)\times (n-1)$ z bocznymi paskami o długości bądź szerokości równej 1.

Bez straty ogólności możemy założyć, że z tych bocznych pasków bierzemy jedynie kwadraty $1\times1$. (Bo i tak będzie trzeba je uwzględnić)

Rozważmy najpierw przypadek $n$ parzyste:

Zauważmy, że w przypadku parzystym maksymalna liczba kwadratów $2\times2$ jaką można wziąć jest równa $\frac{n^2}{2^2} = \frac{n^2}{4}$, ponieważ gdy $n$ jest parzyste to całość możemy zapełnić kwadratami $2\times2$.

Dlatego weźmy $\frac{n^2}{4} - x$ kwadratów $2\times2$, dla pewnego $x\geq0$. Wtedy bierzemy tyle samo ($\frac{n^2}{4} - x$) kwadratów $1\times1$; a ich łączne pole ma być równe $n^2$.

Czyli możemy ułożyć takie równanko:
\begin{align}
    4\left(\frac{n^2}{4} - x\right)+1\left(\frac{n^2}{4} - x\right) &= n^2 \nonumber \\
    5\left(\frac{n^2}{4} - x\right) &= n^2 \nonumber \\
    n^2 + \frac{n^2}{4} - 5x &= n^2 \nonumber \\
    \frac{n^2}{4} &= 5x \nonumber \\
    n^2 &= 20x \nonumber \\
    n &= \sqrt{20x} \nonumber \\ 
    n &= 2\sqrt{5x} \nonumber 
\end{align}

Wiemy, że $n$ jest parzystą (w tym przypadku) liczbą naturalną, czyli, skoro mamy w iloczynie $2$ to wystarczy zapewnić by pierwiastek był całkowity. A to jest możliwe w przypadku, gdy $x$ jest postaci $5\cdot a^2$, gdzie $a\in\mathbb{Z}_{\geq0}$.

Czyli najmniejsze $x$ to $5$.

Podstawiając:
$$ n = 2\sqrt{5\cdot5} = 2\cdot5=10$$

Czyli najmniejsze $n$ dla przypadku parzystego jest równe $10$.

Przy czym bierzemy $\frac{10^2}{4} - 5 = 20$ części każdego rodzaju. (Jest to możliwe ze względu na lemat \ref{ll2})

Teraz przypadek nieparzysty:

W tym przypadku możemy wziąć maksymalnie $\frac{(n-1)^2}{4}$ kwadratów $2\times2$.

Ale zauważmy, że musimy też zapełnić te paski po bokach. Dlatego minimalna liczba kwadratów $1\times1$ jest równa $2n - 1$, a przeto minimalna liczba kwadratów $1\times1$ jest równa $2n - 1$.

Załóżmy, że bierzemy $\frac{(n-1)^2}{4} - x$ kwadratów $2\times2$, dla pewnego $x\in\mathbb{N}$.

Wtedy musimy wziąć tyle samo kwadratów $1\times1$.

Przeto, możemy ułożyć takie równanko:
\begin{align}
    4\left(\frac{(n-1)^2}{4} - x\right) + 1\left(\frac{(n-1)^2}{4} - x\right) &= n^2 \nonumber \\
    5\left(\frac{(n-1)^2}{4} - x\right) &= n^2 \nonumber \\
    \frac{5}{4}\left(n-1\right)^2 - 5x &= n^2 \nonumber \\
    \frac{5}{4}\left(n^2 - 2n + 1\right) - 5x &= n^2 \nonumber \\
    \frac{5}{4}n^2 - \frac{5}{4}2n + \frac{5}{4} - n^2 &= 5x \nonumber \\
    \frac{1}{4}n^2 - \frac{5}{2}n + \frac{5}{4} &= 5x \nonumber \\
    n^2 - 10n + 5 &= 20x \nonumber \\
    (n-5)^2 - 20 &= 20x \nonumber \\
    (n-5)^2 &= 20x + 20 \nonumber \\
    (n-5)^2 &= 20(x + 1) \nonumber \\
    (n-5) &= 2\sqrt{5(x + 1)} \nonumber \\
    n &= 2\sqrt{5(x + 1)} + 5 \nonumber
\end{align}

Zauważmy, że $n$ ma być nieparzyste, czyli po prostu nasz pierwiastek ma dawać liczbę całkowitą (przy czym zauważmy, że nieważne jaką wartość całkowitą będzie miał pierwiastek, to zawsze $n$ będzie nieparzyste).

Czyli $x + 1$ musi być postaci $5\cdot a^2$, gdzie $a\in\mathbb{Z}_{\geq0}$

Najmniejsza taka liczba to $5$ ($a=0$). Czyli: $x+1=5$.

Co nam daje $x=4$.

Podstawiając otrzymujemy $n = 15$.

Czyli minimalne $n = 15$ (gdy $n$ jest nieparzyste).

Przy czym w tym przypadku bierzemy $45$ części każdego rodzaju. Żeby zapełnić paski po bokach używamy $2n - 1 = 29$ kwadratów $1\times1$. Kwadraty $2\times2$ używamy by częściowo zapełnić kwadrat $14\times14$ (patrz rys. \ref{r1}) (na pewno nie zapełnimy go w całości, bo $14^2 = 196 > 4\cdot 45 = 180$). A wiadomo, że reszta kwadratów $1\times1$ (czyli $45-29=16$) idzie na pozostałe pokrycie tego kwadratu.

Podsumowując przypadki: otrzymujemy, że minimalne $n=10$.

\textbf{Odpowiedź:} Najmniejsze $n$ jest równe $10$.

\boxed{\textbf{Sposób 2:}\text{ (firmówka)}}

Zauważmy, że mamy tyle samo części $1\times1$ i $2\times2$. Oznaczmy liczbę tych części przez $k$.

Wtedy sumaryczne pole naszego kwadratu jest równe: $1^2 \cdot k + 2^2 \cdot k = 5k$.

Ale zauważmy, że pole kwadratu (dużego) jest również równe $n^2$.

Zatem możemy przyrównać: $5k = n^2$. 

Stąd wniosek: $n$ jest liczbą podzielną przez 5.

Czy da się $n=5$? Sprawdźmy:

$5k = 25 \Rightarrow k = 5$. Czyli bierzemy 5 z każdej części. Ale zauważmy jedną rzecz: używając części $2\times2$ możemy zapełnić jedynie kwadrat $4\times4$ (patrz rys. \ref{r1}). A istotnie by zapełnić kwadrat $4\times4$ możemy użyć maksymalnie 4 kwadratów $2\times2$. A my musimy użyć 5. Wniosek: nie da się dla $n=5$.

Czy da się $n=10$? Tak, bo mamy $k=20 < \frac{10^2}{4} = 25$ (patrz lemat \ref{ll2}).

Podsumowując: skoro $n$ ma być podzielne przez $5$, to najmniejsze $n$ jest równe 10 (sprawdziliśmy to ręcznie).

\textbf{Odpowiedź:} najmniejsze $n$ jest równe $10$.

\end{document}