%&latex
\documentclass[12pt]{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}

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

\title{Sequences with zero sums}
\author{K.\, Kokhas, K.\,Kuyumzhiyan}
%\date{Версия 0.13}
\date{}

\maketitle

\section{Problems}


\subsection{Zero-sequences}

\bigskip
{\small\noindent
For any nonnegative integer $n$ let $\mathbb Z_n$ denote the set of
residues modulo $n$ equipped with operation ``+'' (addition mod $n$).
We say that the sequence in $\mathbb Z_n$ is a zero-sequence
if its sum equals $0\in\mathbb Z_n$.
%Для каждого натурального числа $n$ обозначим через $\mathbb Z_n$
%множество остатков при делении на $n$ c операцией сложения по модулю~$n$.
%Нуль-последовательностью в $\mathbb Z_n$ будем называть последовательность элементов
%$\mathbb Z_n^d$ с~нулевой суммой.
\par}

\medskip
\begin{problem}
\label{D(Z_n)}
Let $n$ be a nonnegative integer. Let $k$ be the minimal number such that
every sequence of length $k$ in $\mathbb Z_n$ contains a zero-subsequence.
Prove that $k=n$.
%Пусть $n$~--- натуральное число. Пусть $k$~--- наименьшее натуральное число,
%для которого верно, что любая последовательность из $k$ элементов $\mathbb Z_n$
%содержит нуль-подпоследовательность. Докажите, что $k=n$.
\end{problem}

\begin{problem}
\label{D(Z_n)-zerofree}
Describe all the sequences in $\mathbb Z_n$ of length $n-1$
that do not contain zero-subsequences.
%Опишите все последовательности в $\mathbb Z_n$ длины $n-1$, которые не содержат
%нуль-подпосле\-до\-ва\-тель\-но\-стей.
\end{problem}

\begin{problem}
\label{D(Z_n)-zerofree}
Describe all the sequences in $\mathbb Z_n$ of length $n-2$
that do not contain zero-subsequences.
%Опишите все последовательности в $\mathbb Z_n$ длины $n-2$, которые не содержат
%нуль-подпоследова\-тель\-ностей.
\end{problem}

\begin{problem}
What is minimal $m$ such that every sequence of length $m$
containing at least 81 different elements of ${\mathbb Z_{100}}$
has a zero-subsequence of length 100?
%При каком наименьшем $m$ любая последовательность из $m$ элементов ${\mathbb Z_{100}}$,
%содержащая не меньше 81 различных элементов, имеет нуль-подпоследовательность, состоящую
%из 100 элементов?
\end{problem}

\begin{problem}
In some ancient kingdom there were 4 sorts of coins that were worth several copecks each,
but nobody knows the exact nominal value of these coins.
What minimal number of coins should an archeologist excavate in order to be sure that
he has 100 coins whose total value is an integer number of roubles?
%В Тридевятом царстве в ходу были монеты в несколько копеек, четырех разных достоинств
%(сейчас уже никто не знает, каких именно). Какое наименьшее число тридевятских монет
%должен найти археолог, чтобы быть уверенным, что среди них заведомо есть ровно 100 монет,
%в сумме дающих целое число рублей?
\end{problem}

\begin{problem}
\label{EGZ12}
Prove that every sequence in ${\mathbb Z_{12}}$ of length 23
contains a zero-subsequence of length 12.
%Докажите, что всякая последовательность элементов ${\mathbb Z_{12}}$ длины 23
%содержит нуль-подпоследо\-ва\-тель\-ность длины $12$.
\end{problem}

\begin{problem}
Let $S$ be a sequence of length 502 in ${\mathbb Z_{541}}$
that has exactly 10 different elements.
Prove that $S$ contains a zero-subsequence.
%$S$~--- последовательность из 502 элементов ${\mathbb Z_{541}}$, причем $S$
%содержит ровно 10 различных элементов. Докажите, что $S$ содержит нуль-подпоследовательность.
\end{problem}

