Problem done/CZOM/73/Z9/73Z9.2.4.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}

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

\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}{73 CZOM, kat. Z9, etap 2, zadanie 4}

\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}
V pěti pytlících je dohromady 52 kuliček. V žádných dvou pytlících není stejný počet
kuliček, některý pytlík může být i prázdný. Všechny kuličky z kteréhokoli (neprázdného)
pytlíku lze přemístit do ostatních čtyř pytlíků tak, že v nich budou stejné počty kuliček.
\begin{enumerate}[label=\alph*)]
    \item Najděte nějaké rozdělení kuliček do pytlíků, které má všechny uvedené vlastnosti.
    \item Ukažte, že při jakémkoli rozdělení s uvedenými vlastnostmi je v některém pytlíku
    právě 12 kuliček.
\end{enumerate}

\noindent\textbf{Polski:}

W pięciu woreczkach znajdują się łącznie 52 kulki. W żadnych dwóch woreczkach nie ma tej samej liczby kulek, przy czym pewien woreczek może być pusty. Wszystkie kulki z dowolnego (niepustego) woreczka można przenieść do pozostałych czterech woreczków w taki sposób, że w każdym z nich będzie ta sama liczba kulek.
\begin{enumerate}[label=\alph*)]
    \item Znajdź jakieś rozdzielenie kulek do woreczków, które spełnia wszystkie podane warunki.
    \item Pokaż, że przy dowolnym rozdzieleniu spełniającym te warunki w którymś woreczku znajduje się dokładnie 12 kulek.
\end{enumerate}

\bigskip

\noindent\textbf{Solution:}

a) Przykładowe rozdzielenie kulek: \boxed{8} \boxed{9} \boxed{10} \boxed{12} \boxed{13}. (Intuicja za tym przykładem pokaże się w podpunkcie b)

b) 

\noindent\textbf{Sposób 1:}

Skoro wszystkich kulek jest łącznie 52 to skoro wyjmujemy z jednej dowolnej, a potem w innych ma być po równo to w każdej powinno być: $\frac{52}{4} = 13$ kulek.

Skoro tak, to jeśliby w jakimś było więcej niż 13 kulek to się nie da. (bo jeśli byśmy w takim przypadku brali z którejś co ma mniej, to nie możemy zabrać z tej co ma te więcej niż 13).

Ale co jeśli nie będzie żadnego worka z 13 kulkami? Wtedy maksymalnie możemy wziąć:
$$ 12 + 11 + 10 + 9 + 8 = 50 < 52$$

Jak widać za mało – co oznacza, że musi być worek z trzynastoma kulkami.

Ale co jeśli teraz nie będzie żadnego worka z 12 kulkami? Wtedy maksymalnie możemy wziąć:
$$ 13 + 11 + 10 + 9 + 8 = 51 < 52$$

Jak widać za mało – co oznacza, że musi być worek z 12 kulkami.

Co należało dowieść.

\noindent\textbf{Sposób 2} (trochę na około):

Powiedzmy, że w worku pierwszym jest $w_1$ kulek, w worku drugim $w_2$ i tak dalej (w $i$-tym $w_i$). Przy czym bez straty ogólności załóżmy, że 
$$0\leq w_1 < w_2 < w_3 < w_4 < w_5.$$

Z warunku zadania mamy, że: $w_1+w_2+w_3+w_4+w_5=52$.

Dobra, rozważmy teraz dwa przypadki:

\begin{enumerate}[label=\arabic*)]
    \item $w_1\neq0$
    \item $w_1=0$
\end{enumerate}

Najpierw przypadek 1)

Okej, zauważmy taką rzecz: dla pewnego worka musi być w nim tyle kulek by wszystkie pozostałe kulki miały mieć potem co najmniej $w_5$ kulek. W szczególności $w_1$ musi mieć tyle kulek. Ale też wszystkie mają mieć tyle samo kulek. Załóżmy przeto, że końcowa liczba kulek w każdym woreczku to $w_5 + k$. Dlatego możemy ułożyć takie równanko: (przy czym $k\in\mathbb{N} \cup \left\{0\right\}$)
\begin{align*}
w_1 &= (w_5 + k - w_2) + (w_5 + k - w_3) + (w_5 + k - w_4) + (w_5 + k - w_5) \\
0 &= (w_5 + k) + (w_5 + k) + (w_5 + k) + (w_5 + k) - w_1 - w_2  - w_3 - w_4 - w_5 \\
0 &= 4(w_5+k) - (w_1+w_2+w_3+w_4+w_5) \\
0 &= 4(w_5+k) - 52 \\
52 &= 4(w_5+k) \\
13 &= (w_5+k) \\
w_5 &= 13 - k 
\end{align*}

