%&latex
\documentclass[11pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp866]{inputenc}
\usepackage[russian]{babel}
%\usepackage{pscyr}

\usepackage{amsthm,amsmath,amsfonts,amssymb}

\textwidth=17.45cm
\textheight=24.5cm
\advance\voffset-15mm
\hoffset=-2.4cm

\addto\extrasrussian{\renewcommand{\refname}%
{\normalfont\scshape\normalsize Литература}}
\let\le\leqslant
\let\leq\leqslant
\let\ge\geqslant
\let\geq\geqslant
\newcommand\kratno{\mathrel{\smash{\lower.5ex\hbox{$\vdots$}}}}
\def\const{\mbox{const}\,}
\def\conv{\mbox{conv}\,}
\def\answer{О\,т\,в\,е\,т}
\def\lemma{\ifvmode{\smallbreak\par}\fi Л\,е\,м\,м\,а}
\def\proof{\smallbreak\par Д\,о\,к\,а\,з\,а\,т\,е\,л\,ь\,с\,т\,в\,о}
\def\Zn{\mathbb Z_n}

\newcounter{problem}[subsection]
\newcounter{solution}[subsection]
\renewcommand{\thesection}{}
\renewcommand{\thesubsection}{\arabic{subsection}}
\renewcommand{\thesubsubsection}{\arabic{subsection}-\arabic{subsubsection}}
\renewcommand{\theproblem}{\thesubsection.\arabic{problem}}
\renewcommand{\thesolution}{\thesubsection.\arabic{solution}}
\newenvironment{problem}{\refstepcounter{problem}\smallskip\noindent%
{\bf\arabic{subsection}.\arabic{problem}.}}{}
\newenvironment{solution}{\refstepcounter{solution}\medskip\noindent%
{\bf\arabic{subsection}.\arabic{solution}.}}{}

\makeatletter
\renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
{2\baselineskip}{\baselineskip}{\bfseries\large\itshape}} \makeatother

\hyphenation{на-ту-раль-ных}
\marginparwidth20pt \marginparsep1pt
\reversemarginpar

\begin{document}
\pagestyle{empty}

%\makeatletter
%\renewcommand{\@oddhead}{\hfil Последовательности с нулевой суммой. Версия 0.13
%\hfil\thepage}
%\makeatother

\title{Последовательности с нулевой суммой}
\author{Задачу представляют К.\,Кохась, К.\,Куюмжиян}
%\date{Версия 0.13}
\date{}

\maketitle

\section{Условия задач}


\subsection{Нуль-последовательности}

\bigskip
{\small\noindent Для каждого натурального числа $n$ обозначим через
$\mathbb Z_n$ множество остатков при делении на $n$ c операцией сложения по
модулю~$n$. Нуль-последовательностью в $\mathbb Z_n$ будем называть последовательность элементов
$\mathbb Z_n$ с~нулевой суммой.
\par}

\medskip
\begin{problem}
\label{D(Z_n)}
Пусть $n$~--- натуральное число. Пусть $k$~--- наименьшее натуральное число,
для которого верно, что любая последовательность из $k$ элементов $\mathbb Z_n$
содержит нуль-подпоследовательность. Докажите, что $k=n$.
\end{problem}

\begin{problem}
\label{D(Z_n)-zerofree}
Опишите все последовательности в $\mathbb Z_n$ длины $n-1$, которые не содержат
нуль-подпосле\-до\-ва\-тель\-но\-стей.
\end{problem}

\begin{problem}
\label{D(Z_n)-zerofree}
Опишите все последовательности в $\mathbb Z_n$ длины $n-2$, которые не содержат
нуль-подпоследова\-тель\-ностей.
\end{problem}


\begin{problem}
При каком наименьшем $m$ любая последовательность из $m$ элементов ${\mathbb Z_{100}}$,
содержащая не меньше 81 различных элементов, имеет нуль-подпоследовательность, состоящую
из 100 элементов?
\end{problem}

\begin{problem}
В Тридевятом царстве в ходу были монеты в несколько копеек, четырех разных достоинств
(сейчас уже никто не знает, каких именно). Какое наименьшее число тридевятских монет
должен найти археолог, чтобы быть уверенным, что среди них заведомо есть ровно 100 монет,
в сумме дающих целое число рублей?
\end{problem}


\begin{problem}
\label{EGZ12}
Докажите, что всякая последовательность элементов ${\mathbb Z_{12}}$ длины 23
содержит нуль-подпоследо\-ва\-тель\-ность длины $12$.
\end{problem}

\begin{problem}
$S$~--- последовательность из 502 элементов ${\mathbb Z_{541}}$, причем $S$
содержит ровно 10 различных элементов. Докажите, что $S$ содержит
нуль-подпоследовательность.
\end{problem}

\begin{problem}
$S$~--- последовательность из 10 элементов ${\mathbb Z_{17}}$, причем $S$
не содержит нуль-подпоследовательнос\-тей. Докажите, что какой-то элемент
${\mathbb Z_{17}}$ встречается в $S$ не меньше 4 раз.
\end{problem}


\begin{problem}
\label{sums1}
Пусть $S$~--- последовательность из $n$ чисел взаимно простых с $n$.
Докажите, что любой остаток по модулю $n$ равен сумме некоторой подпоследовательности $S$.
\end{problem}

\begin{problem}
\label{N-C_Ext_lemma}
Пусть $S$~--- последовательность из $\mathbb Z_n$ длины $2n-1$.
Предположим, что некоторый элемент $a$ встречается в этой последовательности не менее
$[n/2]$ раз. Докажите, что $S$ содержит нуль-под\-после\-дователь\-ность длины~$n$.
\end{problem}


\begin{problem}
Пусть $p$ --- нечетное простое.
Сколько нуль-подпоследовательностей длины $p$ (в $\mathbb Z_p$)
имеет последовательность
0, 0, 1, 1, 2, 2, \dots, $p-1$, $p-1$?
\end{problem}

\begin{problem}
Дано целое число $n\geq 2$.
$S$~--- последовательность длины $n$ в $\mathbb Z_n\setminus\{0\}$ с ненулевой суммой.
Докажите, что $S$ имеет не меньше $n$ различных нуль-подпоследовательностей.
%Предположим, что целые числа $a_1$, \dots, $a_n$ не
%делятся на $n$ и, более того, $n$~не делит сумму $a_1+\ldots+a_n$. Доказать, что
%существуют по крайней мере $n$ различных подмножеств
%в $\{a_1,\dots, a_n\}$ с суммой, делящейся на $n$.
\end{problem}


\subsection{Экстремальные задачи}

\bigskip
{\small\noindent Для каждого натурального $n$ обозначим через
$\mathbb Z_n^d$ множество всевозможных наборов $(m_1, m_2, \dots, m_d)$, где
$m_i$~--- остатки по модулю~$n$, с операцией покоординатного сложения.
Нуль-последовательностью в $\mathbb Z_n^d$ будем называть последовательность элементов
$\mathbb Z_n^d$, с нулевой суммой (т.\,е.\ с суммой равной $(0, 0, \dots, 0)\in \mathbb Z_n^d$).
Обозначим через $g(n,d)$ наименьшее такое число~$M$, что в любом
подмножестве $\mathbb Z_n^d$, состоящем из $M$ элементов, найдутся
$n$ элементов с нулевой суммой.
Обозначим через $s(n,d)$ наименьшее такое число~$M$, что в любой
последовательности $a_1$, \dots, $a_M\in\mathbb Z_n^d$
найдется нуль-подпоследовательность, состоящая из $n$ элементов,
т.е. найдутся различные индексы $i_1$, \dots, $i_n$, такое что
$a_{i_1}+\ldots+a_{i_n}=0$.
(Под последовательностью мы фактически понимаем мультимножество,
порядок элементов последовательности нам не важен.)
\par}
\medskip

\begin{problem}
\label{s_power2}
Докажите, что $s(2,d)=2^d+1$.
\end{problem}

\begin{problem}
\label{s_nerav}
Докажите, что
$
(n-1)2^d+1\leq s(n,d)\leq (n-1)n^d +1\,.
$
\end{problem}

\begin{problem}
\label{s_multipl}
Докажите, что $s(n_1 n_2,d) \leq s(n_1, d) + n_1\bigl(s(n_2, d)-1\bigr)$.
\end{problem}