\begin{problem}
Let $S$ be a sequence of length 10 in ${\mathbb Z_{17}}$
that does not contain zero-subsequences. Prove that some element of
${\mathbb Z_{17}}$ occurs in $S$ at least 4 times.
%$S$~--- последовательность из 10 элементов ${\mathbb Z_{17}}$, причем $S$
%не содержит нуль-подпоследовательнос\-тей. Докажите, что какой-то элемент
%${\mathbb Z_{17}}$ встречается в $S$ не меньше 4 раз.
\end{problem}

\begin{problem}
\label{sums1}
Let $S$ be a sequence of $n$ integers coprime with $n$.
Prove that every residue modulo $n$ is a~sum of some subsequence in $S$.
%Пусть $S$~--- последовательность из $n$ чисел взаимно простых с $n$.
%Докажите, что любой остаток по модулю $n$ равен сумме некоторой подпоследовательности $S$.
\end{problem}

\begin{problem}
\label{N-C_Ext_lemma}
Let $S$ be a sequence in ${\mathbb Z_n}$ of length $2n-1$.
Assume that some element $a$ occurs at least $[n/2]$ times in $S$.
Prove that $S$ contains a zero-sum subsequence of length $n$.
%Пусть $S$~--- последовательность из $\mathbb Z_n$ длины $2n-1$.
%Предположим, что некоторый элемент $a$ встречается в этой последовательности не менее
%$[n/2]$ раз. Докажите, что $S$ содержит нуль-под\-после\-дователь\-ность длины~$n$.
\end{problem}

\begin{problem}
Let $p$ be an odd prime number.
Consider the following sequence in $\mathbb Z_p$: 0, 0, 1, 1, 2, 2, \dots, $p-1$, $p-1$.
How many zero-subsequences of length $p$ does this sequence have?
%Пусть $p$ --- нечетное простое.
%Сколько нуль-подпоследовательностей длины $p$ (в $\mathbb Z_p$)
%имеет последовательность 0, 0, 1, 1, 2, 2, \dots, $p-1$, $p-1$?
\end{problem}

\begin{problem}
Let $n\geq 2$ be an integer.
Let $S$ be a sequence of length $n$ in ${\mathbb Z_n}\setminus\{0\}$
with nonzero sum. Prove that there exist at least $n$ different
zero-subsequences in $S$.
%Дано целое число $n\geq 2$.
%$S$~--- последовательность длины $n$ в $\mathbb Z_n$ с ненулевой суммой и не содержащая
%нулей. Докажите, что $S$ имеет не меньше $n$ различных нуль-подпоследовательностей.
\end{problem}


\clearpage
\subsection{Extremal problems}

\bigskip
{\small\noindent
For every nonnegative integer $n$ by $\mathbb Z_n^d$ denote the set
of all arrays of the form $(m_1, m_2, \dots, m_d)$, where each
$m_i$ is a residue modulo $n$. We equip this set with operation ``+''
(addition modulo $n$ in each coordinate).
A zero-sequence in $\mathbb Z_n^d$ is a sequence that has zero sum
(i.e. the sequence whose sum equals $(0, 0, \dots, 0)\in \mathbb Z_n^d$).
By $g(n,d)$ denote the minimal number $M$ such that in every subset of $\mathbb Z_n^d$
consisting of $M$ elements there exist $n$ elements with zero sum.
%Для каждого натурального $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))
%Обозначим через $g(n,d)$ наименьшее такое число~$M$, что в любом
%подмножестве $\mathbb Z_n^d$, состоящем из $M$ элементов, найдутся
%$n$ элементов с нулевой суммой.
By $s(n,d)$ denote the minimal number $M$ such that in every sequence
$a_1$, \dots, $a_M\in\mathbb Z_n^d$ there exists a zero-subsequence of length $n$.
In other words there exist different indices $i_1$, \dots, $i_n$ such that
$a_{i_1}+\ldots+a_{i_n}=0$.
%Обозначим через $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$.
(In fact we mean that the sequence is just a multiset,
the order of elements in the sequence is not important for us.)
%Под последовательностью мы фактически понимаем мультимножество,
%порядок элементов последовательности нам не важен.)
\par}
\medskip

