Let $F$ be a finite non-empty set of integers and let $n$ be a positive integer. Suppose that $\bullet$ Any $x \in F$ may be written as $x=y+z$ for some $y$, $z \in F$; $\bullet$ If $1 \leq k \leq n$ and $x_1$, ..., $x_k \in F$, then $x_1+\cdots+x_k \neq 0$. Show that $F$ has at least $2n+2$ elements.
Problem
Source: SMO(O) 2014 #4
Tags: graph theory, combinatorics
23.01.2015 00:45
An old and nice problem of vess, published in Crux Mathematicorum years ago Of course, the restriction $F\subset \mathbb{Z}$ is unneeded. Clearly $0\not \in F$, since otherwise it violates the second condition. Say $m = \min F$; then we must have $m<0$ from the first condition, since $m=y+z \geq m + m$. Say $M = \max F$; then we must have $M>0$ from the first condition, since $M=y+z \leq M + M$. Thus $F$ contains both positive and negative elements. Denote $F^+ = \{x\in F \mid x>0\}$. For $x\in F^+$ we choose from the first condition any representation $x=y+z$. We must have at least one of $y,z$ to also be positive; say $y\in F^+$. We then write $x\stackrel{z}{\longrightarrow} y$. This establishes a digraph on the vertices from $F^+$, with its directed edges as described. Since $\deg^+ x \geq 1$ for any $x\in F^+$, which is finite, there must exist a directed cycle $v_1\stackrel{x_1}{\longrightarrow} v_2 \stackrel{x_2}{\longrightarrow} v_3 \longrightarrow \cdots \longrightarrow v_{k-1} \stackrel{x_{k-1}}{\longrightarrow} v_k \stackrel{x_k}{\longrightarrow} v_1$. But that means $v_i = v_{i+1}+x_i$ for $1\leq i \leq k-1$ and $v_k = v_{1}+x_k$. Summing up these relations we obtain $x_1+x_2+\cdots + x_k = 0$, thus $k\geq n+1$, from the second condition, therefore $|F^+| \geq n+1$. In a completely similar way we obtain $|F^-| \geq n+1$ for $F^- = \{x\in F \mid x<0\}$, thus $|F| = |F^+|+|F^-| \geq 2n+2$. An example with $|F|=2n+2$ for $n=1$ is $\{-2,-1,1,2\}$. An example with $|F|=2n+2$ for $n=2$ is $\{-6,-5,-3, 1,2,4\}$. Can anyone find examples with $|F|=2n+2$ for some larger values of $n$? for all larger values of $n$?
23.01.2015 05:57
mavropnevma, how did you think of that! I got stuck after considering the graph connecting $x$ to $y$, $z$ (both of them). But I never thought of forcing them to be the same sign! Do you know of any resources which teaches the applications of graph-theory to seemingly-unrelated problems, like this one?
28.01.2015 21:56
Courtesy of Marius Bocanu, a general example for $|F| = 2n+2$. Take $F^+ = \{\overline{1}, \overline{10}, \overline{100}, \ldots, \overline{1\underbrace{00\ldots 0}_{n}}\}$ and $F^- = \{-\overline{\underbrace{11\ldots 1}_{n}0}, -\overline{\underbrace{11\ldots 1}_{n-1}01}, \ldots, -\overline{\underbrace{11\ldots 1}_{n}}\}$, with the numbers (obviously) written in binary. It so happens this series continues my examples for $n=1$ and $n=2$ (so unwittingly I was on the right track)