\begin{problem}
Докажите, что $g(3,3)\geq 10$, $s(3,3)\geq 18$. (На самом деле $g(3,3)=10$, $s(3,3)=19$.)
\end{problem}

\begin{problem}
Докажите, что
$g(n,2)\geq \begin{cases} 2n-1 & \hbox{при нечетных $n$}; \\
                          2n+1 & \hbox{при четных $n$}.\end{cases}
$
\end{problem}

\begin{problem}
На клетчатой бумаге нарисован квадрат $3 \times 3$. В узлах сетки (включая границу квадрата)
отмечено 9 точек. Докажите, что можно выбрать 4 точки, у которых центр тяжести также
расположен в узле сетки. Иными словами, докажите, что $g(4,2)=9$.
\end{problem}

\begin{problem}
Докажите, что $s(2048,d)=2047\cdot 2^d +1$.
\end{problem}

\begin{problem}
Докажите, что $s(432,d)=1725$.
\end{problem}




%\clearpage

\subsection{Теорема Эрдеша--Гинзбурга--Зива и близкие вопросы}


\begin{problem} [Теорема Коши\,--\,Дэвенпорта]
Пусть $p$~--- простое число, $A$ и $B$~--- два непустых подмножества в~${\mathbb Z}_p$.
Докажите, что $|A+B|\geq \min\{p, \ |A|+|B|-1\}$.
\end{problem}

\begin{problem} [Теорема Эрдеша\,--\,Гинзбурга\,--\,Зива]
Докажите, что всякая последовательность элементов ${\mathbb Z_n}$ длины $2n-1$
содержит нуль-подпоследовательность длины $n$.
\end{problem}

%\bigskip
{\small
\begin{center}
Вы можете пользоваться этими теоремами в решении следующих задач.
\end{center}

Многие из следующих задач верны в следующей более общей ситуации.
Коммутативной конечной группой будем называть конечное множество, снабженное операцией ``$+$'',
для которой выполнены привычные для этого значка аксиомы:
коммутативность $a+b=b+a$; ассоциативность $a+(b+c)=(a+b)+c$; существование нулевого элемента
со свойством $0+a=a$ при всех $a$; и существование обратного элемента: для каждого $a$
существует элемент $b$, такой что $a+b=0$ (обозначают $b=-a$). Благодаря последней аксиоме
определена и разность: $a-b$ по определению равно $a+(-b)$. Типичная конечная коммутативная
группа устроена похоже на $\mathbb Z_d^n$: зафиксируем набор чисел $k_1$, \dots, $k_n$
и рассмотрим множество ``векторов'' вида $(x_1, x_2, \dots, x_n)$, где $x_i\in\mathbb Z_{k_i}$.
Операция ``+''~---  обычное покоординатное сложение (для $i$-й координаты --- по модулю $k_i$).

Задачи, утверждения которых верны для произвольной конечной коммутативной группы, помечены
значком $\dagger$. Мы особо приветствуем решения, которые не используют специфику $\mathbb Z_n$
и верны для произвольной коммутативной конечной группы.}

\begin{problem}
\label{KD_iterated}
Пусть $p$~--- простое число; $A_1$, $A_2$, \dots, $A_k$~--- непустые подмножества ${\mathbb Z}_p$.
Докажите, что
$$
|A_1+A_2+\ldots+A_k|\geq \min\{p, \ \Bigl(\sum_{i=1}^k |A_i|\Bigr)-k+1\}\,.
$$
\end{problem}

\begin{problem}
Пусть $p$~--- простое число и $S=(a_1, \dots, a_{2p-1})$~--- последовательность в ${\mathbb Z}_p$,
в которой элементы $a_1$, \dots, $a_s$ попарно различны ($s\geq 2$).
Докажите, что в $S$ существует нуль-подпоследовательность длины $p$,
в которую входит ровно один из элементов $a_1$, \dots, $a_s$.
\end{problem}

\begin{problem}
а) Рассмотрим преобразования правильного 12-угольника~--- симметрии и повороты.
Докажите, что среди любых 47 преобразований найдется 24 преобразования, композиция которых
(в некотором порядке) дает тождественное отображение.

б) Докажите аналогичный факт для группы перестановок $S_4$.
\end{problem}

\begin{problem}
\label{lemma_Gao}
Пусть $p$~--- простое число, $T$~--- последовательность в ${\mathbb Z}_p \setminus\{0\}$
длины~$p$, $h$~--- максимальная кратность элемента в~$T$. Докажите, что любой элемент
${\mathbb Z}_p$ является суммой не более чем $h$ элементов~$T$.
\end{problem}

\begin{problem}
Пусть $m\geq k\geq 2$, причем $m$ делится на $k$.
Докажите, что всякая последовательность целых чисел длины $m+k-1$
содержит подпоследовательность длины $m$ c суммой, делящейся на $k$.
\end{problem}

\begin{problem}$\dagger$ [Теорема Кемпермана\,--\,Шерка]
\label{Scherk}
Пусть $n$~--- натуральное число, $A$ и $B$~--- два подмножества ${\mathbb Z}_n^d$,
содержащие 0, и пусть уравнение $a+b=0$, где $a\in A$, $b\in B$, имеет относительно $a$ и $b$
единственное решение $a=b=0$.
Докажите, что $|A+B|\geq \min\{n^d, \ |A|+|B|-1\}$.
\end{problem}

\begin{problem}$\dagger$
Пусть $k$ и $r$~--- натуральные числа и пусть $A=\{a_1, \dots, a_{k+r}\}$~---
последовательность элементов~${\mathbb Z}_k$.
Докажите, что если 0 не является $k$-суммой этой последовательности, то последовательность имеет
не меньше $r+1$ различных $k$-сумм.
\end{problem}

\begin{problem}$\dagger$
\label{N-C_EXT}
Пусть $S$~--- последовательность из $n^d$ элементов $\mathbb Z_n^d$,
$h$~---  максимальная кратность элемента в~этой последовательности.
Докажите, что $S$ содержит нуль-подпоследовательность длины не более~$h$.
\end{problem}


\begin{problem}
\label{G-T_lemma}
Пусть $p$~--- простое  число и $2\leq k\leq p-1$.
Рассмотрим последовательность элементов ${\mathbb Z}_p$ длины $2p-k$.
Докажите, что если никакие $p$ элементов
этой последовательности не дают в сумме 0, то один какой-то элемент
входит в последовательность не менее чем $p-k+1$ раз.
\end{problem}


\begin{problem}
\label{N-C_EXT_reformulation}
Пусть $B_1$, $B_2$, \dots, $B_h$~--- набор некоторых подмножеств $\mathbb Z_n^d$.
Положим $m_i=|B_i|$. Пусть оказалось, что $\sum_{i=1}^h m_i \geq n^d$.
Докажите, что можно выбрать непустое множество элементов $b_j$~--- не более чем по одному
из каждого множества~--- так, что сумма выбранных элементов равна $0\in \mathbb Z_n^d$.
\end{problem}

\begin{problem}
\label{Bovey_Erdos_Niven}
Пусть $n>4$~--- нечетное число. Пусть $S$~---
последовательность элементов ${\mathbb Z}_n$ длины $k$, где $\frac{n+1}2\leq k \leq n$.
Предположим, что если $S$ не содержит нуль-подпоследовательностей.
Докажите, что какой-то элемент ${\mathbb Z}_n$ содержится в $S$ не меньше $2k-n+1$ раз.
\end{problem}

\begin{problem}$\dagger$
Пусть $A\subset\mathbb Z_n^d$, $|A|\geq n^d/k$. Докажите, что существует
число $r$, $1\leq r\leq k$, и последовательность $a_1$, \dots, $a_r$
не обязательно различных элементов $A$, такая что $\sum a_i =0$.
\end{problem}

\begin{problem}
Докажите, что набор из $2n-1$ элементов $\mathbb Z_n$ лишь тогда имеет единственную
нуль-под\-после\-до\-ва\-тельность, когда он состоит из $n$ экземпляров числа $a$ и $(n-1)$
экземпляров числа $b$.
\end{problem}

\begin{problem}$\dagger$
Пусть $S$~--- подмножество $\mathbb Z_n^d$, состоящее из $k$ элементов,
причем $S$ не имеет подмножеств с~нулевой суммой.
Докажите, что существует не меньше $2k-1$ элементов $\mathbb Z_n^d$
представимых в виде суммы нескольких элементов из $S$.
\end{problem}