\begin{problem}
\label{s_power2}
Prove that $s(2,d)=2^d+1$.
\end{problem}

\begin{problem}
\label{s_nerav}
Prove that
$
(n-1)2^d+1\leq s(n,d)\leq (n-1)n^d +1\,.
$
\end{problem}

\begin{problem}
\label{s_multipl}
Prove that $s(n_1 n_2,d) \leq s(n_1, d) + n_1\bigl(s(n_2, d)-1\bigr)$.
\end{problem}


\begin{problem}
Prove that что $g(3,3)\geq 10$, $s(3,3)\geq 18$.
(Actually $g(3,3)=10$, $s(3,3)=19$.)
\end{problem}

\begin{problem}
Prove that
$g(n,2)\geq \begin{cases} 2n-1 & \hbox{for odd $n$}; \\
                          2n+1 & \hbox{for even $n$}.\end{cases}
$
\end{problem}

\begin{problem}
Consider a square $3 \times 3$ on the grid paper.
%На клетчатой бумаге нарисован квадрат $3 \times 3$.
Let 9 points be marked in the nodes of the grid (including the boundary of the square).
Prove that the center of mass of some 4 of these points is a node of the grid too.
%В узлах сетки (включая границу квадрата)
%отмечено 9 точек. Докажите, что можно выбрать 4 точки, у которых центр тяжести также
%расположен в узле сетки. Иными словами, докажите, что
In other words prove that $g(4,2)=9$.
\end{problem}

\begin{problem}
Prove that $s(2048,d)=2047\cdot 2^d +1$.
\end{problem}

\begin{problem}
Prove that $s(432,d)=1725$.
\end{problem}


%\clearpage

\subsection{Erd\H os\,--\,Ginzburg\,--Ziv theorem and related questions}

\begin{problem} [Cauchy\,--\,Davenport theorem]
Let $p$ be a prime number, $A$ and $B$ be two nonempty subsets in ${\mathbb Z}_p$.
Prove that $|A+B|\geq \min\{p, \ |A|+|B|-1\}$.
%Пусть $p$~--- простое число, $A$ и $B$~--- два непустых подмножества в~${\mathbb Z}_p$.
%Докажите, что $|A+B|\geq \min\{p, \ |A|+|B|-1\}$.
\end{problem}

\begin{problem} [Erd\H os\,--\,Ginzburg\,--Ziv theorem]
Prove that every sequence in ${\mathbb Z_n}$ of length $2n-1$
contains a zero-subsequence.
%Докажите, что всякая последовательность элементов ${\mathbb Z_n}$ длины $2n-1$
%содержит нуль-подпоследовательность длины $n$.
\end{problem}

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

Many of the following problems are valid in a more general context.
%Многие из следующих задач верны в следующей более общей ситуации.
A commutative finite group is a~finite set equipped with the operation ``+''
that satisfies the usual axioms for this operation:
%Коммутативной конечной группой будем называть конечное множество, снабженное операцией ``$+$'',
%для которой выполнены привычные для этого значка аксиомы:
commutativity $a+b=b+a$; associativity $a+(b+c)=(a+b)+c$;
existence of zero element with the property $0+a=a$ for all $a$;
and existence of inverse element: for any $a$ there exists $b$ such that
$a+b=0$ (we write $b=-a$).
We can define a difference of two elements using the last axiom: $a-b$ is
defined to be equal to $a+(-b)$.
%коммутативность $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)$.
A typical finite commutative group looks like $\mathbb Z_d^n$:
fix the set of numbers $k_1$, \dots, $k_n$ and a~set of ``vectors''
$(x_1, x_2, \dots, x_n)$, where $x_i\in\mathbb Z_{k_i}$, and
the operation ``+'' is usual coordinatewise addition
(modulo $k_i$ for $i$-th coordinate).
%Типичная конечная коммутативная группа устроена похоже на $\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$).

