Initially given $31$ tuplets $$(1,0,0,\dots,0),(0,1,0,\dots,0),\dots, (0,0,0,\dots,1)$$were written on the blackboard. At every move we choose two written $31$ tuplets as $(a_1,a_2,a_3,\dots, a_{31})$ and $(b_1,b_2,b_3,\dots,b_{31})$, then write the $31$ tuplet $(a_1+b_1,a_2+b_2,a_3+b_3,\dots, a_{31}+b_{31})$ to the blackboard too. Find the least possible value of the moves such that one can write the $31$ tuplets $$(0,1,1,\dots,1),(1,0,1,\dots,1),\dots, (1,1,1,\dots,0)$$to the blackboard by using those moves.
Problem
Source: 2023 Turkey NMO 2nd Round P4
Tags: combinatorics
dnztnc
24.12.2023 13:43
Here is my solution from the contest. Hope it works. Answer: $87=3(31-2)$ Construction: Obtain, in $29$ moves, the following $29$ vectors that are all formed by consecutive $1$s followed by consecutive $0$s: $(1,1,0,...,0),(1,1,1,0,...,0),(1,1,1,1,0,...,0),...,(1,1,1,...,1,0)$. Do the same, in $29$ moves, the other way around. Then, we obtained the first and the last $31$ tuplets that were required by us. Obtain the remaining $29$ vectors easily, each in one move, using the $58$ vectors we already have. For example, to get $(1,1,1,1,0,1,1,1,...,1)$, perform a move on $(1,1,1,1,0,0,...,0)$ and $(0,0,0,0,0,1,1,...,1)$. Proof of the lower bound: Replace $31$ with $n$. We will perform induction on $n$ for $n\geq3$ to show that at least $3(n-2)$ moves are necessary. The base case is trivial. Assume true for $n$; let's prove it for $n+1$. Observation 1: The $(n+1)$-tuplet $(0,0,...,0,1)$ has to be used in a move at least once.
The reason we have to use it at least once is obvious. Assume that's all. Then, consider the other vector that $(0,0,...,0,1)$ was used with in a move. Clearly, it has some non-zero digit. Assume WLOG, it is the first digit. Then, how are we going to obtain $(0,1,1,...,1)$ at the end? Contradiction!
Observation 2: There has to be a move reserved for obtaining $(1,1,1,...,0)$.
This is because the moves in Obs1 don't contribute to the first $n$ digits. The move in Obs2, again, does not contribute anything because we threw out that vector before applying the induction hypothesis.
So, in total, we need at least $3(n-2)+3=3((n+1)-2)$ moves. This finishes the induction.