\begin{problem}
\label{G-T_kratnost2}
Пусть $M=\{(a_1,b_1), (a_2,b_2), \dots, (a_{2p-1},b_{2p-1})\}$~--- подмножество в
$\mathbb Z_p^2$. Пусть ни какой элемент $\mathbb Z_p$ не входит в последовательность
$a_1$, \dots, $a_{2p-1}$ больше двух раз. Докажите, что множество $M$ содержит
нуль-подпоследовательность (в $\mathbb Z_p^2$) длины $p$.
\end{problem}


\begin{problem}
Докажите, что наименьшее $m$, для которого любая последовательность из
$\mathbb Z_p^d$ длины $m$ содержит нуль-подпоследовательность, равно
$d(p-1)+1$.
\end{problem}


\end{document}

%\subsection{Combinatorial Nullstellensatz}

\clearpage
\subsection{Коллекция открытых вопросов}

\begin{problem}
$g(p,2)=2p-1$ для простых $p$.
\end{problem}

{\smallskip\leftskip22pt\noindent
Для $p=3$, 5, 7 это доказал Кемниц
(Kemnitz A., Exremalprobleme f\" ur Gitterpunkte. Ph.D.Thesis. Technische Universit\" at
Braunschweig, 1982), для $p\geq 67$~--- Гао и Тангадураи \cite{GaoThangadurai}.
Первый шаг их рассуждений --- это задача \ref{G-T_kratnost2}.
\par
\smallskip}

\begin{problem}
$g(n,2)= \begin{cases} 2n-1 & \hbox{при нечетных $n$} \\
                       2n+1 & \hbox{при четных $n$}\end{cases}
$
\end{problem}

\begin{problem}
$s(n,2)=4n-3$.
\end{problem}

{\smallskip\leftskip22pt\noindent
Это гипотеза  Кемница.
Кажется, она была доказана в прошлом году (комбинаторно).
Легко предъявить последовательность из $4n-4$ элементов,
не содержащую нуль-подпоследовательностей длины $n$:
$(0,0)^{n-1}$, $(0,1)^{n-1}$, $(1,0)^{n-1}$, $(1,1)^{n-1}$.
%Гао доказал, что для чисел $n$ вида $p^k$ (где $p$ простое) $s(n,2)\leq 4n-2$.
\par\smallskip}

\begin{problem}
Пусть $p$~--- простое число, $A$ и $B$~--- два непустых подмножества ${\mathbb Z}_p$.
Обозначим через $A\dotplus B$ множество всевозможных сумм вида $a+b$, где $a\in A$,
$b\in B$ и $a\ne b$.
Докажите, что $|A\dotplus B|\geq \min\{p, \ |A|+|B|-3\}$.
\end{problem}

{\smallskip\leftskip22pt\noindent
Это утверждение называется гипотеза Эрдеша\,--\,Гайлбронна.
Оно доказано.
Простого комбинаторного доказательства неизвестно.
\par\smallskip}

\begin{problem}
Пусть $S$~--- последовательность из $4n-4$ элементов $\mathbb Z_n^2$.
Если $S$ не содержит нуль-подпоследовательности длины $n$, то $S$ содержит всего 4 различных
элемента, каждый~--- с кратностью $n-1$.
\end{problem}

{\smallskip\leftskip22pt\noindent
Это гипотеза Гао. Он проверил, что эта гипотеза мультипликативна,
т.\,е.\ если она верна для $n=k$ и $n=\ell$, то она верна и для $n=k\ell$.
\par\smallskip}

%\clearpage
\subsection{Запас}


\begin{problem}
Пусть $S$~--- последовательность в $\mathbb Z_n$ длины не меньше $(n+3)/2$, $n\geq 3$,
не содержащая нуль-подпоследо\-ва\-тельностей.
Докажите, что $S$ содержит число, взаимно простое с $n$.
\end{problem}


\begin{problem}
Пусть $p$ простое число, $A\subset\mathbb Z_p$, причем $|A|>2\sqrt p$.

а) Докажите, что $A$ содержит подмножество с нулевой суммой.

б) Докажите, что любой остаток по модулю $p$ реализуется как сумма некоторого подмножества из~$A$.
\end{problem}


\begin{problem}
Докажите, что из любых $3p$ элементов $\mathbb Z_p^2$ с нулевой суммой
можно выбрать $p$ элементов с нулевой суммой.
\end{problem}


\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Решения}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setcounter{subsection}1

\begin{solution}
Последовательность, состоящая из $n-1$ единицы, не имеет нуль-подпоследовательностей.
Следовательно, $k\geq n$.

Пусть $a_1$, $a_2$, \dots, $a_n$~--- произвольная последовательность длины $n$.
Докажем, что она содержит нуль-под\-последовательность.
Рассмотрим $n$ сумм
\begin{align*}
&a_1\,,\\
&a_1+a_2\,,\\
&\dots \qquad \dots \qquad \\
&a_1+\ldots+a_{n-1}\,,\\
&a_1+\ldots+a_{n-1}+a_n\,.\\
\end{align*}
Если ни одна из сумм не равна нулю, то
какие-то две суммы совпадают как элементы $\mathbb Z_n$.
Тогда их разность дает нуль-подпоследовательность.
\end{solution}

\begin{solution}
\answer: это последовательности, содержащие всего один элемент $a$ с кратностью $n-1$,
причем $a$ должно быть взаимно просто с $n$.

Действительно, пусть $a_1$, $a_2$, \dots, $a_{n-1}$~--- последовательность, не
содержащая нуль-подпоследовательностей. Предположим, что $a_1\ne a_2$.
Рассмотрим тогда $n$ сумм
\begin{align*}
&a_1\,,\\
&a_2\,,\\
&a_1+a_2\,,\\
&a_1+a_2+a_3\,,\\
&\dots \qquad \dots \qquad \\
&a_1+\ldots+a_{n-1}\,,\\
&a_1+\ldots+a_{n-1}+a_n\,.\\
\end{align*}
Так как ни одна из сумм не равна нулю, то какие-то две суммы совпадают как
элементы $\mathbb Z_n$. Тогда их разность дает нуль-подпоследовательность.
Противоречие. Следовательно, последовательность не может содержать два разных элемента.
\end{solution}

\begin{solution}
\answer: это последовательности, состоящие из $n-2$ копий некоторого элемента $a$,
либо, последовательности, состоящие из $n-3$ копий элемента $a$ и одного элемента $2a$.

См. \cite{Thangadurai}, proposition 3.4.
\end{solution}


\begin{solution}
\answer: при $m=102$. Пусть $A=\{a_1, a_2, \dots, a_{81}\}$~--- различные элементы некоторой
последовательности. Если в последовательности всего 101 элемент, и сумма всех элементов не лежит
в~$A$, то удаление любого элемента даст 100-элементную последовательность с нулевой суммой.
Если же в последовательности не менее 102 элементов, то отбросим лишние, чтобы осталось ровно 102
элемента, среди которых содержится все множество $A$. Пусть сумма этих 102 элементов равна $s$.
В множестве $A$ нетрудно подобрать два элемента $a_i$ и $a_j$ с суммой $s$.
Отбрасывая их, получаем 100-элементную последовательность с нулевой суммой.
\end{solution}

\begin{solution}
\answer: 197 монет.
\end{solution}


\begin{solution}
Выберем из данной последовательности 11 пар чисел с четной суммой чисел в каждой паре.
Поделим сумму чисел каждой пары на 2. Получим числа $b_1$, $b_2$, \dots, $b_{11}$.
Выберем среди этих чисел 5 пар с четной суммой чисел в каждой паре и снова поделим
сумму чисел каждой пары на 2. Получим числа $c_1$, $c_2$, \dots, $c_5$.
Рассмотрим эти пять чисел по модулю 3. Нетрудно видеть, что либо найдется остаток,
встречающийся 3~раза, либо есть три разных остатка. Взяв эти три числа и припомнив историю
их появления, сразу получаем 12 чисел с суммой, делящейся на 12.
\end{solution}

\begin{solution}
Это частный случай теоремы Эрдеша и Эгглтона \cite{EggletonErdos}.
Число 502 будем для ясности обозначать через~$n$, а~541~--- через $n+39$.
Пусть $a_1$, $a_2$, \dots, $a_n$~--- данная последовательность.
Допустим, что никакая ее подпоследовательность не дает в сумме 0.
Пусть $1\leq m \leq n$~--- некоторое число. Заметим, что тогда
все суммы, которые можно получить, выбирая слагаемые только из $m$ первых членов
последовательности $S$, отличны от всех $n-m$ сумм вида $\sum_{i=1}^r a_i$,
где $m+1\leq r\leq n$ (иначе вычтем одну сумму из другой --- останется как раз
нуль-подпоследовательность).
Покажем, что можно выбрать $m$ так, что первые $m$ членов последовательности $S$
будут определять не менее $m+39$ различных сумм.

