Browse · MathNet
PrintBaltic Way shortlist
Baltic Way counting and probability
Problem
Let there be an operator . Given an expression that includes this operator, one can make the following transformations: 1. An expression of the form can be rewritten as ; 2. An expression of the form can be rewritten as . The transformations may be performed only on the entire expression and not on the subexpressions. For example, may only be rewritten using the first kind of transformation as , but it cannot be transformed into or 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 . For which natural numbers can the expression be rewritten to an expression that does not include a single occurrence of the operator?
Solution
However, the expression cannot be an intermediate result based on what has been showed earlier. Therefore all expressions that can be transformed into are shown in the chain above. Only four of them are in the required form – for .
Final answer
n = 1, 2, 3, 4
Techniques
Logic