Vectors -1, 0, 1

Consider 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.

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₁ ⇾ v₂ ⇾ … ⇾ v_k ⇾ v₁.

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

f(v₁) + f(v₂) + … + f(v_k) = (v₂ – v₁)/2 + (v₃ – v₂)/2 + … + (v₁ – v_k)/2 = 0.

Unknown Author

We do not know where this puzzle originated from. If you have any information, please let us know via email.