Так как в $S$ встречается всего 10 различных элементов, какой-то элемент $a\ne0$
входит в $S$ не менее 51 раза. Так как 541~--- простое число, в $\mathbb Z_{541}$
возможно деление, значит, мы можем поделить все элементы $S$ на~$a$; результат каждого
деления можно интерпретировать как число от 1 до 540.
Таким образом, мы можем считать, что $a_1=a_2=\ldots=a_{51}=1$, а остальные элементы
последовательности --- какие-то натуральные числа от 1 до 540. Если ни одно из чисел $a_i$
не превосходит 51, то в виде сумм чисел $a_i$ представимы все натуральные числа от
1 до $\sum_{i=1}^n a_i$, последняя сумма никак не меньше чем сумма первых 10 натуральных
чисел плюс $n-10$. Все вместе --- больше $n+39$. Противоречие.

Если же в последовательности имеется число большее 51,
мы можем считать, что $a_{52}>51$. Полагая $m=52$, мы видим, что
первые $m$ членов последовательности представляют не менее $m+51$ сумм, что и требовалось.
\end{solution}

\begin{solution}
Частный случай \ref{Bovey_Erdos_Niven}.
\end{solution}

\begin{solution}
Пусть $a_1$, $a_2$, \dots, $a_n$ --- данная
последовательность. Индукцией по $i$ тривиально проверяется, что
множество сумм (mod~$n$) всевозможных подпоследовательностей в $a_1$, $a_2$, \dots, $a_i$
содержит не меньше $i$ различных остатков по модулю $n$.
\end{solution}

\begin{solution}
%Это результат Олсона \cite{Olson}.
Мы взяли это утверждение в \cite{Thangadurai}.
Пусть $S$~--- данная последовательность длины $2n-1$ и элемент $a\in\mathbb Z_n$ встречается
в ней $s\geq [n/2]$ раз. Мы можем считать, что $s\leq n-1$, так как в противном случае
результат очевиден.

Рассмотрим сдвинутую последовательность $S-a$, в ней 0 повторяется $s$ раз.
Пусть $T_1$~--- подпоследовательность $S$, состоящая из всех ненулевых элементов $S$;
в ней содержится не меньше $2n-1-s\geq n$ элементов.  По результату задачи \ref{D(Z_n)},
$T_1$содержит нуль-подпоследовательность. Обозначим ее $T_2$ и пусть она состоит из
$t_2$ элементов, $2\leq t_2\leq n$. Мы можем считать, что последовательность
$T_2$ выбрана так, что ее длина~--- максимально возможная (среди последовательностей
длины не превосходящей~$n$). Если бы оказалось, что $s+t_2\geq n$, то,
добавив к $T_2$ несколько нулей, мы получили бы
требуемую нуль-подпоследовательность длины~$n$.
Следовательно, мы можем считать, что $s+t_2<n$. Кроме того, можно считать, что
$t_2\leq [n/2]$ (иначе нам опять поможет запас из $[n/2]$ нулей).

Теперь легко получить противоречие: так как $s+t_2<n$, то в $T_1\setminus T_2$
опять содержится не менее $n$ элементов и можно выбрать нуль-подпоследовательность $T_3$
из $t_3$ элементов, причем $t_3\leq t_2$ в силу максимальности $T_2$.
Но так как при этом $t_2\leq [n/2]$, мы получаем, что $t_3+t_2\leq n$, что
противоречит максимальности $T_2$.
\end{solution}

\begin{solution}
\answer: $\frac1p( C_{2p}^p-2)+2$.
Задача с IMO1995.
Мы цитируем решение по \cite{MMO}. Разобьем все $p$-элементные подмножества множества
$\{1,2,\dots, 2p\}$, кроме $B\!=\!\{1,2,\dots,p\}$ и $C\!=\!\{p+1,\dots,2p\}$,
на группы по $p$ штук. Для каждого множества $X=\{x_1,\dots,x_k\}\subset B$
обозначим через $X+\ell$ множество $\{x_1+\ell,\dots,x_k+\ell\}$, где все сложения
выполняются по модулю $p$ (т.\,е.\ $X+\ell$~--- это просто
циклический сдвиг множества $X$). В одну группу с подмножеством $A$ поместим
следующие подмножества:
$$
A_0=A; \
A_1=\bigl((A\cap B)+1\bigr)\cup(A\cap C); \
A_2=\bigl((A\cap B)+2\bigr)\cup(A\cap C); \ \dots,
A_{p-1}=\bigl((A\cap B)+p-1\bigr)\cup(A\cap C)\,.
$$
Если $|A\cap B|=q$, $0<q<p$, то суммы чисел множеств $A_i$ и $A_j$ отличаются
на $(j-i)q$. Таким образом, все суммы чисел множеств, попавших в одну группу,
попарно различны. Следовательно, ровно в одном из множеств каждой группы сумма чисел делится
на~$p$.
\end{solution}

\begin{solution}
%Будем считать, что нумерация чисел $a_i$ циклическая.
%Для каждого $k$, $1\leq k\leq n$, рассмотрим набор из $n$ чисел:
%\begin{align*}
%a_k+a_{k+1}+\ldots+a_n+a_1+\ldots+a_{k-1}&\,,\\
%    a_{k+1}+\ldots+a_n+a_1+\ldots+a_{k-1}&\,,\\
%    \dots \qquad \dots \qquad \dots\qquad& \\
%a_{k-2}+a_{k-1}&\,,\\
%a_{k-1}&\,,
%\end{align*}
\end{solution}


\refstepcounter{subsection}

\begin{solution}
Элементы $\mathbb Z_2^d$~--- это всевозможные наборы из $d$ нулей и единиц
с операцией покоординатного сложения по модулю 2. Всего имеется $2^d$ таких наборов,
причем сумма любых двух наборов не равна нулевому набору. Если же взять $2^d+1$
набор, то среди них найдутся два одинаковых. Их сумма равна нулевому набору.
\end{solution}

\begin{solution}
Оценка сверху следует из того, что в последовательности, состоящей из
$(n-1)n^d +1$ элементов множества $\mathbb Z_n^d$, какой-то элемент встречается
$n$ раз. Оценка снизу достигается на следующем примере: рассмотрим $2^n$
наборов вида $(m_1, \dots, m_d)$, где все числа $m_i$~--- это нули или единицы.
Построим последовательность, которая содержит каждый такой набор ровно $n-1$ раз.
Очевидно, никакие $n$ элементов построенной последовательности не дают в сумме 0.
\end{solution}


\begin{solution}
Пусть дана последовательность, состоящая из $s(n_1, d) + n_1(s(n_2, d)-1)$ чисел.
Пользуясь определением чисел $s(n,d)$, будем последовательно выбирать из нее
группы по $n_1$ чисел с суммой, кратной $n_1$. Мы сумеем набрать таким образом
$s(n_2,d)$ групп. Поделим сумму чисел каждой группы на $n_1$. У нас получится
последовательность из $s(n_2,d)$ чисел. Осталось выбрать из нее $n_2$ чисел с суммой,
делящейся на $n_2$.
\end{solution}


\begin{solution}
Следующий пример девяти элементов $\mathbb Z_3^3$, никакие три из которых не дают в сумме 0,
приведен в \cite{Harborth}:
$$
\begin{pmatrix} 2\\1\\2\end{pmatrix}, \
\begin{pmatrix} 0\\0\\0\end{pmatrix}, \
\begin{pmatrix} 0\\0\\1\end{pmatrix}, \
\begin{pmatrix} 0\\1\\0\end{pmatrix}, \
\begin{pmatrix} 0\\1\\1\end{pmatrix}, \
\begin{pmatrix} 1\\0\\0\end{pmatrix}, \
\begin{pmatrix} 1\\0\\1\end{pmatrix}, \
\begin{pmatrix} 1\\1\\2\end{pmatrix}, \
\begin{pmatrix} 1\\2\\2\end{pmatrix}.
$$
Более того, взяв каждый вектор в двух экземплярах, получаем пример последовательности
из 18 элементов, никакие три из которых также не дают в сумме 0.
\end{solution}


