Suppose S ⊂ Z (set of integers) such that1) | S | = 152) ∀ s ∈ S , ∃ a , b ∈ S such that s = a + bShow that for every such S, there is a non-empty subset T of S such that the sum of elements of T is zero and | T | ≤ 7.

Question

Suppose   S  ⊂  Z (set of integers) such that1)   |  S  |  =  152)   ∀     s  ∈  S  ,  ∃     a  ,  b  ∈  S such that   s  =  a  +  bShow that for every such   S, there is a non-empty subset   T of   S such that the sum of elements of   T is zero and   |  T  |  ≤  7.

Boatein · Accepted Answer

A weaker statement, where we allow elements in   T to be repeated, can be proved as below:Since we can look at the set   {  −  s  |  s  ∈  S  } we may assume there are at most   7 positive numbers in   S. Let each positive number be a vertex, from each vertex   s we draw an arrow to any vertex   a such that   s  =  a  +  b. Since if   s  &amp;gt;  0, one of   a  ,  b must be positive, there is at least one arrow from any vertex. So there must be a cycle       s    1    ,  ⋯  ,      s    n    =      s    1   with   n  ≤  8. We can let   T consists of       s    i    −      s          i      +      1      ,   1  ≤  i  ≤  n  −  1.

Suppose S ⊂ <mi mathvariant="double-struck">Z (set of integers) such th

Answered question

Answer & Explanation

New Questions in Precalculus