\documentclass[12pt]{article}
\usepackage{t1enc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath,amsfonts,amsmath,amsthm}
\usepackage[polish]{babel}

\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

%                            ---------- o ----------

\begin{document}
\sloppy

%                            ---------- o ----------

\noindent \textbf{Zadanie:}
Dla jakich $n$, $k$ można podzielić odważniki o masach $1$g, $2$g, ..., $n$g na $k$ równych grup?

\medskip

\begin{scriptsize}
W dalszym ciągu dla wygody będziemy pomijali oznaczenie jednostki masy.
\end{scriptsize}

\medskip

Zauważmy, że jeśli podział jest możliwy, to co najwyżej jedna grupa może składać się z jednego odważnika. Pozostałych $k-1$ grup musi zawierać co najmniej dwa odważniki. Stąd natychmiast:
\begin{equation}\label{eq:dol}
2k-1 \le n.
\end{equation}
Innym warunkiem koniecznym jest oczywiście podzielność łącznej masy odważników w gramach przez $k$. Innymi słowy, masa odważników w jednej grupie:
\begin{equation}\label{eq:masa:def}
m = \frac{n(n+1)}{2k}
\end{equation}
musi być liczbą całkowitą. Udowodnimy, że powyższe warunki są również wystarczające.

Niech $A$ będzie zbiorem trójek $(n, m, k)$ spełniających warunki \eqref{eq:dol} i \eqref{eq:masa:def}, dla których podział nie jest możliwy. Wykażemy, że $A$ jest zbiorem pustym.

Załóżmy przeciwnie, że $A$ nie jest pusty. Niech $n_0$ będzie najmniejszą taką liczbą, że dla pewnych $m, k$ trójka $(n_0, m, k)$ jest elementem $A$. Następnie niech $m_0$ będzie największą taką liczbą, że trójka $(n_0, m_0, k_0)$ należy do $A$, przy odpowiednim doborze $k_0$.

Zauważmy, że jeśli dla pewnych $n$, $k$ podział jest możliwy, to możliwy jest również po dołożeniu kolejnych $2k$ odważników. Wystarczy do pierwszej grupy dodać odważniki o masach $(n+1)$ i $(n+2k)$, do drugiej: $(n+2)$ i $(n+2k-1)$ itd., wreszcie do $k$-tej: $(n+k)$ i $(n+k+1)$. Oznacza to, że niemożliwy jest podział $n_0 - 2k_0$ odważników na $k_0$ grup -- w przeciwnym przypadku $(n_0, m_0, k_0)$ nie należałoby do $A$. Wobec definicji $A$, $n_0$, $m_0$ i $k_0$, otrzymujemy $2k_0 - 1 > n_0 - 2k_0$, czyli:
\begin{equation}\label{eq:gora}
2k_0 - 1 \le n_0 < 4k_0 - 1.
\end{equation}

Zakładamy, że nie jest możliwy podział $n_0$ odważników na $k_0$ grup o masie $m_0$. Wobec \eqref{eq:dol} oraz \eqref{eq:gora}:
\begin{equation}\label{eq:masa}
n_0 \le m < 2n_0.
\end{equation}
Możliwych jest kilka sytuacji.
\begin{enumerate}
\item
Jeśli $n_0 = 2k_0 - 1$, to w pierwszej grupie umieszczamy odważnik o masie $(2k_0 - 1)$, w drugiej: dwa o masach $(2k_0 - 2)$ i $1$, w trzeciej: $(2k_0 - 3)$ i $2$ itd., w $k_0$-wej: $k_0$ i $(k_0 - 1)$. Sprzeczność.
\item
Jeśli $n_0 = 2k_0$, to w pierwszej grupie umieszczamy dwa odważniki o masach $2k_0$ i $1$, w drugiej: $(2k_0 - 1)$ i $2$, w trzeciej: $(2k_0 - 2)$ i $3$ itd., w $k_0$-wej: $(k_0 + 1)$ i $k_0$. Sprzeczność.
\item
Załóżmy, że $m_0$ jest nieparzyste i $n_0 > 2m_0$. Niech $l = n_0 - \frac{m_0-1}{2}$. Ponieważ $m_0 - n_0 < n_0$, więc możemy umieścić w pierwszej grupie odważniki $n_0$ i $(m_0 - n_0)$, w drugiej: $(n_0 - 1)$ i $(m_0 - n_0 + 1)$ itd., w $l$-tej: $(n_0 - l + 1)$, $(n_0 - l)$. Pozostało nam $n = m_0 - n_0 - 1$ odważników o masach od $1$ do $n$, które należy rozmieścić w $k = k_0 - l$ grupach, po $m_0$ w każdej. Zauważmy, że:
\[
n - 2k + 1 = (m_0 - n_0 - 1) - (2k_0 - (2n_0 - m_0 + 1)) + 1 = n_0 - 2k_0 + 1 \ge 0,
\]
czyli zachodzi \eqref{eq:dol}. Zatem, na mocy definicji $A$, $n_0$, $m_0$ i $k_0$, podział $n$ odważników na $k$ grup jest wykonalny. Zatem udało się podzielić $n_0$ odważników na $k_0$ grup. Sprzeczność.
\item
Załóżmy, że $m_0$ jest parzyste i $n_0 > 2m_0$. Niech $l = n_0 - \frac{m_0}{2}$. Jak poprzednio, w pierwszej grupie umieśćmy odważniki $n_0$ i $(m_0 - n_0)$, w drugiej: $(n_0 - 1)$ i $(m_0 - n_0 + 1)$ itd., w $l$-tej: $(n_0 - l + 1)$, $(n_0 - l - 1)$. Pozostał nam odważnik o masie $\frac{m_0}{2}$ oraz $n = m_0 - n_0 - 1$ odważników o masach od $1$ do $n$, które należy podzielić na $k_0 - l$ grup o masie $m_0$. Zrobimy to następująco. Wpierw podzielimy $n$ odważników na $k = 2k_0 - 2l - 1$ grup o masie $\frac{m_0}{2}$. Następnie do jednej z nich dołożymy odważnik o masie $\frac{m_0}{2}$, zaś pozostałe połączymy w pary. Wraz z wcześniejszymi krokami da nam to szukany podział $n_0$ odważników na $k_0$ grup, przeczący założeniu. Trzeba tylko sprawdzić warunek \eqref{eq:dol}. Ale:
\[
n - 2k + 1 = (m - n_0 - 1) - (4k_0 - (4n_0 - 2m_0) - 2) + 1 = 3n_0 - m_0 - 4k_0 + 2,
\]
czyli na mocy \eqref{eq:gora}:
\[
2k_0 (n - 2k + 1) = 6k_0n_0 - n_0^2 - n_0 - 8k_0^2 + 4k_0 = (4k_0 - n_0)(n_0 - 2k_0 + 1) \ge 0 .
\]
\end{enumerate}
Powyższe przypadki wyczerpują wszystkie możliwości, każdy zaś prowadzi do sprzeczności. Oznacza to, że poczynione przez nas założenie jest fałszywe, a więc zbiór $A$ jest pusty. To kończy dowód.

%                            ---------- o ----------

\end{document}