\begin{solution}
См. \cite{GaoThangadurai}.
При нечетных $n$ следующее подмножество $\mathbb Z_n^2$, состоящее из $2n-2$ элементов,
не содержит подмножества из $n$ элементов с нулевой суммой:
$$
(0,0), (0,1), \dots, (0,n-2), \ (1,1), (1,2), \dots, (1, n-1)\,.
$$
При четных $n$ есть аналогичное подмножество $\mathbb Z_n^2$, состоящее из $2n$ элементов,
не содержащее подмножеств из $n$ элементов с нулевой суммой:
$$
(0,0), (0,1), \dots, (0,n-1), \ (1,0), (1,2), \dots, (1, n-1)\,.
$$
\end{solution}

\begin{solution}
Это доказано в \cite{GaoThangadurai}, но как то уж очень муторно.
\end{solution}

\begin{solution}
Неравенство $s(2^m, d) \geq (2^m-1)2^d+1$~--- это частный случай утверждения
\ref{s_nerav}.
Противоположное неравенство $s(2^m, d) \leq (2^m-1)2^d+1$ легко доказывается по индукции.
База $m=1$ --- это утверждение задачи \ref{s_power2}, а переход обосновывается
с помощью \ref{s_multipl}.
\end{solution}

\begin{solution}
Нетрудно видеть, что $s(2,2)=5$. Читатель, конечно, сможет перебрать варианты
и убедиться, что $s(3,2)=9$. Теперь с помощью неравенства
задачи~\ref{s_multipl} сразу получаем, что $s(n,2)=4n-3$, если число $n$ имеет вид
$2^k 3^\ell$. Так как $432 = 27\cdot 16$, то $s(432, 2) =4\cdot 432-3 = 1725$.
\end{solution}




%\clearpage
\refstepcounter{subsection}


\begin{solution}
Следующее рассуждение, принадлежащее Дэвенпорту \cite{Davenport},
мы цитируем по \cite{AlonDubiner}.

Случай $|A|+|B|> p$ достаточно прост, мы его оставляем читателю.
Будем рассматривать множества с дополнительным условием
$|A|+|B|\leq p$.
Допустим, что для некоторых множеств $A$ и $B$ верно противоположное
неравенство
$$
|A+B|\leq |A|+|B|-1\,.
\eqno{(*)}
$$
Среди всех таких пар множеств выберем пары с наименьшим
возможным значением величины $|A+B|$, а~среди таких пар~--- ту, у которой
меньшее множество $A$ содержит меньше всего элементов. Можно считать, что
$|A|\geq 2$.

Заметим, что если сдвинуть одно из множеств, т.\,е., например, вместо
множества $A$ рассмотреть множество $A+c$ при некотором
$c\in{\mathbb Z}_p$, то старое множество $A+B$ также сдвинется на~$c$.
В частности, количество элементов в множестве $A+B$  не изменится.

Сдвинем множество $A$ таким образом, чтобы множества $A$ и $B$ пересекались,
но при этом $A\not\subset B$. Это можно сделать по следующей причине.
Допустим, что любой сдвиг $A$ приводит к~тому, что если сдвинутое множество
$A$ пересекается с $B$, то оно содержится в $B$. Рассмотрим любой
из таких случаев взаиморасположения множеств. Пусть $a$, $b\in A\cap B$ и
$A\subset B$.  Сдвинем множество $A$ на $b-a$. Точка $a$ перейдет в $b$,
и~следовательно, пресечение множеств не исчезнет. Если по-прежнему
$A\subset B$, то образ точки $b$ принадлежит обоим множествам.
Рассмотрим еще один сдвиг на $b-a$ и т.\,д.
Если каждый раз сдвинутое множество $A$ будет содержаться в $B$,
мы установим, что все точки
$$
a, \ b, \ b + (b-a), \ b+2(b-a), \ b+3(b-a), \ \dots
$$
(все арифметические операции по модулю $p$) принадлежат множеству $B$.
Это невозможно, покольку множество этих точек совпадает с ${\mathbb Z}_p$.

Итак, мы можем сдвинуть множество $A$ таким образом, чтобы множества
$A$ и $B$ пересекались, но при этом $A\not\subset B$. Заметим, что тогда
для множеств $A_1=A\cap B$ и $B_1=A\cup B$ верно, что
$A_1+B_1 \subset A+B$, т.\,е.\
$|A_1+B_1|\leq |A+B|$; кроме того, $|A_1|+|B_1|=|A|+|B|$.
Таким образом, пара множеств $A_1$, $B_1$ удовлетворяет неравенству $(*)$.
Но при этом $|A_1|<|A|$, что противоречит минимальности множества $A$.
\end{solution}

\begin{solution}
Сначала сведем утверждение к случаю, когда $n=p$~--- простое число.
Индукция по количеству простых множителей. Пусть $n=pm$, где $p$~--- простое
и пусть $a_1$, $a_2$, \dots, $a_{2n-1}$~--- данная последовательность.
По утверждению задачи для простых $p$, мы можем последовательно выбирать
наборы из $p$ чисел, сумма которых делится на $p$.
Так мы сумеем выбрать $2m-1$ различных наборов $I_1$, $I_2$, \dots, $I_{2m-1}$.
(Действительно, если $2m-2$ набора уже выбрано, то количество оставшихся элементов не меньше
$2pm-1-(2m-2)p=2p-1$.)
Для каждого $i$, $1\leq i\leq 2m-1$, положим $a_i'=\frac1p\sum_{j\in I_i} a_j$.
По предположению индукции эта последовательность содержит нуль-подпоследовательность
из $m$ элементов. Это дает нам требуемое подмножество из $pm$ элементов с суммой,
делящейся на~$n$.

Теперь докажем утверждение для простых $p$.
Пронумеруем элементы последовательности в порядке возрастания:
$0\leq a_1 \leq a_2 \leq\ldots\leq a_{2p-1}$.
Если $a_i=a_{i+p-1}$ при каком-нибудь $i$, то $a_i+a_{i+1}+\ldots+a_{i+p-1}=pa_i=0$
(в ${\mathbb Z}_p$) и мы нашли то, что требуется. В противном случае
пусть $a_i=\{a_i, a_{i+p-1}\}$ при $1\leq i\leq p-1$. Последовательно применяя
теорему Коши\,--\,Дэвенпорта (или один раз~--- утверждение задачи \ref{KD_iterated}),
заключаем, что $|A_1+A_2+\ldots+A_{p-1}|=p$. Следовательно, каждый элемент
${\mathbb Z}_p$ представим в виде суммы в $p-1$ слагаемых, выбранных из первых $2p-2$
членов нашей последовательности. Тогда $-a_{2p-1}$ также можно представить в~таком виде,
и это дает нам требуемую нуль-подпоследовательность.

Мы почерпнули это решение в \cite{AlonDubiner}. Там же приведено еще несколько
решений (менее элементарных).

\bigskip
Вот еще одно рассуждение из \cite{Thangadurai}.
Фактически это модификация решения \ref{N-C_Ext_lemma},
где вместо неравенства $s\geq [n/2]$ мы пользуемся
утверждением задачи \ref{N-C_EXT}
(а в ее решении используется теорема Кемпермана\,--\,Шерка).

Пусть $S$~--- данная последовательность длины $2n-1$. И пусть $a$~--- элемент, содержащийся
в этой последовательности с наибольшей кратностью, обозначим ее $s$. Если $s\geq n$,
доказывать нечего. Пусть $s\leq n-1$.

%При $[n/2]\leq s\leq n-1$ получаем утверждение
%задачи~\ref{N-C_Ext_lemma}. Разберем остающийся случай $2\leq s\leq[n/2]-1$.

Рассмотрим сдвинутую последовательность $S-a$, в ней 0 повторяется $s$ раз.
Пусть $T_1$~--- подпоследовательность $S$, состоящая из всех ненулевых элементов $S$;
в ней содержится не меньше $2n-1-s\geq n$ элементов.
По результату задачи \ref{D(Z_n)},
$T_1$содержит нуль-подпоследовательность. Обозначим ее $T_2$ и пусть она состоит
из~$t_2$ элементов, $2\leq t_2\leq n$. Мы можем считать, что последовательность
$T_2$ выбрана так, что ее длина~--- максимально возможная (среди последовательностей
длины не превосходящей~$n$).

