## Vectors -1, 0, 1

Take all 1024 vectors in a 10-dimensional space with elements ±1. Show that if you change some of the elements of some of the vectors to 0, you can still choose a few vectors, such that their sum is equal to the 0-vector.

**SOLUTION**

Denote the 1024 vectors with u_{i} and their transformations with f(u_{i}). Create a graph with 1024 nodes, labeled with u_{i}. Then, for every node u_{i}, create a directed edge from u_{i} to u_{i}-2f(u_{i}). This is a valid construction, since the vector u_{i}-2f(u_{i}) has elements -1, 0, and 1 only. In the resulting graph, there is a cycle:

v_{1} ⇾ v_{2} ⇾ … ⇾ v_{k} ⇾ v_{1}.

Now, if we pick the (transformed) vectors from this cycle, their sum is the 0-vector:

f(v_{1}) + f(v_{2}) + … + f(v_{k}) = (v_{2} – v_{1})/2 + (v_{3} – v_{2})/2 + … + (v_{1} – v_{k})/2 = 0.