We mark the problem by the sign  $\dagger$ if its statement is valid for an
arbitrary finite commutative group. Solutions that do not use specific
properties of $\mathbb Z_n$ and remain valid in the case of an arbitrary finite commutative group
are especially welcome.
%Задачи, утверждения которых верны для произвольной конечной коммутативной группы, помечены
%значком $\dagger$. Мы особо приветствуем решения, которые не используют специфику $\mathbb Z_n$
%и верны для произвольной коммутативной конечной группы.}

\begin{problem}
\label{KD_iterated}
Let $p$ be a prime number; let
$A_1$, $A_2$, \dots, $A_k$ be nonempty subsets in ${\mathbb Z}_p$. Prove that
%Пусть $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}
Let $p$ be a prime number and let $S=(a_1, \dots, a_{2p-1})$
be a sequence in ${\mathbb Z}_p$ such that its elements
$a_1$, \dots, $a_s$ are pairwise distinct ($s\geq 2$).
Prove that $S$ has a zero-subsequence of length $p$ that contains exactly one of
the elements $a_1$, \dots, $a_s$.
%Пусть $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}
a) Take a regular 12-gon on the plane. We consider all symmetries and rotations
of the plane which preserve the 12-gon.
%Consider transformations of the regular 12-gon: symmetries and rotations.
Prove that for any 47 transformations there exist 24 of them such that
their composition (in some order) is an identity transformation.
%Рассмотрим преобразования правильного 12-угольника~--- симметрии и повороты.
%Докажите, что среди любых 47 преобразований найдется 24 преобразования, композиция которых
%(в некотором порядке) дает тождественное отображение.

b) Prove a similar statement for the symmetric group $S_4$.
%Докажите аналогичный факт для группы перестановок $S_4$.
\end{problem}

\begin{problem}
\label{lemma_Gao}
Let $p$ be a prime number, $T$ be a sequence in ${\mathbb Z}_p \setminus\{0\}$
of length $p$, $h$ be a maximal multiplicity of elements in~$T$.
Prove that every element of ${\mathbb Z}_p$ is a sum of at least $h$ elements of $T$.
%Пусть $p$~--- простое число, $T$~--- последовательность в ${\mathbb Z}_p \setminus\{0\}$
%длины~$p$, $h$~--- максимальная кратность элемента в~$T$. Докажите, что любой элемент
%${\mathbb Z}_p$ является суммой не более чем $h$ элементов~$T$.
\end{problem}

\begin{problem}
Assume  $m\geq k\geq 2$, and let $m$ be divisible by $k$.
Prove that every sequence of integers of length $m+k-1$ contains
a subsequence of length $m$ whose sum is divisible by $k$.
%Пусть $m\geq k\geq 2$, причем $m$ делится на $k$.
%Докажите, что всякая последовательность целых чисел длины $m+k-1$
%содержит подпоследовательность длины $m$ c суммой, делящейся на $k$.
\end{problem}

\begin{problem}$\dagger$ [Kemperman\,--\,Scherk theorem]
\label{Scherk}
Let $n$ be a nonnegative integer. Let $A$ and $B$ be two subsets of ${\mathbb Z}_n^d$,
such that $0\in A$, $0\in B$ and the equation $a+b=0$
has only the trivial solution $a=b=0$ if $a\in A$, $b\in B$.
Prove that $|A+B|\geq \min\{n^d, \ |A|+|B|-1\}$.
%Пусть $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$
Let $k$ and $r$ be nonnegative integers and let $A=\{a_1, \dots, a_{k+r}\}$
be a sequence in ${\mathbb Z}_k$, such that 0 is not a $k$-sum
of this sequence. Prove that the sequence has
at least $r+1$ different $k$-sums.
%Пусть $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}
Let $S$ be a sequence of length $n^d$ in $\mathbb Z_n^d$, let
$h$ be a maximal multiplicity of elements in this sequence.
Prove that $S$ contains a zero-subsequence of length at most $h$.
%Пусть $S$~--- последовательность из $n^d$ элементов $\mathbb Z_n^d$,
%$h$~---  максимальная кратность элемента в~этой последовательности.
%Докажите, что $S$ содержит нуль-подпоследовательность длины не более~$h$.
\end{problem}