Czyli otrzymujemy: $w_5 = 13 - k$, gdzie $k\geq 0$ co oznacza, że $w_5 \leq 13$.

Zauważmy, że gdyby $w_5$ było równe 12, to się nie da zrobić tak, by suma kulek była równa 52. Bo nawet jeśli weźmiemy najwięcej jak się da: 
$$8+9+10+11+12=50 < 52$$

Jak widać się nie da...

Z tego wynika, że $w_5 = 13$.

Ale zauważmy, że $52 = 4\cdot 13$, czyli, innymi słowy, wszystkie worki końcowo otrzymane \textbf{muszą} mieć 13 kulek. (gdy nie bierzemy z $w_5$ oczywiście) (przy czym to częściowo wynika z tego, że $k = 0$ (ale było to robione jedynie dla przypadku, gdy bierzemy z $w_1$, więc trzeba było się upewnić))

Dobra, ale co jeśli bierzemy z $w_5$?

Wtedy wszystkie worki powinny mieć $w_4 + k_4$ kulek. Gdzie $k_4\in\mathbb{N} \cup \left\{0\right\}$. Dlatego możemy ułożyć następujące równanko:
\begin{align*}
w_5 &= (w_4 + k_4 - w_1) + (w_4 + k_4 - w_2) + (w_4 + k_4 - w_3) + (w_4 + k_4 - w_4) \\
0 &= (w_4 + k_4) + (w_4 + k_4) + (w_4 + k_4) + (w_4 + k_4) - w_1 - w_2  - w_3 - w_4 - w_5 \\
0 &= 4(w_4+k_4) - (w_1+w_2+w_3+w_4+w_5) \\
0 &= 4(w_4+k_4) - 52 \\
52 &= 4(w_4+k_4) \\
13 &= (w_4+k_4) \\
w_4 &= 13 - k_4 
\end{align*}

Czyli otrzymujemy: $w_4 = 13 - k_4$, gdzie $k_4\geq 0$ co oznacza, że $w_4 \leq 13$.

Przy czym już nam wyszło, że $w_5 = 13$, a wiemy, że $w_4 < w_5$, co oznacza, że $w_4<13$. A zatem musi być $k_4\geq1$.

Ale co jeśli $w_4$ nie jest równe 12? Zauważmy, że wtedy się nie da, bo nawet jak weźmiemy najwięcej jak się da to nie zsumują się do 52:
$$8+9+10+11+13=51<52$$

A zatem mamy, że $w_4 = 12$, $k_4 = 1$.

\textbf{Czyli tutaj udało się dowieść dla przypadku pierwszego, że musi być jakiś worek co ma w sobie 12 kulek.}

Przy czym dodatkowy komentarz: że w takim wypadku nie ma znaczenia ile kulek mają pozostałe worki – ważne tylko by się sumowały do $52-12-13 = 27$.

Bo zauważmy, że nasz $w_5$ daje każdemu tyle by miał wynik równy 13. Czyli do $w_4$ daje 1, do $w_3$ daje $w_4+1-w_3$, itd. Dowód:
\begin{align*}
w_5 &= 1 + (w_4+1-w_3) + (w_4+1-w_2) + (w_4+1-w_1) \\
w_5 &= 1 + 13-w_3 + 13-w_2 + 13-w_1 \\
w_5 &= 1 + 13-w_3 + 13-w_2 + 13-w_1 \\
w_5 &= 40 - w_1 - w_2 - w_3 \\
13 &= 40 - w_1 - w_2 - w_3 \\
-27 &= - w_1 - w_2 - w_3 \\
27 &= w_1 + w_2 + w_3 \\
\end{align*}

I tak samo, potem każdy chce sumować każdemu do $w_5 = 13$, ale (przy czym $i < 5$):
\begin{align*}
w_i &= 4w_5 - w_1 - w_2 - w_3 - w_4 - w_5 + w_i \\
w_i &= 52 - 52 + w_i \\
w_i &= w_i
\end{align*}

