%&latex
\documentclass[10pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{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}
\pagestyle{myheadings}

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

%\kern-\baselineskip

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

\maketitle

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


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

\smallskip
{\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}
При каком наименьшем $m$ любая последовательность из $m$
элементов ${\mathbb Z_{100}}$, содержащая ровно 4~различных элемента,
имеет нуль-подпоследовательность длины 100?
%В Тридевятом царстве в ходу были монеты в несколько копеек, четырех разных достоинств
%(сейчас уже никто не знает, каких именно). Какое наименьшее число тридевятских монет
%должен найти археолог, чтобы быть уверенным, что среди них заведомо есть ровно 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-1$ различных
(непустых) нуль-подпоследовательностей.
\end{problem}


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

\smallskip
{\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$,
$1\leq i_1<i_2< \dots< i_n\leq M$, такие что
$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 19$.
(На самом деле $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,2)=1725$.
\end{problem}


\kern-5pt

\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$.
Докажите, что
$$
\smash{
|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$ ($r\leq k-1$).
Докажите, что если 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}$\dagger$
\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}$\dagger$
\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$,
когда он состоит из $n$ экземпляров числа $a$ и $(n-1)$ экземпляров числа $b$.
\end{problem}

\begin{problem}$\dagger$
\label{ErdosEggleton}
Пусть $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}


%\clearpage
\subsection{Промежуточный финиш. Добавления}

{\bf 2.9.} Найдите $g(8,2)$ и, по возможности, $g(2^n,2)$.

\smallskip
{\bf 2.10.}
Докажите, что существует функция $f(d)$, такая что
$s(n,d)\leq f(d) n$.

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

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

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

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

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



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

\setcounter{subsection}4

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

