In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word.
If we are given an ordered triple of words $(a,b,c)$, an operation on that tuple consists of replacing one of the $x\in\{a,b,c\}$ by $x0,\ x1,$ or $y$ such that $x\neq y\in\{a,b,c\}$, e.g: $$(\epsilon,\epsilon,\epsilon)\xrightarrow{b:=b1}(\epsilon,1,\epsilon)\xrightarrow{b:=b0}(\epsilon,10,\epsilon)\xrightarrow{c:=c1}(\epsilon,10,1)\xrightarrow{a:=b}(10,10,1) $$ Given a non-negative integer $h$, we say that $(a,b,c)$ is $h$-complete if the length of each of $a,b,c$ is $h$, that is $|a|=|b|=|c|=h$. We say that a series of operations is healthy if and only any tuple $(a,b,c)$ appears at most once. For example, the sequence $$(\epsilon,\epsilon,\epsilon)\xrightarrow{b:=b0}(\epsilon,1,\epsilon)\xrightarrow{ b:=c}(\epsilon,\epsilon,\epsilon)$$ is not healthy because $(\epsilon,\epsilon,\epsilon)$ appears twice.
The length of a tuple $(a,b,c)$ is defined as $|(a,b,c)|=\max(|a|,|b|,|c|)$
My question:
What is the maximum number of healthy operations in a sequence which can transform $(\epsilon,\epsilon,\epsilon)$ into an $h$-complete tuple with all the intermediate tuples have length less than or equal to $h$
The minimum number of operations is $h+2$, but I'm interested in the worst case, and my problem consists of a generalization for $n$ words and not just $3$.
If you know any references for such problems, or have any idea about this problem, it will be appreciated!
Edit: the answer for couples is $f_2(h)=\frac{(h+2)(h+1)}{2}-1$ when we are taking pairs $(x,y)$ instead of $3$-tuples $(a,b,c)$
- If $h=1$ there is only two operations which can transform $(\epsilon,\epsilon)$ to $(0,0),(0,1),(1,0),(1,1)$ so: $$f_2(1)=2 $$
- Suppose that there is only that the result is true for $h$ given two words of lenght $|x|=|y|=h+1$ my idea is described by the following process: $$(\epsilon,\epsilon)\underbrace{-------\rightarrow}_{m(h) \text{ operations}} \begin{Bmatrix} (0,0)\\ (0,1)\\ (1,0)\\ (0,0) \\ (w,w') \big/ |w|\text{or }|w'|>1 \end{Bmatrix}\underbrace{-------\rightarrow}_{x(h) \text{ operations}} (x,y)$$ the added intermediate step is necessary (we can not complete the process without passing throught it) and one can prove that : $m(h)\leq h+2$ and clearly $x(h)\leq f_2(h)$ so: $$f_2(h+1)\leq f_2(h)+h+2$$ to complete the proof we have to construct a process with $f_2(h+1)=h+2+f_2(h)$ which can be done using the schema