Category: Brain Teasers

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.

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.

The sides of a rectangle have lengths which are odd numbers. The rectangle is split into smaller rectangles with sides which have integer lengths. Show that there is a small rectangle, such that all distances between its sides and the sides of the large rectangle have the same parity, i.e. they are all even or they are all odd.

Source: Shortlist IMO 2017

Split the large rectangle into small 1×1 squares and color it in black and white, chessboard-style, such that the four corner squares are black. Since the large rectangle has more black squares than white squares, one of the smaller rectangles also must have more black squares than white squares. Therefore, the four corners of that smaller rectangle are all black. Then, it is easy to see that all distances between its sides and the sides of the large rectangle have the same parity.