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 ui and their transformations with f(ui). Create a graph with 1024 nodes, labeled with ui. Then, for every node ui, create a directed edge from ui to ui-2f(ui). This is a valid construction, since the vector ui-2f(ui) has elements -1, 0, and 1 only. In the resulting graph, there is a cycle:

v1 ⇾ v2 ⇾ … ⇾ vk ⇾ v1.

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

f(v1) + f(v2) + … + f(vk) = (v2 – v1)/2 + (v3 – v2)/2 + … + (v1 – vk)/2 = 0.

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

Notify of
Inline Feedbacks
View All Comments