{\smallskip\leftskip22pt\noindent
Для $p=3$, 5, 7 это доказал Кемниц~\cite{Kemnitz},
для $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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.

Случаи $n\le 5$ разбираются вручную.
Пусть есть элементы $a_1\neq a_2$.
Для любого другого элемента $a_3$ аналогично предыдущему решению
получаем, что среди элементов
$a_1$, $a_2$, $a_1+a_3$, $a_2+a_3$, $a_1+a_2+a_3$, \dots,
$a_1+\dots+a_{n-2}$ есть два одинаковых.
Это могут быть только суммы $a_1=a_2+a_3$ или $a_2=a_1+a_3$,
т.\,е.\ $a_3=\pm(a_1-a_2)$.
Итак, для любого элемента $a_3$ мы имеем равенство  $a_3=\pm(a_1-a_2)$.
Если в исходной последовательности встречаются как $a_1-a_2$,
так и $-(a_1-a_2)$, то они в сумме дают 0, что невозможно.
Значит, одновременно для всех элементов $a_3$ в полученной формуле
реализуется один и тот же знак,т.\,е.\
все элементы последовательности, кроме $a_1$ и $a_2$,
равны некоторому числу $a$. Одно из чисел $a_1$ и $a_2$ не равно $a$,
пусть это $a_1$. Тогда аналогично все числа, кроме $a_1$ и $a$,
равны между собой, т.\,е.\ есть при при $n>5$
получаем $a_2=\dots=a_{n-2}=a$, и при $a_1\neq a,2a$ получаем нулевую подпоследовательность, что невозможно.
\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: $m=197$.

Пусть последовательность длины 196 содержит числа $-1$, 2, 97 нулей и 
97 единиц,  Тогда в этой последовательности нет нуль-подпоследовательностей 
длины 100. Следовательно, $m\geq 197$.

Докажем, что $m=197$ подходит. Пусть $S$ --- последовательность из 
197 элементов, среди которых лишь четыре различных.
Пусть $a$ --- элемент максимальной кратности, обозначим его
кратность через $s$. По принципу Дирихле, $s\geq 50$.
Если $s\geq 100$, то доказывать нечего.
Вычтем $a$ из каждого элемента  последовательности, 
при этом суммы по 100 останутся неизменными. 
В полученной последовательности 0 имеет кратность $s$. 

Пусть $s\leq 96$, $T$ --- подпоследовательность из всех ненулевых 
элементов $S$. Выберем из $T$ длиннейшую подпоследовательность $U$ 
(длины не больше 100) с нулевой суммой.  
Если $|U|\geq 50$, то, дополнив ее нулями, получим требуемое. 
Если $|U|\leq 47$, то в $T\setminus U$
найдется еще подпоследовательность по \ref{D(Z_n)}. 
Эта подпоследовательность также имеет длину, не превосходящую 50, поэтому,
добавив ее к $U$, получим более длинную нуль-подпоследовательность, 
что невозможно.
Значит, $|U|=48$ или $|U|=49$. При этом, аналогично, $T\setminus U$ 
не имеет нуль-подпоследовательностей. Но тогда, по предыдущим задачам,
в $T\setminus U$ есть 97 одинаковых элементов, 
что противоречит рассматриваемому случаю.

Значит, $s\geq 97$. Если $s=98$ или $s=99$, то, аналогично, из всех ненулевых элементов нельзя выбрать нуль-подпоследовательность.
Тогда среди них не более двух различных, а всего в $S$ --- не более трех, что невозможно. Наконец, если $s=97$, то в $T$
нуль-подпоследовательность может быть только длины 2. 
Пусть ее образуют элементы $a$ и $b$. Если $a=b$, то $2a=0$, 
и $T$ содержит не более трех элементов, равных  $a$ (если бы их было 4 или
больше, мы могли бы составить более длинную нуль-подпоследовательность).
Расставив элементы $T$ в ряд так, чтобы элементы $a$ не стояли подряд, воспользуемся методом из \ref{D(Z_n)} и получим еще одну
нуль-подпоследовательность длины 2, не содержащую элементов $a$. 
Тогда наши две пары образуют нуль-подпоследовательность длины четыре. 
Если же $a\neq b$, то расставим $T$ в ряд так:
сначала все, равные $a$, потом все элементы, кроме $a$ и $b$, 
и в конце все элементы $b$. 
Тогда аналогично можно найти нуль-подпоследова\-тель\-ность длины,
большей двух.


\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$.
(При этом  $a_{52}<488$, так как иначе при помощи $a_{52}$
и нескольких единиц можно сразу получить нуль-подпоследова\-тель\-ность.)
Полагая $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}.
Будем считать, что последовательность представляет собой
объединение двух одинаковых множеств $B$ и $C$, где $B=C=\{0,1,2,\dots,p-1\}$.

Разобьем все $p$-элементные подпоследовательности нашей последовательности,
кроме $B$ и $C$, на группы по $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$.

Итак всего мы имеем $C_{2p}^p$ $p$-элементных последовательностей,
две из них (с нулевой суммой) мы отбросили, а среди остальных
лишь каждая $p$-я имеет нулевую сумму. Получается ответ $\frac1p( C_{2p}^p-2)+2$.
\end{solution}

%\clearpage

\begin{solution}
Пусть $A=(a_1, \dots, a_n)$~--- данная последовательность.
В задаче 1.1 описан способ получения нуль-подпоследовательности,
элементы которой расположены подряд в данной нумерации.
Т.е. эта подпоследовательность имеет вид
$a_i$, $a_{i+1}$, \dots, $a_j$, где $1\leq i < j\leq n$.
Последовательности такого вида будем называть интервалами.
Построив несколько нуль-подпоследовательностей, мы можем
попытаться ``перемешать'' числа, изменив их нумерацию так,
чтобы в новой нумерации ни одна из построенных подпоследовательностей
не была бы интервалом. Если это удастся, мы с помощью способа из задачи
1.1 сумеем построить еще одну нуль-подпоследовательность вида ``интервал'',
не совпадающую ни с одной из уже построенных.
Продолжая в таком духе, мы построим нужные $n-1$
непустых подпоследовательностей.