Заметим, что если $s+t_2 \geq n$, то мы бы сразу получили требуемую нуль-подпоследовательность,
добавив к $T_2$ несколько нулей. Значит, $s+t_2< n$. Рассмотрим последовательность
$T_3=T_1\setminus T_2$, ее длина равна
$$
2n-1-s-t_2\geq 2n-1 - (n-1) =n\,.
$$
При этом кратности элементов, входящих в $T_3$, не превосходят $s$. По утверждению задачи
\ref{N-C_EXT} (при $d=1$) мы можем выбрать нуль-подпоследовательность $T_4$, длина которой
не больше $s$. Тогда неравенство $s+t_2< n$ противоречит максимальности
последовательности $T_2$, поскольку нуль-последовательность $T_2\cup T_4$ содержит $s+t_2$
элементов.
\end{solution}


\begin{solution}
Понятно.
\end{solution}

\begin{solution}
Мы взяли это утверждение в \cite{GaoThangadurai}.
Утверждение очевидно, если какой-то элемент встречается в $S$ $p$ раз.
Пусть никакой элемент не входит в~$S$ больше чем $p-1$ раз.
Положим $A_1=\{a_1, \dots, a_s\}$, а остальные элементы $S$ распределим по $p-1$ множествам
$A_2$, \dots, $A_{p-1}$. По теореме Коши\,--\,Дэвенпорта
$$
|A_1+\ldots+A_p|\geq \min\{p, \sum|A_i| -p+1\}=\min\{p, 2p-1-p+1\}=p\,.
$$
Следовательно, $A_1+\ldots+A_p=\mathbb Z_p$, откуда и следует требуемое утверждение.
\end{solution}


\begin{solution}
Композиция двух симметрий~--- поворот. А поворот 12-угольника мы можем интерпретировать как
элемент группы ${\mathbb Z}_{12}$. Разбиваем все 47 преобразований на пары из
двух симметрий или двух поворотов (преобразование, не вписавшееся в эту схему по четности,
нам не потребуется). Фиксируем порядок в каждой паре. Пар~---
23, композиция внутри каждой пары~--- поворот, далее применяем теорему
Эрдеша\,-- Гинзбурга\,--\,Зива для $n=12$ (или утверждение задачи \ref{EGZ12}).
\end{solution}

\begin{solution}
Распределим элементы $T$ по $h$ непересекающимся множествам $A_1$, $A_2$, \dots, $A_h$.
Суммы не более чем по $h$ элементов из $T$ образуют множество
$A_h\cup \smash[b]{\bigcup\limits_{i=1}^{h-1}} \bigl(A_i\cup \{0\}\bigr)$.
По теореме Коши\,--\,Дэвенпорта
$$
\Bigl|A_h\cup \bigcup\limits_{i=1}^{h-1} \bigl(A_i\cup \{0\}\bigr)\Bigr|\geq
\min\bigl\{p, \ |A_1\cup\{0\}| +\ldots+|A_{h-1}\cup\{0\}| + |A_h| - h+1 \bigr\}=p\,.
$$
\end{solution}

\begin{solution}
С помощью теоремы ЭГЗ будем последовательно выбирать группы по $k$ чисел,
с суммой кратной $k$, пока не наберем $m$ чисел.
\end{solution}


\begin{solution}
%Мы почерпнули это утверждение в \cite{HalberstamRoth}, гл.~1, теорема 15'.
Это утверждение доказано в \cite{MoserScherk}.
Как и в доказательстве теоремы Коши\,--\,Дэвен\-пор\-та,
можно считать, что $|A|+|B|-1\leq n$. Среди всех пар $A$, $B$, удовлетворяющих
условию, выберем такую, в которой величина $|A|$ наименьшая.
Заметим, что существует элемент $b^*\in B$, такой что $b^*+A\not\subset B$.
Действительно, если бы это было не так, то для ненулевого элемента $a_1\in A$ мы бы имели
равенство $a_1+B=B$ и, в частности, так как $0\in B$, мы бы нашли нетривиальное представление
$a_1+b_i=0$, что противоречит условию.

Воспользуемся элементом $b^*$, чтобы перестроить имеющуюся пару множеств. А именно,
пусть $A^*$~--- это множество всех таких $a\in A$, для которых $a+b^*\notin B$.
Положим $A'=A\setminus A^*$, $B'=B\cup (b^*+A^*)$.

Ясно, что $0\notin A^*$, поэтому по-прежнему $0\in A'$. Очевидно, $0\in B'$.

Уравнение $a'+b'=0$ для множеств $A'$, $B'$ имеет только тривиальное решение.
Действительно, если нашлось нетривиальное решение $a_1+(b^*+a_2)=0$,
где $a_1\in A'$, $a_2\in A^*$, то тогда и $(a_1+b^*)+a_2=0$,
что невозможно, так как $a_1+b^* \in B$, $a_2\in A$, $a_2\ne0$, а нетривиальных разложений
нуля для множеств $A$ и $B$ не существует.

Наконец, отметим, что $A'+B'\subset A+B$.

