Question 67
Let there be an operator $*$. Given an expression that includes this operator, one can make the following transformations:
1. An expression of the form $x * (y * z)$ can be rewritten as $((1 * x) * y) * z$;
2. An expression of the form $x * 1$ can be rewritten as $x$.
The transformations may be performed only on the entire expression and not on the subexpressions. For example, $(1 * 1) * (1 * 1)$ may only be rewritten using the first kind of transformation as $((1 * (1 * 1)) * 1) * 1$, but it cannot be transformed into $1 * (1 * 1)$ or $(1 * 1) * 1$ using a single step – in the latter two cases the second kind of transformation would have been applied just to the left or right subexpression of the form $1 * 1$.
For which natural numbers $n$ can the expression $1 * (1 * (1 * (\cdots * (1 * 1))))$ be rewritten to an expression that does not include a single occurrence of the $*$ operator?
1. An expression of the form $x * (y * z)$ can be rewritten as $((1 * x) * y) * z$;
2. An expression of the form $x * 1$ can be rewritten as $x$.
The transformations may be performed only on the entire expression and not on the subexpressions. For example, $(1 * 1) * (1 * 1)$ may only be rewritten using the first kind of transformation as $((1 * (1 * 1)) * 1) * 1$, but it cannot be transformed into $1 * (1 * 1)$ or $(1 * 1) * 1$ using a single step – in the latter two cases the second kind of transformation would have been applied just to the left or right subexpression of the form $1 * 1$.
For which natural numbers $n$ can the expression $1 * (1 * (1 * (\cdots * (1 * 1))))$ be rewritten to an expression that does not include a single occurrence of the $*$ operator?