Bo dla pewnego $w_i$ to widać, że zawsze daje 1 do czwartego, a reszcie daje odpowiednio by się sumowały do 13. Ale wiemy, że $w_1+w_2+w_3=27$. Czyli przykładowo $w_1 = 27 - w_2 - w_3$. A on daje każdemu iście $13-w_j$. Co daje:
\begin{align*}
w_1 &= (13 - w_2) + (13-w_3) + (13-w_4) \\
w_1 &= (13 - w_2) + (13-w_3) + 1 \\
w_1 &= 27 - w_2 - w_3
\end{align*}

Dobra, teraz przypadek 2):

Spróbujmy zrobić podobnie. Mamy, że $w_1 = 0$, czyli możemy powiedzieć, że:
$$w_1+w_2+w_3+w_4+w_5 = w_2+w_3+w_4+w_5 = 52$$ 

Okej, jeśli $w_2$ ma dawać jakimś innym gościom to wyjdzie coś takiego (bo zauważmy, że każdy worek ma mieć $w_5+k_2$ kulek, przy czym $k_2\in \mathbb{Z} \wedge k_2 \geq 0$)
\begin{align*}
w_2 &= (w_5 + k_2 - w_1) + (w_5 + k_2 - w_3) + (w_5 + k_2 - w_4) + (w_5 + k_2 - w_5) \\
0 &= (w_5 + k_2) + (w_5 + k_2) + (w_5 + k_2) + (w_5 + k_2) - w_1 - w_2  - w_3 - w_4 - w_5 \\
0 &= 4(w_5+k_2) - (w_1+w_2+w_3+w_4+w_5) \\
0 &= 4(w_5+k_2) - 52 \\
52 &= 4(w_5+k_2) \\
13 &= (w_5+k_2) \\
w_5 &= 13 - k_2 
\end{align*}

Jak widać otrzymujemy to samo, co w pierwszym przypadku. Używając tej samej argumentacji co w pierwszym przypadku otrzymujemy: $w_5 = 13$. A skoro $w_5 = 13$ to robiąc tak jak w pierwszym przypadku dostaniemy $w_4 = 12$. Co należało dowieść.

\bigskip
\textbf{P.S.}

Zauważmy, że jedynymi możliwościami są:
\[
13+12+11+10+6, \quad 13+12+11+9+7, \quad 13+12+10+9+8.
\]

Dowód: ponieważ wcześniej pokazaliśmy, że $w_5 = 13$ i $w_4 = 12$, to trzeba dobrać $w_1+w_2+w_3=27$, ale nie ma innej trójki liczb $(w_1,w_2,w_3)$, gdzie $0\leq w_1 < w_2 < w_3 < 12$, spełniającej $w_1+w_2+w_3 = 27$.

\bigskip
\textbf{P.S. 2} \boxed{\text{Firmówka:}}

Możliwe rozwiązanie: Po przemieszczeniu kulek, jeden worek jest pusty, a w pozostałych czterech jest taka sama liczba kulek. Łącznie mamy 52 kulki, więc po przemieszczeniu w każdym z niepustych worków musi być 13 kulek (\( 52 : 4 = 13 \)). Z tego wynika, że w żadnym worku nie mogło być więcej niż 13 kulek.

a) Możliwe początkowe liczby kulek w workach odpowiadają możliwym rozkładom liczby 52 jako sumy pięciu różnych liczb całkowitych nie większych niż 13. Przez próbę można znaleźć następujące możliwości:
\[
52 = 13+12+11+10+6 = 13+12+11+9+7 = 13+12+10+9+8.
\]

b) Gdyby w żadnym worku nie było więcej niż 12 kulek, to łączna liczba kulek nie mogłaby przekroczyć \( 12+11+10+9+8 = 50 \). Zatem w jednym z worków musiałoby się znaleźć 13 kulek.
Jeśli w żadnym worku nie ma 12 kulek, to suma mogłaby wynieść najwyżej \( 13+11+10+9+8 = 51 \), więc w którymś worku musiałaby być 12 kulek.

\textbf{Uwaga:} Rozkłady podane w części a) to jedyne możliwe rozwiązania. Można to udowodnić, stopniowo podstawiając coraz mniejsze różne liczby nie większe niż 13 i kontrolując ich sumę. W każdym z podanych przypadków znajduje się liczba 12.

\end{document}