Чтобы воплотить этот план в жизнь, нам осталось доказать
следующее утверждение.

{\bf Лемма.} Пусть даны $k\leq n-2$ подпоследовательности исходной
последовательности $A$ длины $n$, каждая из которых содержит
не меньше 2 и не больше $n-1$ элементов. Тогда мы можем так
перенумеровать элементы последовательности $A$, что ни одно из
множеств в новой нумерации не будет интервалом.

{\bf Доказательство.}
Когда нам не важен порядок элементов, мы будем в этом доказательстве
наряду со словом ``последовательность'' использовать слово ``множество'',

Индукция по $n$. Базу при $n\le 4$ нетрудно получить хотя бы перебором.
Пусть утверждение доказано для какого-то значения $n\ge 4$.
Докажем его для $n+1$, т.\,е.\ проверим, что верно следующее
утверждение.

{\it Дана последовательность $B=(b_1, b_2, \dots, b_{n+1})$.
И пусть $D_1$, \dots, $D_k$~--- несколько ее подпоследовательностей,
причем $k\leq n-1$ и подпоследовательности содержат от 2 до
$n$ элементов. Тогда существует перенумерация, в которой
ни одна из подпоследовательностей $D_i$ не является интервалом.}

Так как множеств $D_i$ не больше $n-1$, то существует элемент $b_k$, содержащийся
не более чем в одном двухэлементном множестве из $D_i$; без ограничения общности,
это $b_{n+1}$. Выкинем элемент $b_{n+1}$ из исходной последовательности
и всех содержащих его подмножеств. Если существует пара $D_i$, содержащая
$b_{n+1}$, то выкинем ее. Если существует множество $D_j=\{b_1,\dots,b_n\}$, то
его также выкинем. Если нет ни того, ни другого, то выкинем произвольное множество $D_m$.

К оставшимся элементам и множествам можно применить предположение индукции, так
как все полученные множества содержат от 2 до $n-1$ элементов.
Посмотрим, в какое место полученной последовательности можно вставить $b_{n+1}$
так, чтобы все требуемые условия выполнились. Если было выброшено произвольное
множество $D_m$, то достаточно вставить $b_{n+1}$ так, чтобы элементы $D_m$
не стояли подряд
--- очевидно, это можно сделать. Иначе, если есть пара $D_i$, то
$b_{n+1}$ нельзя вставить в два места (соседних со вторым элементом пары), а
если есть множество $D_j$, то также появляются два ``запрещенных''
места --- края последовательности. Поскольку $b_{n+1}$ можно было вставить в
$n+1\ge 5$ различных мест, то хотя бы одно осталось незапрещенным.
Вставив туда $b_{n+1}$, получаем требуемую последовательность.
\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_1,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,1), \dots, (1, n-1)\,.
$$
\end{solution}

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

Заметим, что для любых целочисленных векторов $a_1$, $a_2$, $a_3$, $a_4$
выполнено тождество
$$
\frac{a_1+a_2+a_3+a_4}{4}=\frac{\frac{a_1+a_2}{2}+\frac{a_3+a_4}{2}}{2}\,.
$$
Разделим отмеченные 9 точек на 4 группы так, чтобы в каждой группе четности
обеих координат были фиксированы. В каждой группе $x_1$, $x_2$, \dots, $x_k$
вычислим значения $\frac{x_1+x_2}{2}$, $\frac{x_1+x_3}{2}$,
$\dots$, $\frac{x_1+x_k}{2}$. Получилось $k-1$
целочисленных векторов, разных как элементы $\mathbb Z_2^2$.
Рассмотрев все 4 группы, мы получим не меньше чем $9-4=5$
целых векторов. Выберем из них два вектора с совпадающими
четностями координат. Соответствующие им пары не могли быть
получены из одной группы, следовательно,  они дают искомую четверку.
\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} и левого неравенства~\ref{s_nerav} сразу получаем, что $s(n,2)=4n-3$, если число $n$ имеет вид
$2^k 3^\ell$. Так как $432 = 27\cdot 16$, то $s(432, 2) =4\cdot 432-3 = 1725$.
\end{solution}