\begin{problem}
\label{G-T_lemma}
Let $p$ be a prime number and $2\leq k\leq p-1$.
%Пусть $p$~--- простое  число и $2\leq k\leq p-1$.
Consider a sequence of length $2p-k$ in ${\mathbb Z}_p$, such that
every $p$ elements of this sequence have a nonzero sum.
Prove that some element occurs in the sequence at least $p-k+1$ times.
%Рассмотрим последовательность элементов ${\mathbb Z}_p$ длины $2p-k$.
%Докажите, что если никакие $p$ элементов
%этой последовательности не дают в сумме 0, то один какой-то элемент
%входит в последовательность не менее чем $p-k+1$ раз.
\end{problem}

\begin{problem}
\label{N-C_EXT_reformulation}
Let $B_1$, $B_2$, \dots, $B_h$ be a collection of subsets in $\mathbb Z_n^d$.
Let $m_i=|B_i|$. Assume that $\sum_{i=1}^h m_i \geq n^d$.
Prove that for each $j$ we can choose at most one element $b_j\in B_j$ in such a way
that the sum of the resulting nonempty collection of chosen elements is $0\in \mathbb Z_n^d$.
%Пусть $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}
Let $n>4$ be an odd number. Let $S$ be a sequence of length $k$ in ${\mathbb Z}_n$,
where $\frac{n+1}2\leq k \leq n$. Assume that $S$ does not contain zero-subsequences.
Prove that some element of ${\mathbb Z}_n$ is contained in $S$ with
multiplicity $2k-n+1$.
%Пусть $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$
Let $A\subset\mathbb Z_n^d$, $|A|\geq n^d/k$. Prove that there exists a number
$r$, $1\leq r\leq k$, and a sequence $a_1$, \dots, $a_r$
(of not necessarily different elements of $A$) such that $\sum a_i =0$.
%Пусть $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}
Prove that the sequence of length $2n-1$ in $\mathbb Z_n$ has a unique
zero-subsequnce if and only if it consists of $n$ copies of some number
$a$ and $(n-1)$ copies of number $b$.
%Докажите, что набор из $2n-1$ элементов $\mathbb Z_n$ лишь тогда имеет единственную
%нуль-под\-после\-до\-ва\-тельность, когда он состоит из $n$ экземпляров числа $a$ и $(n-1)$
%экземпляров числа $b$.
\end{problem}

\begin{problem}$\dagger$
Let $S$ be a subset of $\mathbb Z_n^d$ containing $k$ elements.
Assume that $S$ does not contain a subset with zero sum.
Prove that there exist at least $2k-1$ distinct elements of $\mathbb Z_n^d$
that can be represented as a sum of several elements of $S$.
%Пусть $S$~--- подмножество $\mathbb Z_n^d$, состоящее из $k$ элементов,
%причем $S$ не имеет подмножеств с~нулевой суммой.
%Докажите, что существует не меньше $2k-1$ элементов $\mathbb Z_n^d$
%представимых в виде суммы нескольких элементов из $S$.
\end{problem}

\begin{problem}
\label{G-T_kratnost2}
Let $M=\{(a_1,b_1), (a_2,b_2), \dots, (a_{2p-1},b_{2p-1})\}$
be a subset in $\mathbb Z_p^2$. Assume that every element of $\mathbb Z_p$
is contained in the sequence $a_1$, \dots, $a_{2p-1}$ at most twice.
Prove that the set $M$ contains a zero-subsequence of length~$p$.
%~--- подмножество в $\mathbb Z_p^2$. Пусть ни какой элемент $\mathbb Z_p$ не входит
%в последовательность $a_1$, \dots, $a_{2p-1}$ больше двух раз. Докажите, что множество $M$
%содержит нуль-подпоследовательность (в $\mathbb Z_p^2$) длины $p$.
\end{problem}


\begin{problem}
Prove that the minimal $m$ such that every sequence of length $m$ in $\mathbb Z_p^d$
contains a zero-subsequence is equal to $d(p-1)+1$.
%Докажите, что наименьшее $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 штук с нулевой
суммой.