Итак, мы построили новую пару множеств $A'$, $B'$, удовлетворяющую условию задачи, но при этом
${|A'|<|A|}$. Противоречие.
\end{solution}

\begin{solution}
Мы почерпнули это утверждение в \cite{HongBingYu}.
Заметим, что при сдвиге последовательности $k$-суммы не меняются, поэтому можно считать, что
0 является элементом, входящим в последовательность $A$ с наибольшей кратностью.
Обозначим через $L$ подпоследовательность $A$, состоящую из всех нулей; пусть $\ell$~---
количество элементов в~$L$. Ясно, что $\ell\leq k-1$. Среди всех подпоследовательностей
$A\setminus L$ длины не более $k-1$ выберем самую длинную нуль-подпоследовательность $S$,
обозначим ее длину через $s$ (возможно, $S=\varnothing$ и $s=0$).
Тогда $\ell+s\leq k-1$, так как в противном случае,
дополнив $S$ нескольким нулями, мы получили бы нуль-подпосле\-до\-ва\-тельность из $k$ элементов.

Итак, в последовательности $A\setminus(L\cup S)$ не меньше $r+1$ элементов.
Возьмем любые $r$ из них, пусть они образуют последовательность $T$.
Пусть $h$~--- наибольшая кратность элемента в $T$. Тогда $h\leq \ell$
по определению числа~$\ell$. Разобьем $T$ в объединение $h$ непересекающихся множеств
(не последовательностей!) $X_1$, \dots, $X_h$ и~положим $X_i'=X_i\cup\{0\}$ ($i=1$, \dots, $h$).
Заметим теперь, что $0\notin T$ и что при $1<j\leq h$ никакие $j$ элементов $T$  не дают в сумме~0.
Действительно, так как $h+s\leq \ell+s\leq k-1$, то если бы какие-то $j$ элементов из $T$ давали
бы в сумме 0, мы могли бы объединить эти элементы с $S$ и получили бы более длинную
нуль-подпоследовательность, что противоречит определению $S$.
Таким образом, мы проверили, что к набору $X_1'$,~\dots, $X_h'$ можно последовательно применять
теорему Кемпермана\,--\,Шерка, что дает нам неравенство
$$
|X_1'+\ldots+X_h'| \geq |X_1'|+\ldots+|X_h'|+1=r+1\,.
$$
Иными словами, если к последовательности $T$ добавить $h$ нулей из $L$, то полученная
последовательность имеет не меньше $r+1$ $h$-сумм.
Добавив оставшиеся элементы $A$ (а их в точности $k+r-(r+h)$) к каждой из этих $h$-сумм,
мы получим $r+1$ различных $k$-сумм.

Теорема ЭГЗ является частным случаем доказанного утверждения при $r=k-1$.
Рассуждение верно для произвольной конечной абелевой группы.
\end{solution}

\begin{solution}
Результат следует из теоремы Кемпермана\,--\,Шерка \ref{Scherk}.
Действительно, если $0\in S$, то доказывать нечего.
Пусть $0\notin S$. Распределим элементы $S$ по $h$ непересекающимся множествам
$B_1$, \dots, $B_h$ и положим $A_i=0\cup B_i$ при $1\leq i\leq h-1$ .
Если уравнение $a_1+a_2+\ldots+a_{h-1}=0$ имеет нетривиальное решение, то доказывать
опять нечего. В противном случае
$$
|A_1+A_2+\ldots+A_{h-1}|\geq \Bigl(\sum_{i=1}^{h-1} |A_i|\Bigr)-(h-1)+1 =
(n+h-1-|B_h|)-(h-1)+1=n+1-|B_h|.
$$
Это значит, что какое-то из чисел вида $(-b)$, где $b\in B_h$ совпадает с некоторой суммой вида
$a_1+a_2+\ldots+a_{h-1}$, $a_i\in A_i$. Тогда $a_1$, $a_2$, \dots, $a_{h-1}$, $b$~---
искомая нуль-подпоследовательность.
\end{solution}

\begin{solution}
Мы почерпнули это утверждение в \cite{GaoThangadurai}.
При сдвиге последовательности суммы по $p$ элементов не меняются.
Следовательно, мы можем считать, что максимальную кратность $h$ имеет элемент~0.
Пусть $T$~--- последовательность, составленная из остальных элементов, $s$~--- ее сумма.
Допустим, что утверждение задачи неверно и $h\leq p-k$. Тогда $|T|\geq p$. Так как при
этом $T$ не содержит нулей, то по утверждению задачи~\ref{lemma_Gao} $s$~можно представить в
виде суммы не более чем $h$ элементов из $T$. Пусть $Q$~--- последовательность,
состоящая из этих $h$ элементов. Положим $T_1=T\setminus Q$. Ясно, что сумма элементов $T_1$
равна~0 и~$p-h\leq |T_1|\leq |T|-1$. Если бы оказалось, что $|T_1|\leq p$,
то мы бы легко составили нуль-подпоследовательность длины~$p$, добавив к $T_1$ несколько нулей.
Следовательно, $|T_1|\geq p$. Тогда опять применим утверждение задачи~\ref{lemma_Gao}
и построим подпоследовательность $Q_1$ не более чем из $h$ элементов, сумма которой равна~0
(=~сумме элементов $T_1$). Положим $T_2=T_1\setminus Q_1$. Опять имеем, что сумма
элементов $T_2$ равна нулю и~$p-h\leq |T_2|\leq |T_1|-1$. Продолжая дальше в том же духе, мы
все-таки сумеем построить нуль-подпоследовательность длины~$p$. Противоречие.
\end{solution}


\begin{solution}
%Пусть $B_1$, $B_2$, \dots, $B_h$~--- набор некоторых подмножеств $\mathbb Z_n^d$.
%Положим $m_i=|B_i|$. Пусть оказалось, что $\sum_{i=1}^h m_i \geq n^d$.
%Тогда можно выбрать непустое множество элементов $b_j$~--- не более чем по одному
%из каждого множества~--- так, что сумма выбранных элементов равна $0\in \mathbb Z_n^d$.
Утверждение эквивалентно утверждению задачи \ref{N-C_EXT}.
\end{solution}

\begin{solution}
Доказано в \cite{BoveyErdosNiven}.
Допустим, утверждение неверно и каждый элемент входит в $S$ с кратностью не более $2k-n$.

Заметим сначала, что если $a$ и $b\in S$, причем $a\ne b$,
то $a$, $b$ и $a+b$~--- это три различных элемента $S$.
(Это следует из того, что $S$ не содержит нуль-подпоследовательностей.)

\medskip
Лемма. Если $a$, $b$, $c\in S$~--- три попарно различных элемента,
то среди сумм всевозможных подмножеств множества $\{a, b, c\}$
имеется не меньше 6 различных элементов $\mathbb Z_n$.

Доказательство. Рассмотрим три  равенства в $\mathbb Z_n$:
$$
a+b=c, \quad a+c=b, \quad b+c=a\,.
$$
Пусть выполнены хотя бы два из этих равенств (например, первое и второе).
Складывая их, мы приходим к равенству $2a=0$.
Поскольку $n$ нечетно, отсюда получаем, что $a=0$, что невозможно,
так как $S$ не содержит нуль-подпоследовательностей, в том числе, одноэлементных.

Если же наоборот, по крайней мере два из равенств НЕ выполнены (пусть это опять
первое и второе равенство), то мы легко можем построить 6 несовпадающих сумм:
$a$, $b$, $c$, $a+b$, $a+c$, $a+b+c$. Действительно, если, скажем, оказалось, что
$a+b+c=a$, то мы сразу получаем, что $b+c=0$, что невозможно.
\medskip

Будем последовательно выбирать из $S$ тройки попарно различных элементов.
Допустим, что нам удалось выбрать $j$ таких троек $A_1$, $A_2$, \dots, $A_j$,
после чего в последовательности осталось не более двух различных элементов:
$a$ (с кратностью $\lambda$) и $b\ne a$ (с~кратностью~$\mu$), $\lambda \geq \mu\geq 0$.
Очевидно, $\lambda\leq 2k-n$ в силу сделанного допущения.
Мы можем сформировать из оставшихся элементов $\mu$ двухэлементных множеств
$A_{j+1}$, \dots, $A_{j+\mu}$ и $\lambda-\mu$
одноэлементных множеств $A_{j+\mu+1}$, \dots, $A_{j+\lambda}$.

Мы разбили последовательность $S$ в объединение $j+\lambda$ множеств $A_i$.
Следовательно,
$$
k=3j+\lambda+\mu\,.
$$
Для каждого множества $A_i$ обозначим через $\Sigma A_i$ множество сумм всевозможных
подмножеств $A_i$.
По лемме $|\Sigma A_i|\geq 6$ для трехэлементных множеств. Ясно, что
$|\Sigma A_i|=3$ для двухэлементных множеств и  $|\Sigma A_i|=1$ для одноэлементных.
Следовательно,
$$
\sum_{i=1}^{j+\lambda} |\Sigma A_i| = 6j + 3\mu + (\lambda-\mu) =
2(3j + \mu + \lambda) - \lambda = 2k-\lambda \geq n\,.
$$
Осталось применить утверждение задачи \ref{N-C_EXT_reformulation}.

Для четных $n$ утверждение задачи также верно. В доказательство требуется
внести технические поправки, связанные с тем, что в последовательности $S$, возможно,
присутствует число $n/2$ с кратностью не больше~1.
\end{solution}


\begin{solution}
Утверждение сразу следует из задачи \ref{N-C_EXT_reformulation}
для набора одинаковых множеств.
Мы приведем еще одно решение из \cite{Alon}, похожее
на \ref{sums1}. Допустим, что утверждение задачи неверно.

Пусть $A(i)$~--- множество всевозможных сумм вида $a_1+a_2+\ldots+a_r$, где $1\leq r\leq i$
и элементы $a_j\in A$ не обязательно различны. Докажем индукцией по $i$,
что $|A(i)|\geq i\cdot |A|$. При $i=1$ это утверждение очевидно.

Предположим, оно верно при всех $i<k$. Пусть $B=A(i)\cup \{0\}$, $C=A\cup \{0\}$.
По предположению, $0\notin A(i)$, следовательно, $|B|=|A(i)|+1$, $|C|=|A|+1$.
Кроме того, если $0=b+c$ для некоторых $b\in B$, $c\in C$, то $b=c=0$, так как
иначе $0\in A(i+1)$, что противоречит нашему предположению. По теореме
Кемпермана\,--\,Шерка \ref{Scherk}, $|B+C|\geq |B|+|C|-1=|A(i)|+|A|+1$.
А поскольку $B+C=A(i+1)\cup 0$, мы получаем, что $|A(i+1)|\geq (i+1)\cdot |A|$,
что и требовалось.

В частности, $A(k)\geq k|A|\geq n^d$, поэтому $0\in A(k)$. Полученное противоречие
и доказывает утверждение задачи.
\end{solution}


\begin{solution}
Похоже на \ref{G-T_lemma}.
Пусть дан набор из $2n-1$ элементов $\mathbb Z_n$, имеющий единственную
нуль-подпоследова\-тель\-ность. Удалим из него любой элемент, входящий в эту
нуль-подпоследовательность.
Тогда оставшийся набор $S$ из $2n-2$ элементов вообще не содержит
нуль-подпоследовательностей. Пусть $a$~--- элемент $S$, имеющий наибольшую кратность,
обозначим ее $s$.
Рассмотрим сдвинутую последовательность $S-a$, в ней 0 повторяется $s$ раз.
Пусть $T_1$~--- подпоследовательность $S$, состоящая из всех ненулевых элементов $S$.

Ясно, что $s<n$. Если $s\leq n-2$, добавим к последовательности $S-a$ еще один нулевой
элемент. Получится последовательность длины $2n-1$, не содержащая нуль-подпоследовательностей.
По теореме ЭГЗ это невозможно.

Таким образом, $s=n-1$. Тогда последовательность $T_1$ имеет длину $n-1$
и не содержит нуль-подпосле\-до\-ва\-тельностей.
По утверждению задачи \ref{D(Z_n)-zerofree}, последовательность $T_1$ состоит из
$n-1$ копии некоторого элемента~$c$.

Итак, последовательность $S$ содержит всего лишь из два различных элемента,
каждый c к кратностью $n-1$. Нетрудно сообразить, что отброшенный в самом начале
элемент равен одному из них.
\end{solution}


\begin{solution}
Это частный случай еще одной теоремы Эрдеша и Эгглтона \cite{EggletonErdos}.
Пусть $f(k)$ обозначает наименьшее возможное число элементов $\mathbb Z_n^d$,
которые представимы в виде сумм подпоследовательностей какой-либо последовательности $S$,
состоящей из $k$ элементов и не содержащей нуль-подпоследовательностей.
Нам нужно доказать, что $f(k)\geq 2k-1$.
Докажем это индукцией по $k$.

Очевидно, $f(1)=1$.

Допустим, что $f(k)\geq 2k-1$ при некотором $k$.
Рассмотрим последовательность $S=(a_1, a_2, \dots, a_{k+1})$, не содержащую
нуль-подпоследовательностей и проверим, что в виде суммы элементов $S$ можно представить
не менее $2k+1$ элементов.

Случай 1. Какой-то из элементов $S$ не представим в виде суммы подпоследовательности
элементов $S$. Пусть это $a_{k+1}$. По предположению индукции множество всевозможных сумм элементов
$S\setminus\{a_{k+1}\}$ состоит не менее чем из $2k-1$ элементов, и при этом в него не входят
ни $a_{k+1}$, ни $\sum_{i=1}^{k+1} a_i$ (поскольку иначе разность этой суммы и предыдущей
определяла бы нуль-подпоследовательность). Таким образом, с помощью $S$ можно представить
не менее $2k+1$ элементов.

Случай 2. Каждый элемент $S$ представим в виде суммы некоторых из остальных $k$ элементов.
Напомним, что при этом $S$ не содержит нуль-подпоследовательностей. Тогда множества
$A=B=\{0, a_1, a_2, \dots, a_{k+1}\}$ удовлетворяют условию теоремы Кемпермана\,--\,Шерка.
Следовательно, $|A|+|B|\geq 2k+3$. При этом всякий элемент вида $2a_j$ представим в виде
``$a_j\,+$ сумма некоторых элементов $S$, не равных $a_j$''. Таким образом,
каж\-дый ненулевой элемент множества $A+B$ представим в виде суммы элементов из $S$.
Значит, этих элементов даже не меньше чем $2k+2$.
\end{solution}

\begin{solution}
Мы взяли это утверждение в \cite{GaoThangadurai}.
Поскольку речь опять идет о $p$-суммах, последовательности можно сдвигать.
Тогда можно считать, что в последовательность $a_n$ один раз входит элемент 0
и по два раза~--- все остальные элементы $\mathbb Z_p$. Тогда
$$
(a_n) = (0,z), \ (1, x_1), (1, y_1), \  (2, x_2), (2, y_2), \ \dots, \
(p-1, x_{p-1}), (p-1, y_{p-1})\,,
$$
где $x_i\ne y_i$ при всех $i$ (так как это разные элементы множества $M$).
Заметим, что $0+1+2+\ldots+(p-1) = 0$ в~$\mathbb Z_p$.
Положим $C_i=\{x_i, y_i\}$. По теореме Коши\,--\,Дэвенпорта \ref{KD_iterated}
$$
|C_1+C_2+\ldots+C_{p-1}|\geq 2(p-1) - (p-1) +1 = p\,.
$$
Это значит, что нулевой элемент может быть записан в виде $0=\sum_{i=0}^{p-1} z_i$,
где $z_0=z$, а при всех остальных $i$ элемент $z_i$~--- это или $x_i$ или $y_i$.
Это разложение нуля и определяет требуемую нуль-подпоследовательность в~$M$.
\end{solution}


\begin{solution}
Это результат Олсона \cite{OlsonNT2}.
То, что искомая величина не меньше $d(p-1)$, показывает простой пример:
возьмем $d$ ``базисных'' векторов $e_i=(0,0,\dots, 0,1,0,\dots,0)$
(единица на $i$-м месте), $1\leq i \leq d$, причем каждый вектор возьмем с
кратностью $p-1$.

А вот в другу-у-у-ю-у сторону ...
\end{solution}


\clearpage


\refstepcounter{subsection}

\begin{solution}
\end{solution}

\begin{solution}
\end{solution}

\begin{solution}
В \cite{AlonDubiner} этот факт доказан алгебраически.
\end{solution}


\clearpage
\begin{thebibliography}{99}

\bibitem{MMO}
Школьные олимпиады. Международные математические олимпиады /
Сост. А.\,А. Фомин, Г.\,М. Кузнецова. М: Дрофа, 1998.

\bibitem{Alon}
Alon N. Subset sums /\!/
J. Number Theory. 1987. Vol. 27. P.~196--205.

\bibitem{AlonDubiner}
Alon N., Dubiner M. Zero-sum sets of prescribed size.
In: Combinatorcs, Paul Erd\H os is Eighty.
Bolyai Society, Math. Studies, Keszthely. Hungary, 1993. P.~33--50.

\bibitem{BoveyErdosNiven}
Bovey J.\,D., Erd\H os P., Niven I.
Conditions for a zero sum modulo $n$ /\!/
Canad. Math. Bull. 1975. Vol. 18. №~1. P.~27--29.

\bibitem{Davenport}
Davenport H. On the addition of residue classes /\!/
J. London Math. Soc. 1935. Vol. 10. P.~30--32.

\bibitem{EggletonErdos}
Eggleton R.\,B., Erd\H os P. Two combinatorial problems in group theory /\!/
Acta Arithmetica. 1972. Vol 19. P.~111-116.

\bibitem{GaoThangadurai}
Gao W.D., Thangadurai R. A variant of Kemnitz conjecture /\!/
J. of Comb. Theory. Ser. A. 2004. Vol. 107. P.~69--86.

\bibitem{HalberstamRoth}
Halberstam H., Roth K.F., Sequences. New York, Heidelberg, Berlin: Springer-Verlag, 1966.

\bibitem{Harborth}
Harborth H. Ein Extremalproblem f\" ur Gitterpunkte /\!/
J. Reine Angew. Math. 1973. Vol. 262/263. P.~356-360.

\bibitem{HongBingYu}
Hong Bing Yu, A simple proof of a theorem of Bollob\'as and Leader /\!/
Proc. of the AMS. 2002. Vol.~131. №\,9. P.~2639--2640.

\bibitem{MoserScherk}
Moser L., Scherk P.  Distinct elements in a set of sums /\!/
Amer. Math. Monthly. 1955. Vol. 62. P.~46--47.

\bibitem{OlsonNT2}
Olson J.E., A combinatorial problem on finite Abelian groups, II /\!/
J. Number Theory. 1969. Vol. 1. P.~195--199.

\bibitem{Olson}
Olson J.E., An addition theorem modulo $p$ /\!/ J. Comb. Theory.  1968. Vol. 5. P.~42--52.

\bibitem{Thangadurai}
Thangadurai R.  Non-canonical extensions of Erd\H os--Ginzburg--Ziv theorem /\!/
Integers: Electronic J. of Comb. Number Theory. 2002. V.~2.

\end{thebibliography}

\end{document}

Алон пишет, что если есть 6n-5 элементов группы Z_n х Z_n, то из них можно
выбрать n штук с нулевой суммой (и сообщает гипотезу, что это должно быть
верно для 4n-3 элементов; Ронья умеет доказывать это для 4n-2 элементов и
простого p).

Еще он сообщает факт попроще: то же самое для простых n, но рассматривают
3n элементов, сумма которых равна нулю.

Zhi-Wei Sun сообщает формулу Gao: в любой конечной абелевой группе из n
элементов  d=S+n-1, где d -- константа Дэвенпорта (min k, такое что из
любых k элементов можно выбрать несколько с нулевой суммой), а S -- это
min k, такое что из любых k элементов можно выбрать n штук с нулевой
суммой.