\begin{solution}
Мы не знаем элементарного решения этой задачи.
\end{solution}

\begin{solution}
Это утверждение доказано в \cite{AlonDubiner2} неэлементарными средствами.
\end{solution}


%\clearpage
\refstepcounter{subsection}

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

Случай $|A|+|B|> p$ достаточно прост, мы его оставляем читателю.
Будем рассматривать множества с дополнительным условием
$|A|+|B|\leq p$.
Допустим, что для некоторых множеств $A$ и $B$ верно противоположное
неравенство
$$
|A+B|< |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$.


База индукции. Пусть $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$,
$A_p=\{a_{2p-1}\}$. Последовательно применяя
теорему Коши\,--\,Дэвенпорта (или один раз~--- утверждение задачи \ref{KD_iterated}),
заключаем, что $|A_1+A_2+\ldots+A_{p-1}+A_p|=p$.
Следовательно, каждый элемент ${\mathbb Z}_p$, в том числе 0,
представим в виде суммы из $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$.

Мы почерпнули это решение в \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$, но не больше $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}$ (см.~определение канонического разбиения
в~решении задачи~\ref{lemma_Gao}).
По теореме Коши\,--\,Дэвенпорта
$$
|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$.
Для этого определим $A_i$ как множество тех элементов $T$,
которые входят в $T$ с кратностью не меньше~$i$.
Такое разбиение последовательности на несколько множеств назовем
\emph{каноническим}. Отметим, что при этом множество
$A_1$ содержит все различные элементы последовательности~$T$.

