Competition problem — Combinatorics

Library / /21 of 31

Combinatorics Difficulty 8.4 Shortlist Prove it Baltic Way

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?

Solution

$\begin{align*} 1 &\overset{(2)}{\rightleftharpoons} 1 * 1 \\ &\overset{(2)}{\rightleftharpoons} (1 * 1) * 1 \\ &\overset{(2)}{\rightleftharpoons} ((1 * 1) * 1) * 1 \\ &\overset{(1)}{\rightleftharpoons} 1 * (1 * 1) \\ &\overset{(2)}{\rightleftharpoons} (1 * (1 * 1)) * 1 \\ &\overset{(2)}{\rightleftharpoons} ((1 * (1 * 1)) * 1) * 1 \\ &\overset{(1)}{\rightleftharpoons} (1 * 1) * (1 * 1) \\ &\overset{(2)}{\rightleftharpoons} ((1 * 1) * (1 * 1)) * 1 \\ &\overset{(1)}{\rightleftharpoons} 1 * ((1 * 1) * 1) \\ &\overset{(2)}{\rightleftharpoons} (1 * ((1 * 1) * 1)) * 1 \\ &\overset{(2)}{\rightleftharpoons} ((1 * ((1 * 1) * 1)) * 1) * 1 \\ &\overset{(1)}{\rightleftharpoons} ((1 * 1) * 1) * (1 * 1) \\ &\overset{(1)}{\rightleftharpoons} 1 * (1 * (1 * 1)) \\ &\overset{(2)}{\rightleftharpoons} (1 * (1 * (1 * 1))) * 1 \\ &\overset{(2)}{\rightleftharpoons} ((1 * (1 * (1 * 1)))) * 1 * 1 \\ &\overset{(1)}{\rightleftharpoons} (1 * (1 * 1)) * (1 * 1) \\ &\overset{(2)}{\rightleftharpoons} ((1 * (1 * 1)) * (1 * 1)) * 1 \\ &\overset{(1)}{\rightleftharpoons} (1 * 1) * ((1 * 1) * 1) \\ &\overset{(2)}{\rightleftharpoons} ((1 * 1) * ((1 * 1) * 1)) * 1 \\ &\overset{(1)}{\rightleftharpoons} 1 * (((1 * 1) * 1) * 1) \\ &\overset{(2)}{\rightleftharpoons} (1 * (((1 * 1) * 1) * 1)) * 1 \\ &\overset{(2)}{\rightleftharpoons} ((1 * (((1 * 1) * 1) * 1)) * 1) * 1 \\ &\overset{(1)}{\rightleftharpoons} (((1 * 1) * 1) * 1) * (1 * 1). \end{align*}$

However, the expression $(((1 * 1) * 1) * 1) * (1 * 1)$ cannot be an intermediate result based on what has been showed earlier. Therefore all expressions that can be transformed into $1$ are shown in the chain above. Only four of them are in the required form – for $n = 1, 2, 3, 4$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.