Суммы не более чем по $h$ элементов из $T$ образуют множество
$A_1+ \smash{\sum\limits_{i=2}^{h}} \bigl(A_i\cup \{0\}\bigr)$.
По теореме Коши\,--\,Дэвенпорта
$$
\Bigl|A_1+ \sum\limits_{i=2}^{h} \bigl(A_i\cup \{0\}\bigr)\Bigr|\geq
\min\bigl\{p, \ |A_1|+|A_2\cup\{0\}| +\ldots+|A_{h}\cup\{0\}| - 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^d$. Среди всех пар $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.
Действительно, так как $j+s\leq 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$ (см.~задачу~\ref{lemma_Gao})
и положим $A_i=0\cup B_i$ при $1\leq i\leq h-1$.
Если уравнение $a_1+a_2+\ldots+a_{h-1}=0$ имеет нетривиальное решение
$a_1\in A_1$, \dots, $a_{h-1}\in A_{h-1}$
то доказывать
опять нечего. В противном случае
$$
|A_1+A_2+\ldots+A_{h-1}|\geq \Bigl(\sum_{i=1}^{h-1} |A_i|\Bigr)-(h-1)+1 =
(n^d+h-1-|B_h|)-(h-1)+1=n^d+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.

\medskip
Вот другое решение, к тому же пригодное для любой конечной коммутативной
группы. Пусть никакое число в последовательности $S$ не встречается более
$2k-n$ раз. Тогда последовательность можно разбить на $2k-n$ подмножеств
$A_1$, $A_2$, \dots, $A_{2k-n}$. Пусть $B_i$~--- множество сумм
всевозможных непустых подмножеств элементов из $A_i$, $1\leq i \leq 2k-n$.
По утверждению задачи \ref{ErdosEggleton} $|B_i|\geq 2|A_i|-1$.
Применим теорему Кемпермана\,--\,Шерка к набору множеств
$B_1\cup \{0\}$, \dots, $B_{2k-n-1}\cup \{0\}$
(это можно делать, поскольку нетривиальное решение уравнения
из условия теоремы сразу дало бы нам нуль-подпоследовательность в~$S$):
\begin{align*}
\bigl| (B_1\cup\{0\})+(B_2\cup\{0\})+\ldots+
(B_{2k-n-1}\cup\{0\}) \bigr| &\geq
\min\bigr\{n, 2\bigr(|A_1|+|A_2|+\!\ldots\!+|A_{2k-n-1}|\bigl) - (2k-n-1)+1\bigl\}
= \\ &=
\min\bigr\{n, 2k- 2|A_{2k-n}|-2k+n+1+1\bigl\}
= \\ &=
\min\bigr\{n, n+1-\bigl(2|A_{2k-n}|-1\bigr)\bigr\}>n-|B_{2k-n}|\,.
\end{align*}
Значит, сумма множеств в самой левой части содержит хотя бы один из
элементов множества $-B_{2k-n}$, что сразу дает нам нуль-подпоследовательность
в $S$. Это противоречит условию. Следовательно, сделанное предположение
неверно.
\end{solution}


\begin{solution}
Утверждение сразу следует из задачи \ref{N-C_EXT_reformulation}
для набора одинаковых множеств.
\end{solution}

%\clearpage

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

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

Пусть теперь $s\leq n-2$.
Тогда подпоследовательность $T_1$ содержит не меньше $n$ членов
и кратность элементов в ней не превосходит $s$.
По утверждению задачи~\ref{N-C_EXT} в $T_1$ можно выбрать
нуль-подпоследователь\-ность~$S_1$ длины~$s_1$, причем $s_1\leq s$.
Если $s+s_1\geq n$, то мы построим нуль-подпоследователь\-ность длины $n$,
дополнив подпоследовательность $S_1$ нулями из~$S_0$.
Если $s+s_1\leq n-2$, выберем из $T_2=T_1\setminus S_1$
нуль-подпоследовательность $S_2$ длины~$s_2$, $s_2\leq s$.
Далее, если $s+s_1+s_2\geq n$, то мы построим нуль-подпоследовательность
длины $n$, дополнив $S_1\cup S_2$ нулями. Если нет~---
построим новую подпоследовательность $S_3$ и т.д.
Эти построения кончатся тем, что мы либо построим-таки на очередном шаге
нуль-подпоследовательность длины $n$, либо придем к случаю, когда
построено несколько нуль-подпоследовательностей $S_1$, $S_2$, \dots,
$S_k$ и для их длин выполнено соотношение $s+s_1+s_2+\ldots+s_k=n-1$.

Если $T_{k+1}$ не содержит больше нуль-подпоследовательностей,
то по результату задачи \ref{D(Z_n)-zerofree} $T_{k+1}$
состоит из одинаковых элементов, т.\,е.\ содержит элемент
кратности~$n-1$. Это значит, что $s\geq n-1$, что противоречит условию разбираемого случая.
Если же $T_{k+1}$ содержит нуль-подпоследовательность $U$ длины, скажем,~$u$
(теперь уже не обязательно $u\leq s$), то
$s+s_1+s_2+\ldots+s_k+u \geq n$. Убирая из последовательности
$S_0\cup S_1 \cup \dots S_k\cup U$ подходящее число
последовательностей $S_i$, $1\leq i\leq k$, и несколько нулей из $S_0$,
мы все-таки построим нуль-подпоследовательность
длины $n$.

%добавим к последовательности $S-a$ еще один нулевой
%элемент. Получится последовательность длины $2n-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$ (так как $(i,x_i)$ и $(i,y_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}

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


\begin{solution}
\end{solution}

\begin{solution}
\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{AlonDubiner2}
Alon N., Dubiner M. A lattice point problem and additive number theory /\!/
Combinatorica. 1995. Vol. 15. P. 301--309.

\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{Kemnitz}
Kemnitz A.
Exremalprobleme f\" ur Gitterpunkte. Ph.D.Thesis. Technische Universit\" at
Braunschweig, 1982.

\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).

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